<http://en.wikipedia.org/wiki/Graph_(mathematics)> http://en.wikipedia.org/wiki/Graph_(mathematics)
If you are unclear on what a graph is, I wouldn't recommend trying to write a pathfinding system youself. Perhaps try something higher-level or a library that includes one. --Noah From: [email protected] [mailto:[email protected]] On Behalf Of Yanom Mobis Sent: Monday, January 26, 2009 5:12 PM To: [email protected] Subject: RE: [pygame] Pathfinding a graph, as in just a regular x, y kind of thing? I don't need an overly complex library, is something less complex available? --- On Mon, 1/26/09, Noah Kantrowitz <[email protected]> wrote: From: Noah Kantrowitz <[email protected]> Subject: RE: [pygame] Pathfinding To: [email protected] Date: Monday, January 26, 2009, 6:13 PM You need to construct a graph of possible paths. In a tile-based game this is easy, but it can be done in other kinds of games the same technique can be applied. A* is also used in other types of AIs, such a many board games. As for doing pathfinding in 3D worlds or similar, the word "complex" is a vast understatement. --Noah From: [email protected] [mailto:[email protected]] On Behalf Of Yanom Mobis Sent: Monday, January 26, 2009 3:39 PM To: [email protected] Subject: Re: [pygame] Pathfinding it seems to me that A* only works on tile-based games. What if my game isn't tile-based? --- On Sun, 1/25/09, Noah Kantrowitz <[email protected]> wrote: From: Noah Kantrowitz <[email protected]> Subject: Re: [pygame] Pathfinding To: [email protected] Date: Sunday, January 25, 2009, 9:20 PM 1) People can, and do, get PhDs in pathfinding algorithms. A* (pronounced a-star) is the most commonly used algorithm in games though. 2) Alter the chain length score computation to reduce exploitation. --Noah On Jan 25, 2009, at 7:16 PM, Yanom Mobis wrote: > 1) How is pathfinding done? > 2) How do you prevent a moving sprite from being caught in a v- > shaped rut made of obstacles? Like this: > __ > A -> # | B > __| > > > Where A and B are the points the sprite needs to travel, > # is the sprite, > -> is the direction the sprite is moving, and > _ and | are obstacles? > > > >
