Ok, so I can count all of my previous experience programming path finding algorithms on two fingers. The first was in high school when Steve and I had a very rudimentary computer class instead of typing. One of the basic programming tasks we were asked to perform was to make a simple chase game on an old HP CPM desktop computer. I actually don’t remember if the machines ran CPM or not, but they surely didn’t run MS Dos. Maybe HP had some sort of proprietary desktop operating system, but I didn’t care enough at the time to find out. I am sure I also attempted some simple chase games on the Atari 800, but I can’t put my finger on any solid examples. The only other time I have even some simple AI was in Retro Blaster, my forthcoming Asteroids on steroids game. In that game I created some simple and complex patterns for the enemy ships to use, and I had enemy missile find the player using simple vector math which produced a direction for them to move toward the player.

So, this morning I decided to read up on path finding around objects for Retro Goes Berserk. If you have read any of the other entries on this game, you might recall that it is a maze chase style action adventure game where the player must negotiate a series of rooms, fight robots and find the pieces to a reactor before time expires. In the game, I need to robots to chase the user. The play field is set up using a grid of 10X10 blocks as tiles. The walls are just a series of these blocks attached to one another. The most difficult problem I had accomplished so far was to create a tile based collision detection routine for the player’s hero. This is an efficient method of collision detection because it doesn’t rely on looping through all of the tiles on every game loop pass to check collisions between the player and the walls.

Anyway, to make the robots move, I had to use the exact same collision detection code, but add path finding around the walls so the robots would move in at somewhat realistically intelligent manner. I first consulted Jobe Markar’s discussions of A* in his great Flash game programming books. A* sounded great, but after more investigation I found it better for use with over-head perspective sprites that can be rotated 360 degrees for absolute realism. Since my game is to be much simpler than that – all characters can only move up/down/left/right, I figured it would be better to create a modified version that would include changing the facing and animation frames for each direction the robot would be able to move.

After also consulting O’Reilly’s AI for Game Developers book, I decided on this for my pseudo code:

*** jeff’s 4 direction path finder (j* for short)
//1. figure out where the player is in relation to the robot
//2. re-arrange up, down, right, left directions in an array best possible moves
//3. try the best one first, if robot can move there (tile is a floor) then move him.
//4. if he cannot move there (tile is a wall) then try the other three until he can find a direction to move, or don’t move at all.

That’s it, it seems pretty simple at first glance, and after some fits and starts at figuring out how to use and sort associative arrays in Flash ( the first idea I came up with a complex data structure that can be sorted) I went to work creating this code in a sample .fla file:

var aDirection:Array=new Array();
var x2:Number=player._x;
var x1:Number=enemy._x;
var y2:Number=player._y;
var y1:Number=enemy._y;

var diffx = x2-x1;
var diffy = y2-y1;

trace(“player x=”+x2);
trace(“player y=”+y2);
trace(“enemy x=”+x1);
trace(“enemy y=”+y1);
trace(“diffx=”+diffx);
trace(“diffy=”+diffy);

var absDiffx:Number=Math.abs(diffx);
var absDiffy:Number=Math.abs(diffy);
if (diffx < 0) {
aDirection.push({direction:”left”,value:absDiffx});
aDirection.push({direction:”right”,value:1000});
} else if (diffx>0) {
aDirection.push({direction:”left”,value:1000});
aDirection.push({direction:”right”,value:absDiffx});
} else if (diffx == 0) {
aDirection.push({direction:”left”,value:1000});
aDirection.push({direction:”right”,value:1000});
}
if (diffy>0) {
aDirection.push({direction:”down”,value:absDiffy});
aDirection.push({direction:”up”,value:1000});
} else if (diffy<0) {
aDirection.push({direction:”down”,value:1000});
aDirection.push({direction:”up”,value:absDiffy});
} else if (diffy == 0) {
aDirection.push({direction:”down”,value:1000});
aDirection.push({direction:”up”,value:1000});
}

aDirection.sortOn(“value”, Array.NUMERIC);

for (ctr=0;ctr<aDirection.length;ctr++) {
trace(aDirection[ctr].direction + ” ” + aDirection[ctr].value);

}

If you place two movie clips on the screen, and name them “player” and “enemy”, this code will create an associative array that contains the values up,down, right, left in the order of which is more relevant to moving the robot (enemy) in the direction on the player. The relevance is based on how far each is from the player. This was just my first attempt, but it worked pretty well in theory. I added in rudimentary hit detection by taking 3 points on the robot and checking whether any of those 3 points will hit a wall in the first direction, if so, then I choose the next direction in the list, and so on until the robot can find a direction to move. Since in reality, there will always only be two relvant paths directly to the player (without worrying about walls), either up/down or right/left will be #’s 1 and #2  in the sorted list,. The remaining two get values of 1000 (for sorting)  and will only be tried if needed.

The this took all day to write and integrate into the existing game, and unfortunately, I will have to go back to the drawing board. The problem is this: if the robot needs to go down, but it hits a wall, it then looks left, right and up for a new direction that doesn’t hit a wall. Well, for some reason, it doesn’t go left and right, it seems to go up, then on the next frame go right back down again and then go back up, etc and repeat. This basically happens if the player stops in front of the robot, but behind a wall. Anyway, I am tired and need to get back to this tomorrow. My next attempt will be closer to A* (which uses tiles to find all adjacent tiles that the robots can move in, and then grades each for which would be the best move). I will use something similar, but I will just move the robot in 4 directions so I can make effective use of my pre-created robot animations that go only in 4 directions.

Play test this version of the game with the flawed first edition of J* path finding.