Math Collision & Tricks

---By Emperor-Baal---

For DarkBASIC (classic) users

Introduction

If you need perfect collision than you probably won't want to read this. This tutorial will only show you how to code FAST good collision. These examples are not perfect, that's why collision is sometimes detected well you are touching nothing. You can prevent that by using multiple and different collision checks. This tutorial will NOT show you how to detect collision for each polygon in your program, it will show you how to detect collision using formulas. 

In this tutorial, I will use a basic FPS game as example. I will tell you about:

• the Basics of the 3D space/grid

• the basics of movement

• box collision

• sphere collision

• rooms 

• stairs/slopes

• character collision

• multiple floors

• height# variable

• gravity

• jumping

 

Note: Most of the examples are using darkbasic commands. You can replace them when you use a different language, because the math-calculations remain the same. Copy and pasting these examples sometimes result errors, because my editor (frontpage) is putting invisible characters in them and that's why you should type them over instead of copy-pasting them. These examples are all tested in DarkBASIC classic 1.13 and are proven error-free. You may use different variable names than the ones I use.

 

Before you jump in, it's a good idea to take a look at beginner tutorials (like monster hunt 3D) to learn how to write a simple 3D program and how to make a cube move around a matrix. Because I am not gonna explain rotations and how variables / if-statements / functions / and all other things work.

Basics

Before I will show you how to detect collision, you will first have to learn the basics of a 3D space (using math). This is neccesary for detecting collision. You can skip this part of the tutorial if you are familiar with 3D spaces and movement using math.

You can compare the 3D space with a 3D grid (with a X-axis Y-axis and Z-axis):

• The green arrow is the Y-axis (height)

• The red arrow is the X-axis (width)

• The blue arrow is the Z-axis (depth)

 

 

As you can see, I've made a cube in anim8or (a free 3D modelling program, www.anim8or.com) and placed it on the ground (bottom hits Y-0)

The cube has 8 points, here you can see their coordinates:

The cube's center is X0,Y1,Z0. When I pressed on the "place on ground" command in anim8or, it positioned the box at Y(0 + ( object height / 2 ) ) while leaving X and Z alone.

Why am I telling you this? Because it's useful too know when you want to place an object on a matrix or terrain.

Position object number, object position x(number),get ground height(matrix_number,object position x(number),object position z(number))+(object size y(number)/2),object position z(number)

This will put object number on the ground, just like the cube. This code requires a matrix, but that's not neccesary when using a height variable. I explain that later on.

 

 

 

What if we want to move the same cube to X0,Y1,Z2.5? Then we need the SIN and COS command and the objects Y angle. The cube is not rotated, so it's angles are X0^o,Y0^o,Z0^o

Here's its old (black) and new (yellow) position:

Here is a picture of the outputs when using SIN and COS:

So we have the angle, the sin command and the cube's current position. It's Y angle is 0^o. So how are we going to move the cube?

With the COS command.  New position = Old position + cos(object angle y()) * movement_speed.

Don't worry, I will explain it:

New Position = Old position + cos(object angle y()) * movement_speed New Position = 0                   + cos(0)                        * 2.5 New Position = 0                   + 1                                * 2.5 New Position = 2.5

And it will look like this in DarkBASIC:

position object number,object position x(number),object position y(number),object position z(number) + cos(object angle y(number)) * 2.5

 

 

The smart guys will probably notice that this is useful for movement in your game. We need to place the object on the X-axis as well. We cannot use the COS because it would return the wrong values! But we can use the SIN command to move it on the X-axis. Using this modified code, we can move an object quite easily:

position object number,object position x(number) + sin(object angle y(number)) * 2.5, object position y(number),object position z(number) + cos(object angle y(number)) * 2.5

 

 

When we Y-rotate the cube in DarkBASIC, we are able to move it in all directions without any kind of problems. Because we are using a FPS game as example, we don't need to move it on the Y-axis, because gravity will handle that.

Here's your code for movement:

if leftkey()=1 then yrotate object number,wrapvalue(object angle y(number)-1.0) if rightkey()=1 then yrotate object number,wrapvalue(object angle y(number)+1.0) if upkey()=1 then position object number,object position x(number) + sin(object angle y(number)) * 2.5, object position y(number),object position z(number) + cos(object angle y(number)) * 2.5

 

Collision Basics:

Collision is everywhere (try walking trough a wall for example). It's part of our life and our games. In this chapter I will show you how to properly use math collision. If you are doing it wrong then collision can be detected while your object isn't touching anything! The proper way (resulting in smooth&sliding collision) is checking for collision in this order:

• Move the object on the X-axis

• Check for collision, put it back at it's original position when it's hitting something

• Move the object on the Z-axis

• Check for collision, put it back if necessary.

• Move the object on the Y-axis

• Check for collision, put it back if necessary.

