# Pathfinding (Jump Point Search)

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

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] ]

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

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