# Part 1 – Time based motion

## Introduction

Have you ever played a very old game to discover that it runs so ridiculously fast that you cant play it? Wondered why it happened? I will tell you that and how to avoid that your game acts like that on fast computers. The reason why it happens is that the game is made for a slower computer then yours. The fps gets too high when it’s running on faster computers. Don’t worry, there are some ways around this. The first way is to limit the max fps. This is good, but you need to be sure that every computer is fast enough to run it at that framerate(or, better, a higher framerate). When you execute it at slower computers, you get an slow and inconsequent fps. To avoid this you can heavily optimize your program, or you can use time based motion instead of limiting the fps. This won’t get you a higher fps on slow computers, but makes sure that your movement is “fitting” with the fps. That means, when a fps is two times higher then another, the speed will be two times slower. The thing is: there are twice as many frames, so when the speed in every frame is half as high, the speed per second will be the same.

## Using time based motion

When you’ve read the introduction, you know what time based motion is, but not how to use it. Here you can read that ;). First, you all know this formula, for moving an object in a straight line, right?

Xposition = Xposition + Xspeed

Yposition = Yposition + Yspeed

Now, when we do time based motion, we do this :

Xposition = Xposition + Xspeed * time

Yposition = Yposition + Yspeed * time

Where time is the time that is passed since last frame. When you want to use this formula in your program, you have to give up the speed in pixels per second, instead of pixels per frame. When you’re having problems with low speeds, use either fixed point math or floating point math. This is needed, because if you run your game at fast computer which run your game at let’s say 100 fps(this is very high but for a simple game good possible), and you have an object that moves at 50 frames per second. That makes 50/100=0.5 pixels movement per frame. That doesn’t work when you use integers, cause they work only with whole numbers. 0.5 is for an integer the same as 0. The solution? One: Use floating point(singles). Two: Use fixed point math. That means: multiply the number(0.5 here) by a value, for example 10. Then you have 5. Later, when you calculate the position, integer divide by 10 again. The bigger the number you multiply and divide with, the bigger the accuracy. For instance, when you multiply by ten, only the first number behind the dot is saved. When you use 100, the first 2 numbers after the dot. Of course you can use all numbers instead of ten’s and hundred’s, you can choose every number you want. One thing to keep in mind is that the final number (here: 0.5 x 10 = 5) may not exceed 32767. So when you have coordinates between 0 and 319, you can multiply with hundred.

To know what value to give to timer:

Timegone! = (Lasttimer! - TIMER)

Where Lasttimer! Is the value of TIMER in the past frame(You have to save it in an variable).

## How a time based motion engine should look

Here’s some pseudo code for a time based motion engine.

<code>

Begin of loop

Calculate how much time is gone since the last timer save

Save the value of the timer

Draw everything

End of loop

</code>

Easy, huh?

## Problems and possible solutions

When you use time based motion you can face some serious problems. The main one is when you have a TIMER with not enough accuracy. The solution to this is to use Freebasic. This has a much better timer. With Qbasic, it is hard (or not possible) to get more accuracy timing.

You get another problem when you want to run your game at very slow computers. When the frame rate is low, the speed in pixels per frame is high. This is not good, since you can’t control and see everything well when everything moves too much between two frames. The solution is just to set a maximum to the time difference. What I mean is that you say: if the difference in time between two frames is too high, act like the difference in time is the maximum. By carefully choosing the maximum number you can get good(but slower, because you don’t use time based motion correctly) results.

A problem that I already faced, is the inverse: the speed per frame is very low due to the high framerate. I told you already that you should use floating point math or preferably fixed point math. When you multiply by hundred, and run at 100fps, a speed of 1 pixel per second is okay. And that is very slow. Anyway, when you’re still having troubles (I can’t imagine that, but okay), you can use long type variables and multiply and divide by a much bigger number, or just use floating point math(but that is much slower then integers or long integers).

# Part 2 - Collision detection

By RubyNL

## Introduction

Collision detection in something very important in almost all action games. It is VERY annoying when the collision detection sucks (that means that your bullets are going straight through the enemies but they stay alive ;)). Collision detection is also fairly easy to do, if you know how to. I think this tutorial is an absolute must when you want to program an action/shooting game but you don’t know about collision detection ;).

