[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[pygame] A* module using surfaces for walkability data
- To: pygame-users@xxxxxxxx
- Subject: [pygame] A* module using surfaces for walkability data
- From: Forrest Voight <voights@xxxxxxxxx>
- Date: Fri, 27 Mar 2009 02:48:49 -0400
- Delivered-to: archiver@xxxxxxxx
- Delivered-to: pygame-users-outgoing@xxxxxxxx
- Delivered-to: pygame-users@xxxxxxxx
- Delivery-date: Fri, 27 Mar 2009 02:48:52 -0400
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:date:message-id:subject :from:to:content-type; bh=EWHHlG9eQLelTCFpuqniYE0LIMlLxgNvcn6OtOLlmHs=; b=fanzWYxx6mTfIWRQKgVPVdfVfKVqlDb0Q0bnveqnG5lAnE6stcZ3OmD0AkzU0o6PKW T1SsGUbYfxE2tFiMX9y5RtHKUba2+O2Br7jBykGKj3AmMnu4oenKo2N+sXaXVeEBy9bM I4gIT6B8V3UH4O75PF7M6JXBZeLUM7Z5lM1b8=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:date:message-id:subject:from:to:content-type; b=ojDVQV9uelznxDfUx9PnbTrz1zLcDhXP4fxCDPTaCMwLFmj1bNREqJDxIlE4dvGFsm YtXibwctPmTCilNXRGFPPnqBpIBsxTO7tcjvqdjN0ZMt5vVs4itJ0ZbruFggoUrR2WI4 TCzI2v1GaoY9JzfimgAEG+EHfcztbPs93OQU8=
- Reply-to: pygame-users@xxxxxxxx
- Sender: owner-pygame-users@xxxxxxxx
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
Attachment:
pathfind.zip
Description: Zip archive