Road Pathfinder Modifications

[fanioz]

Judging from the downloads, nobody seems interested. I'll leave those here, if you want updated versions I suggest you have a look at the road pathfinders integrated in several AIs.

Yes, I can download it here, but IMO, BaNaNas is still the best place
so, my (under-development) AI would find it libraries there

[Yexo]

Judging from the downloads, nobody seems interested. I'll leave those here, if you want updated versions I suggest you have a look at the road pathfinders integrated in several AIs.

Yes, I can download it here, but IMO, BaNaNas is still the best place

That would indeed be the right place, but not at this time. Uploading it there would mean I actually have to finish it, and as long as nobody seems interested I've very little motivation to do so.

[Zutty]

Judging from the downloads, nobody seems interested. I'll leave those here, if you want updated versions I suggest you have a look at the road pathfinders integrated in several AIs.

Yes, I can download it here, but IMO, BaNaNas is still the best place

That would indeed be the right place, but not at this time. Uploading it there would mean I actually have to finish it, and as long as nobody seems interested I've very little motivation to do so.

I'm interested, but I'm really really busy at the moment. I have a couple of bugs related to bridge construction at the moment, so I might want to tweak my part of it a little bit more. Hopefully I can do this in time for an official update.

[Yexo]

I'm interested, but I'm really really busy at the moment. I have a couple of bugs related to bridge construction at the moment, so I might want to tweak my part of it a little bit more. Hopefully I can do this in time for an official update.

Then I'll wait for your changes before finishing it

[GeekToo]

Slight communication problem. It was not lack of interest, as far as I'm concerned, but the following phrase:

Edit: I forgot to add the callback functions, I'll post an update later.

that kept me from downloading. Maybe more people had that impression.

[Zutty]

After having actually read the new version (sorry - I have been extremely busy) I note that the only thing you kept from my intial patch was a few variable names! Perhaps on reflection I would be better off maintaining my own pathfinder after all. I can see that not many people like my style!

I will use the new version you posted so that I can keep up to date with any future updates, but I'll re-apply my own changes the way I originally implemented them. My code is still GPL so anyone is free to use my changes still.

By the way Yexo, does the way you've implemented demolition really work? How thoroughly have you tested it? I tried something similar to your approach when developing my patch a while back and couldn't get it to work that way. Its fine for 99.5% of cases, but occasionally it would make a mistake. Thats why I created that hideous _IsConnectable() method. I personally favour a slower, less efficient pathfinder that does not make mistakes. Ofcourse I could be have been doing it wrong. I have already explained to GeekToo my somewhat untenable position on that functionailty!!

[Yexo]

Ok, here a new version. Every suggested suggested change should be implemented now, please tell me if I forgot something.

And here I have a proposal for the new road library (version 4).

Changes (in no particular order):
- Updated version to 4.
- Change the way callback parameters are passed to the pathfinder (internal change)
- Use only a single tile in the _Estimate function (instead of looping over all tiles)
- Add the option to specify a maximum length for the pathfinder, this prevents looping over the complete map if the destination can't be reached.
- Add a cost for crossing rail tiles, this should prevent always building crossings.
- Add the option to build bridges starting on flat tiles when the next tile is a rail or water tile.
- Option to demolish houses (based on patch by Zutty)
- Default for maximum bridges length changed from 10 to 25.
- Use the cheapest bridge instead of the first one to try if a bridge can be build, this way you need less money while pathfinding.
- Add the option to ignore certain tiles.
- Add a multiplier for the estimate function. Default is 1 ('perfect' pathfinding, setting a higher value (higher then 2 is not recommended) will speed up pathfinding at the cost of your routes being less optimal).
- Add custom callbacks for the cost function (patch by Zutty).

Changes to A*:
- Update version to 5.
- Add GetLength() next to GetCost()
- Modified the callback parameters. Instead of a parameter now the 'this' instance is passed.

I've tested it a bit, but I'd like some more people to test it. I hope some of you can do some more testing and report problems / more suggested changes.

I've attached the new tars (road pathfinder and AyStar library), and also a diff of the road pathfinder against the previous version (3). Changes to both the road pathfinder and A* library have been done in a hg patch queue. Zip files with all the separate patches available on request.

[Yexo]

After having actually read the new version (sorry - I have been extremely busy) I note that the only thing you kept from my intial patch was a few variable names! Perhaps on reflection I would be better off maintaining my own pathfinder after all. I can see that not many people like my style!

I'm sorry if you feel this way. As you may have noticed, I already said I forgot to include the cost callbacks, these were nearly half your patch and are included now (with only a few minor changes regarding code style.

