Implement A star JPS + alternative technique for grid pathfinding

[reyman]

I think implementation of this JPS + algorithm could be a plus for gama platform in the long term :)

You could find basic informations here :

• [text] https://en.wikipedia.org/wiki/Jump_point_search
• [visual explanation] http://zerowidth.com/2013/05/05/jump-point-search-explained.html
• [video] http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than
• [repository] https://github.com/SteveRabin/JPSPlusWithGoalBounding

[AlexisDrogoul]

Problems of these highly optimized algorithms/pruning techniques is that (1) they need some preprocessing of data; (2) they can't handle dynamically changing grids/topologies/graphs. Seems to me that they're designed for AI competitions and not real-life applications...

[ptaillandier]

I just finished to implement A* and JPS. You have now 4 algorithms (you just have to define the algorithm used in the optimizer facet of the grid agent):

• A : default algorithm: Very efficient for both Moore (8) and Von Neumann (4) neighborhoods. An introduction to A: http://www.redblobgames.com/pathfinding/a-star/introduction.html
• Dijkstra : Classic Dijkstra algorithm. An introduction to Dijkstra : http://www.redblobgames.com/pathfinding/a-star/introduction.html
• JPS : Jump Point Search, only usable for Moore (8) neighborhood. Most of time, more efficient than A*. An introduction to JPS: https://harablog.wordpress.com/2011/09/07/jump-point-search/#3
  • BF : Breadth First Search. Should only be used for Von Neumann (4) neighborhood. An introduction to BF: http://www.redblobgames.com/pathfinding/a-star/introduction.html

I added a model in the library to illustrate their use.

[sriramab]

Hi Patrick, which one of these do you think will be most efficient for flood modelling?

[ptaillandier]

Hi,

I am not sure how you want to use the shortest path computation for flood modeling, but on the (toy) tests I carried out, most of time, I got:

• Moore neigborhood (8) : JPS >(more efficient) A* > Dijkstra
• Von Neumann neighborhood (4) : A* > BF > Dijkstra

2017-05-11 17:13 GMT+02:00 Srirāma Bhamidipāti notifications@github.com:

Hi Patrick, which one of these do you think will be most efficient for flood modelling?

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/gama-platform/gama/issues/2115#issuecomment-300820830, or mute the thread https://github.com/notifications/unsubscribe-auth/ABb7HfogXDsBVh8ar8YUNYua4wzgHB_Hks5r4yWMgaJpZM4MIrE_ .

[sriramab]

Hmm, high grid_value is high land (high elevation). The shortest path is based on grid value isn't it?