# Build a collision algorithm

il y a 2 ans

Hi,
I'm currently working on a "kind-of-platformer-game". I'm quite a beginner with game programming, even more in C++, and I'm having a lot of troubles with conceiving  a working collision algorithm.

So what I'm asking here is not really a direct source code answer but more of an advice on how should I do to establish a clean and consistent algorithm. What kind of diagram should I draw to see clearly what I must see ? Is there a typical conventional pattern that I should apply to be able to work with gravity and collisions ?

I'm totally losing my brain here and the source codes I looked at from different games are too raw for me to understand the thinking behind it. I think what I miss is more of a conceptual knowledge...

Anyway I'm not even sure myself about what am I asking so I asume this is not a very clear question. But if anyone feels inspired to give a little advice on "how to conceive a gravity/collision pattern", I'll take anything, I'm a little desperate here... ^^ !

Thank you :) !!

NEW il y a 2 ans

Hi Codnpix!

Look at this diagram.... look at it well! Doesn't the solution immediately come to your mind?

You know the position of your player `(x,y)`....
You can determine the positions of all your platforms `(xp,yp)` if you have modeled your universe with a simple grid like this:

```0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1```

Conversely, you can deduce the indexes `(i,j)` of your grid from the coordinates `(x,y)`...

Should I continue or did the spark light up?....

Codnpix

il y a 2 ans

Thank you Steph !

This is kinf of what I am try to do basically, but I have problem when I reach the gravity question.

To get more concrete, my current algorithm goes that way :

My arduino loop () tells to a game controller to update the game

Gamecontroller::update :

- that gameupdate() checks the buttons inputs and those inputs tells to the character model to update some "movement requests values

-  then it tells the character to check collisions

Character::checkCollisions() :

- the character parses each tile of the space map, then the character cross the coordinates of each tiles with with his own coordinates, and determines if there is a collision and write updates some booleans like "onground", "collidesLeft" etc...

- then the character updates his position regarding the collisions constraints, so if "collides left is true he can go left, etc...

The the loop call a View::draw to display all of this on the right coordinates on the screen.

Mainly this seems to go fine, if I go right and if I collide with someting I stop, idem if I go left, if I jump I play a jump pattern, I go up then down and I stop when I reach the top of a solid tile.

BUT, if I am walking on a platform, and if and reach the edge of the platform, so I arrive on top of nothing, here I should naturally fall with the gravity value to the next ground below me. And here is the problem : the moment I walk out the platform is not marked by an event, so the change of state must be updated by the collision parsing : "I'm not colliding nothing, so I fall until I do again". But I never get to do that. I never get to update that can of "non-state" on a "non-event".

So currently I'm trying to looking for a solution into "define a character behavior when he colliding a void tile", but it seems a little convoluted. So I'l pretty sure I'm not on the right way here.

That's why I ask how should I model a real collision pattern... I understand the basic but I'm lost with the details (even if that's a pretty huge detail ^^).

NEW il y a 2 ans

Steph

Thank you Steph !

This is kinf of what I am try to do basically, but I have problem when I reach the gravity question.

To get more concrete, my current algorithm goes that way :

My arduino loop () tells to a game controller to update the game

Gamecontroller::update :

- that gameupdate() checks the buttons inputs and those inputs tells to the character model to update some "movement requests values

-  then it tells the character to check collisions

Character::checkCollisions() :

- the character parses each tile of the space map, then the character cross the coordinates of each tiles with with his own coordinates, and determines if there is a collision and write updates some booleans like "onground", "collidesLeft" etc...

- then the character updates his position regarding the collisions constraints, so if "collides left is true he can go left, etc...

The the loop call a View::draw to display all of this on the right coordinates on the screen.

Mainly this seems to go fine, if I go right and if I collide with someting I stop, idem if I go left, if I jump I play a jump pattern, I go up then down and I stop when I reach the top of a solid tile.

BUT, if I am walking on a platform, and if and reach the edge of the platform, so I arrive on top of nothing, here I should naturally fall with the gravity value to the next ground below me. And here is the problem : the moment I walk out the platform is not marked by an event, so the change of state must be updated by the collision parsing : "I'm not colliding nothing, so I fall until I do again". But I never get to do that. I never get to update that can of "non-state" on a "non-event".

So currently I'm trying to looking for a solution into "define a character behavior when he colliding a void tile", but it seems a little convoluted. So I'l pretty sure I'm not on the right way here.

That's why I ask how should I model a real collision pattern... I understand the basic but I'm lost with the details (even if that's a pretty huge detail ^^).

Steph

il y a 2 ans

Okay... ;-)

First of all, my diagram should have inspired you to optimize your collision test!..... Indeed, you do not need to perform the test with ALL the tiles in your universe!!!... The transposition of the player's coordinates `(x,y)` into the grid `(i,j)` immediately tells you which tiles you should take into account for your collision test: only look at the player's "neighbourhood" in the grid!

In addition, the problem of gravity must be addressed more generally by using Newton's 2nd Law, also known as the Fundamental Relation of Dynamics. I had covered this subject in my Shading Effect in High Resolution tutorial. In your case, what are the forces that apply?... 1. gravity, certainly!... but 2. the reaction force induced by the platform on which the player rests!.... So you have to take into account this second force in your equations of motion. Indeed, when the player is on a platform, the reaction applies and is perfectly opposed to gravity (which explains why the player does not fall while crossing the platform)... but when he is in the void (during a jump), this reaction force no longer applies! Only gravity persists.

Are you seeing more clearly now?

NEW il y a 2 ans

Codnpix

Okay... ;-)

