Exposing internal pathfinder cost?

Discuss the new AI features ("NoAI") introduced into OpenTTD 0.7, allowing you to implement custom AIs, and the new Game Scripts available in OpenTTD 1.2 and higher.

Moderator: OpenTTD Developers

Post Reply
User avatar
Simons Mith
Transport Coordinator
Transport Coordinator
Posts: 326
Joined: 14 Jan 2010 23:45

Exposing internal pathfinder cost?

Post by Simons Mith »

I'm hoping this is just something obvious I've overlooked.

If the road pathfinder finds a straight 5-tile route with one up-slope across clear terrain, AFAICS it should generate a default 'internal' cost of 140+140+140+140+340=900 points.

(using the default values here: https://wiki.openttd.org/AI:RoadPathfinder)

I'm playing about with the pathfinder, and I have an AI that tries to build roads from any point on a map to any other as controlled by its config settings. I'd like to expose whatever its calulated internal pathfinder cost is, so I can better understand it. Especially when and why it decides to build bridges. For longer routes this quickly gets unreliable to work out on paper.

My placeholder code once it's built a road is:

Code: Select all

    AILog.Info("Done. Pathfinder cost " + [b]pathfinder.cost[/b]);
    AILog.Info("Cash cost £" + expenditure);
    AILog.Info("Now waiting for new coordinates.");
Is there something I can enter now for the bit in bold, or will I need to tweak my scratch copy of Pathfinder.Road to expose that bit of information?
If there's a graceful way to do it I'd be grateful for advice. Thanks.
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: Exposing internal pathfinder cost?

Post by Alberth »

For longer routes this quickly gets unreliable to work out on paper.
Could you elaborate on this, perhaps it's just a matter of going about it in the wrong way.

I don't think the total cost of the final solution would give much insight, beyond validating whether the cost that you use are also really used. For getting insight in how it works, I would propose a different approach (which I agree is quite labour intensive, but not difficult or unreliable, as far I can see).


The path finder makes single tile steps afaik, where it tries to avoid computing tiles that are not useful.
It's not hard to do this on paper too, if you don't care about avoiding computing useless tiles. (It reduces the amount of work, but the result doesn't change.)

Take a sheet of paper, and draw a grid of squares on them, large enough to hold a number. Mark the starting point with 0. Then, find all squares with an empty neighbour square, drop all squares that do not have the lowest possible number, then take any of the remaining squares. (that is, find a numbered square at the border of the numbered squares with the lowest possible value).

From that square, take the number (which is the cost to get there), for each movement direction, add the cost of the move to the neighbour (resulting in the cost to reach the neighbour through the chosen square), and check the computed value with the number at the neighbour (in the computed direction). If the neighbour has no number, or if it has a higher number, the computed value should be written in the neighbouring square.

Next, go back to "find all squares ..." to expand the next numbered square.

Do this until you have picked the destination square as square to use for checking its neighbours.


What you get at each square is the cost to reach that square. The real path is then found by starting from the destination, and repeatedly finding the (reachable) neighbour with the smallest number, thus reversing your way back the the start square.

The trick is thus not to compute a single route, but to compute smallest possible costs for all squares at the same time.
Being a retired OpenTTD developer does not mean I know what I am doing.
User avatar
Simons Mith
Transport Coordinator
Transport Coordinator
Posts: 326
Joined: 14 Jan 2010 23:45

Re: Exposing internal pathfinder cost?

Post by Simons Mith »

Alberth wrote:
For longer routes this quickly gets unreliable to work out on paper.
Could you elaborate on this, perhaps it's just a matter of going about it in the wrong way.
It's the tedium mainly. The AI lets me tweak all the cost parameters individually, and I really don't want to have to calculate routes by hand for dozens of routes and dozens of cost combos, especially as the routes which start to give interesting behaviour tend to be 30-150 tiles long. My longer-term goal is adaptive behaviour - a pathfinder that can handle terraforming tiles here and there on the way to smooth its route.

A plain road isn't too bad; road + bridges + tunnels is more of a challenge; but road + bridges + tunnels + embankments + cuttings + different cost weightings for uphill vs downhill or left turns vs right is more than I want to hand-calculate. Especially when the question is 'at what weighting value will it decide to build a bridge here rather than a tunnel there' which might take several iterations to narrow down - and will probably vary from one route to another.
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: Exposing internal pathfinder cost?

Post by Alberth »

Program a path finder yourself, find an A* description, and go from there.
Being a retired OpenTTD developer does not mean I know what I am doing.
User avatar
Zuu
OpenTTD Developer
OpenTTD Developer
Posts: 4553
Joined: 09 Jun 2003 18:21
Location: /home/sweden

Re: Exposing internal pathfinder cost?

Post by Zuu »

If you don't want to program the pathfinder yourself, you can open the pathfinder library source code. You will find that you can not only configure it, but you can subclass it and override methods in order to add cost computation code etc. In there, you could of course also for debug purposes create signs with the resulting cost. Add to that usage of breakpoints and you can step through the work of the pathfinder.
My OpenTTD contributions (AIs, Game Scripts, patches, OpenTTD Auto Updater, and some sprites)
Junctioneer (a traffic intersection simulator)
User avatar
Simons Mith
Transport Coordinator
Transport Coordinator
Posts: 326
Joined: 14 Jan 2010 23:45

Re: Exposing internal pathfinder cost?

Post by Simons Mith »

As an aside, OTTD could really do with a Jump Point Search pathfinder, but even if I did manage to code one of them, I'd never,
ever expect anyone else to use what I'd written.

If you haven't seen the article link FLHerne posted, looky here: https://harablog.wordpress.com/2011/09/ ... nt-search/

Very interesting. It was mentioned in passing in the 'Ships too far from previous destination' thread.
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: Exposing internal pathfinder cost?

Post by Alberth »

I am quite aware of jump point search :)

jump point search seems to assume the center of the tile has 8 directions, which is not the case in openttd, so at least you have to rewrite the search details.
Secondly, it assumes a uniform cost grid, which would work for the ocean, but not much elsewhere, I assume
Being a retired OpenTTD developer does not mean I know what I am doing.
User avatar
Simons Mith
Transport Coordinator
Transport Coordinator
Posts: 326
Joined: 14 Jan 2010 23:45

Re: Exposing internal pathfinder cost?

Post by Simons Mith »

I thought it merely required worthwhile areas of the grid to have the /same/ cost?
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: Exposing internal pathfinder cost?

Post by Alberth »

Simons Mith wrote:I thought it merely required worthwhile areas of the grid to have the /same/ cost?
Uniform costs are more general, you can have different costs, depending on direction. The main point (and perhaps that is what your 'same' means(?)) is that a move from one tile to a neighbour in a direction has the same cost everywhere.

That means no additional penalties can be added, like signals, bridges, hills, speed, trains ahead, or whatever fine-tuning you want to do while looking for a path.
(To be clear, this is only about additional penalties. You can have a bridge, or a hill, but climbing a hill or crossing a bridge must have the same cost as plain road.)
Being a retired OpenTTD developer does not mean I know what I am doing.
krinn
Transport Coordinator
Transport Coordinator
Posts: 339
Joined: 29 Dec 2010 19:36

Re: Exposing internal pathfinder cost?

Post by krinn »

The problem with the pathfinder (road/rails) is that to lower search cost, it try to build a bridge/tunnel if the previous tile is not be buildable.
And because JPS jump tiles to remove tie, you have plenty times where the tile next the unbuildable tile is just not search, as such, no bridge could be build, making your path finally calc faster, but no more optimize! (JPS is optimize, but if this case with the bridge rule, it is not!!!)

If you goes from A1->F1 and a river is blocking C1, C2, C3, A* will finally look at D1 tile and D1 previous tile is C1 that is block, allowing it to build a bridge from B1->D1, end path is A1->B1->C1->D1->E1->F1 (6 tiles)
But because of JPS, it will not see D1, and not build a bridge: end path is : A1->B1->B2->B3->B4->C4 (it's when JPS find it could jump from C4 to F4)->D4->E4->F4->F3->F2->F1 (12 tiles, wow!!!)

Don't mistake, A* has search a lot: all tiles between the square B1->F4
while JPS has only search B1->B4, C4->F4 and F4->F1, that's really faster, if you compare A* without bridge, A* would endup with the same path size (12 tiles), but still with the same search cost as with bridge, making JPS beating A* to death (same length path == optimize, but search cost really lowered)
But that bridge rule is a killer for JPS.
krinn
Transport Coordinator
Transport Coordinator
Posts: 339
Joined: 29 Dec 2010 19:36

Re: Exposing internal pathfinder cost?

Post by krinn »

krinn wrote:Don't mistake, A* has search a lot: all tiles between the square B1->F4
in real it's not, because it has find a bridge, A* will only search the square B1->D4 and once it find D1, it will only search D1->F1 because no other path could beat the low cost of B1->D1 then (but you should get the idea of A* search high cost)
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: Exposing internal pathfinder cost?

Post by Alberth »

krinn wrote:f you goes from A1->F1 and a river is blocking C1, C2, C3, A* will finally look at D1 tile and D1 previous tile is C1 that is block, allowing it to build a bridge from B1->D1, end path is A1->B1->C1->D1->E1->F1 (6 tiles)
But because of JPS, it will not see D1, and not build a bridge: end path is : A1->B1->B2->B3->B4->C4 (it's when JPS find it could jump from C4 to F4)->D4->E4->F4->F3->F2->F1 (12 tiles, wow!!!)
This cannot be right. JPS has the same optimality properties as A*, and as such, if you apply the same rules to both, the answer is the same.

I think you are not doing true A*, but some extended form of it.
The only reason it ever visits D1 is because you cannot move diagonally to the goal. (Assume you can move diagonally, will it run back from C4 to D1 and then to F1? No, it will diagonally go to D3->E2->F1 and never visit D1 either.)

The proper way would be to try extending B1 over the river to D1, even if it is unbuildable (in that case it should find the other shore, test for buildability there, find it working, and then extend B1 -> D1), and never explore C4.
Being a retired OpenTTD developer does not mean I know what I am doing.
krinn
Transport Coordinator
Transport Coordinator
Posts: 339
Joined: 29 Dec 2010 19:36

Re: Exposing internal pathfinder cost?

Post by krinn »

Alberth wrote:The only reason it ever visits D1 is because you cannot move diagonally to the goal. (Assume you can move diagonally, will it run back from C4 to D1 and then to F1? No, it will diagonally go to D3->E2->F1 and never visit D1 either.)
JPS is present for 8 ways, when you go in diagonal with JPS you must expand horizontally and vertically, as the author describe it (from my understanding), you would jump from D3->E2->F1 but each time you do that, you expand horizontally and vertically too ; so when you goes from C4->D3 you should expand from D3->D1 and D3->F3 too, finding D1 then. And optimality is preserved.

But you cannot goes diagonally with roads... And JPS will fail as-is, maybe someone wrote about 4 ways only implementation of JPS.
Dwachs
Engineer
Engineer
Posts: 46
Joined: 02 Jun 2005 07:28

Re: Exposing internal pathfinder cost?

Post by Dwachs »

Alberth wrote:I am quite aware of jump point search :)

jump point search seems to assume the center of the tile has 8 directions, which is not the case in openttd, so at least you have to rewrite the search details.
Secondly, it assumes a uniform cost grid, which would work for the ocean, but not much elsewhere, I assume
Pathfinding on oceans is where JPS shines. I implemented it for simutrans only for route search on open water, and it reduced the number of visited tiles (tiles put in open list) dramatically.

Simutrans also has only 4 directions. The modification that I did was: as long as the route is going straight only expand in the same direction, when going diagonal, expand in all possible directions. At the end, the change to the existing path finder was almost trivial.
Post Reply

Return to “OpenTTD AIs and Game Scripts”

Who is online

Users browsing this forum: No registered users and 2 guests