Wednesday, December 07, 2005

PathFinding 2

I had earlier promised of explaining pathfinding through obstacles. Well i just wrote a quick applet to show it (using astar algorithm). Unfortunately its time for me to leave, so will explain later :).
CTRL + left click to set predator
ALT + left click to set prey
click and drag to create walls
right click to solve

To clear use ALT + right click

yeah, i know that i should not be a ui programmer


neo said...

I gave an impossibly closed path for the Predator..

He jumped out of the walls to catch the Prey !

phobos said...

well a predator can move diagonally. so you should close all the diagonal path to prey also by providing a corner wherever two wall meets

Zeus said...

I gave no obstacles with predator and prey in a straight line. Shouldn't the path be a straight line??

phobos said...

I will explain the algo, then you will understand why its behaving like that.
The predator calculates the cost of moving from its current cell to its neighbours (8 neighbours). You can associate the weight for [north, south, east and west cells] as 10 and for [northwest, northeast, southeast and southwest] as 14 (since those four are diagonal and it cost approx 10*sqrt(2))

In the current implementation i gave both the weights as 10, so for predator its same case whether walks straight or diagonally. If you set it as 14, it would look mechanical

Zeus said...

Bravo! What a predator! I feel like saying "What the hell ARE you" in a stiff Arnie accent!