News:

Simutrans Forum Archive
A complete record of the old Simutrans Forum.

New much faster algorithm for pathfinding realized

Started by prissi, January 11, 2013, 05:55:49 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

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
Parsley, sage, rosemary, and maggikraut.

Ashley

Use Firefox? Interested in IPv6? Try SixOrNot the IPv6 status indicator for Firefox.
Why not try playing Simutrans online? See the Game Servers board for details.

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Combuijs

Quote
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.
Bob Marley: No woman, no cry

Programmer: No user, no bugs



VS

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

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

jamespetts

I suspect that this could only be used for wayfinding at sea.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Dwachs

Quote from: jamespetts on January 12, 2013, 03:04:41 PM
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.
Parsley, sage, rosemary, and maggikraut.

AP

Quote from: jamespetts on January 12, 2013, 03:04:41 PM
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.
My Sketchup open project sources
various projects rolled up: http://dl.dropbox.com/u/17111233/Roll_up.rar

Colour safe chart:

dennosius

Quote from: Combuijs on January 12, 2013, 02:46:02 PM
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).

Quote from: VS on January 12, 2013, 03:00:57 PM
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

Quote from: dennosius on January 12, 2013, 06:33:23 PM
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.
Bob Marley: No woman, no cry

Programmer: No user, no bugs



Ters

Quote from: dennosius on January 12, 2013, 06:33:23 PM
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.