Collision detection Revisited part 1

1-3-2018 to 1-6-2018
The problem with Tile based collisions

Tile based game engines seem to have an inherent problem with collisions that I can’t seem to easily work out, that of Collision detection. Here is the issue at hand, a tile is based on a square grid. In the case of FASE, but not limited to FASE is while everything nicely aligns to squares, not everything is exactly square.

In the case of my game, our main character is a circle, but other games may not exactly be a circle, you could have a plumber shaped sprite or a space-ship. Any of a number of different shapes. Your obstacles will have the same issue, they are probably not all blocks. What we find is that we are trying to place an object into a square and that will not apply in most cases. In fact, in most cases, the obstacle will not be a square.

In our last covering of this subject, we created 3 arrays. One was used for the X position, one for the Y position and a third one for the attribute. It worked, however, it measures all of the obstacles as blocks and that leads to inaccurate colliding.

Case in point.

Here is our sprite colliding with a square. Works OK.

Sprite colliding with the circle, note: not even touching.

The reason the second case is true is that our sprite is touching the box that the circle resides in, but it’s not touching the actual object.

We will find this problem anytime an object that is in the square is smaller than the square itself. You will find this true with any TILE BASED game engine. The same problems occur with the Churrera as well as other game engines.

This makes simple object collision difficult and tricky.

What can be done?

I’m sure there is some sort of convoluted object collision detection routine, but trying to find some routines via google appears to be elusive for me.

Now for reference, I have toyed around with a few just in my head, not trying to find an actual code solution, but just a thought process. Sometimes, I can try to envision what happens first before I try to actually code the thing.

My first thought was to have some sort of pixel-based detection. I could read in the pixel values around the player’s sprite and when there was an object encountered, the pixel value would change in the blank space around my player sprite.

The problem with that thought was that whereas any pixel would be detected, another routine would have to be run to find out what that object was. Also reading in up to 32 pixels would make the game very slow.

Another thought that sprang to mind was we could read a block of pixels at the edges (in groups of 4) and then read the same group of pixels right above the edge and place a binary AND operator. If the end result was 0 then no detection, if the end result was larger than 0, then a collision was detected. A separate routine would be needed to actually tell what the object was. Again, this seems faster, yet still bulky.

The challenge seems to be, have a collision detection that runs fast, yet have a simple implementation as well as a fairly accurate one. Perhaps it does not need to be pixel perfect, but we can’t have large gaps between your player and an object. Speed needs to play a big role, otherwise, a slowly crawling arcade game is just not fun to me.

Let’s play around with some code. Remember this is experimental.

We are going to base this next routine off of a tile-based system. There is already an array made for that: the tiles array.

Advantage, no extra memory, runs fast.
Disadvantage, inaccurate

void tileBasedCollision (unsigned char playerX, unsigned char playerY)
{
    //this version you do not have to have a separate array
    //more memory friendly, but based on 16x16 tile space
    unsigned char attribute = 0;
    playerX = playerX >> 4;
    playerY = playerY >> 4;
    attribute = tiles[playerY * scrw + playerX];
    //tiles[y*scrw+x]
    if (attribute > 0)
    {
        //collision detected
        M_OUTP(0xfe, 4);//changes border color
    }	
}

our calling command.

playerXpos = (unsigned char)(x >> 8);
playerYpos = (unsigned char)(y >> 8);
tileBasedCollision(playerXpos,playerYpos);

This is fast, about as fast as we can hope for. The speed is due to the simplicity of the routine. Now please note, we are using as an input x 0 to 240 and y 0 to 160. The function really needs x 0 to 15 and y 0 to 9.

Here is the problem with the accuracy

No collision

Collision

This is similar to any object within the tiles grid. However, this type of detection is attractive because of speed and memory.

I need to start to think about using the tile-based collision detection, but we need it to be a little more accurate.

In FASE, the grid or Tiles that are used are 16×10 or 16 tiles wide and 10 tiles high. In each tile, the pixels are 16×16.