Collision detection needs to be done:

To check if the hero/controlled object hits anything,

To check if your bullets/projectiles hit an enemy or destroyable object

Collision needs to be done every frame to make sure that objects with an high speed miss another object. Another solution is to do a line check. You check if the line between the old object position and the new one intersects any other lines from objects. This is quite hard to do(I actually have no clue how to ;) and you can do it either in this way, so I’ll learn you only this one.

That is for a simple game. For a complex game, you need to check much more (about anything that is moving or can move). I will teach you three kinds of collision detection:

(Non-rotated) square objects

Spheres

Per pixel detection

It’s all simple, except the square-sphere collision detection which is a bit tricky. I’ll start with squares because they are the simplest.

## Collision detection of squares and spheres

### Square objects

Point-square collisions

Point-square collisions are really easy to check. Squares are defined of two points(like you draw them with line):

A point is in the square (so there is a collision) if its x coordinate is between x1 and x2 AND if its y coordinate is between y1 and y2.

To check if the x-coordinate is between x1 and x2, just use:

<code>

IF pointx > squarex1 AND pointx < squarex2 THEN

</code>

Where pointx is of course the x coordinate of the point to check and squarex1 and squarex2 are the coordinates of the two points where the square is made from.

This is exactly the same for the y coordinate. When you have a point at (pointx, pointy) and a square defined by (dqaurex1, squarey1)-(squarex2, sqaurey2), you can do point-square collision detection with:

<code>

IF pointx => squarex1 AND pointx =< squarex2 AND pointy => squarey1 AND pointy =< squarey2 THEN …

</code>

Well, then you have an intersection :P. By the way:

Be sure that squarex2 > squarex1 and squarey2 > squarey1.

Else, the intersection messes up (it will never happen). You can swap the values if squarex1 > squarex2 or squarey1 > squarey2. Code for this is:

<code>

IF squarex1 > squarex2 THEN SWAP squarex1, squarex2

IF squarey1 > squarey2 THEN SWAP squarey1, squarey2

</code>

When I think about it: this is very much like the classic way of keeping a moving pixel in the screen. That is: Do separate a check for the x-axis and the y-axis. When it is out of the screen, invert the horizontal or vertical speed of the pixel.

<code>

IF pointx > screenxlimit OR pointx < 0 THEN xspeed = -xspeed

IF pointy > screenylimit OR pointy < 0 THEN yspeed = -yspeed

</code>

That should do it. Of course you can replace screenxlimit, screenylimit and the two 0’s by variables that represents the edge of a square or a viewing screen (that could be another size then the real screen).

Square-square collisions

Square-square collisions are almost as easy as point-square intersections. First, you need to get four points instead of two for the square. We will check all this points for intersections.

This image will show you how to get these four points(point A-D in the image) from two points(point A & D in the image):

pointax = squarex1

pointay = squarey1

pointbx = squarex2

etc.

Now you just check for each point (A-D) if it’s in the square. Just do a point-square collision. If one of the four points is in the square, there is a collision. That was all about it for square objects. Let’s move on the round objects!

### Spheres

Point-sphere collision

Sphere objects are checked in a simple, but complete different way then squares. Instead of checking if a point is between two axes, you need to calculate the distance. But first assume this object, a nice UFO:

To do collision detection for a round object, you need to know its radius:

Well, when you need the radius, all you further need to know to check if a point is its distance to the center of the sphere. That is done like this:

distance = SQR((pointx - spherex) ^ 2 + (pointy - spherey) ^ 2)

(Pointx, spherex, pointy and spherey can all be swapped in the equation, don’t worry about that) When the distance is less then the radius of the sphere, there is a collision.

IF distance =< radius THEN …

But, as some of you may know: a square root(SQR, used to calculate the distance, has nothing to do with squares ;)) is very slow. We can optimize this by squaring both the distance and the radius. It is also faster to multiply(x * x) then to square(x ^ 2), and be sure to precalculate (r * r) for all the spheres with a different radius. So we get:

<code>

r2 = r * r

xd = (pointx - spherex)

yd = (pointy - spherey)

distance = xd * xd + yd * yd

IF distance < r2 THEN …

