Yonaba / Jumper

Fast, lightweight and easy-to-use pathfinding library for grid-based games
http://yonaba.github.io/Jumper
MIT License
607 stars 122 forks source link

Bettern pruning rules for Jump Point Search in orthogonal mode #20

Open Yonaba opened 10 years ago

Yonaba commented 10 years ago

Jump Point Search was not actually devised for orthogonal search on uniform cost grids. It actually takes advantage of heading diagonally (over straight directions) to reach a goal.

In the actual implementation of JPS, the problem was partially solved, but not in a very elegant manner, as it floods the search with forced neighbors, jump points and discards evrey single diagonal expansion. It works fine, but the search time is a bit long (higher than standard A-star) and the return path is a step-by-step path.

The point here is to look into ways to develop a new set of pruning rules for 4-directions grids. Some starting points that might be worth investigating further or detailed articles that can be used for reference: