Monday, June 27, 2005

Pathfinding - Part 1

In many games, you need to find path to a particular object. Suppose its a predator-prey game and predator need to go to the location of prey. Suppose this is a tile based game.
In this part, we will consider that there is no obstacle between predator and prey.

In a simple path finding we could increment(or decrement) predators x and y positions until both of them coincide with prey's.
ie

if predator.x < prey.x:
predator.x++
elif predator.x > prey.x:
predator.x--
if predator.y < prey.y:
predator.y++
elif predator.y > prey.y:
predator.y--

This is pretty much simple and doesnt require much cpu power.


The problem with above method is that, it doesnt give a direct line between predator and prey.

For eg, in fig, predator will move in x and y direction, until one of them conincides. Then it will move in other direction. ie in the above pic, y got coincided first, then x increases.


You can avoid this problem by using Bresenham's algorithm.
In Bresenham's algorithm, we find out which is large ie x distance or y distance, and will increment the larger one much faster than the other. ie

deltaX = prey.x - predator.x
deltaY = prey.y - predator.y

if abs(deltaX) > abs(deltaY):
delta = deltaX
else:
delta = deltaY

xincr = float(deltaX)/delta
yincr = float(deltaY)/delta
while round(predator.x) != prey.x and round(predator.y) != prey.y:
predator.x += xincr
predator.y += yincr
//draw

This would look like





which is an approximation of line.







Next part - How to move around if obstacles are present.

3 comments:

Zeus said...

Cant say i really understood the code...but the algorithm seems to make sense to me...

What do you know! even this old dog is able to follow some new tricks...Looking forward to part II

Zeus said...

Hey! Where is part II?

phobos said...

part2 will be coming soon .. i want to make it simple :)