New much faster algorithm for pathfinding realized

[prissi]

This should speed up pathfinding especially for ships be a factor of 3-20, as about a magnitude less points have to search while still getting the best possible path! Read for more detail http://harablog.wordpress.com/2011/09/07/jump-point-search/

[Dwachs]

Very interesting! I  read the first two parts long ago, but never realized that their was a third part - which is the most interesting for us. Of course, the idea has to be adapted for our case.

Link to research paper: http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf

[Ashley]

That's rather clever!

[dennosius]

I think the advantage will be a bit smaller in ST as we can't go (truely) diagonal, so we only have four jump points, and need to consider that Simutrans' way of going diagonal needs two jumps which are nevertheless shorter than two straight jumps. But I think the concept can still work if adapted.

I'm also thinking whether this could be used not only for path- but also for routefinding. This would require to build a virtual grid of all stops and adapting the concept so there can be more than eight jump points.

[jamespetts]

This is very interesting. Any improvement in ship routing speed would be most welcomed.

[Combuijs]

I'm also thinking whether this could be used not only for path- but also for routefinding. This would require to build a virtual grid of all stops and adapting the concept so there can be more than eight jump points.

Don't think so, as the grid is not equidistant in that case. The given method supposes uniformity in all directions and it will fail if that is not the case.

[VS]

Ways with different speed give nonuniform grid anyway, don't they?

[jamespetts]

I suspect that this could only be used for wayfinding at sea.

[Dwachs]

I suspect that this could only be used for wayfinding at sea.

Yes it looks so, however still the algorithm promises to visit fewer nodes ... There is definitely some potential in this idea.

[AP]

I suspect that this could only be used for wayfinding at sea.

Unless someone decides to code hovercraft for all-terrain use... (?!)

[ӔO]

hovercrafts usually have a landing pad at the dock and don't go inland too far.

conversely, amphibious tourist buses also need a landing pad, but keep to calm, shallow waters.

[dennosius]

Don't think so, as the grid is not equidistant in that case. The given method supposes uniformity in all directions and it will fail if that is not the case.

Does current routing consider distances? I thought it only considered hops ( =  jump points).

Ways with different speed give nonuniform grid anyway, don't they?

Even waterways can have different max speeds in Simutrans. This would also require adaptions if shortest path != fastest path shall be considered.

[Combuijs]

Does current routing consider distances? I thought it only considered hops ( =  jump points).

That is true, but the route finding for ships can consume a lot of time now, especially when no direct route can be found and when there are many options and when the map is large. Jump points make a difference here. The number of tiles to be considered for ships is significantly higher than the number of transfers for a train route.

[Ters]

Does current routing consider distances? I thought it only considered hops ( =  jump points).

I think so, too, if by routing you mean routing of goods. Pathfinding for vehicles consider more than just distance.

[prissi]

Routing of goods is not on a grid, this jump search will not work. Even A* improved goods routing only a little (compared to factor of 2-60 for jump search on seas), as the heuristic is conservative.

The other nice thing of this algorithm is, that it will automtically minimize turns, i.e. the current weight to discourage additional turns of ships will be no longer needed while still giving nice long legds for the ships to go.

Im am not so much worried about speed limits. It were rare occasions when there was really a choice for ways for ships with different speed limits; if really needed one could make the route longer to jump points at channel/river entrances.