[Library] Introducing pathfinder.road

[TrueBrain]

Dear all,

As of this moment, in SVN (and in 18 hours and 45 minutes in the binary), we have a basic road pathfinder (with a big tnx to Yexo for the hard work). It is built on the A* algorithm in the library system, which is built on the BinaryHeap. It's basic function is to find a road-route from A to B, where the assumption is that A and B are either clear or road tiles. You can configure all costs, so you can for example make it check if there is a route between A and B. Well, for more details I suggest to read the documentation in the file. Soon we will produce doxygen pages of it, so you can read it more easy.

This pathfinder is just a suggestion, a piece of the puzzle to make it easier for you to make your own AI. As most people have a lot of problems getting the slopes correct and stuff. It is all figured out for you now Well.. pathfinding that is. Making a powerful AI is still something very tricky Either way, don't feel obligated to use this pathfinder. Feel free to build your own. And if you think yours is better, feel free to send it in. The libraries are not a mandatory something, more something to make your life a tiny bit easier.

Problems? Suggestions? Bugs? Related to 'pathfinder.road' library? Post them here!

Have fun all!

Ps: this pathfinder is limited to building roads only. No bridges or tunnels it will build (or want to build, you need to do the building yourself anyway). It does however reuse existing bridges and tunnels.

[Zutty]

Nice!

