Running into a Tile, Tile based Collision

2-7-2018

Tile-based collision is quite basically a no-frills, square based collision detection technique. Quite like the square based detection, this will only detect based on a square region. There is no radius needed, nor does it require any additional memory, as an added benefit, it runs rather rapidly. Unlike the other collision detection methods, this method automatically tells you the tile number, without any memory requirements. This method was suggested by Antonio several months ago and I just now got around to coding the method.

It’s a nice simple and clean routine. It speeds up the game as it does not have to iterate through an array of tile positions nor attribute positions. The memory savings comes from not having to declare the arrays in the first place.

The first thing we need to accomplish is our prototyping before we try to optimize our memory. Let’s do a measurement before creating the routine. 12995 bytes free before we do anything.

The method only requires that we add or subtract 8 (depending on the direction) from our pixel-based character position and then convert that to a character position.

Here’s our prototyping function.

void tileCollision(unsigned char playerX, unsigned char playerY)
{
    unsigned char playerCharX, playerCharY;
    unsigned char playerXwest, playerXeast;
    unsigned char playerYnorth, playerYsouth;
    unsigned char north, south, east, west;    
    playerXwest = (playerX - 8) >> 4;
    playerXeast = (playerX + 8) >> 4;
    playerYnorth = (playerY + 8) >> 4;
    playerYsouth = (playerY - 8) >> 4;
    playerCharX = playerX >> 4;
    playerCharY = playerY >> 4;
    north = tiles[(playerYnorth - 1) * scrw + playerCharX];
    south = tiles[(playerYsouth + 1) * scrw + playerCharX];
    east = tiles[playerCharY * scrw + (playerXeast - 1)];
    west = tiles[playerCharY * scrw + (playerXwest + 1)];
}

Let’s run through this quickly.

First, all we need for our routine as input is our player position X and Y.

We then declare some temporary local variables, this part will be memory-optimized a little later. The playerCharX and playerCharY are character based positions. The playerXwest, playerXeast, playerYnorth, playerYsouth are our converters. Finally, our north, south, east, west are our detectors which detect the tile number you have just touched.

Next, playerXwest takes our pixel-based position and subtracts 8 from the position as the sprite control is based on the center position of the sprite itself, we then also shift the bits to the right to acts as a divisor 16, which is the same as dividing by 16 (only faster). This is when the sprite touches the right of the tile. PlayerXeast likewise takes the center pixel and adds 8 so that the sprite can tell when it touches the left of the tile, it also shifts the bits by 4 to divide by 16. We repeat the same logic for playerYnorth and playerYsouth.

The next assignments are the playerCharX and playerCharY. These two are also crucial to the function as they are the straightforward conversion of the pixel position to the character position of the player’s sprite.

Now comes the most interesting part, we look to the player’s north, south, east and west by referencing the tile array using a pointer conversion formula.

Remember in Z88dk, we cannot use 2d arrays, but must use a 1d array. A 1d array can look like a 2d array with the proper indexing and that is what we are doing here. Just FYI, there is no array in C that when compiled is actually a 2d array, but rather a converted 1d array, just some compilers will do the work for you automatically as part of the compilation process.

That’s it for the actual logic, but even so, this performs no action when you touch a tile, just will look in the proper place. For the actual detection, we need to add a few more lines in the form of If statements.

if (north > 0){
    zx_border(6);}
if (south > 0){
    zx_border(6);}
if (east > 0){
    zx_border(6);}
if (west > 0){
    zx_border(6);}

Now we are detecting the tiles, all we are indicating is that when we see something to our north, south, east or west that is higher than 0, we detect something and change the border of our display. All we need to do now is call the function using

tileCollision(playerXpos,playerYpos);

And now we are working.

Now, let’s optimize a little. The compilation size shows 12542 bytes free with this function in place, a cost of 453 bytes.

Looking at our globals, we can reuse some variables and eliminate the locals which seem to take up memory.

We have already defined

unsigned char playerXattr;//player x attribute position
unsigned char playerYattr;//player y attribute position

and