El-Cheapo collision (a.k.a. Box Collision):

In our FPS game, we have a cube that's being controlled by the player and a wall that supposed to stop the cube when the cube is too close. We need Box Collision for this. First we will write a function that accepts the cube's number + wall's number and returns a 1 when collision is taking place.

  Before I will explain what the code does above, take a look at the scene and maybe you can discover what it does yourself:

 Here are some clues:

• The wall is 10X,5Y,1Z

• The center of the wall is X0,Y2.5,Z5.5

 

 

 

If the cube's center is inside the "box" then the function will return 1. Here's a example how we could use it in darkBASIC:

The example doesn't need to be explained. If you wonder why I check for collision TWICE than think of what will happen in this situation:

      [WALL]   [WALL]   [WALL]

               [object]        [WALL]

The object is in a corner and there's still room to move on the X-axis on the right. When I check for collision after position the object on the X-axis and Z-axis without a check between the movement, he will be positioned back at his original position (but that's not what we want!).

When I check for collision after position the object on the X-axis first, there's no collision detected. So he will move to the right.

Sphere Collision (a.k.a Dinstance Check)

Okay, take a look at this scene:

Our cube will never be able to move when we use a box collision check. We will need a more challenging approach to this one. We will need a distance check.

So, how do we figure out the distance between the cube's center and ball's center? We will have to use Pythagora's Theorem.

C = SQRT( A² + B² )

In this picture, the cube is at X0,Y1,Z0 and the ball is at X1.7,Y1.05,Z1.8

A = X_cube - X_ball

B = Z_cube - Z_ball

C = SQRT(A² + B² )

 

A = -1.7

B = -1.8

C = SQRT( 2.89 + 3.24)

C = 2.47

 

You will see that this Pythagora's Theorem only works with 2D (height doesnt matter). If you need 3D distance then we need to modify the formula a bit (in DarkBASIC style):

Distance# = SQRT(  (object position x(number)-object position x(ball))^2 + (object position y(number)-object position y(ball))^2 + (object position z(number)-object position z(ball))^2)

 

 

Now you only have to check if the distance between the cube and the ball is smaller than a given number.

That's all. If the cube gets closer than 2.5, it will be repositioned. So how do you check collision for a whole scene? Easy, use for-loops.

In this example we will use these object numbers:

• 1 = cube

• 10 - 50 = are crates

• 100 - 150 = are balls/spheres/bullets/whatever

This will check for collision for all objects. You can change the distance ( < 2.5 ) if you want. A good way is to check for < object size x(a) as this will check for the size of the sphere instead of a fixed number.

 

Now I covered the basic math collision. You can try these methods with this little code:

Rooms

Now you've learned how to code collision for boxes (crates / walls / pillars / etc) and round objects (spheres / balls / etc), but what if you want an indoor scene?

Our FPS is indoors aswell. Here's a little scene I made:

A room with a pillar. The easiest room to code collision for. For the scene we need to check for collision 4 times using box collision.

 

 

We will use a modified box_collision function, because I've made this scene in anim8or. That means that the whole room counts as 1 object and size x, size y, size z will return wrong values.

 

 

Let's start coding collision for the wall I made a little brighter:

Each tile on the floor is 1X and 1Z big. The grid coordinates start at X0,Y0,Z0 at the left-bottom of the floor. For this wall we should use this code:

Wall_Collision(number, -0.5, 0.0, -0.5, 0.5, 5.0, 9.5)

Take a look at these coordinates and look at the function, we've just replaced the box_collision with a more flexible one:

 

That wasn't difficult was it? Here's the code for all walls:

Wall_Collision(number, -0.5, 0.0, 8.5, 9.5, 5, 9.5)

Wall_Collision(number, 8.5, 0.0, -0.5, 9.5, 5, 9.5)

As you can see, the walls are 10X, 5Y, 1Z big. What about the pillar? Easy:

Wall_Collision(number, 4.0, 0.0, 4.0, 5.0, 5.0, 5.0)

 

 

If you combine the Wall_Collision with the movement code above we are done. The cube cannot walk trough the walls and pillar. There is one problem though, coordinates.

 

 

 

 

How to get the right coordinates

Note: You will need this file: scene.zip or you will need to skip this chapter. Unzip this file with winzip in the same directory where you will put the example.

If we have made a room by just throwing in walls, floors, doors, pillars, etc. using a 3D modelling program then the coordinates will not be the same in DarkBASIC. There's a easy way to get the right ones using free flight. You must write a little program that loads your scene and where free flight is possible. You move the camera instead of a cube and can rotate the camera using the mouse:

xrotate camera wrapvalue(camera angle x() + mousemovey())

yrotate camera wrapvalue(camera angle y() + mousemovex())

When we press the upkey the camera will move:

if upkey()=1 then move camera 1.0

