Re: [pygame] Pathfinding

To: pygame-users@xxxxxxxx

Subject: Re: [pygame] Pathfinding

From: Eli Bendersky <eliben@xxxxxxxxx>

Date: Tue, 27 Jan 2009 17:13:12 +0200

Delivered-to: archiver@xxxxxxxx

Delivered-to: pygame-users-outgoing@xxxxxxxx

Delivered-to: pygame-users@xxxxxxxx

Delivery-date: Tue, 27 Jan 2009 10:13:20 -0500

Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type; bh=SJTEs6mE/OF8Dh7UH2C8GpQOXXvn2deXTkA3/uVfcYI=; b=RlJnmIbgOpuvCSCuF/9iFLlpuGOiyMil2jGwFcbfj9GK2jrj0A/awQ6e8li0wuTK0n /DVIT4r4OGZ2PTCuMvjHPT+PGlgRMpUhvPli0WvtlKzLQ2ZvTWSlnGEkt6Kgf+EpntWP vULlduX8TzQCSFMMMh7iMAUAU7EkJszHT5Tt4=

Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; b=hJcufzM7YVPEnOe0vn7Ejh6ceUEA5X6zeRGKqf+tMUGoelaVfyuyrjojMPfdSKihLP cOOrkztfXDksxb9fQtmYe98EtbuWlxQTbXAK/noiR37rXAK7SahLO/j+hz+nl/Xgb85y YVbjgRsi3Xd4+ecqx0EyNK5MN8O4AVD0c2UVY=

In-reply-to: <497DEC77.5030301@xxxxxxxxxxxxxx>

References: <2313616A-7814-4517-B331-2A32FDF1578B@xxxxxxx> <8AE30A70-DF19-4428-9DE5-C0344555BFC1@xxxxxxxxxxxxxx> <273795.54601.qm@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> <20090126085327.GE11369@platonas> <497DEC77.5030301@xxxxxxxxxxxxxx>

Reply-to: pygame-users@xxxxxxxx

Sender: owner-pygame-users@xxxxxxxx

Here's a tutorial of pathfinding with A*, specifically for PyGame:

http://eli.thegreenplace.net/2009/01/09/writing-a-game-in-python-with-pygame-part-iii/

On Mon, Jan 26, 2009 at 19:01, Michael George <mdgeorge@xxxxxxxxxxxxxx> wrote:

Marius Gedminas wrote:

My personal snag with A* is that the NPCs seem to know too much about
the map and directly walk the most optimal path without exploration.

One possibility to solving this is to have the npc move as it's performing the algorithm. i.e. as your search explores a path, the character walks along that path. This could probably be implemented fairly cleverly by using generators. You'd probably have to experiment with different algorithms to find a more "realistic" approach - I suspect that A* would involve lots of wandering since it assumes constant access time for all known branches (whereas the character has to walk up and down the tree). DFS would probably be more realistic.

--Mike