So let’s start with tiles. I see the problem as if we are using Tiles, our number range is much too small. A 0 to 16 and 0 to 9 range will never lead to an accurate range. Our X and Y on the playing screen is x 0 to 240 and y 0 to 160.

on pixel level
x = 0 to 240
y = 0 to 160

on character block level
x = 0 to 15
y = 0 to 9

Knowing the numbers, we can come up with a quick formula on how to transfer the range.

Given a block region on a square, we can define the square like this.

Whereas XX1 and YY1 are 0
and XX2 and YY2 are 16.

Our formula could then be

XX1= (tile based X position * 16)
YY1 = (tile based Y position * 16)
XX2 = (tile based X position * 16) + 16
YY2 = (tile based Y position * 16) + 16

So, in reality, all we have done is increase or normalize the range of the Character-based tiles to the pixel ranged x,y graphics.

We can base a little experiment on the xx1, xx2, yy1, and yy2

Let’s create a testing function. This is based on our tile is at x = 3.

void obsticleCollision2 (unsigned char playerX, unsigned char playerY, unsigned char level, unsigned char x1[], unsigned char y1[])
{
    unsigned char xx1,xx2,yy1,yy2;	
    xx1 = 3 * 16;	
    if ((playerX == xx1))
    {
        zx_border(6);
        //collision has happened
    }
    printtester1(xx1);
    printtester2(playerX, playerY);
}

And of course we call the function with

obsticleCollision2(playerXpos,playerYpos,level,x1,y1);

We place the calling code in the same area as edge checking.

And fail!

What the devil is going on.

I believe the problem lies in the center pixel, we will have tweak a little.

Change the xx1 code to be

xx1 = 3 * 14;

That seems to detect OK.

Now let’s add something similar to xx2.

void obsticleCollision2 (unsigned char playerX, unsigned char playerY, unsigned char level, unsigned char x1[], unsigned char y1[])
{
    unsigned char xx1,xx2,yy1,yy2;	
    xx1 = 3 * 14;
    xx2 = (3 * 14) + 28;	
    if ((playerX == xx2))
    {
        zx_border(6);
    }
    printtester1(xx2);
    printtester2(playerX, playerY);
}

And yes that works.

Now, let’s combine xx1 and xx2 in a single if statement.

if ((playerX > xx1) && (playerX < xx2))
{
        zx_border(6);
}

And also simplify our xx1 and xx2 math.

xx1 = 3 * 14;
xx2 = xx1 + 28;

Now, let’s try the same for yy1 and yy2.

yy1 = 3 * 14;
yy2 = yy1 + 28;	
if ((playerY > yy1) && (playerY < yy2))
{
    zx_border(6);
}

And of course that seems to work.

Now combine all four edges.

if ((playerX > xx1) && (playerX  yy1) && (playerY < yy2))

Now we have the basis for our boxed in collisions.

We can as a test, also make variables for the obstacle’s X and Y

Here’s what that would look like.

void obsticleCollision2 (unsigned char playerX, unsigned char playerY, unsigned char level, unsigned char x1[], unsigned char y1[])
{
    unsigned char xx1,xx2,yy1,yy2;
    unsigned char obsticleX, obsticleY;	
    obsticleX = 3;
    obsticleY = 3;
    xx1 = obsticleX * 14;
    xx2 = xx1 + 28;
    yy1 = obsticleY * 14;
    yy2 = yy1 + 28;
	
    if ((playerX > xx1) && (playerX  yy1) && (playerY < yy2))
    {
        zx_border(6);
        //collision has happened
    }
    printtester1(xx2);
    printtester2(playerX, playerY);
}

We have covered some of this material in a prior article, but we are going in a bit of a different direction this time and we have changed our formula a little bit.

Expanding on our tile reader array method. Instead of typing each tile entry by hand, we can make a method to read the tiles for us and place those tiles in an array.

Last time we covered the subject, we created 3 arrays, I’ll rehash.

In our global variables, we define 3 arrays

unsigned char x1[90] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};//changed from short to unsigned char
unsigned char y1[90] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};//changed from short to unsigned char
unsigned char tileAttribute[90] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};//read tile value

This is assuming we will have up to 90 objects on the screen.

