Taxicab Difference part 2, optimzations

4-19-2018

Our last approach to using Taxicab difference is a memory hog and rather slow, two items that are not appealing to programming in general and especially in games and especially, especially on a ZX Spectrum where we have limited speed and limited memory. So, let’s see what we can do to make it better. So, where we last left off, memory was before we added our Taxicab routine at 13823 bytes free and after 10965 bytes free, for a total of 2858 Bytes.

First of all, let’s reconsider the following code.

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];
    barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
    barrierEast = 99;
    barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
    border = 1;
}
if (enemyCharY == 9)//do not scan south
{
    barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];
    barrierSouth = 99;
    barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
    barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
    border = 1;
}
if ((enemyCharX == 0) && (enemyCharY == 0))//do not scan north west
{
    barrierNorth = 99;
    barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
    barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
    barrierWest = 99;
    border = 1;
}
if ((enemyCharX == 14) && (enemyCharY == 0))//do not scan north east
{
    barrierNorth = 99;
    barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
    barrierEast = 99;
    barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
    border = 1;
}
if ((enemyCharX == 0) && (enemyCharY == 9))//do not scan south west
{
    barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];
    barrierSouth = 99;
    barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
    barrierWest = 99;
}
if ((enemyCharX == 14) && (enemyCharY == 9))//do not scan south east
{
    barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];
    barrierSouth = 99;
    barrierEast = 99;
    barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
}

There many redundancies in this code, such as every time we scan for the barriers in the North, South East, and West. We can rework this code to simplify it. And simplification pays up back with increased speed and reduced memory.

Let’s use a little Boolean code and clean up some items.

First, let’s check if our baddy is on the edge of the screen. Before we were using 8 if statements

if (enemyCharX == 0)//do not scan west
if (enemyCharY == 0)//do not scan north
if (enemyCharX == 14)//do not scan east
if (enemyCharY == 9)//do not scan south
if ((enemyCharX == 0) && (enemyCharY == 0))//do not scan north west
if ((enemyCharX == 14) && (enemyCharY == 0))//do not scan north east
if ((enemyCharX == 0) && (enemyCharY == 9))//do not scan south west
if ((enemyCharX == 14) && (enemyCharY == 9))//do not scan south east

and of course all of the code in between those statements.

We can combine two statements in one by using the following

if ((enemyCharX == 0) || (enemyCharY == 0))

The || is an OR statement, and it basically looks to see if the enemyCharX OR enemyCharY are equal to 0. Testing this shows that it works well.

If it works for two, let’s try all 4

if ((enemyCharX == 0) || (enemyCharY == 0) || (enemyCharX == 14) || (enemyCharY == 9))
        border = 1;
    else
        border = 0;

We are using the border variable to see if we are on the edge of the screen.


//lets read all 4 directions
if (border == 1)
{
    barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];
    barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
    barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
    barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
		
    //now eliminate the borders of the screen
    if (enemyCharY == 0)//do not scan north
        barrierNorth = 99;
		
    if (enemyCharX == 14)//do not scan east
        barrierEast = 99;
		
    if (enemyCharY == 9)//do not scan south
        barrierSouth = 99;
			
    if (enemyCharX == 0)//do not scan west
        barrierWest = 99;
}

By switching to the new code, we just saved 458 bytes.

Now, let’s look at our next section of code.

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

It looks pretty straightforward here, however, there is some room for improvement. In the last section of code, we checked the north, east, south and west already. This section seems a bit redundant. So, let’s eliminate it.

Our new code looks like this.

if ((enemyCharX == 0) || (enemyCharY == 0) || (enemyCharX == 14) || (enemyCharY == 9))
    {border = 1;}
    else
    {border = 0;}
	
    //lets read all 4 directions
    barrierNorth = taxicab[(enemyCharY - 1) * scrw + enemyCharX];
    barrierEast = taxicab[enemyCharY * scrw + (enemyCharX + 1)];
    barrierSouth = taxicab[(enemyCharY + 1) * scrw + enemyCharX];
    barrierWest = taxicab[enemyCharY * scrw + (enemyCharX - 1)];
	
    if (border == 1)
    {
        //now eliminate the borders of the screen
        if (enemyCharY == 0)//do not scan north
            barrierNorth = 99;
		
        if (enemyCharX == 14)//do not scan east
            barrierEast = 99;

        if (enemyCharY == 9)//do not scan south
            barrierSouth = 99;

        if (enemyCharX == 0)//do not scan west
            barrierWest = 99;
    }