First of all, my diagram should have inspired you to optimize your collision test!..... Indeed, you do not need to perform the test with ALL the tiles in your universe!!!... The transposition of the player's coordinates `(x,y)` into the grid `(i,j)` immediately tells you which tiles you should take into account for your collision test: only look at the player's "neighbourhood" in the grid!

In addition, the problem of gravity must be addressed more generally by using Newton's 2nd Law, also known as the Fundamental Relation of Dynamics. I had covered this subject in my Shading Effect in High Resolution tutorial. In your case, what are the forces that apply?... 1. gravity, certainly!... but 2. the reaction force induced by the platform on which the player rests!.... So you have to take into account this second force in your equations of motion. Indeed, when the player is on a platform, the reaction applies and is perfectly opposed to gravity (which explains why the player does not fall while crossing the platform)... but when he is in the void (during a jump), this reaction force no longer applies! Only gravity persists.

Are you seeing more clearly now?

Codnpix

il y a 2 ans

For the gravity question yes I'm doing something like what you said, the vy value of my character is equal to `GRAVITY - G_resistance`, and the G_resistance is the variable I modify if I'm jumping or if I reach a ground.

So what I first tried to do is set the reaction to `0` when `isOnGround` is not true, but it doesn't seems that simple because I need an event to update the change (it works fine if I jump from the platform for example, but not if I just walk out of it). I really don't understand what I'm missing...

And for the map parsing part ,I think I'm only testing the tiles that are in direct contact with the character but maybe I'm not doing it right because I iterate on the entire array, then I call actions only for tiles of a certain type and if the character is in contact with them, so maybe I sould directly parse only the tile around the character. Anyway I'm sure my problems come fom that part of the code. Maybe I need to wipe it and try to really build it differently.

In case you are interested you can have a look on my code here https://github.com/Codnpix/Glitch_META

But please do not waste too much time in this, I will end by figure it out :).

Thanks anyway !

NEW il y a 2 ans

Steph

For the gravity question yes I'm doing something like what you said, the vy value of my character is equal to `GRAVITY - G_resistance`, and the G_resistance is the variable I modify if I'm jumping or if I reach a ground.

So what I first tried to do is set the reaction to `0` when `isOnGround` is not true, but it doesn't seems that simple because I need an event to update the change (it works fine if I jump from the platform for example, but not if I just walk out of it). I really don't understand what I'm missing...

And for the map parsing part ,I think I'm only testing the tiles that are in direct contact with the character but maybe I'm not doing it right because I iterate on the entire array, then I call actions only for tiles of a certain type and if the character is in contact with them, so maybe I sould directly parse only the tile around the character. Anyway I'm sure my problems come fom that part of the code. Maybe I need to wipe it and try to really build it differently.

In case you are interested you can have a look on my code here https://github.com/Codnpix/Glitch_META

But please do not waste too much time in this, I will end by figure it out :).

Thanks anyway !

Steph

il y a 2 ans

but it doesn't seems that simple because I need an event to update the change

You don't need to detect a particular event for that.
The simple examination of the player's neighborhood tells you which tiles to look at:

```      i
-----
| 0 0 0
j | 0 P 0
| 1 1 1```

And this analysis is performed at each pass in the `loop()` function : -)

Steph

il y a 2 ans

I don't have time to look at your code right now, but I will do it as soon as possible... I'm about to finish a tutorial and I would really like to finish it now. But right after that, I'll look at your code and propose a solution.

But you already have all the keys in hand ;-)

By the way, I see you have now adopted the object approach and the MVC architecture. That is a very good thing.

NEW il y a 2 ans

Codnpix

