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.
Better pathfinding algorithm
Moderator: OpenTTD Developers
Re: Better pathfinding algorithm
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.
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.
- HackaLittleBit
- Director
- Posts: 550
- Joined: 10 Dec 2008 16:08
- Location: tile 0x0000
Who is online
Users browsing this forum: No registered users and 27 guests