Pathfinding (Jump Point Search)

Code Snippets
1

I’m a bit fed up with PandAI and the way it works… so I finally made a more or less universal, 2D pathfinding AI.

I used the Jump Point Search algorithm, so it works best with a map that has a lot of empty space or is divided into large rooms. It’s not so good with labyrinth type of maps. It finds a path in about 0.03-0.04seconds in a 256x256 map (YMMV), I think it’s a good result for a pure python solution - just don’t call it every frame :wink:

I divided it into two parts, the Pathfinder finds a path and the Pathfollower moves a node along the path both classes are simple to use.

The Pathfinder.
To use it you first need to initialize it:

finder=Pathfinder()

load a nav map as an image where unwalkable areas are marked red:

finder.loadMap('navmesh.png')

or as a list of list where walkable is -1 and unwalkable is -10

map = [                       
[-10, -10, -10, -10, -10, -10, -10, -10, -10, -10], 
[-10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1, -10], 
[-10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1, -10], 
[-10,  -1,  -1,  -1,  -1, -10,  -1,  -1,  -1, -10], 
[-10,  -1,  -1,  -1,  -1, -10, -10,  -1,  -1, -10], 
[-10,  -1,  -1, -10, -10, -10,  -1,  -1,  -1, -10], 
[-10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1, -10], 
[-10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1, -10], 
[-10,  -1,  -1,  -1,  -1,  -1,  -1,  -1,  -1, -10], 
[-10, -10, -10, -10, -10, -10, -10, -10, -10, -10] ]
finder.loadMap(map)

or a json file that has a map just like the one above

finder.loadMap('navmesh.json')

If you have an image but want to load it faster you can turn it into a json file with:

finder.loadMap('navmesh.png') 
finder.saveMap('navmesh.json')

Once you have a Pathfinder with a loaded map call finder.getPath(start, end) to get a path (a list of tuples). The start and end points can be lists, tuples, Vec2, or Vec3, the Pathfinder will only ever use the first two coordinates (x,y).

path= finder.getPath(start=smiley.getPos(render), end=(181, 83))

The Pathfollower.
This class will try to move a node along a path. You can set how fast it will move, how fast it will rotate - if it moves too fast and rotates too slow it will miss the path and orbit around the nearest point in the path without ever reaching it, so always test it.

seeker=Pathfollower(node=smiley, move_speed=10.0, turn_speed=300.0, min_distance=0.5)
seeker.followPath(path)

It also has stop() and start() functions if you happen to need them.

It’s all CC0, public domain … or whatever the original code at github.com/c2huc2hu/jps was :question:

Here’s the code and a bit of extra code showing how to use it, have fun:
pathfind.zip (5.62 KB)