We just saved an additional 176 bytes with the new code, that’s 634 bytes from the original. Pretty good stuff there. Now our function cost 2224 bytes all-together.

Let’s give the game a test. And the logic works the same.

Next, let’s look at the following code segment.

if ((barrierNorth < barrierEast) && 
    (barrierNorth < barrierSouth) && 
    (barrierNorth < barrierWest))
        decision = 1;//go north
				
if ((barrierEast < barrierNorth) && 
    (barrierEast < barrierSouth) && 
    (barrierEast < barrierWest))
        decision = 2;//go east
				
if ((barrierSouth < barrierNorth) && 
    (barrierSouth <barrierEast) && 
    (barrierSouth < barrierWest))
        decision = 3;//go south
				
if ((barrierWest < barrierNorth) && 
    (barrierWest < barrierEast) && 
    (barrierWest < barrierSouth))
        decision = 4;//go west

This section of code looks for a local minimum in a 4 neighborhood areas (north, south, east and west). It checks to see if, for example, North is less than east AND south AND west. If it is, then we will base a decision on that, in this case, we go north.

However, this can be rewritten in a different way to save some memory by depending a little more on Boolean logic, while retaining the same number of comparisons.

So, I rewrote the code to the following.

if (barrierNorth < barrierEast && barrierSouth && barrierWest)
    decision = 1;//go north
if (barrierEast < barrierNorth && barrierSouth && barrierWest)
    decision = 2;//go east
if (barrierSouth < barrierNorth && barrierEast && barrierWest)
    decision = 3;//go south
if (barrierWest < barrierNorth && barrierEast && barrierSouth)
    decision = 4;//go west

Our cost savings is 73 Bytes.

Let’s now consider the remaining portion of that code section.

if ((barrierNorth == barrierEast) && 
    (barrierNorth < barrierSouth) &&
    (barrierNorth < barrierWest))
        decision = 5;//north or east
					
if ((barrierNorth == barrierSouth) && 
    (barrierNorth < barrierEast) &&
    (barrierNorth < barrierWest))
        decision = 6;//north or south
				
if ((barrierNorth == barrierWest) && 
    (barrierNorth < barrierEast) &&
    (barrierNorth < barrierSouth))
        decision = 7;//north or west
					
if ((barrierEast == barrierSouth) && 
    (barrierEast < barrierWest))
        decision = 8;//east or south
					
if ((barrierEast == barrierWest) && 
    (barrierEast < barrierSouth))
        decision = 9;//east or west
			
if ((barrierSouth == barrierWest) && 
    (barrierSouth < barrierEast))
        decision = 10;//south or west

We can use the same logic from above to reduce the code size.

if ((barrierNorth == barrierEast) && barrierNorth < barrierSouth && barrierWest)
    decision = 5;//north or east
			
if ((barrierNorth == barrierSouth) && barrierNorth < barrierEast && barrierWest)
    decision = 6;//north or south
			
if ((barrierNorth == barrierWest) && barrierNorth < barrierEast && barrierSouth)
    decision = 7;//north or west
			
if ((barrierEast == barrierSouth) && barrierEast < barrierWest)
    decision = 8;//east or south
			
if ((barrierEast == barrierWest) && barrierEast < barrierSouth)
    decision = 9;//east or west
			
if ((barrierSouth == barrierWest) && barrierSouth < barrierEast)
    decision = 10;//south or west

That shaves off another 27 bytes for a total of 100 bytes saved.

The next section we can play with is our random decisions area.

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;
}

We can do a simple restructure of the code.

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;
    }			
}