My road pathfinder is heavily customised (I've just finished getting it to build tunnels and bridges) so I'll probably stick with what I have, but I'm keen to take a peek at your strategy for building on slopes. My AI is still stumped by certain combinations of slopes (it ignores them for risk of failing), and I'm not happy with my implementation which is messier than I'd like.

[Yexo]

For those wanting some sample code on how to use the pathfinder, see http://wiki.openttd.org/index.php/AI:Pathfinder. There is a sample ai there that finds the two biggest towns and build a route between them. So now go and create more road AIs

@Zutty: success with your code, building corners on slopes is the most tricky.

[GeekToo]

Wow, you guys are hard to keep keep up with! What an incredible amount of cool things you are doing

As a matter of fact, I was planning on improving the pathfinding of Convoy, but I took a quick peek at your pathfinder, and it looks like it already contains everything I planned to do.
When writing an AI a lot of things need to be implemented, and I abused the 80/20 rule: 80 percent of the functionality is implemented in 20% of the development time. So I implemented pathfinding and line management, and strategic planning etc in a way that is not optimal, but renders quick results, so a complete AI, with acceptable quality is created.

Next step I planned, was to improve sub-projects like pathfinding. So, at the moment, the pathfinding of Convoy is pretty good at it's job, but far from perfect. While I was creating the AI, you guys have been busy creating a better pathfinding algorithm.

Things I planned for Convoy pathfinding were:
-improve on slopes. Though most situations were covered, I was aware that improvements on some slopes were possible
-separate planning and building, sometimes Convoy builds a route, that is too expensive, so it is not completed, making a loss, because the route is not completed, but costs were made to create that part of route.

Both aspects are already present in your pathfinder, so I changed my plan: I'll rewrite Convoy to use this pathfinder, cause I think it does show the quality that I was aiming for as final result, and it's a waste of time to reinvent the wheel.

When I've rewritten it, would it be a problem to run a tournament between the old Convoy, and the new one, using this pathfinder? Because, although I think this pathfinder is very good, measurement that proves it is, is better. ( as you may have noticed, I like incremental improvements, and when this pathfinder would improve Convoys performance, I will use it, no use to reinvent the wheel as long as AI development is already difficult enough)

[TrueBrain]

(..)

When I've rewritten it, would it be a problem to run a tournament between the old Convoy, and the new one, using this pathfinder? Because, although I think this pathfinder is very good, measurement that proves it is, is better. ( as you may have noticed, I like incremental improvements, and when this pathfinder would improve Convoys performance, I will use it, no use to reinvent the wheel as long as AI development is already difficult enough)

Sure, no problem. We just name them differently, and run them

Also, if it turns out that the Pathfinder in the library isn't better, feel free to improve it until it is It would be nice to have a really good pathfinder for people to use, as you explained pretty nice in your post

[GeekToo]

OK, first update then: replaced the pathfinding with the lib pathfinder. It's doing quite well, esp. on mountains ( see attached cfg file ).
Some behaviour is different, it does avoid slopes more than my pathfinder did, I did not yet tweak the costs.
I've not yet implemented the saving of the path if costs are too high, to get a more pure comparison of the pathfinding.


Btw I fixed some things on the wiki:
http://wiki.openttd.org/index.php/AI:Pathfinder

[TrueBrain]

The pathfinder.road only uses slopes when they are symmetrical (it doesn't matter from which side you build them, they connect). Strictly speaking a few more are allowed, but this can give nasty problems when building the route .. so that might explain a few things

[GeekToo]

The pathfinder.road only uses slopes when they are symmetrical (it doesn't matter from which side you build them, they connect). Strictly speaking a few more are allowed, but this can give nasty problems when building the route .. so that might explain a few things

I did some experiments tonight, and the lib pathfinder did perform at least as good or better (depending on the map) than my pathfinder. So I think I'll continue to use it.
The library pathfinder is doing a very good job connecting tiles on slopes. It does manage to connect tiles that my pathfinder didn't. The problem of slope avoidance was not a symmetrics problem, but a cost problem.

But.., there's room for improvement, please don't see this as criticism (well, it is, but meant to be constructive, I think you're doing a great job, and this remark is only meant to achieve our common goal: to offer the users a very good pathfinder).

The penalty for slopes is much too high: in my experiment I set up two parallel routes: one with an uphill slope, followed by a downhill slope, and one completely flat. I wanted to find out the costs for slopes.

It did show that a bus going uphill, followed by a dowhill does lose approximately a half tile compared to a flat road.

If a bus is going uphill only, it will lose app. 1 tile compared to flat.

So going downhill is good, but only after going uphill before ( the speed of the bus is limited to it's max speed, even going downhill, which is not physically correct, but it's implemented that way). Going uphill is not good. But currently every slope is penalized with 200 extra costs, which is too hard.

I suggest to take the z-height into account: going uphill has a penalty of 100, going downhill has a reward ( negative penalty ) of 50.

[Finaldeath]

This works really well, as long as the values are tuned a bit to my liking (tried increasing the cost of an empty tile - works great for using all existing road it can it seems ).

Might have to make use of it at least as a brilliant example, especially if bridges and tunnels might be added eventually

(This is great stuff to have available, saves much time, I prefer the planning rather then the building code, heh).

One thing; it'd be nice if the pathfinder could be initialised to find out (although I will hack this in if necessary if the code won't change when I get to using it) if there is any possible route for the road (but doesn't build it, although perhaps it could return an array of road actions to perform if we did want to do it?) and perhaps have it also check if there is a optimal-enough route using existing roads if so wanted. A way to estimate the cost too would be cool.

These are only ideas, and like I said I'll put them in myself if there is no real reason for this library to have them, but they'd be useful in my mind

[Yexo]

This works really well, as long as the values are tuned a bit to my liking (tried increasing the cost of an empty tile - works great for using all existing road it can it seems ).

Might have to make use of it at least as a brilliant example, especially if bridges and tunnels might be added eventually

(This is great stuff to have available, saves much time, I prefer the planning rather then the building code, heh).

One thing; it'd be nice if the pathfinder could be initialised to find out (although I will hack this in if necessary if the code won't change when I get to using it) if there is any possible route for the road (but doesn't build it, although perhaps it could return an array of road actions to perform if we did want to do it?) and perhaps have it also check if there is a optimal-enough route using existing roads if so wanted. A way to estimate the cost too would be cool.

These are only ideas, and like I said I'll put them in myself if there is no real reason for this library to have them, but they'd be useful in my mind

Good ideas, but there're already possible.
1) The pathfinder will return an array of tiles. You still have to actually build the road yourself (by checking if adjacent tiles are already connected and if build a road between them.
2) To check for a route using existing roads only, set pathfinder.cost.no_existing_road to a value higher then pathfinder.cost.max_cost.
3) The check for the length of an existing roadyou set cost.no_existing_road to some high value (as explained in 2)). You'll then either get null back (no route via existing road) or an array of tiles. You could check the length of the returned array to get some extimate of the route-length.
Check for optimal-ehough route can be done via 3) and comparing it to AIMap.DistanceManhattan, or by comparing it to a second run of the pathfinder without a too high cost.no_existing_road value.

[glx]

I suggest to take the z-height into account: going uphill has a penalty of 100, going downhill has a reward ( negative penalty ) of 50.

Using negative penalty is very bad for A*.

[Finaldeath]

If you wanted that behaviour, having 0 for downhill, 50 for no change and 100 for uphill I guess would be better but then it'd be a bit biased towards downhill, haha.

And Yexo, I didn't look into the code too deeply, so thanks for the tips. Higher then max_cost, interesting method to achieve it. The "estimate" you mention if a hard one, but manhattan distance should do nicely for most times - although in some cases, this pathfinder obviously will take a long way around without bridges/tunnels, but that's not always a bad thing (since those things cost mucho cash).

[paullb]

If you wanted that behaviour, having 0 for downhill, 50 for no change and 100 for uphill I guess would be better but then it'd be a bit biased towards downhill, haha.

This is bad because then there is no penalty to going over rolling hills (1-up, 1 down, 1 up, 1 down) which is much slower than going over flat ground.

So I would suggest downhill 0, flat 50, uphill 200

[Yexo]

