1
DF Suggestions / Pathfinding: Jump Point Search algorithm
« on: October 11, 2013, 03:50:18 am »
It is my understanding that there was no significant progress at the pathfinding issue, at least if the forum search is to be believed. Maybe this will help things.
Here's an article that I've found: http://harablog.wordpress.com/2011/09/07/jump-point-search/. It talks about an improvement to A* called Jump Point Search (JPS), which eliminates a problem that A* has on regular uniform-cost grids, such as DF maps, called path symmetry: basically the many equal-cost pathes that differ only in the order of evaluating them. The article claims that JPS can consistently speed up A* by over 10 times (the longer the path, the bigger the speed-up) and even outperforms HPA despite being optimal.
The potential problems that I see are:
- JPS has no general solution for every kind of grid. The article presents a variant for 2D square grid, which would have to be adapted for DF's 3D grid;
- JPS can be adapted for weighted grids, but this will require work (there are some ideas on this in the comments to the article);
- JPS speeds up when there is a lot of path symmetry. It will work excellently on open spaces, but it's unknown how it will handle an average fortress' labyrinthine floorplan.
Here's an article that I've found: http://harablog.wordpress.com/2011/09/07/jump-point-search/. It talks about an improvement to A* called Jump Point Search (JPS), which eliminates a problem that A* has on regular uniform-cost grids, such as DF maps, called path symmetry: basically the many equal-cost pathes that differ only in the order of evaluating them. The article claims that JPS can consistently speed up A* by over 10 times (the longer the path, the bigger the speed-up) and even outperforms HPA despite being optimal.
The potential problems that I see are:
- JPS has no general solution for every kind of grid. The article presents a variant for 2D square grid, which would have to be adapted for DF's 3D grid;
- JPS can be adapted for weighted grids, but this will require work (there are some ideas on this in the comments to the article);
- JPS speeds up when there is a lot of path symmetry. It will work excellently on open spaces, but it's unknown how it will handle an average fortress' labyrinthine floorplan.