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

Re: [pygame] Pathfinding

Have you played any of the unreal tournament games? The way it pathfinds is like what you're asking. It uses a graph ( a bunch of nodes connecting to each other. It actually pre-calculates pathfinding, but you don't need to worry about that at first )

The link posted has a good image: http://en.wikipedia.org/wiki/Graph_%28mathematics%29 ( look at the first one )

Looking at the image, image 1 = health,l 2=flak gun, 3 = ammo, 5 = flag, etc... If a bot wants to go from 3 to 5, you can use A* to find the path.

It just needs a graph ( a bunch of nodes, which can connect to other nodes ) The actual (x,y,z) location of the nodes doesn't matter. ( But if the distance is too far, you need to take that into account by the weight, or, add a node between them )

On Mon, Jan 26, 2009 at 7:11 PM, Yanom Mobis <yanom@xxxxxxxxxxxxxx> wrote:
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?

You can use a regular list-type of tiles. And each list item holds a list of pointers to all tiles that it connects to. If you are doing a tile based map, using a 2D array could simplify things. ( using numPy )

# this is a bad example, but, to give you an idea:

>>> class Tile():
>>>     def __init__(self): self.clist = []

>>> t1 = Tile()
>>> t2 = Tile()
>>> t3 = Tile()

# 1 connects to 2 and 3
>>> t1.clist.append( t2 )
>>> t1.clist.append( t3 )

# 2 connects to 1
>>> t2.clist.append( t1 )

# 3 connects to 1
>>> t3.clist.append( t1 )

# map a list of Tile()s
>>> map = [t1, t2, t3]