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

Re: [pygame] Pathfinding



my game is 2d, but probably not tile-based.

so your saying I can make it do only a few iterations per turn?
how about doing the whole calculation beforehand, then not having to do many calculations?

--- On Tue, 1/27/09, Casey Duncan <casey@xxxxxxxxxxx> wrote:

From: Casey Duncan <casey@xxxxxxxxxxx>
Subject: Re: [pygame] Pathfinding
To: pygame-users@xxxxxxxx
Date: Tuesday, January 27, 2009, 5:06 PM

On Jan 27, 2009, at 3:36 PM, Yanom Mobis wrote:

> is it easier to make the game tile-based?

Probably, but it really depends on the details.

> if I make every pixel a node, and there are 2 obstacles really close together, how will I     make sure something 20 pixels wide doesn't try to go into a 2 pixel wide opening?

If this is a 3D game, what does a pixel mean? ;^)

This could be done by vetting candidate routes using collision detection. Assuming you can reduce the path into a series of straight lines, you could create a rectangular prism with its height and depth set to the size of the bounding rectangle of the frontal area of the thing you are moving and it's length set to the distance of the path segment from one node to another. You position that rectangle along the node path and check for collisions with obstacles. If it collides, you can't go that way. Repeat for each path between nodes. You could also use a cylinder with a sufficient radius.

If the paths can't be decomposed into straight segments, you could do something similar with a bounding box around the thing you are moving. Take that box and position it in steps along the candidate path. If it collides with anything along the way, it can't go that way.

Note with either of these approaches I would suggest not trying to calculate the pathfinding every frame. You can do it piecemeal. Real things often start heading the wrong way and correct later anyhow so it might actually be more "realistic".

-Casey