unsigned char tmpx1, tmpy1, tmpx2, tmpy2;

So, let’s reuse those.

We can also reuse a few shorts that we had already defined in globals.

short xx1, xx2, yy1, yy2;

So, now our function looks like.

void tileCollision(unsigned char playerX, unsigned char playerY)
{
    playerXattr = playerX >> 4;
    playerYattr = playerY >> 4;

    tmpx1 = (playerX - 8) >> 4;
    tmpx2 = (playerX + 8) >> 4;
    tmpy1 = (playerY + 8) >> 4;
    tmpy2 = (playerY - 8) >> 4;

    yy1 = tiles[(tmpy1 - 1) * scrw + playerXattr];
    yy2 = tiles[(tmpy2 + 1) * scrw + playerXattr];
    xx1 = tiles[playerYattr * scrw + (tmpx2 - 1)];
    xx2 = tiles[playerYattr * scrw + (tmpx1 + 1)];

    if (yy1 > 0)
    {
        zx_border(6);
    }
    if (yy2 > 0)
    {
        zx_border(6);
    }
    if (xx1 > 0)
    {
        zx_border(6);
    }
    if (xx2 > 0)
    {
        zx_border(6);
    }
}

And on compilation, we discover the size to be 12588 bytes free and we save 46 bytes, with a total cost of 407 bytes.

Of course, it’s not all paradise, we can still have issues on the corners. As the next screen shot shows.

Collision not detected on edge conditions.

So, how can we fix that, by adding some additional conditions.

For that, we will need to add 4 more additional variables in our global’s. xx3, xx4, yy3 and yy4.

short xx1, xx2, yy1, yy2, xx3, xx4, yy3, yy4;

And modify our routine to include the corners, so now our routine looks like.

void tileCollision(unsigned char playerX, unsigned char playerY)
{
    playerXattr = playerX >> 4;
    playerYattr = playerY >> 4;
    
    tmpx1 = (playerX - 8) >> 4;
    tmpx2 = (playerX + 8) >> 4;
    tmpy1 = (playerY - 8) >> 4;
    tmpy2 = (playerY + 8) >> 4;
    
    //xx3 = tiles[tmpy1 * scrw + (tmpx2)]
    xx1 = tiles[playerYattr * scrw + (tmpx2 - 1)];// right side
    xx2 = tiles[playerYattr * scrw + (tmpx1 + 1)];//left side
    yy1 = tiles[(tmpy2 - 1) * scrw + playerXattr];//bottom side
    yy2 = tiles[(tmpy1 + 1) * scrw + playerXattr];//top side
    xx3 = tiles[((playerY + 5) >> 4) * scrw + (tmpx2)];//top left
    xx4 = tiles[((playerY + 5) >> 4) * scrw + (tmpx1)];//top right
    yy3 = tiles[((playerY - 6) >> 4) * scrw + (tmpx1)];//bottom right
    yy4 = tiles[((playerY - 6) >> 4) * scrw + (tmpx2)];//bottom left
    
    if (xx1 > 0)
    {
        zx_border(6);
    }
    if (xx2 > 0)
    {
        zx_border(6);
    }
    if (xx3 > 0)
    {
        zx_border(6);
    }
    if (xx4 > 0)
    {
        zx_border(6);
    }    
    if (yy1 > 0)
    {
        zx_border(6);
    }
    if (yy2 > 0)
    {
        zx_border(6);
    }    
    if (yy3 > 0)
    {
        zx_border(6);
    }
    if (yy4 > 0)
    {
        zx_border(6);
    }    
}

On compiling, we show 12359 bytes free, so our routine has a cost of 636 bytes.

The question in my head, is it worth it? It’s hard to say. Using the radius of each square (covered in another article) is smaller, but you are limited to 40 items on the board and you require an iteration through each array item, plus as the size grows, the routine slows and you do require 40×3 (120 bytes) to for the 3 arrays needed to perform the algorithm. Using both is redundant for your player, however, we still may use both as there is a need for our enemy to detect collisions.

The choice is yours, I just wanted to present yet another technique to perform collisions.

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