# A different approach to enemy movement. Taxicab Difference

4-7-2018
If we are trying to find the distance between 2 points on a grid, then perhaps one of the simplest ways to do so is by using what is called Taxicab distance. Taxicab difference is also called the Manhattan difference and it’s a descriptor of a block by block approach to distance.

For example, the distance between the green block and the red block is 9 spaces or blocks.

A difference in angle between two areas might be represented like this.

Notice, that I am skipping the diagonals. There are also two straightforward paths one could take, the other one would be.

There are 15 blocks that separate the two objects.

Of course, we are going to want to number every block to calculate the difference, so if we populate the entire grid, we would see something like this.

To further illustrate Taxicab difference, I am going to color in the grid with matching numbers colored the same.

It looks similar to a distance heat map with everything radiating diagonally from the center 0.

Going back to finding the pathways, here are our two main paths that we could use to reach the destination.

If you look at the numbers, you will also see that there are also alternative paths that could be taken as well, here is one such example.

I do not have enough whitespace and patience to show all of the possibilities here, as I am certain you can see them. The main point of this exercise is to show how we can number this grid to guide the enemy to the player.

Exactly how are we guiding the enemy (in red) toward the player (in green)? We are simply looking at the grid one space ahead of the enemy positions to the North, East, South, and West. We find a number that is the smaller of the 4 positions and move our enemy to that position.

So, let’s look at how this happens. Our enemy (in red) wants to know how to travel to the player, so it looks up, down, left and right and looks for the lowest number. In this case, up and right are the two lowest number at 14. Down and left are set at 16, so we avoid those.

We now move our enemy to the new grid position. Let’s check our numbers again. And we continue to do so until we move completely to the player.

What happens then, when we throw a wrench in the works. Let’s place some obstacles. When we find an obstacle, in our grid, let place a number to it. A fairly high number, let’s use 99.

We have a few simple obstacles here, let’s see how using the taxicab difference might be able to navigate the obstacles.

If the path is chosen wisely, then we navigate smoothly toward our goal (the player). However, our pathway does not always lead toward the goal. What happens when we choose the following path.

At this point, we cannot reach our goal and our enemy gets stuck. We can also get stuck if we take another pathway.

So, our paths may not always reach our goal. However, the concept is not bad at all and we might be able to correct some of the path-finding by using randomization.

Here another example of this algorithm failing

No matter which path you take, the enemy will get stuck. To our eyes, the solution is simple, just move to the edge and up. But with Taxicab difference, we get stuck at the smallest value.

Despite its flaws, let’s try to implement it.

Here comes a code dump, I’ll explain various sections.

void enemydistance1(unsigned char playerX, unsigned char playerY, unsigned char enemyXX, unsigned char enemyYY, unsigned char enemyFF)
{
unsigned char border;
{
//we will need enemySteps, need to be 0 to 15
// 0000 1111
//enemySteps will be first 4 bits. Need to push last 4 bits off of binary
// so, 0000 1111 will need to be 1111 0000
// need to push back 4 bits
// so, 1111 0000 will need to be 0000 1111
enemySteps = enemyFF  4;
//enemy last direction is next 3 bits
// 0111 0000
// so need to push bit 8 off of binary
// so, 0111 0000 becomes  1110 0000
enemyDirection = enemyFF  5;
// bit 8 is used for enemyRetreat
// if enemy gets hit by a bullet, make the enemy retreat from the player.
// shift 7 places to the right
//so, 1000 0000 becomes 0000 0001
enemyRetreat = enemyFF >> 7;
}

//screen is 15 tiles wide and 10 tiles high
//playerX pixel range 0 - 240
//playerY pixel range 0 - 160
//enemyX pixel range 0 - 240
//enemyY pixel range 0 - 160
playerCharX = playerX >> 4;
playerCharY = playerY >> 4;

enemyCharX = enemyXX >> 4;
enemyCharY = enemyYY >> 4;

count = 0;
tile = 0;
attribute = 0;

//scan the screen to find the taxicab difference
for (screenY = 0; screenY < 10; screenY++)
{
for (screenX = 0; screenX < 15; screenX++)
{
attribute = tiles[screenY * scrw + screenX];
if (attribute == 0)
{//if no obsticle calculate taxicab distance
differenceX = abs(playerCharX - screenX);
differenceY = abs(playerCharY - screenY);
taxicab[count] = differenceX + differenceY;
}
else
{taxicab[count] = 99;}
count++;
}//end x
}//end y

border = 0; //check to see if on the border
barrier = 0;//being used for edge detection
barrierWest = 0;
barrierNorth = 0;
barrierEast = 0;
barrierSouth = 0;

if (enemyCharX == 0)//do not scan west
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = 99;
border = 1;
}
if (enemyCharY == 0)//do not scan north
{
barrierNorth = 99;
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
border = 1;
}
if (enemyCharX == 14)//do not scan east
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];//OK
barrierEast = 99;
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];//OK
border = 1;
}
if (enemyCharY == 9)//do not scan south
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = 99;
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];//OK
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];//OK
border = 1;
}

