The International Simutrans Forum

 

Author Topic: New much faster algorithm for pathfinding realized  (Read 6523 times)

0 Members and 1 Guest are viewing this topic.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 10829
  • Languages: De,EN,JP
New much faster algorithm for pathfinding realized
« on: January 11, 2013, 05:55:49 PM »
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/

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4899
  • Languages: EN, DE, AT
Re: New much faster algorithm for pathfinding realized
« Reply #1 on: January 11, 2013, 07:19:12 PM »
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

Offline Ashley

  • Coder/Patcher
  • Devotees (Inactive)
  • *
  • Posts: 1288
    • entropy.me.uk
Re: New much faster algorithm for pathfinding realized
« Reply #2 on: January 12, 2013, 12:29:17 PM »
That's rather clever!

Offline dennosius

  • *
  • Posts: 63
  • Languages: EN,DE
Re: New much faster algorithm for pathfinding realized
« Reply #3 on: January 12, 2013, 01:20:36 PM »
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.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20918
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: New much faster algorithm for pathfinding realized
« Reply #4 on: January 12, 2013, 01:42:38 PM »
This is very interesting. Any improvement in ship routing speed would be most welcomed.

Offline Combuijs

  • Web Team
  • Devotee
  • *
  • Posts: 1408
  • Maintainer of maps.simutrans.com
    • Combuijs
  • Languages: EN, NL
Re: New much faster algorithm for pathfinding realized
« Reply #5 on: January 12, 2013, 02:46:02 PM »
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.

Offline VS

  • Senior Plumber (Devotee)
  • Devotees (Inactive)
  • *
  • Posts: 4856
  • Vladimír Slávik
    • VS's Simutrans site
  • Languages: CS,EN
Re: New much faster algorithm for pathfinding realized
« Reply #6 on: January 12, 2013, 03:00:57 PM »
Ways with different speed give nonuniform grid anyway, don't they?

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20918
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: New much faster algorithm for pathfinding realized
« Reply #7 on: January 12, 2013, 03:04:41 PM »
I suspect that this could only be used for wayfinding at sea.

Offline Dwachs

  • DevTeam, Coder/patcher
  • Administrator
  • *
  • Posts: 4899
  • Languages: EN, DE, AT
Re: New much faster algorithm for pathfinding realized
« Reply #8 on: January 12, 2013, 04:18:37 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.

Offline AP

  • Devotee
  • *
  • Posts: 1213
  • Languages: EN
Re: New much faster algorithm for pathfinding realized
« Reply #9 on: January 12, 2013, 04:23:12 PM »
I suspect that this could only be used for wayfinding at sea.
Unless someone decides to code hovercraft for all-terrain use... (?!)

Offline ӔO

  • Devotees (Inactive)
  • *
  • Posts: 2345
  • Hopefully helpful
  • Languages: en, jp
Re: New much faster algorithm for pathfinding realized
« Reply #10 on: January 12, 2013, 04:45:38 PM »
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.

Offline dennosius

  • *
  • Posts: 63
  • Languages: EN,DE
Re: New much faster algorithm for pathfinding realized
« Reply #11 on: January 12, 2013, 06:33:23 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).

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.

Offline Combuijs

  • Web Team
  • Devotee
  • *
  • Posts: 1408
  • Maintainer of maps.simutrans.com
    • Combuijs
  • Languages: EN, NL
Re: New much faster algorithm for pathfinding realized
« Reply #12 on: January 12, 2013, 07:02:27 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.

Offline Ters

  • Coder/patcher
  • Devotee
  • *
  • Posts: 5695
  • Languages: EN, NO
Re: New much faster algorithm for pathfinding realized
« Reply #13 on: January 12, 2013, 07:24:24 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.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 10829
  • Languages: De,EN,JP
Re: New much faster algorithm for pathfinding realized
« Reply #14 on: January 12, 2013, 10:36:59 PM »
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.