The cost savings is not too significant here, only 2 bytes saved, however it seems a little more readable to me, more readable and a little more memory savings, an added bonus.

On further examination of this section, we might be able to benefit from using a ternary operator as opposed to an IF statement.

A ternary operator comes in the form of:

expression? True Value: False Value

A little closer to our usage would be:

(x == y) ? True Value: False Value

So, let’s examine the same case:

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

Would change to:

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

Let’s give it a try with the entire section.

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

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

The cost savings is another 32 bytes with the same functionality.

Our total cost savings is now 768 Bytes.

Another problem that we have with this algorithm is that it bogs down the game. The main reason for this is the actual way the grid is built.

For example look at the following code.

//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

What this does again is build up our navigable grid and provides a distance function. However, in doing so, we are iterating through each tile to grab its value and then placing it in an array. We are scanning 10 X 15 or 150 times. That’s each time the enemy movement function is called. It’s a huge bottleneck for the speed. What can be done about that?

The idea that comes to my mind is to not update all 150 tiles all at once. The enemy movement is scanned every time the sprites are drawn, so it happens quite often. There is usually during that short amount of time, there are not many changes that happen in that time frame.

So the idea is to update only 25 tiles in one pass, to visualize this, I’ve made a chart.

During the first pass of the enemies, we update tiles 0 to 24 (represented by the green 1 blocks). The second pass, we update tiles 25-49 (represented by the light blue 2 blocks). We continue on until we reach tile 149. At this point, we start over again and refresh tile block 1.

Now in order to do this, we are going to have to restructure how our tileset is read. This actually brings up speed idea number 2. Unroll the loop. There should only be a slight gain in speed for this, but as an unintended consequence of having to restructure our loop, we end up gaining a more speed.

Our prior loop looked like this.

for (screenY = 0; screenY < 10; screenY++)
{
    for (screenX = 0; screenX < 15; screenX++)
    {
        attribute = tiles[screenY * scrw + screenX];
    }//end x
}//end y

Which is a fairly easy to understand loop. We however need to rewrite this to show as a 1d loop that iterates through all of the required x and y positions.

The general structure of the loop will look like this.

for (tile = 0; tile < 150; tile ++)
{
    if (screenX == 15)
    {
        screenX = 0;
        screenY ++;			
    }
    if (screenY == 10)
    {
        screenY = 0;
        screenX = 0;
    }
	
    attribute = tiles[screenY * scrw + screenX];

    screenX ++;//last line
}

It’s a little more complicated, but not by very much. The loop still goes through all 150 tiles (at the moment). To accommodate for our x and y positions, we are placing 2 if statements in here. If the X position hits 15, then we need to restart X, while also incrementing Y by 1. If the Y position hits 10, then we reset both back to 0. The last line increments X by one. This is the structure we will build our partial update algorithm with.

However, before I do that, I want to show off the unrolled loop with the taxicab difference built in that stores our obstacle map.

screenY = 0;
screenX = 0;
count = 0;	
	
//update_screen();
for (tile = 0; tile < 150; tile ++)
{
    attribute = tiles[screenY * scrw + screenX];
    if (screenX == 15)
    {
        screenX = 0;
        screenY ++;			
    }
    if (screenY == 10)
    {
        screenY = 0;
        screenX = 0;
    }

    if (attribute == 0)
    {//if no obsticle calculate taxicab distance
        differenceX = abs(playerCharX - screenX);
        differenceY = abs(playerCharY - screenY);				
        taxicab[screenScanX + scrw * screenScanY] = differenceX + differenceY;
    }
    else
        taxicab[count] = 99;
	
    count++;		
    screenX ++;//last line
}

This structure while programmatically the same as the nested loop version allows us to more easily break the tasks into parts.

In order to be able to do the split screen trick, we are going to have to have unique variables that are only addressed by this routine.

So, let’s create some variables in variables.h

unsigned screenScanX, screenScanY, screenCounter, screenCounterStart, screenCounterEnd;//only use this during partial screen scanner in enemies.h

In our main.c, let’s initialize those variables in our level initializer.

if (isLevelRead == 0)
{
}

with