By the way Yexo, does the way you've implemented demolition really work? How thoroughly have you tested it? I tried something similar to your approach when developing my patch a while back and couldn't get it to work that way. Its fine for 99.5% of cases, but occasionally it would make a mistake. Thats why I created that hideous _IsConnectable() method. I personally favour a slower, less efficient pathfinder that does not make mistakes. Ofcourse I could be have been doing it wrong. I have already explained to GeekToo my somewhat untenable position on that functionailty!!

I've not been able to find a case were it didn't work. If you find any, please upload a savegame. Your patch missed a few cases here (it could remove your own rail tiles, for example), I hope this one is complete.

[fanioz]

Attachments:
File comment: New road pathfinder.
pathfinder.road.4.tar [30 KiB]
Downloaded 1 time
------------------------
File comment: Diff against road.3, for viewing all changes.
combined_road_changes.diff [19.04 KiB]
Downloaded 1 time
--------------------------
File comment: New AyStar library.
graph.aystar.5.tar [20 KiB]
Downloaded 1 time

I'm first ...
Or ... the other download via svn/hg...

[Yexo]

I'm first ...
Or ... the other download via svn/hg...

You were indeed the first one, as the only place these are available is here. There is no hg/svn repository for them (except on my local harddisk).

[Zutty]

I'm sorry if you feel this way. As you may have noticed, I already said I forgot to include the cost callbacks, these were nearly half your patch and are included now (with only a few minor changes regarding code style.

Oh theres no need to be sorry, I didn't mean to whine that you weren't ALL using my code!!

I accept that not everyone likes my style and that it was certainly in need of refinement. I haven't tried running the new RPF yet, but it looks like it should be MUCH faster than my version, which will be nice. The whole reason I started using the library pathfinder was so that I can benefit from situations like this.

However I still think I'll keep a parallel version of my own, as I doubt all my quirky ideas for the pathfinder will be shared by everyone!

By the way I WILL get around to looking at your newly posted version at some point Yexo, but I am really really busy at the moment. Thanks for you hard work on this

[Yexo]

However I still think I'll keep a parallel version of my own, as I doubt all my quirky ideas for the pathfinder will be shared by everyone!

There is nothing wrong with that. I'm doing the exact same thing myself currently, because I wanted to make some small changes not worth of updating the library version. Quite a lot of the changes are ports from my own version were I think others would benefit too. Even with this new library version, I still might include my own version in admiralai. I haven't checked yet whether I have more changes that I want to keep.

By the way I WILL get around to looking at your newly posted version at some point Yexo, but I am really really busy at the moment. Thanks for you hard work on this

DOn't hurry, no reason to rush reviewing/testing.

[fanioz]

Hi Yexo, ..
the 'declaration/interface' section of InitializePath() function on pathfinder.road 4 said there's no ' ignored_tiles' (line 67)
but the 'implementation' has (line 153), there is no problem with that since the debugger says no error. But, if that
feature is still supportted, IMO it would be better to write the same as implementation.

All ....

