[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] Pathfinding



On Sun, Jan 25, 2009 at 07:16:38PM -0800, Yanom Mobis wrote:
> 1) How is pathfinding done?

There are algorithms for it.  Breadth-first search is the simplest one
and works well for grids where the distance between nearby cells is the
same.  Dijkstra is a generalization that works for arbitrary maps.  A*
is essentially Dijkstra with an extra heuristic that makes it work
faster, which is important for large maps.  All of them find the
shortest possible path.

Wikipedia describes them all.

> 2) How do you prevent a moving sprite from being caught in a v-shaped
> rut made of obstacles?

You use a pathfinding algorithm.

On Sun, Jan 25, 2009 at 07:20:36PM -0800, Noah Kantrowitz wrote:
> 2) Alter the chain length score computation to reduce exploitation.

Could you please translate that to something mere mortals without PhDs
could understand?

On Sun, Jan 25, 2009 at 09:13:28PM -0800, Bill Coderre wrote:
> There are still ways that this can get confused or beaten, of course.
> Until someone comes out with a low-cost traveling-salesman solver,
> however, whatever algorithm you find will have some snags.

I don't see how traveling salesman applies here.  Could you elaborate?

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.

Marius Gedminas
-- 
<niemeyer> philiKON: I'm changing ZCML to parse files twice as fast..
<philiKON> niemeyer, weee
<benji>    ooh, I like it!
<philiKON> how do you do that?
<niemeyer> Lying
<philiKON> i knew it
* benji cries fowl!
		-- #zope3-dev

Attachment: signature.asc
Description: Digital signature