Better pathfinding algorithm

Got an idea for OpenTTD? Post it here!

Moderator: OpenTTD Developers

Post Reply
User avatar
Ketsuban
Engineer
Engineer
Posts: 3
Joined: 30 Jan 2016 16:56

Better pathfinding algorithm

Post by Ketsuban »

I am led to believe that OpenTTD uses the A* pathfinder algorithm, and that this results in slowdown for ships due to the wide-open ocean having no prelaid tracks to follow.

Has jump point search been considered? It's significantly faster than A*, especially when dealing with open spaces, but results in a speedup in confined spaces as well since it can immediately jump between junctions rather than going one square at a time.
Alberth
OpenTTD Developer
OpenTTD Developer
Posts: 4763
Joined: 09 Sep 2007 05:03
Location: home

Re: Better pathfinding algorithm

Post by Alberth »

OpenTTD has several pathfinders, one of them is A*-ish.
It is however heavily modified, and afaik (but I didn't dig down to full understanding), it makes larger steps than a single tile.

JPS still does single tile steps unlike you think, much like the original A* algorithm. The main thing that changes is that it does less internal administration, which leads to the increase in speed. That is, tile access is not the problem for speed, administration of next points to explore is the cause.

Standard JPS does not fit, since it assumes that the center-point of movement is at the center-point of a tile, while in OpenTTD, that is at the center of each tile-edge. The result is that you always have only 6 directions of movement rather than 8. This means the algorithm should be adapted to that situation.

Has it been considered? It depends on what you mean with "consider".
- If you mean "think about it?" I at least have thought about, see above for my conclusions. Other people have pointed to the algorithm before as well, so yes, it has been considered in that meaning.
- If you mean "consider" as "has it been tried by making an implementation?", then I think nobody has done that yet.
Being a retired OpenTTD developer does not mean I know what I am doing.
User avatar
HackaLittleBit
Director
Director
Posts: 550
Joined: 10 Dec 2008 16:08
Location: tile 0x0000

Re: Better pathfinding algorithm

Post by HackaLittleBit »

Ketsuban

Maybe you should have a look at this approach
from JazzyJaffa.
Post Reply

Return to “OpenTTD Suggestions”

Who is online

Users browsing this forum: No registered users and 8 guests