Here some try out of Aystar.5 and RPF 4
=========================
Map Size = 512 x 512
Difficulty Setting = Medium (Hilly Land)
Climate = Temperate
Connecting 2 town with road (I've choose the most far)
879 tile distance manhattan

1. Set the parameters :
max_length_multiplier = 1.5
max_length_offset = 0
pathfinder.cost.estimate_multiplier = 5
ignore_tile = AITilelist( !IsBuildAble || !IsRoadTile )
------------
total time needed to connecting the road = 13 days
path.length become 891

2. Set the parameters :
max_length_multiplier = 1.5
max_length_offset = 0
pathfinder.cost.estimate_multiplier = 5
ignore_tile = []
------------
total time needed to connecting the road = 13 days
path.length become 891

3. Set the parameters :
max_length_multiplier = 0 (default)
max_length_offset = 10000 (default)
pathfinder.cost.estimate_multiplier = 5
ignore_tile = []
------------
total time needed to connecting the road = 13 days
path.length become 887

4. Set the parameters :
max_length_multiplier = 1.5
max_length_offset = 0
pathfinder.cost.estimate_multiplier = 2
ignore_tile = AITilelist( !IsBuildAble || !IsRoadTile )
------------
total time needed to connecting the road = 33 days
path.length become 881

5. Set the parameters :
max_length_multiplier = 1.5
max_length_offset = 0
pathfinder.cost.estimate_multiplier = 1.5
ignore_tile = AITilelist( !IsBuildAble || !IsRoadTile )
------------
total time needed to connecting the road = 1605 days
path.length become 883

6. Set the parameters :
max_length_multiplier = 1.5
max_length_offset = 0
pathfinder.cost.estimate_multiplier = 1.7
ignore_tile = AITilelist( !IsBuildAble || !IsRoadTile )
------------
total time needed to connecting the road = 64 days
path.length become 881

7. Set the parameters :
max_length_multiplier = 1.5
max_length_offset = 0
pathfinder.cost.estimate_multiplier = 1 (default)
ignore_tile = AITilelist( !IsBuildAble || !IsRoadTile )
------------
stopped pathfinding, it take 5 years and path still 'false'

Note:
when cost.estimate_multiplier is set to 5, most of bridge was built, even over a town road (remind me of PathZilla CMIIW zutty)
when cost.estimate_multiplier is set to 2, the pathfinder look avoid building bridge/tunnel and made a nice road I thought
just wondering, the Heuristic function really make a different processing time (see 4,5,6,7)

Nice pathfinder

[Pat]

Hi,
I started writing my own AI, using old pathfinder (v3). I used it to find path between two drive thought road stations and it worked without problem. Then i replaced old pathfinder with new, which work only on maps grater than 256x256 (if source and goal isn't drive thought station it works every time). I'm new to squirrel and noAI, so there is big probability I'm doing something wrong but only thing i done is replaced 3 by 4 in import("pathfinder.road", "RoadPathFinder", 4);
Do you have any idea where could be problem?

btw I apologizes for my English.

[Yexo]

Hello Pat,

I'm sorry I don't have any clue why you have this problem. Can you upload a test ai that demonstrates the problem? If you don't want to publish your AI, you can also pm it to me, so I can take a look at what the problem is.

[Pat]

I tried it few more times, and it sometimes work sometime not. I made two test maps and testai which build always same road. It look like it fail if i start one game, then leave it and start another one. But I have absolutely no idea what's happening. (I'm using openttd 0.7.0 beta1)
my testai (maps included):

[fanioz]

I tried it few more times, and it sometimes work sometime not. I made two test maps and testai which build always same road. It look like it fail if i start one game, then leave it and start another one. But I have absolutely no idea what's happening. (I'm using openttd 0.7.0 beta1)
my testai (maps included):

Hi Pat, have you solved the problem ?
If not, here may we could take some learning ..
First time I run your AI : (with Aystar.5 and RoadPF 4)

Big Scenario => Pathfinding succes
Small Scenario => Pathfinding Fail


Looking at the source, I've noticed that it fail since first call to .FindPath() methode

So, I suspect that the problem is at .InitializePath(..)
I've tried several changes (multiplier, max_length etc.) -> still got failed
Checking AITile.IsValidTile says both of source and destination are valid (and the Sign was successfully build too)

And then after change your code to :

Code: Select all

route.src_road <- AIRoad.GetRoadStationFrontTile(lloc + AIMap.GetTileIndex(0,0)); 
route.dst_road <- AIRoad.GetRoadStationFrontTile(lloc + AIMap.GetTileIndex(0,0)); 

the path finder running now and found it path.

Hope this will solve your problem

IMO, AIMap.GetTileIndex(0,0) is redundancy, as it doesn't give any change to your 'lloc'

[Pat]

It seams that there is problem searching path with begin/end on drive thought station. But it's odd than it appear only when change size of map.
PS
I left AIMap.GetTileIndex(0,0) there from testing, because it's easier change 0,0 to 1,0 than writing everything again (:

[Zutty]

*sob* Sometimes bug fixing drives me to the very brink of insanity.

Yexo can you tell me what max_length_multiplier means?...

Code: Select all

function Road::InitializePath(sources, goals, max_length_multiplier = 0, max_length_offset = 10000)

Is it something to do with making the pathfinder sub-admissable? i.e. that a value > 1 means the RPF prefers faster completion to cheaper cost.

I've spent the past few days battling with a bizarre bug that I magically fixed by changing this value from the 1.2 that you use in Admiral to 1.0.

Ive been trying to fix the random bridges issue in my AI, but even when my metric gave EXACTLY the same cost to bridges as it did to an equivalent number of road tiles, it kept builing random bridges in my test scenario. I now think that this was because the RPF was simply not finding the cheaper path because of this multiplier.

Please PLEASE for the love of god tell me I'm right. I've been tearing my hair out over this one!

Edit: Im annoyed with myself BTW, not the new RPF. I just wish I had bothered to understand stuff before copying it parrot-fashion.

[Rubidium]

Building bridges can be cheaper than actually building road there. 'newai' got some code to prevent building unnecessary bridges even though it's more expensive.