</code>

That is fully optimized point-sphere collision detection. On to the sphere-sphere collision detection. It’s almost the same as point-sphere collision detection.

Tip: I am teaching you how to do a collision detection for perfect round spheres, but this works for ellipses also. You just divide or multiply xd or yd by a number. You can set the x/y ratio also with the qb command CIRCLE.

Experiment a bit with it, this is handy when you have to corporate ellipses in your sprites.

Sphere-sphere collision

Sphere-sphere collision is in fact the same as a point-sphere collision. The only difference is that the distance between the centers of the spheres is compared with the sum of the radius of the two spheres. If you don’t understand, this picture will show you:

So, together with the optimizations from the point-sphere collision, that makes (I’ve token sphere A and sphere B):

<code>

r2A = rA * rA

r2B = rB * rB

xd = (sphereAx - sphereBx)

yd = (sphereAx - sphereBx)

IF xd * xd + yd * yd < r2A – r2B THEN ...

</code>

This is it. When you understand this, you can go on to the tricky square-sphere collision detection.

Square-sphere collision

Square-sphere collision is tricky because there can be two types of collision. The first is what I call a straight intersection, where the sphere ‘hits’ the square on a side. Then you have the ‘corner’ intersection, where the sphere hits a corner of the square.

To know for which type of collision we have to check, I first look where the center of the sphere is. This is a picture from the point-square check:

Consider the red area as the square. If the center of the sphere is in the red area, there has to be an collision. If the center is in the yellow area, we have to check for a straight intersection. If the center is in the white area, we check for a corner intersection. But before we check, we decide in which area the center of the sphere is.

I assume a sphere (spherex, spherey, radius) and a square(squarex1, squarey1)-(squarex2, squarey2).

For this I made a table. I assign 1 to a variable called xc if the center of the sphere is less then squarex1. If the center is between squarex1 and squarex2 I assign 2 to it, and else(it is more then squarex2) 3. For y-axis I do the same. Code:

<code>

IF spherex < squarex1 THEN

xc = 1

ELSEIF spherex < squarex2 THEN

xc = 2

ELSE

xc = 3

END IF

IF spherey < squarey1 THEN

yc = 1

ELSEIF spherey < squarey2 THEN

yc = 2

ELSE

yc = 3

END IF

</code>

Then we lookup what to do with this table:

A corner intersection check is just a normal point-sphere collision detection. As point you take the closest corner point and as sphere the sphere where you are doing the check on.

A straight intersection check is the ‘straight’ distance between the center and an edge.

(I referred to the edge as ‘axis’ in the table). A picture and some code for this:

<code>

distance = ABS(spherex – squarex1)

</code>

Note: when you use ellipses instead of circles, be sure that you divide or multiply the x/y coordinate here too.

The code for a square-sphere collision detection(after you assigned values for xc and yc):

(This code is only to show you how it should be used and interpreted: I wrote it down from my head, so there may be some bugs)

<code>

intersection = 0

IF xc = 1 THEN

IF yc = 1 THEN intersection = cornercheck(squarex1, squarey1, spherex, spherey, radius)

IF yc = 2 THEN intersection = straightcheck(squareyx1, spherex, radius)

IF yc = 3 THEN intersection = cornercheck(squarex1, squarey2, spherex, spherey, radius)

ELSEIF xc = 2 THEN

IF yc = 1 THEN intersection = straightcheck(spherey, squarey1, radius)

IF yc = 2 THEN intersection = 1

IF yc = 3 THEN intersection = straightcheck(spherey, squarey2, radius)

ELSE

IF yc = 1 THEN intersection = cornercheck(squarex2, squarey1, spherex, spherey, radius)

IF yc = 2 THEN straightcheck(squareyx2, spherex, radius)

IF yc = 3 THEN intersection = cornercheck(squarex2, squarey2, spherex, spherey, radius)

END IF

FUNCTION cornercheck(pointx, pointy, spherex, spherey, radius)

xd = (pointx - spherex)

yd = (pointy - spherey)

r2 = radius * radius

distance = (xd * xd + yd * yd)

IF distance <= r2 THEN cornercheck = 1 ELSE cornercheck = 0

END FUNCTION