I may sound like a good idea to have seperate downhill / uphill bonusus, but you don't need that. Say the pathfinde founds a route from start_tile to end_tile. AITile.GetHeight(start_tile) = 2 and AITile.GetHeight(end_tile) = 4. The route will have to go uphill at least twice. Say there are some hills in the route, so it'll go uphill 4 times and therefore downhill 2 times. (Note how the number of times you go downhill is linked to the number of times you go uphill.) Using uphill / downhill, you would apply a penalty of 4 * uphill + 2 * downhill. However, if the pathfinder tries to find a route from end_tile to start_tile, you would apply a penalty of 4 * downhill + 2 * uphill. This can be a good thing, but only when you check for a route both ways, and not just once.

Now say you check for a route just in one direction, and assume vehicles will be able to go the same route the other way. Instead of applying both the uphill and the downhill bonus for example 5 times, you can also apply the slope bonus 10 times. Say uphill bonus = 200 and downhilll bonus = 0, take slope bonus 100 ((200 + 0) / 2) to get exactly the same route. Furthermore, using only slope bonus and not seperate uphill / downhill bonuses ensures that the pathfinder finds the same route (or at least different routes with exactly the same cost) no matter if you do FindPath(sources, goals) or FindPath(goals, sources).

[GeekToo]

I suggest to take the z-height into account: going uphill has a penalty of 100, going downhill has a reward ( negative penalty ) of 50.

Using negative penalty is very bad for A*.

Of course, but I was referring to the extra penalty for slopes, added to the normal tile costs. The sum of the normal tile cost and the extra penalty must always be positive.

Yexo, I'll explain my point a little better:

Take this hill:

______/-----------\______

Loss compared to flat: 1 tile , i.e. the extra cost should be 100, ie 50 per sloped tile.
The default library costs will penalize the hill with 2*200 = 400.
See also the attachments, one before one bus goes uphill, one after and regaining full speed.
So the default costs for slope are too high imo: it will try to avoid slopes more than necessary

But I was referring to this case:
______/\__________

When the bus has lost speed on a hill, it is preferred to have a downhill tile immediately after it:
the extra cost of this hill is only half a tile, so should be 50. So in the special case when an uphill slope is immediately followed by a downhill
the downhill cost should be less.

So, summarized,
-extra cost for slopes: 50
-extra cost for downhillslopes immediately after an uphill: 0

[Zutty]

I don't use the library pathfinder, but I have a thrid option for you. My preferred solution for a hill like __/\__ is to use a tunnel. I have to make tunnels quite cheap for this to work, but its better than having to make a special case for the hill cost IMHO.

BTW: GeekToo - Gorgeous screenshots there! Does your extra zoom levels patch fit easily into NoAI?

[Yexo]

Tonight the second version of pathfinder.road was committed to svn. It now supports building bridges / tunnels. For usage instructinos, see http://wiki.openttd.org/index.php/AI:Pathfinder

[paullb]

In the wiki there is the following text

This code loops over all the whole route. For every element, it checks whether it's already connected to the previous tile via road or via a bridge. If it's not connected it tries to build a road. Note that in a real AI you'll probably want to check if AIRoad.BuildRoad returns true, and if not restart pathfinding.

I have been trying with little success to get such an alogithm working. Its the primary reason that Jinjaba cannot keep up with Convoy (it winds up looping over and over the same path)

I was wondering if anyone might be willing to share their alorithm for the above.

[Yexo]

In the wiki there is the following text

This code loops over all the whole route. For every element, it checks whether it's already connected to the previous tile via road or via a bridge. If it's not connected it tries to build a road. Note that in a real AI you'll probably want to check if AIRoad.BuildRoad returns true, and if not restart pathfinding.

I have been trying with little success to get such an alogithm working. Its the primary reason that Jinjaba cannot keep up with Convoy (it winds up looping over and over the same path)

I was wondering if anyone might be willing to share their alorithm for the above.

I think you're confusing two things now: building a route and keeping track what route to build. Code for the first is in the wiki.

As soon as my AI builds a route between two towns, it adds both TownIDs to an AIList. Whenever I start searching for a new route. I creaet a townlist with
townlist = AITownList();
And remoev all used towns from it using
townlist.RemoveList(this.used_towns);

[paullb]

In the wiki there is the following text

This code loops over all the whole route. For every element, it checks whether it's already connected to the previous tile via road or via a bridge. If it's not connected it tries to build a road. Note that in a real AI you'll probably want to check if AIRoad.BuildRoad returns true, and if not restart pathfinding.

I have been trying with little success to get such an alogithm working. Its the primary reason that Jinjaba cannot keep up with Convoy (it winds up looping over and over the same path)

I was wondering if anyone might be willing to share their alorithm for the above.

I think you're confusing two things now: building a route and keeping track what route to build. Code for the first is in the wiki.

Not really, its building a route. Jinjaba handles which cities it has build to in a different way.

The alogoithim I am looking for is the one to make sure that the route is build sucessfully which is not on the wiki. I find mine is always stopping and winding up in a loop forever. (I discovered this looking at the overview logs from the tournaments)