search

Yonaba / Jumper

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

Provide some early exit to getPath #3

Closed Yonaba closed 11 years ago

Yonaba commented 11 years ago

Pathfinder:getPath(...) triggers the selected finder, and returns nil if a path was not found. That is easy to circumvent, using an efficient floodfill algorithm applied on the entire grid, we specify what nodes are related using integer values, and if a path can be found of not between two nodes. The finder will then lookup these values and early exit in case they do not match (i.e, there's no path between the given locations).

The floodfill should be run once, upon initialization. It should obviously be called again in case the collision map is updated.

The trade-off would be the amount of space needed to store the floodfill values, so let's make of it an optional feature.

Yonaba commented 11 years ago

I am hereby dropping this idea. Tested, got it working, but there are some flaws : the trade-off in terms of memory consumed when storing floodfill values for different walkable values doesn't worth it, and the feature itself might not be much useful to the common user. Maybe keeping it simple and rely on getPath(...) is the best solution here. Closing this issue as of now.