Re: [pygame] Pathfinding

[Casey Duncan <casey@xxxxxxxxxxx>]

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