FUNCTION straightcheck(edgec, spherec, radius)

straightdistance = ABS(spherec - edgec)

IF straightdistance => radius THEN straightcheck = 1 ELSE straightcheck = 0

END FUNCTION

</code>

Optimization trick:

When you have a TYPE specially for a circle, consider adding r2 to it: the square of the radius:

<code>

TYPE sphere

Centerx as integer

Centery as integer

Radius as integer

R2 as integer

End type

</code>

When you do this, r2 doesn’t have to be calculated during the collision detection.

### How to corporate spheres and squares into sprites

I first assumed that all the sprites you used are:

1. Just circles and squares drawed with qb’s line and circle or

2. Perfect round or square.

I thought that people may want other shapes as well :P. So here is a lil text for when you have a sprite that is not quite round or square but you don’t want to use per pixel checking.

Let’s start with this paddle, I made for possible use in a Pong-like game:

This is not a sphere, but neither a square. To still have a correct collision, we split it up into two spheres and one square:

I’ve got to tell you one thing on collision detection when you want to bounce a ball on some object. You might want to check every position of the ball where it current is, and when it has a collision, bounce it. This is wrong. What you need to do is bounce actually before there is an collision. So you need to check what the new position would be if there wouldn’t be a collision. If there is a collision at THAT place, then bounce. So actually the ball never has a collision because it bounces before it has a collision. This may sound stupid, but when you check after you updated the position, and there is a collision and you draw it, you draw the object over another(while it should bounce off it).

Here is another sprite:

We can split this shape up into this:

You see that it impossible to exactly fit the sprite in the spheres and squares without using a huge amount of squares/spheres. You can give it your best try, or you can use pixel perfect manner, which is a bit harder to use.

## Pixel perfect collision detection

Pixel perfect collision detection allows you to use complex sprites and still have precise collision detection. This manner is called ‘pixel perfect’ because you have to check for each pixel. This could make it slow, but when you optimize it well it will be worth it. There are two different manner that I’ll explain to you. The first is based on colour checking.

### Colour checking

I will directly introduce the downside of colour checking: you have to divide your palette in different ‘areas’. For example:

0-127 Background colours

127-150 Character colours

150-200 Bullets and booby traps colours

200-255 Object colours

When you draw everything to your buffer in a fixed sequence(background, powerups, enemies), you draw everything except the character. Instead of just drawing it, you check the colour of every pixel before you over paint it.

Then you lookup what to do with that colour. For instance (using the table above, of course you could make your own ;)), when a colour is 0-127 you don’t have to anything, because that are background colours. But, when a colour is from 150 to 200, you know that the hero is hit by a bullet or booby trap. This is the essence of the colour checking method. If you want, you could make a lookup table for every colour where is saved what to do with that single colour (subtract a life, game over, extra health, etc). This is the easy variant of pixel perfect collision detection.

### Array checking

Array checking is a good method when you want to use more colours in your sprite, instead of having a limited amount of colours that you can use for the background, your character, etc. Instead of painting except the hero, you paint the hero, and keep an array of points which will be checked for collision. Now when you paint the other sprites, you check if they are on any of the points in the array. This is all about array checking. It sounds simple, but it is actually a lot of work to code.

## Some notes on optimization

The pixel perfect manner is slow when you use the array checking method. To make it faster you do the ‘bounding box’ optimization like I told you above. Checking for one box is faster then to check for all pixels of the hero. This shouldn’t be done for each pixel of the sprite, so don’t use a point-square collision detection but a square-square collision detection. If there is a collision, then check for each pixel if it is one of the coordinates stored in the array.

A bounding box is also useful if you have a sprite that consists out of more then tree pieces(spheres or squares).

Also, you can get the whole thing faster, always use as much integers as possible for everything! When you’re getting overflow errors, try too use LONG type variables. This is very much faster then singles. Singles are only needed when you need much accuracy. Examples are ray tracers, fractals and sometimes for speeds(very slow rolling balls, less then one pixel per frame).

Well, this was all I know about collision detection. Succes with using it, and I hope this tutorial helped you. Else, mail me! For other tutorials, check out my website: http://members.lycos.nl/rubynl.

RubyNL

basicallybest@live.nl