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.