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

[Forrest Voight <voights@xxxxxxxxx>]

> I guess in pygame.pathfinding ?
It'd probably be part of the AI module.

> 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.
I was thinking that you'd probably have a seperate surface just for
pathfinding. This lets you have per-pixel attributes such as variable
costs.

> 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.
I was thinking just the value would be the cost. 0 for unwalkable, 1
for easily walkable, 2 for harder ... and so on.

> It doesn't look like you can pass in your own heuristic function?  Is
> this needed?
Right now it uses the euclidean distance and precalculates all the
costs to make it really fast. There definitely could be an option for
a callback, but that would slow it down greatly. Perhaps different
options like manhattan distance and multiples of both types of
distances.

> 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.
Sure, though I haven't worked with masks much. This restricts having
costs per node though.

> How could this be used with platformers, where you go left to right?
> Where the AI can't fly, but they can jump.
In the current state it can't be used for that, but I think it could
be changed to work with some assumptions of the physics, like having
the children of a node be up, left, and right if the node under the
current one isn't walkable, and down-left, down-center, and down-right
if the node under the current one is walkable. This doesn't take into
account speed and acceleration however. For that you need a more than
2D search space (other dimensions are the speed) or some kind of hack.

These expansions would need either special modes for the restrictions
on children or optional callbacks. Maybe it would work to allow code
to subclass the pathfinder and implement methods which would be used.