//do not scan north or west
if ((enemyCharX == 0) && (enemyCharY == 0))
{
barrierNorth = 99;
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = 99;
border = 1;
}
//do not scan north or east
if ((enemyCharX == 14) && (enemyCharY == 0))
{
barrierNorth = 99;
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = 99;
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
border = 1;
}
//do not scan south or west
if ((enemyCharX == 0) && (enemyCharY == 9))
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = 99;
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = 99;
}
//do not scan south or east
if ((enemyCharX == 14) && (enemyCharY == 9))
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = 99;
barrierEast = 99;
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
}
if (border == 0)//not on any border, check obstacles
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + (enemyCharX)];//OK
barrierSouth = taxicab[(enemyCharY + 1) * scrw + (enemyCharX)];//OK
barrierEast = taxicab[(enemyCharY) * scrw + (enemyCharX + 1)];//OK
barrierWest = taxicab[(enemyCharY) * scrw + (enemyCharX - 1)];//OK
//scan current enemy position
enemyPosition = taxicab[enemyCharY * scrw + enemyCharX];
}

{
decision = 0;//start off undecided ,decision starts at 0 when function is called
//assuming 1 tile is less than others
if (decision == 0)
{
if ((barrierNorth < barrierEast) &&
(barrierNorth < barrierSouth) &&
(barrierNorth < barrierWest))
decision = 1;//go north
else
decision = 0;
}
if (decision == 0)
{
if ((barrierEast < barrierNorth) &&
(barrierEast < barrierSouth) &&
(barrierEast < barrierWest))
decision = 2;//go east
else
decision = 0;
}
if (decision == 0)
{
if ((barrierSouth < barrierNorth) &&
(barrierSouth < barrierEast) &&
(barrierSouth < barrierWest))
decision = 3;//go south
else
decision = 0;
}
if (decision == 0)
{
if ((barrierWest < barrierNorth) &&
(barrierWest < barrierEast) &&
(barrierWest < barrierSouth))
decision = 4;//go west
else
decision = 0;
}
//if any two of the tiles match
if (decision == 0)
{
if ((barrierNorth == barrierEast) &&
(barrierNorth < barrierSouth) &&
(barrierNorth < barrierWest))
decision = 5;//north or east
else
decision = 0;
}
if (decision == 0)
{
if ((barrierNorth == barrierSouth) &&
(barrierNorth < barrierEast) &&
(barrierNorth < barrierWest))
decision = 6;//north or south
else
decision = 0;
}

if (decision == 0)
{
if ((barrierNorth == barrierWest) &&
(barrierNorth < barrierEast) &&
(barrierNorth < barrierSouth))
decision = 7;//north or west
else
decision = 0;
}
if (decision == 0)
{
if ((barrierEast == barrierSouth) &&
(barrierEast < barrierWest))
decision = 8;//east or south
else
decision = 0;
}
if (decision == 0)
{
if ((barrierEast == barrierWest) &&
(barrierEast  232)
{
enemyX--;
}
if (enemyX  152)
{
enemyY--;
}
if (enemyY < 8)
{
enemyY++;
}
}

// enemyDirection is shifted 4 bits
enemyDirection = enemyDirection << 4;
// 0000 0111 becomes
// 0111 0000
//enemyRetreat is shifted 7 bits
//so, 0000 0001 becomes 1000 0000
enemyRetreat = enemyRetreat << 7;
//now combine all 3 variables
enemyF = enemySteps | enemyDirection | enemyRetreat;
}

We had covered this previously, but I’ll cover it again,

The very first and very last part of this algorithm is taking our enemyFF variable, and splitting it apart and finally reassembling it. Right now, we are not using the enemyFF variable, but we’ll keep it in as I might be using it later on.

Those sections look like:

Disassembly of enemyFF.

{
//we will need enemySteps, need to be 0 to 15
// 0000 1111
//enemySteps will be first 4 bits. Need to push last 4 bits off of binary
// so, 0000 1111 will need to be 1111 0000
// need to push back 4 bits
// so, 1111 0000 will need to be 0000 1111
enemySteps = enemyFF  4;
//enemy last direction is next 3 bits
// 0111 0000
// so need to push bit 8 off of binary
// so, 0111 0000 becomes  1110 0000
enemyDirection = enemyFF  5;
// bit 8 is used for enemyRetreat
// if enemy gets hit by a bullet, make the enemy retreat from the player.
// shift 7 places to the right
//so, 1000 0000 becomes 0000 0001
enemyRetreat = enemyFF >> 7;
}

Reassembly of enemyFF

// enemyDirection is shifted 4 bits
enemyDirection = enemyDirection << 4;
// 0000 0111 becomes
// 0111 0000
//enemyRetreat is shifted 7 bits
//so, 0000 0001 becomes 1000 0000
enemyRetreat = enemyRetreat << 7;
//printtester1(enemyRetreat);
//now combine all 3 variables
enemyF = enemySteps | enemyDirection | enemyRetreat;

Our next section is assignment of variables.

//screen is 15 tiles wide and 10 tiles high
//playerX pixel range 0 - 240
//playerY pixel range 0 - 160
//enemyX pixel range 0 - 240
//enemyY pixel range 0 - 160
playerCharX = playerX >> 4;
playerCharY = playerY >> 4;
enemyCharX = enemyXX >> 4;
enemyCharY = enemyYY >> 4;
count = 0;
tile = 0;
attribute = 0;

When the function is called, our enemy and player X and Y variables are in the 0 to 240 range, we want to reduce that to the 0 to 15 and 0 to 9 range. We covered this previously. We are also setting our count, tile and attribute variables to 0.

//scan the screen to find the taxicab difference
for (screenY = 0; screenY < 10; screenY++)
{
for (screenX = 0; screenX < 15; screenX++)
{
attribute = tiles[screenY * scrw + screenX];
if (attribute == 0)
{//if no obsticle calculate taxicab distance
differenceX = abs(playerCharX - screenX);
differenceY = abs(playerCharY - screenY);
taxicab[count] = differenceX + differenceY;
}
else
{taxicab[count] = 99;}
count++;
}//end x
}//end y

Here is our taxicab difference routine. We scan the all the X and Y positions, check to see if a barrier is there, if not, we find the difference between the scanned X and Y position and the player and place that in an array. If there is a barrier there, we assign the position a 99, which is a high number tells the enemy not to go there.

border = 0; //check to see if on the border
barrier = 0;//being used for edge detection
barrierWest = 0;
barrierNorth = 0;
barrierEast = 0;
barrierSouth = 0;

Resetting some more variables to 0.

if (enemyCharX == 0)//do not scan west
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = 99;
border = 1;
}

