<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: owner-pygame-us...@seul.org [mailto:owner-pygame-us...@seul.org] On Behalf Of Yanom Mobis Sent: Monday, January 26, 2009 5:12 PM To: pygame-users@seul.org 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 <n...@coderanger.net> wrote: From: Noah Kantrowitz <n...@coderanger.net> Subject: RE: [pygame] Pathfinding To: pygame-users@seul.org 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: owner-pygame-us...@seul.org [mailto:owner-pygame-us...@seul.org] On Behalf Of Yanom Mobis Sent: Monday, January 26, 2009 3:39 PM To: pygame-users@seul.org 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 <n...@coderanger.net> wrote: From: Noah Kantrowitz <n...@coderanger.net> Subject: Re: [pygame] Pathfinding To: pygame-users@seul.org 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? > > > >