screenScanX = screenScanY = screenCounter = screenCounterStart = screenCounterEnd  = 0;//only use this during partial screen scanner in enemies.h

In our enemies.h, we will need to make sure the variables will not go past their top limits.

if (screenScanX > 15)
     screenScanX = 0;	
if (screenScanY > 10)
     screenScanY = 0;	
if (screenCounter > 150)
     screenCounter = 0;

When compiled and run, you will notice quite a speed up from the nested loop. However, we can speed it up even more.

In order to clean up our code base, let’s separate our taxicab difference and place it into a separate function.

void TaxicabDifference(unsigned char playerCharX, unsigned char playerCharY, unsigned char enemyCharX, unsigned char enemyCharY)
{
}

Now, let’s try to implement our partial screen update.

In our variables.h, we are placing in some global variables.

unsigned screenScanX, screenScanY, screenCounter, screenCounterStart, screenCounterEnd;//only use this during partial screen scanner in enemies.h

These are going to be used to control our partial screen updates.

Back to our enemies.h and our Taxicab function

The first variable assignment should be:

screenCounterEnd = screenCounterStart + 25;

This sets our end counter to the same as the start counter but adding 25 to the number, so if the start number is 25, our end would be 50.

Next, we are going to want to make sure we don’t exceed the size of the array by using the next checks.

if (screenCounterStart == 150)
{
    screenCounterStart = 0;
    screenCounter = 0;
    screenCounterEnd = 0;
}

The rest of the routine remains the same. Here’s the complete routine.

void TaxicabDifference(unsigned char playerCharX, unsigned char playerCharY, unsigned char enemyCharX, unsigned char enemyCharY)
{
    screenCounterEnd = screenCounterStart + 25;
    for (screenCounter = screenCounterStart; screenCounter < screenCounterEnd; screenCounter ++)
    {
        if (screenCounterStart == 150)
        {
            screenCounterStart = 0;
            screenCounter = 0;
            screenCounterEnd = 0;
        }
        if (screenScanX == 15)
        {
            screenScanX = 0;
            screenScanY ++;			
        }
        if (screenScanY == 10)
        {
            screenScanY = 0;
            screenScanX = 0;
        }
		
        attribute = tiles[screenScanY * scrw + screenScanX];
		
        if (attribute == 0)
        {//if no obsticle calculate taxicab distance
            differenceX = abs(playerCharX - screenScanX);
            differenceY = abs(playerCharY - screenScanY);	
            taxicab[screenScanX + scrw * screenScanY] = differenceX + differenceY;
        }
        else
            taxicab[screenCounter] = 99;

        screenCounterStart ++;

        screenScanX ++;//last line
    }
}

This increases the speed tremendously, with one caveat; the screen map is not updated all at once, so when the player moves, certain enemies will not know where the player is until that part of the map is updated. Since in this game, the player is constantly moving, it might be difficult for the enemy to have the latest position and thus guide itself to the old position. However, I feel that’s fine.

One, another thing that I noticed while using this technique, is that the enemy will sometimes get stuck on a wall. There are probably a number of solutions to this (other than changing the numeric metric), however, the first one that comes to my mind is a temporary marker.

A temporary marker works like this, if an enemy is on a tile, temporary mark the tile that it is on as a barrier, the enemy will try to propel itself away from the temporary barrier. After the taxicab difference routine passes over the area again, the temporary marker will be gone. This keeps the enemy constantly moving.

Adding this part is fairly simple:

//need to temporarily mark current position with 99 so we know we have already been there
taxicab[enemyCharY * scrw + enemyCharX] = 255;//should repel the enemy away from it current position

This is placed in the taxicab function just outside the loop, either in front of the back of the loop, it doesn’t seem to matter.

I think that we have taken this particular graphing technique far enough. We may revisit it again, however, at this point, I think we have optimized it as far as we can. Time to try another.

Until next time, happy programming.

Advertisements

Author: andydansby

I'm a hobbyist coder working with the ZX Spectrum. Living in New York state near the Syracuse area. I grew up in Virgina. The first computer my parents bought for me was a Timex Sinclair 2068.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s