And we need to know the right coordinates:

text 5,5,str$(camera position x())

text 5,20,str$(camera position y())

text 5,35,str$(camera position z())

 

Take a look at this scene again:

I know those coordinates are not the same in DarkBASIC, so we are gonna discover them ourselves. Do you see the corner where I wrote "X-1.05,Y0,Z-0.5"? Fly towards it with the camera. When reach it, write down the numbers at the top our screen. We now have 3 right coordinates.

Now fly at the corner where I wrote "X0.5,Y5,Z9.5" and write down the numbers again.

If you are flying to fast you can always lower the movement speed (if upkey()=1 then move camera 0.5)

Here's the free flight code:

Doors and openings

We will need multiple multiple box_collision tests if we want collision for a scene like this:

We would need 7 checks for this scene:

Every color is one box that has to be coded by you. Now you know why people are too lazy to use math collision, because it's time-consuming.

 

 

 

 

Slopes and Stairs

So you want a stair in your game. No problem, but it's not the easiest thing to code.

Take a look at this scene:

Here are some coordinates that we need:

Before we will continue, we will need a "height#" variable. This variable will hold the height of the floor, so that we can position the player or camera at the right height.

In this case, the height# is 0. Now how are we going to calculate the camera's new height on the stair? We are going to use the position check method:

First we will need to check if the player is in the "box" of the stair:

Wall_Collision(number, 0.0, 0.0, 1.0, 4.0, 2.0, 4.0)

The function will return a 1 when the camera is in the "box". When it's 1 we will use a method to calculate the new Y position:

New Height = Height# + ( Height of the stairs - (camera position x() * ( height of the stairs / length of the stairs ) ) )

 

In DarkBasic it would look like this

if Wall_Collision(number, 0.0, 0.0, 1.0, 4.0, 2.0, 4.0) = 1 then position camera camera position x(), height# + ( 2.0 - ( camera position x() * ( 2.0 / 4.0 ) ) ) ), camera position z()

These codes will only work when the stair's height changes on the X-axis and the stair starts at X0 and ends at X4. 

 

 

 

It's really easy to alter these codes, take a look at these scene:

Here are the coordinates:

Okay, the stair's height changes on the Z-axis and starts at Z20, instead of Z0. The coordinates above shows us that the lowest point is X31/X32,Y0,Z20 and the heighest is X31/X32,Y0,Z23. This is quite easy to code. First of all, the box_collision check.

Wall_Collision(number,31.0,0.0,20.0,32.0,2.0,23.0)

 

And we will need the height code

New Height = Height# + ( (camera position z() - z_beginning_coordinate) * (height of stairs / length of stairs) ) 

We need to substract the z_beginning_coordinate from the camera position z(), because the stairs doesn't start at Z0. It will look like this in DarkBASIC:

if Wall_Collision(number,31.0,0.0,20.0,32.0,2.0,23.0) = 1 then position camera camera position x(), height# + ((camera position z() - 20.0) * (2.0 / 3.0))

It's critical that we substract the z_beginning_coordinate from the camera position z(). Or this could be the result:

• Camera position z() = 22.0
• New Height would be: 0.0 + ( 22.0 * (2.0 / 3.0) ). And that will result in: 14.666, which is not correct. 

The correct value should be:

• Camera position z() = 22.0
• New Height: 0.0 + ( ( 22.0 - 20.0 ) * ( 2.0 / 3.0 ) ). Result is 1.33333, which is correct.

That was easy, wasn't it?

 

Now what would we do if I X-mirrored the stairs? That means the highest point would be X31/X32,Y2,Z20 and the lowest would be X31/X32,Y0,Z23. Then we only need to do some adjustments to the code:

New Height = Height# + height of stairs - ((camera position z() - z_end_coordinate) * (height of stairs / length of stairs) )

The z_end_coordinate would be Z20, because that's the coordinate where the "height changing" stops.

