Re: [pygame] A* module using surfaces for walkability data

[René Dudfield <renesd@xxxxxxxxx>]

Hey,

that sounds pretty cool!  It's such a common algorithm and use, I
think it'd be good to be included with pygame.

I guess in pygame.pathfinding ?

You'd need to include tests, docs, an example if you want it in
pygame.  If, so I can get you svn access to add it.  However you've
already got an example/test of sorts, so that shouldn't be too much
work.




Thinking of use cases, and ideas...

I guess you'd want a way of determining which pixels are path, and
which are not.  Either a color key, or color range.  In a lot of maps,
there are multiple colors which are path... and multiple colors which
are blockers.

Often in a map, you have different tiles represented with different
colors.  eg, (0,0,2) could be grass, so could (0,0,3), and (0,0,4)
could be sand.  So the colors could be used for travel cost
optionally.

It doesn't look like you can pass in your own heuristic function?  Is
this needed?

A future optimization might be to use it with the masks, as well as
surfaces.  For 1 bit data, they can be a pretty quick way to do
things... since you've got 32 times less data to operate on.


How could this be used with platformers, where you go left to right?
Where the AI can't fly, but they can jump.


cheers,





On Fri, Mar 27, 2009 at 5:48 PM, Forrest Voight <voights@xxxxxxxxx> wrote:
> 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
>