Collision detection Revisited part 3 – Pythagoras was a gamer

1-8-2018

Collision detection within a circle.

Ancient Greece, 520 B.C., nighttime. Pythagoras looked up at the night sky and saw three stars: Deneb, Vega, and Altair. These 3 starts formed a perfect triangle. He thought to himself, I wonder how to calculate the distance from one star to another using this triangle. Moments later, he came up with A squared + B squared = C squared. He then loudly pronounced, “my work here is done”. While walking home another thought came to him. These stars look like pixels, if I draw lines between them in my mind, I’ve got a vector based game I can envision.

Hoped you enjoyed that small cock and bull story, but the lesson A^2 + B^2 = C^2 still remains the same. It’s a measurement of distance.

The measurement of two points requires the knowledge of where those two points will lie, and in this case, the points are the center pixels of the sprite and the center point of the object or another sprite.

Now, if we are talking equal distance from all points to a center, then we are talking about a circle. And that is what this is, collision detection within a circle.

Well, that should be easy to calculate, since our sprites are 16×16 and our objects are the same, then the center point of the player’s sprite is playerSprite + 8 for x and y. If using the x = 0 to 240 and y = 0 to 160 (the playing area of the game).

We can then try to use the Pythagoras distance between 2 points formula.

Find the square root of the squared objects X and squared objects Y

squareroot(square(object1 x coordinate – object 2 x coordinate) + square(object1 y coordinate – object 2 y coordinate))

which can be rewritten as

squareroot((object1 x coordinate*object 2 x coordinate)+(object1 y coordinate*object 2 y coordinate))

So as a tester, let’s make a function

void obsticleCollision3 (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;
unsigned char playerRadius, objectRadius;
printtester2(playerX, playerY);//print our position
playerRadius = 16;
objectRadius = 16;
for (iterator = 0; iterator < 90; iterator ++)
{
obsticleX = x1[iterator];
obsticleY = y1[iterator];
attribute = tileAttribute[iterator];
//xx1 needs to be center point x
//yy1 needs to be center point y
//center point of the tiles
xx1 = (obsticleX * 16) + 8;
yy1 = (obsticleY * 16) + 8;
bob = ((unsigned char)sqrt(16));
if (attribute == 99) break;// break out of the loop earlier if we encounter 99
}
}

At the top of my program I place

#include math.h (yes I used the carrot symbols, but wordpress does not seem to like it.)

And I change my compiling string to.

zcc +zx -zorg=32772 -O3 -vn main.c -o build\main.bin -lndos -lmz

Note the -lmz at the end to include the math library.

And a compiler error.

Troubleshoot error for about an hour. And still nothing. Searched Z88DK’s website and still nothing. Question my choices of writing this article.

OK, let’s scratch that.

The fact of the matter is, using square root to find this, the collision was going to be a point I was going to make. Calculating the square root of any number is a processor intensive operation. Adding more to that will surely slow down our game, and we don’t need any more slowdowns.

Is there a faster way to do this? I’m glad you asked because I asked Google the same thing.

Why yes, there apparently is.

In fact, we don’t even need square root at all, the operation is expensive and unneeded, then let’s forget it all together.

What we need is to check to see if squared difference x + squared difference y is less than the squared radius’s (um err is it radii).

That we can do rather efficiently. Now I had to experiment, and I’ll spare you the details of me getting frustrated by having the wrong variable type.

Here’s our code

void obsticleCollision4 (unsigned char playerX, unsigned char playerY, unsigned char level, unsigned char x1[], unsigned char y1[])
{
unsigned char xx1,yy1;
unsigned char obsticleX, obsticleY;
unsigned char iterator;
unsigned char attribute;
unsigned char objectRadius;
unsigned char differenceX,differenceY;
short squaredRadius, squaredDifferenceX, squaredDifferenceY;
//these have to be shorts or larger because the numbers are too large to fit in char objectRadius = 15;
for (iterator = 0; iterator < 90; iterator ++)
{
obsticleX = x1[iterator];
obsticleY = y1[iterator];
attribute = tileAttribute[iterator];
//center point of the tiles
xx1 = (obsticleX * 16) + 8;
yy1 = (obsticleY * 16) + 8;
//differences between the objects
differenceX = abs(playerX - xx1);
differenceY = abs(playerY - yy1);
//now square the objects
squaredDifferenceX = differenceX * differenceX;
squaredDifferenceY = differenceY * differenceY;
//now square the radius
//This could be done outside the loop as the radius don't change
squaredRadius = objectRadius * objectRadius;
//Pythagoras theorm
if ( ( squaredDifferenceX ) + ( squaredDifferenceY ) < objectRadius * objectRadius )
{
zx_border(6);
//force a break below as we have already found a collision
//needs to be the last line in this if statement
attribute = 99;
}
if (attribute == 99) break;// break out of the loop earlier if we encounter 99
}
}

and calling our function

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

Here is our results


Just outside our circle, no collision.


Just inside our circle, collision

And to boot, it runs pretty fast.

I love it when a plan comes together.

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