but it doesn't seems that simple because I need an event to update the change

You don't need to detect a particular event for that.
The simple examination of the player's neighborhood tells you which tiles to look at:

```      i
-----
| 0 0 0
j | 0 P 0
| 1 1 1```

And this analysis is performed at each pass in the `loop()` function : -)

Codnpix

il y a 2 ans

I'm going to try to work on this. Thanks Steph !

NEW il y a 2 ans

Steph

I'm going to try to work on this. Thanks Steph !

NEW il y a 2 ans

Codnpix

I don't have time to look at your code right now, but I will do it as soon as possible... I'm about to finish a tutorial and I would really like to finish it now. But right after that, I'll look at your code and propose a solution.

But you already have all the keys in hand ;-)

By the way, I see you have now adopted the object approach and the MVC architecture. That is a very good thing.

NEW il y a 2 ans

I don't have time to look at your code right now, but I will do it as soon as possible... I'm about to finish a tutorial and I would really like to finish it now. But right after that, I'll look at your code and propose a solution.

Thank you very much :). But please do not lose time in solving this for me, I'm not looking for a ready-made solution but more of a real understanding of the way to build a game with a physical model.

Steph

il y a 2 ans

Don't worry, I don't feel like I'm wasting my time at all... otherwise I wouldn't even answer you ;-)

• On the one hand, I am happy to be able to provide help when I can...
• On the other hand, the issues raised by the community lead me to ask myself how to solve them.
• And finally, these kinds of (interesting) questions shed light on what I could develop in a tutorial to benefit the whole community.

NEW il y a 2 ans

Codnpix

Don't worry, I don't feel like I'm wasting my time at all... otherwise I wouldn't even answer you ;-)

• On the one hand, I am happy to be able to provide help when I can...
• On the other hand, the issues raised by the community lead me to ask myself how to solve them.
• And finally, these kinds of (interesting) questions shed light on what I could develop in a tutorial to benefit the whole community.

NEW il y a 2 ans

This is finally working !! =)

Indeed what unlocked me was to do the collision tests only on the few tiles around the character. So I created a little array for those tiles and then it is a lot easier to set the conditions of collision.

Everything works fine, I feel so much better :) ! Even knowing this is just a start and that I might have a lot of other questions later, this already great.

Thank you so much for your help Steph !

Steph

il y a 2 ans

Hello,

I'm glad you were able to unlock the situation on your own. Now you can move on. Sometimes, a small sketch scribbled on a notebook is enough to illuminate the evidence.

I'm just starting a new tutorial that should interest you... I'm not saying any more for the moment. But you will probably find new inspirations there ;-)

On that note, good night! It's late in Reunion Island... and I'm going to bed!

Steph

il y a 2 ans

Here, look at this!

You will soon be able to read my tutorial and examine in detail an optimization procedure for collision detection ;-)

Always keep in mind that, in an environment where resources are limited, such as the META, it is always important to save memory and computing time when possible...

NEW il y a 2 ans

Codnpix

Hello,

I'm glad you were able to unlock the situation on your own. Now you can move on. Sometimes, a small sketch scribbled on a notebook is enough to illuminate the evidence.

I'm just starting a new tutorial that should interest you... I'm not saying any more for the moment. But you will probably find new inspirations there ;-)

On that note, good night! It's late in Reunion Island... and I'm going to bed!

NEW il y a 2 ans

Codnpix

Here, look at this!

You will soon be able to read my tutorial and examine in detail an optimization procedure for collision detection ;-)

Always keep in mind that, in an environment where resources are limited, such as the META, it is always important to save memory and computing time when possible...

Codnpix

il y a 2 ans

You will soon be able to read my tutorial and examine in detail an optimization procedure for collision detection ;-)

I can't wait to read it :) !

NEW il y a 2 ans

Steph

You will soon be able to read my tutorial and examine in detail an optimization procedure for collision detection ;-)

I can't wait to read it :) !

Steph

il y a 2 ans

Soon... soon ;-)

And... now... when you have a problem on your apps, don't hesitate to use META Screen Recorder to show us in pictures what's wrong ;-)

It can also be used for that!

NEW il y a 2 ans

Steph, your example picture is amazing good. Very good idea. It's important. Making good codes are fine but having good ideas to explain it for tuto are more important for all who learn to code. This example is really so clear. Good job  ;)

NEW il y a 2 ans

Codnpix

Soon... soon ;-)

And... now... when you have a problem on your apps, don't hesitate to use META Screen Recorder to show us in pictures what's wrong ;-)

It can also be used for that!

Codnpix

il y a 2 ans

I've seen that, it's great. Thank you for your work !