Giving a Blind octopus 4 white canes, directional obstacle collision detection for enemies.


Our enemy sprites cannot see, they do not know what is in front of them, behind them, nor to the left or right, they are completely oblivious to barriers. When we last approached enemy AI in artificial stupidity, we had the enemy move toward the player. They went completely through all obstacles and did not vary from their path. Would it not be more interesting if the enemies followed the same rules as the player does, avoid all obstacles while still trying to move toward the player?

Well, we come to the problem, the enemy does not know about the obstacles, they just continuously make their move. What can be programmed so that the enemy sprites can detect if there is something in their pathway?

This subject is closely related to our last collision detection subject I blogged about “Tile Based Collision”. In fact, we are going to reuse the same code for that and place it here.

As I do with all of the functions, we have to think about what we want to accomplish with this function, come up with a series of logical steps we want to perform, prototype and code the function and finally try to optimize for memory.

First, let’s think of our logical steps.

FASE works by placing our sprites in a 16×16 character space. It really works by using character spacing and the performing internally via a character space. It will then internally use a character shifting method to move our sprites so that we can utilize a pixel placement for smooth movement. Our tiles, however, use a character placement method and thus need some form of calculations to translate them into the pixel numbering system.

In other words, tiles are measured in a 0-15 in the X-axis and 0-9 in the Y-axis in the character numbering system, while sprites are measured (for smooth movement) in 0-240 in the X-axis and 0-160 in the Y-axis in the pixel numbering system.

Furthermore, we want to be able to measure a few pixels ahead before a collision occurs, thus the white cane analogy. If an enemy does not use the white cane, it runs into the obstacle only detecting once it hits and not before. But why only 4 white canes? Because that’s all our imaginary octopus needs.

To perform this, we will need to program an offset to the sprite range before converting it to the character range. We will need to do this in all 4 directions: north, south, east and west. These are our 4 canes.

Next, in order to determine the direction, we will need to place a variable that will detect which direction the obstacle is in. If you have all 4 canes going at once, then one or more canes can determine where the object or objects are. If you have a cane to your north and to your south touch something, then you know that you cannot move north or south, but must go either east or west. The same goes for any other object or combination of objects.

Our variable can use the binary system to hold the information about what is where. So let’s say, for example, you assign North to add 1 to the variable Let’s say that we assign south we add 2 to the variable. So then, if we encounter 3, we know that there are obstacles to our north and to our south. The only logical conclusion is that we must move to the east or west.

Before we can start to apply this toward your enemies, you need to test it by applying to your character and move around to test each scenario. I’m also going to link to my test code to print the results to the screen.

So let’s try prototyping our code.

void enemyCollision(unsigned char playerX, unsigned char playerY)
    unsigned char barrierPosition;
    unsigned char playerCharX, playerCharY;
    unsigned char enemyCharX, enemyCharY;    
    unsigned char playerXwest, playerXeast;
    unsigned char playerYnorth, playerYsouth;    
    unsigned char barrierNorth, barrierSouth, barrierEast, barrierWest;
    //playerCharX character range 0 - 15
    //playerCharY character range 0 - 9    
    //enemyCharX character range 0 - 15
    //enemyCharY character range 0 - 9
    //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;
    playerXwest = (playerX - 6) >> 4;
    playerXeast = (playerX + 6) >> 4;
    playerYnorth = (playerY + 6) >> 4;
    playerYsouth = (playerY - 6) >> 4;
    enemyCharX = enemyX >> 4;
    enemyCharY = enemyY >> 4;
    decision = 0;
    barrierPosition = 0;
    barrierNorth = tiles[(playerYnorth - 1) * scrw + playerCharX];
    barrierSouth = tiles[(playerYsouth + 1) * scrw + playerCharX];
    barrierWest = tiles[playerCharY * scrw + (playerXeast - 1)];
    barrierEast = tiles[playerCharY * scrw + (playerXwest + 1)];

    //if a tile to the north + 1
    //if a tile to the south + 2
    //if a tile to the east + 4
    //if a tile to the west + 8    
    if (barrierNorth > 0)
        barrierPosition = barrierPosition + 1;
    if (barrierSouth > 0)
        barrierPosition = barrierPosition + 2;
    if (barrierEast > 0)
        barrierPosition = barrierPosition + 4;
    if (barrierWest > 0)
        barrierPosition = barrierPosition + 8;

    printtester2(playerCharX, playerCharY);