• Camera position z() = 21
• New Height: 0.0 + 2.0 - (( 21.0 - 20.0) * (2.0 / 3.0). Result is 1.33333, which is correct.

I will explain how to code rotated stairs later. Now it's time for the next chapter. Everything you read now about stairs are the basics to know when we are going to work with the Height# variable.

Character Collision (a.k.a Ellipsoid Collision)

This is probably one of the easiest to code. If you know how to do Sphere Collision then you will be able to do Ellipsoid Collision. Take a look at this character:

Isn't he a beauty? And sphere collision won't help him, take a look (When a object is inside the ball, collision is taking place):

That's why ellipsoid collision is invented, take a look at this new method:

 

We will only need to make a tiny adjustment to the sphere collision method.

sqrt( (object position x(number) - object position x(character)^2 + ((object position y(number) - object position y(character)) / scale#)^2 + (object position z(number) - object position z(character))^2) < distance

You will need to replace scale# by a number. In the example below, i've replaced it with 3.0. The bigger the number, the higher the ellipsoid will be.

 

sync on sync rate 0 make object sphere 1, 10.0 position object 1, 0.0, 0.0, 0.0 scale object 1, 100.0, 400.0, 100.0 for a=2 to 175 make object cube a, 2.0 position object a, rnd(400)-200,rnd(400)-200,rnd(400)-200 point object a, 0.0, 0.0, 0.0 next a position camera 0.0, 0.0, -45.0 point camera 0.0, 0.0, 0.0 randomize timer() do for a=2 to 175 if sqrt( (object position x(a))^2 + (object position y(a) / 3.0)^2 + (object position z(a))^2) > 7.5 then move object a, 1.0 next a sync loop

 

 

Multiple floors using the height variable

Now it's time to learn what the height variable is. The height variable holds the height of the floor. We need this variable when we want to use stairs and slopes.

Take a look at this scene:

3 floors and 2 stairs. We will need 3 different values for the height# variable if we want to code this. Here are the coordinates:

 

 

The three height# values would be:

• 0.0 (+ stair height)

 

• 2.0 (+ stair height)

 

• 4.0

 

We will have to use box_collision to see if the camera is inside the "box", if it's inside then we only change the height#. In this case we would need 5 box_collision checks.

• The first floor, change value to 0.0
• First stair, change value to "depends"
• Second floor (between the two stairs), change value to 2.0
• Second stair, change value to "depends"
• Third floor, change value to 4.0

Let's start coding the box_collisions, here are the coordinates and a reference picture:

 

if wall_collision(number, 0.0, 0.0, 0.0, 5.0, 3.9, 5.0) = 1 then height# = 0.0

if wall_collision(number, 5.1, 0.0, 0.0, 8.0, 3.9, 2.5) = 1 then height# = (camera position x() - 5.0) * (2.0 / 3.0)

if wall_collision(number, 8.1, 2.0, 0.0, 10.0, 6.0, 5.0) = 1 then height# = 2.0

if wall_collision(number, 5.1, 2.0, 2.5, 8.0, 6.0, 5.0) = 1 then height# = 2.0 + (2.0 - ( camera position x() - 5.0) * (2.0 / 3.0) )

if wall_collision(number, 0.0, 4.0, 0.0, 5.0, 8.0, 5.0) = 1 then height# = 4.0

Simple, now we only have to check for collision in this order:

• Move the object on the X-axis.

• Check for collision, put it back at it's original position when it's hitting something.

• Move the object on the Z-axis.

• Check for collision, put it back if necessary.

• Check for box_collision, modify the height# variable value if necessary.

• Put the camera on the height value.

 

Isn't this simple? Now it's time for the next chapter, gravity & jumping:

 

 

 

Gravity and Jumping

Gravity and jumping is easy. First I will tell you about gravity: 

if camera position y() > height# then position camera camera position x(),camera position y()-1.0,camera position z()

You can replace "camera" by "object". If you placed several wall_collisions for the height# variable it will work flawlessly.

 

 

Jumping is a bit harder and you would need to change gravity code a bit.

First we would need a two variables. Player_Jumps , Player_Jump_Angle and Player_Jump_Height#. You don't have to use the same names though. We will use SIN to calculate the jumping. In our FPS game we will use the spacekey for jumping:

if spacekey()=1 and Player_Jumps = 0  Player_Jumps = 1 : Player_Jump_Angle = 0 : Player_Jump_Height# = height# endif   If Player_Jumps =1  inc Player_Jump_Angle position camera camera position x(),Player_Jump_Height# + sin(Player_Jump_Angle) * 1.0, camera position z()  If camera position y() <= height#  or  Player_Jump_Angle > 90 then Player_Jumps = 0 endif

When the player presses space the variable Player_Jumps is set to 1. When it's 1 the player would be positioned above the ground using SIN. Everytime darkBASIC enters the if player_jumps = 1 statement, the angle is increased thus positioning the camera/object higher or lower.

You can increase or decrease the height of the SIN curve (thus allowing the player to jump higher or lower) by changing * 1.0.

Take a look at the SIN curve again:

 

And this is what happens:

 

Now we still have to adjust the gravity code:

if camera position y() > height# and Player_Jumps = 0 then position camera camera position x(),camera position y()-1.0,camera position z()

if camera position y() < height# and Player_Jumps = 0 then position camera camera position x(),height#,camera position z()

Now the gravity would only pull down the object when it's not jumping and this code also prevent the camera being positioned below the ground.

That was all, If you understand everything then you can start coding collision.

 I hope this tutorial was helpful. If you encounter any errors or if you have suggestions contact me:

geile_teddybeer@msn.com

Please include "-Math" in the subject line.

 

---The End---