Now, with those in place, we will create a function to fill those arrays.

void readScreenTiles (unsigned char x1[], unsigned char y1[], unsigned char tileAttribute[])
{
	unsigned char screenX;
	unsigned char screenY;
	unsigned char count;//count how many items are in the array	
	unsigned char tile;
	unsigned char tim;//a temporary variable	
	FRAME;// we force update screen to be able to catch the tile-set for the attributes
	// as per Antonio, tile array is unsigned char.
	//scrw - screen width is constant
	//unsigned char *tiles= 0x5b40;
	//only called when isLevelRead == 0
	
	//clear out array from prior level
	//have no more than 89 objects
	//make everything 99, this is a trigger to stop
	//scanning the tiles array to speed up
	//collision detection
	for (tile = 0; tile < 90; tile ++)
	{
		x1[tile] = 99;
		y1[tile] = 99;
		tileAttribute[tile] = 99;
	}	
	count = 0;
	tile = 0;	
	//screenX 0 to 15
	//screenY 0 to 9
	for ( screenY = 0; screenY < 10; screenY++)
	{
		for (screenX = 0; screenX  0)
			{
				//mark the x & y position and place it 
				//in the array
				//this is where the problem lies
				//writing to array x1, y1 and attribute
				
				x1[count] = screenX;
				y1[count] = screenY;				
				tileAttribute[count] = tile;
				count++;//increment the counter for the next slot in array
				zx_border(2);
				Pause (350);
			}
		}
	}
	
	//now lets print back our values
	for (tile = 0; tile < 90; tile ++)
	{
		screenX = x1[tile];
		screenY = y1[tile];
		tim = tileAttribute[tile];
		printtester1(tim);
		printtester2(screenX, screenY);			
		FRAME;// we force update screen to be able to catch the tile-set for the attributes
		Pause (300);		
		if (tim == 99) break;// break out of the loop earlier if we encounter 99
	}
}

To call the function, we have to place it when we start a new level.

if (isLevelRead == 0)
{
    readScreenTiles(x1,y1,tileAttribute);
    ……
}

Of course, the actual function is a tester. I’ve purposely added commands to slow it down considerably so we can read the values.

If you compile and run

You will see the tiles tick away at the top, once it finds a tile greater than 0, the program will pause a long time so that you can see the x and y tile coordinate as well as the attribute value.

When the program goes through all of the tiles, it will then report the x and y tile position as well as the attribute, this is to make sure the value is stored in the array. If the array encounters a 99 in the attribute area, it will break out early.

Using this, we can see that all of the values are stored in arrays x1,y1 and attribute arrays. Now let’s take out our testing junk by commenting them out.

void readScreenTiles (unsigned char x1[], unsigned char y1[], unsigned char tileAttribute[])
{
    //only called when isLevelRead == 0
    unsigned char screenX;
    unsigned char screenY;
    unsigned char count;//count how many items are in the array	
    unsigned char tile;
    unsigned char attribute;	
    count = 0;
    tile = 0;
    attribute = 0;
	
    //FRAME;// we force update screen to be able to catch the tile-set for the attributes
    // as per Antonio, tile array is unsigned char.
    //scrw - screen width is constant
    //unsigned char *tiles= 0x5b40;
    //only called when isLevelRead == 0
	
    //clear out array from prior level have no more than 89 objects
    //make everything 99, this is a trigger to stop scanning the tiles array to speed up
    //collision detection
    for (tile = 0; tile < 90; tile++)
    {
        x1[tile] = 99;
        y1[tile] = 99;
        tileAttribute[tile] = 99;
    }	

    count = 0;
    tile = 0;
    attribute = 0;
	
    //screenX 0 to 15 screenY 0 to 9
    for ( screenY = 0; screenY < 10; screenY++)
    {
        for (screenX = 0; screenX < 16; screenX++)
        {
            attribute = tiles[screenY * scrw + screenX];

            //if (checking the tile  0)
            //tile 0 is a blank tile to travel
		
            //good
            /*printtester1(attribute);
            printtester2(screenX, screenY);			
            FRAME;// we force update screen to be able to catch the tile-set for the attributes
            zx border(0);
            Pause(15);*/

            if ((attribute > 0) && (attribute < 99))
            {
                //mark the x & y position and place it 
                //in the array
                //this is where the problem lies
                //writing to array x1
                // check to make sure less than 99 as well
				
                x1[count] = screenX;
                y1[count] = screenY;				
                tileAttribute[count] = attribute;
				
                count++;//increment the counter for the next slot in array
            }
        }
    }
}