And we call the function with

enemyCollision(playerXpos, playerYpos);

The cost of this function so far is only 17 bytes, so it’s a fairly small routine that fits our needs (for now). In our testing, you will see 3 numbers, the top two numbers (near the Killed enemies) is your x,y position in character coordinates. The bottom number (bottom left) is which direction the barrier is in.

I have also redesigned our playing field to account for all different types of barrier placements so we can make sure the algorithm is working properly.

If there is a barrier to the north = 1

If there is a barrier to the south = 2

Barriers to north and south = 3
1 for north + 2 for south

If there is a barrier to the east = 4

Barriers to north and east = 5
1 for north + 4 for east

Barriers to south and east = 6
2 for south + 4 for east

Barriers to north, south and east = 7
1 for north + 2 for south + 4 for east

If there is a barrier to the west = 8

Barriers to north and west = 9
1 for north + 8 for west

Barriers to south and west = 10
2 for south + 8 for west

Barriers to north, south and west = 11
1 for north + 2 for south + 8 for west

barriers to the east and west = 12
4 for east + 8 for west

barriers to the north, east and west = 13
1 for north + 4 for east + 8 for west

barriers to the south, east and west = 14
2 for south + 4 for east + 8 for west

Completely surrounded barriers to the north, south, east and west = 15
1 for north + 2 for south + 4 for east + 8 for west

That was a bit long-winded with the pictures, but we needed to test how the barrierPosition variable worked as well as the entire routine. At only 17 bytes, it’s on the short path to my list of functions.

However, so far we have only indicated which tiles are near your character. There are no decisions on what to do once you get near a tile, nor do we have this applied to the enemy sprites. This is only the start of our new enemyAI, for an enemyAI to work, we need to have the enemy make decisions and actions based on what it requires.

So let’s think about what our actions should be.

Some are easy, some will be more difficult to perform.

An easy one is if a sprite is completely surrounded (an unrealistic scenario). If completely surrounded, do nothing, do not move because it breaks the rules of the game.

So, we might code this as

if ( barrierPosition == 15)
    //do nothing, completely surrounded

A more realistic and easier scenario might be if the enemy is surrounded on all 3 sides, move toward the side that is not surrounded.

It would be coded like this:

if ( barrierPosition == 7)
    //barriers to the north, south and east
    //can only move west
    //logic to move west (move on X axis
    enemyX - -;

There are going to be 4 situations where the enemy will be surrounded on all 3 sides. We might be better served if we list out all of our scenarios and possible actions.

Surrounded by all 3 sides
north + south + east = 7 – Action, move west
north + south + west = 11 – Action, move east
north + east + west = 13 – Action, move south
south + east + west = 14 – Action, move north

two sides
north + south = 3 – Action, move either east or west
north + east = 5 – Action, move either south or west
south + east = 6 – Action, move either north or west
north + west = 9 – Action, move either south or east
south + west = 10 – Action, move either north or east
east + west = 12 – Action, move either north or south

one side
north = 1 – Action, move either south or east or west
south = 2 – Action, move either north or east or west
east = 4 – Action, move either north or south or west
west = 8 – Action, move either north or south or east

No barriers = 0, move toward player

We’re not going into those details during this article as we are starting to venture into another realm that will take quite a bit of exploration.

Until next time, happy coding


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: Logo

You are commenting using your 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