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
signature.asc
Description: Digital signature
