The problem with Taxicab, examining a different graphing technique.

4-27-2018
I covered in my last article using the taxicab difference to find a pathway to our target (the player). It does help to use the Taxicab difference as it does help guide our enemy to the player, however, there are times when the enemy can and will get stuck on a tile. This is the weakness of our algorithm.

If we examine our taxicab distance, we see that there are a number of tiles that share several local minimums.

So, for example, tiles 1,1

The choices we have are north and west are 14 while south and east are 12. The local minimum is 12, but that number is shared on the south and the east border, so we must make a random decision.

If we examine our chart, we will discover that there are actually very few local minim values, which are highlighted in yellow. The vast majority of the tiles are multi-purpose whereas ne means the enemy can go north or east, se means the enemy can go south or east, nw means the enemy can go north or west and sw means the character can go south or west. The purple highlight indicates there are problems navigating this area. The green highlight is the player tile. Finally, the red highlight tiles are the barriers.

This all means that we are subject to a lot of randomization. Not that randomization is bad, but there is not a clear pathway to the player with a lot of randomization.

So clearly, the problem lies with tiles that do not have a unique local minimum

Let’s examine another graph-based distance measurement.

The first one that comes to my mind is Chebyshev distance, which is called another name, kings distance, or the distance a King (referring to chess) can travel to get from point A to point B on a chess board.

Here is what the Chebyshev Distance looks like on a graph.

If we place a heat map to the numbers it looks like this.

Whereas 0 is where our player is.

Of course in this example, we can easily place the enemy at any point and by finding our minimum, we can guide ourselves to the player.

However, when we add obstacles to the mix, things start to get odd.

There are a number of areas where our enemy can get stuck or get caught in randomize mode (where it can not make a decision. Look at tiles 2,3 (in x,y format). North and south are the same numbers, so the enemy will wander aimlessly until it can hit the 9 and then move on. The same happens at any vertical wall. If you look at tile 10,8 you will see another circumstance where it can get caught in randomize mode. Now, to help that we can also insert our temporary marker in place, to keep the enemy moving.

Nonetheless, let’s code it in and give it a try.

void ChebyshevDifference(unsigned char playerCharX, unsigned char playerCharY, unsigned char enemyCharX, unsigned char enemyCharY)
{
    screenCounterEnd = screenCounterStart + 25;	
	
    //update_screen();//temp for displaying game stats
    for (screenCounter = screenCounterStart; screenCounter  screenScanX) ? playerCharX - screenScanX : screenScanX - playerCharX;

            differenceY = (playerCharY > screenScanY) ? playerCharY - screenScanY : screenScanY - playerCharY;
            //this is our funky Absolute value formula for unsigned variables

            difference = (max(differenceX,differenceY));			
            taxicab[screenScanX + scrw * screenScanY] = difference;
        }
        else
            taxicab[screenCounter] = 99;

        screenCounterStart ++;
		
        screenScanX ++;//last line
    }
    //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
}

You will notice a few things, first, we are using a funky way to use the absolute value on an unsigned char. I had issues with assigning an absolute value to an unsigned char which never goes negative in the first place, however, it can go funny really quick if you place it into negatives. This quick formula fixes that. The second thing you may notice is that I have placed our temporary marker to try to push the enemy away.

We can even tweak our metric a little.

differenceX = (playerCharX > enemyCharX) ? playerCharX - enemyCharX : enemyCharX - playerCharX;
differenceY = (playerCharY > enemyCharY) ? playerCharY - enemyCharY : enemyCharY - playerCharY;

This measures the distance from the enemy to the player instead of the distances of the entire board, doing this, the logic is slightly different, but the overall play is the same, the enemies will get stuck.

While writing this, another idea springs to mind, what would it look like if we combined the Chebyshev Distance with the Taxicab distance? The end result should look like this.

There are still a few spots on the board that the enemy might get stuck on, but let’s see how it plays out.

void DistanceMetric(unsigned char playerCharX, unsigned char playerCharY, unsigned char enemyCharX, unsigned char enemyCharY)
{
    screenCounterEnd = screenCounterStart + 25;	

    for (screenCounter = screenCounterStart; screenCounter  screenScanX) ? playerCharX - screenScanX : screenScanX - playerCharX;			
            differenceY = (playerCharY > screenScanX) ? playerCharY - screenScanX : screenScanX - playerCharY;
            difference = (max(differenceX,differenceY));
			
            //taxicab distance
            differenceX = abs(playerCharX - screenScanX);
            differenceY = abs(playerCharY - screenScanY);
			
            taxicab[screenScanX + scrw * screenScanY] = (difference) + differenceX + differenceY;
        }
        else
            taxicab[screenCounter] = 99;

        screenCounterStart ++;		
        screenScanX ++;//last line
    }
    //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 its current position
}

Using this particular metric, the enemy robots track you down fairly easily without getting stuck too much, the weakness behind this is the same as the other metrics we have been using, you can still hide behind walls. However, we are not caught up as much with randomization as the other two metrics. Most of the numbers are unique within the north, south, east and west area our enemy is looking for.

Nonetheless, this is a pretty strong algorithm and metric. I’m fairly happy with the way the enemies are moving, not perfect, but pretty solid.

However, I feel compelled to try another type of enemy AI, one that has a clear pathway to the player and one that does not require as much randomization.

Our next enemy AI article will start to cover the optimal path algorithms.

This article is dedicated to Rick Dickinson who passed from this life on April 26th, 2018. My heart goes out to his family.

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