if (enemyCharY == 0)//do not scan north
{
barrierNorth = 99;
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
border = 1;
}

if (enemyCharX == 14)//do not scan east
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];//OK
barrierEast = 99;
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];//OK
border = 1;
}

if (enemyCharY == 9)//do not scan south
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = 99;
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];//OK
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];//OK
border = 1;
}

//do not scan north or west
if ((enemyCharX == 0) && (enemyCharY == 0))
{
barrierNorth = 99;
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = 99;
border = 1;
}

//do not scan north or east
if ((enemyCharX == 14) && (enemyCharY == 0))
{
barrierNorth = 99;
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = 99;
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
border = 1;
}

//do not scan south or west
if ((enemyCharX == 0) && (enemyCharY == 9))
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = 99;
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = 99;
}

//do not scan south or east
if ((enemyCharX == 14) && (enemyCharY == 9))
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = 99;
barrierEast = 99;
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
}

if (border == 0)//not on any border, check obstacles
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + (enemyCharX)];//OK
barrierSouth = taxicab[(enemyCharY + 1) * scrw + (enemyCharX)];//OK
barrierEast = taxicab[(enemyCharY) * scrw + (enemyCharX + 1)];//OK
barrierWest = taxicab[(enemyCharY) * scrw + (enemyCharX - 1)];//OK
//scan current enemy position
enemyPosition = taxicab[enemyCharY * scrw + enemyCharX];
}

