A while ago I made a really efficient A* pathfinding module in C that
is integrated with Pygame. It has all kinds of optimizations, some of
which increase the speed at the expense of memory.
It uses a binary heap for the open list, gridded storage for the
closed list and a counter so the grid doesn't have to be cleared. It
also has a system for more detailed control of allowable movements,
but they are hardcoded.
Last, it has 'layers' which are not actually fully implemented, but
the idea is that you can have seperate Surfaces, possibly of seperate
sizes that affect the costs and walkability data. For example, on the
bottom you would have the actual terrain. Then you would have the fog
of war layer, which could be a surface that circles are drawn to to
reaveal parts of the map to the pathfinder.
Right now it's not very configurable. The movement directions and
costs are hardcoded.
If there's any interest or possibility of it being integrated, I can
make everything configurable and clean it up.
To use the attached file:
* run make
* run python pathtest.py map.png