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] ]
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
Here’s the code and a bit of extra code showing how to use it, have fun:
pathfind.zip (5.62 KB)