Here is where we are making our detentions for movement, there are a lot of them here, but they are grouped in sections, let’s just examine them separately.

if (enemyCharX == 0)//do not scan west
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = 99;
border = 1;
}

if (enemyCharY == 0)//do not scan north
{
barrierNorth = 99;
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
border = 1;
}

if (enemyCharX == 14)//do not scan east
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];//OK
barrierEast = 99;
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];//OK
border = 1;
}

if (enemyCharY == 9)//do not scan south
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = 99;
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];//OK
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];//OK
border = 1;
}

These 4 scenarios are for when the enemy is on the border of the playing field. If X or Y is equal to 0, then we are going to ignore the edge and mark it as a 99, meaning do not go there. We will also set the border variable to 1.

//do not scan north or west
if ((enemyCharX == 0) && (enemyCharY == 0))
{
barrierNorth = 99;
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = 99;
border = 1;
}

//do not scan north or east
if ((enemyCharX == 14) && (enemyCharY == 0))
{
barrierNorth = 99;
barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
barrierEast = 99;
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
border = 1;
}

//do not scan south or west
if ((enemyCharX == 0) && (enemyCharY == 9))
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = 99;
barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
barrierWest = 99;
}

//do not scan south or east
if ((enemyCharX == 14) && (enemyCharY == 9))
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];//OK
barrierSouth = 99;
barrierEast = 99;
barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
}

Here, we are doing almost the exact same thing, except this is when the enemy is in the corners.

if (border == 0)//not on any border, check obstacles
{
barrierNorth = taxicab[(enemyCharY - 1) * scrw + (enemyCharX)];//OK
barrierSouth = taxicab[(enemyCharY + 1) * scrw + (enemyCharX)];//OK
barrierEast = taxicab[(enemyCharY) * scrw + (enemyCharX + 1)];//OK
barrierWest = taxicab[(enemyCharY) * scrw + (enemyCharX - 1)];//OK
//scan current enemy position
enemyPosition = taxicab[enemyCharY * scrw + enemyCharX];
}

Finally, if the enemy is not in a corner or on an edge, we will then scan the areas to the north, south, east and west of the enemy.

The next section is where we are going to make our decisions and there’s a lot going on here.

decision = 0;//start off undecided
//decision starts at 0 when function is called

//assuming 1 tile is less than others
if (decision == 0)
{
if ((barrierNorth < barrierEast) &&
(barrierNorth < barrierSouth) &&
(barrierNorth < barrierWest))
decision = 1;//go north
else
decision = 0;
}

if (decision == 0)
{
if ((barrierEast < barrierNorth) &&
(barrierEast < barrierSouth) &&
(barrierEast < barrierWest))
decision = 2;//go east
else
decision = 0;
}

if (decision == 0)
{
if ((barrierSouth < barrierNorth) &&
(barrierSouth < barrierEast) &&
(barrierSouth < barrierWest))
decision = 3;//go south
else
decision = 0;
}

if (decision == 0)
{
if ((barrierWest < barrierNorth) &&
(barrierWest < barrierEast) &&
(barrierWest < barrierSouth))
decision = 4;//go west
else
decision = 0;
}

//if any two of the tiles match
if (decision == 0)
{
if ((barrierNorth == barrierEast) &&
(barrierNorth < barrierSouth) &&
(barrierNorth < barrierWest))
decision = 5;//north or east
else
decision = 0;
}

if (decision == 0)
{
if ((barrierNorth == barrierSouth) &&
(barrierNorth < barrierEast) &&
(barrierNorth < barrierWest))
decision = 6;//north or south
else
decision = 0;
}
if (decision == 0)
{
if ((barrierNorth == barrierWest) &&
(barrierNorth < barrierEast) &&
(barrierNorth < barrierSouth))
decision = 7;//north or west
else
decision = 0;
}

if (decision == 0)
{
if ((barrierEast == barrierSouth) &&
(barrierEast < barrierWest))
decision = 8;//east or south
else
decision = 0;
}

if (decision == 0)
{
if ((barrierEast == barrierWest) &&
(barrierEast < barrierSouth))
decision = 9;//east or west
else
decision = 0;
}

if (decision == 0)
{
if ((barrierSouth == barrierWest) &&
(barrierSouth < barrierEast))
decision = 10;//south or west
else
decision = 0;
}