When we compile and run, the tiles are read lightning fast, but remember that this loop only happens once during each level read.

Also, please note that when you, we seem to require another screen read function.

if (isLevelRead == 0)
{
    FRAME;// we force update screen to be able to catch the tile-set for the attributes
    readScreenTiles(x1,y1,tileAttribute);
    ……
}

Furthermore, we can test to see if the array is changed by running another test from within the isLevelRead command sequence.

if (isLevelRead == 0)
{
    FRAME;// we force update screen to be able to catch the tile-set for the attributes
    readScreenTiles(x1,y1,tileAttribute);		
				
    //test to print array
    for (iterator = 0; iterator < 90; iterator ++)
    {
        screenX = x1[iterator];
        screenY = y1[iterator];
        tim = tileAttribute[iterator];
        printtester1(tim);
        printtester2(screenX, screenY);			
        FRAME;
        Pause (300);
        if (tim == 99) break;// break out of the loop earlier if we encounter 99
    }
…
}

Yes, the values do test correctly.

So, now I want to try to combine the new tile reader function with the collision detection function, so let’s see how that plays out.

The first thing I want to do is change our testing graphics to red ink and blue paper, this will show our classic color clash and show how well our collision is working by changing the color of our sprite.

The next thing I will do is introduce a newly coded function. The only real difference is now we are iterating through the x1, y1 and attribute arrays and reading the values. We introduce our calculations and if the attribute array hits a 99, then we break out of the loop.

void obsticleCollision2 (unsigned char playerX, unsigned char playerY, unsigned char level, unsigned char x1[], unsigned char y1[])
{
    unsigned char xx1,xx2,yy1,yy2;
    unsigned char obsticleX, obsticleY;
    unsigned char iterator;
    unsigned char screenX,screenY,attribute;

    printtester2(playerX, playerY);
	
    for (iterator = 0; iterator  xx1) && (playerX  yy1) && (playerY < yy2))
        {
            zx_border(6);
        }
		
        if (attribute == 99) break;// break out of the loop earlier if we encounter 99
        }
}

And FAIL. Arrrgh!

Collision detected and we are not even close. So that means the formula is incorrect.

So, let’s play around with the formula.

A game show theme song plays while I scratch my head.

How about we plug in this.

xx1 = (obsticleX * 16) - 8;
xx2 = xx1 + 32;		
yy1 = (obsticleY * 16) - 8;
yy2 = yy1 + 32;

And

No collision

and …

Collision!

It works on the X and Y axis.

Thank goodness.

Of course, there are good and bad things with this detection.

Minus
Works with 16×16 square objects only.
The more objects added, the slower everything will be, meaning not constant time.
Uses up some memory.

Pluses
Very intuitive to use.
Can track tile type

For those of you that have actually been keeping track of the code here’s the function.

void obsticleCollision2 (unsigned char playerX, unsigned char playerY, unsigned char level, unsigned char x1[], unsigned char y1[])
{
	unsigned char xx1,xx2,yy1,yy2;
	unsigned char obsticleX, obsticleY;
	unsigned char iterator;
	unsigned char screenX,screenY,attribute;
	
	printtester2(playerX, playerY);
	
	for (iterator = 0; iterator  xx1) && (playerX  yy1) && (playerY < yy2))
		{
			zx_border(6);
		}		
		if (attribute == 99) break;// break out of the loop earlier if we encounter 99
	}
}

Will we use this in the end product? Who knows, but we had to explore this technique to see how it would work and how well it would work.

We will continue to explore other methods as soon as I can cook them up.

Until the next article, keep on coding.

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