First, we are going in undecided.

decision = 0;//start off undecided

If we are undecided, let’s start checking our options.

//assuming 1 tile is less than others
if (decision == 0)
{
if ((barrierNorth < barrierEast) &&
(barrierNorth < barrierSouth) &&
(barrierNorth < barrierWest))
decision = 1;//go north
else
decision = 0;
}

This section asks if there is no decision, then let’s compare North to east, south and west. If north has a smaller value, then we are decided and assigned that decision to 1, if not, then we are undecided.

if (decision == 0)
{
if ((barrierEast < barrierNorth) &&
(barrierEast < barrierSouth) &&
(barrierEast < barrierWest))
decision = 2;//go east
else
decision = 0;
}

Now, do the same with east. If east is the smallest, set the decision to 2.

Repeat for the next two directions, south and west.

So basically, our algorithm looks for the smallest value of the 4 directions and goes in the direction that is the smallest value. However, we can be caught in a scenario, where there are two small values of equal size. What to do then?

//if any two of the tiles match
if (decision == 0)
{
if ((barrierNorth == barrierEast) &&
(barrierNorth < barrierSouth) &&
(barrierNorth < barrierWest))
decision = 5;//north or east
else
decision = 0;
}

So now, we are checking to see if North is smaller than everything else but east. If north and east are equal and smaller, then we assign our decision to 5. We repeat for the other possible scenarios.

//detect barrier
if (decision == 0)
{
if (barrierNorth == 99)
decision = 3;//go south
if (barrierEast == 99)
decision = 4;//go west
if (barrierSouth == 99)
decision == 1;//go north
if (barrierWest == 99)
decision == 2;//go east
}

If we still haven’t come up with a decision, then we just might be on a border, here we are looking a the 4 edges to determine that and making a decision based on it.

Our next section delves into the multiple lowest scenario.

if (decision > 4)// for multiple possible paths
{
barrier = (SHR3 % 2) + 1;
}

if (decision == 5)//north or east
{
if (barrier == 1)
decision = 1;
if (barrier == 2)
decision = 2;
}
if (decision == 6)//north or south
{
if (barrier == 1)
decision = 1;
if (barrier == 2)
decision = 3;
}
if (decision == 7)//north or west
{
if (barrier == 1)
decision = 1;
if (barrier == 2)
decision = 4;
}
if (decision == 8)//east or south
{
if (barrier == 1)
decision = 2;
if (barrier == 2)
decision = 3;
}
if (decision == 9)//east or west
{
if (barrier == 1)
decision = 2;
if (barrier == 2)
decision = 4;
}
if (decision == 10)//south or west
{
if (barrier == 1)
decision = 3;
if (barrier == 2)
decision = 4;
}

If our decision is higher than 4 then we are in a scenario where there are multiple low values. I.e, north and east are equally low. If that’s the case, then we are going to make a random decision.

if (decision > 4)// for multiple possible paths
{
barrier = (SHR3 % 2) + 1;
}

Here we are seeing if the decision is above 4 (5 or higher), if it is, then we generate a random number.

if (decision == 5)//north or east
{
if (barrier == 1)
decision = 1;
if (barrier == 2)
decision = 2;
}

Repeat the same logic for the remainder.

Now, finally, we have made some sort of decision-based on barriers, the edges, the corners and equal lowest numbers. Finally, we get a chance to move in that direction, one pixel.

if (decision == 1)
{
enemyY--;//go north
}
if (decision == 2)
{
enemyX++;//go east
}
if (decision == 3)
{
enemyY++;//go south
}
if (decision == 4)
{
enemyX--;//go west
}

Hooray, we finally moved!

Finally, we need to check to make sure our enemy will not go past the borders.

//keep enemies from going past border
//need hard numbers
{
if (enemyX > 232)
{
enemyX--;
}
if (enemyX  152)
{
enemyY--;
}
if (enemyY < 8)
{
enemyY++;
}
}

And there we go, our first path-finding routine. Does it have flaws, YES. Does it work in all scenario’s, NO. Is it fast, NO. But, it’s a start.

The cost of this algorithm is pretty high in memory and in speed. If we look at the size of our program before we added this routine, we see that we have 13823 bytes free, afterward, we have 10965 bytes free. That’s a memory cost of 2858 Bytes. The speed of the algorithm makes our enemies crawl slowly. Our next article, we will try to see if we can improve this.

Code Happy, code often.