Jump to content

View more

Image of the Day

Working on an auto spawn system. #gamedev #indiedev #screenshotsaturday https://t.co/Mm2kfekz7b
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Sign up now

collision detection

4: Adsense

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 Ahmad239   Members   


Posted 26 February 2014 - 11:26 AM


a few weeks ago i made a simple platformer level, the map is saved to a text file and loaded into a 2D array where i handled collision by comparing the position of the player to the 2D array to see if the slot he's in is occupied or not then adjust its position.


i wanted to add more to the level so i started using tiled map editor to build the map and adding some slopes, stairs, etc..,

in tiled collision is added by drawing shapes(rectangles, polygons, and lines), the problem is colliding with polygons and lines (slopes)

i tried searching for it and all i found was things about separation of axis or speculative contacts and other things which i find very advanced and confusing for my level.


so i wanted to ask if there was an easier way to this ? 


also should i handle all collisions in one separate class or i make every entity handle it's own collision ?

#2 Kaptein   Prime Members   


Posted 26 February 2014 - 11:51 AM

An easy way to simplify "complicated" collision is to create a function that only returns true if the internal coordinates passed to it are inside a function.


An example:

We've already discovered that the player was indeed touching the tiles T1, T2 and T3 since the player unfortunately has an area.

So, to simplify things we take the players extremities and calculate which tiles they are inside, and from there we calculate the fractions of the players position inside those tiles.

Fractions are 0.0 to 1.0 only, and that makes math really easy.

If the players left foot is 0.8 fractions inside a tile, our tileHitbox() function can use simple math to determine if that specific point is solid, or not.

bool tileHitbox(int tileID, float fx, float fy)
    // depending on the tile, the math functions are abit different
    switch (tileID)
    case T_AIR:
         return false; // air is never solid
    case T_SLOPE_UP_RIGHT:
         // the solid area only exists where fx < fy, a slope that goes up to the right (assuming +y is up)
         return (fx < fy);
    case T_SLOPE_UP_LEFT:
         // the solid area only exists where (1-fx) < fy, a slope that goes up to the left
         return ((1.f - fx) < fy);
         // in the default case, we just assume the entire tile is solid, for no particular reason
         return true;

So, doing it this way adds some complications to your physics department. But we can solve that, using divide and conquer:

You'll notice that if your player has a high speed downwards, you can hit tiles too early due to gravity, which makes him stop a little bit too far up -- preventing him from "landing" pixel-perfect against the tiles.

To fix that, we let there be a function gravity() which takes a parameter telling us just how much the player needs to go downwards at this particular time:


bool gravity(float x, float y, float rate_down);


Each time gravity fails to move (x, y) down by (rate_down), you should call gravity() again, but halve rate_down. You can stop trying after a given number of tries. 4 tries could be more than enough, since all that matters is that no one notices the difference.


float rate_total = rate_down;
int tries = 4;
while (tries-- && rate_total > 0)
     if (gravity(px, py, rate_down)
         // success, move point downwards
         py -= rate_down;
         // measuring how far we moved the point down prevents us from continuing
         // after we had in fact moved down all the way
         rate_total -= rate_down
     // we always halve the speed here, just in case the loop continues
     rate_down /= 2;

The example above is just written off the top of my head. I hope it's not entirely wrong.

Another thing you can do is to calculate the size of a pixel, and just move 1 pixel at a time continually until the gravity rate is travelled. That would probably me much simpler code.


If your rate_down is too big, you risk skipping tiles entirely. So make sure rate_down is not too big, and instead call gravity() more times with a lower number to make up.


Solving these problems with the force (not just gravity) movement rate will give you access to defining tile hitboxes with simple math. It is very cheap and simple programming to test against tiles this way, but not particularly efficient. What it does though, is make your life easy. And that counts more than anything to me.


EDIT: This is going to get slightly more complicated now, since you probably want to "automatically" walk up and down slopes, or on the top of a circle tile should you want to create one.

So, how do you automatically walk up a slope? Well, you can just define different rules for moving the player right/left, jumping and falling down.

For jumping you need to check if his head hit something hard.

For falling, you need to check his feet.

And for right/left you need to check his knees, or something even higher up, because that allows you to to move "into" a slope. Your unstuck mechanism should make sure your player stays on top of the terrain at all times, simply by always moving him up until he is no longer stuck.

The drawback here is that your movement upwards a slope will not be at the rate of the slope, but rather at the rate of moving directly right/left. It may be noticeable, and if you don't want it to be like that you could do some combination stations with moving right/left that penalizes the player if he is indeed moving upwards.

To do that, you need to check if the player can move right/left at his feet level first, and if he can't but he still can move if we measure at his knees, then penalize the movement rate a little to make up for the impending upwards movement.


So, how do you unstuck someone? Well the cheapest way is:

void unstuck(SomeGuy& guy)
   while (terrain.test(guy.footLeft()) || terrain.test(guy.footRight())) guy.move(0.0, 0.1); // move slightly upwards until no longer stuck

Or something in that fashion.

Edited by Kaptein, 26 February 2014 - 01:58 PM.

#3 Melkon   Members   


Posted 26 February 2014 - 02:34 PM



Here you can found ALOT of things about math in game game development.




There is one topic about collision detection too. ( Collision Detection (Gino van den Bergen) )

Edited by Melkon, 26 February 2014 - 02:35 PM.

#4 Ahmad239   Members   


Posted 02 March 2014 - 03:27 PM

@Kaptein that was an amazing explanation, thank you 


but my collision layer is made of rectangles to represent flat tiles and a triangle for every group of slope tiles

#5 Kaptein   Prime Members   


Posted 02 March 2014 - 04:29 PM

@Kaptein that was an amazing explanation, thank you 


but my collision layer is made of rectangles to represent flat tiles and a triangle for every group of slope tiles


Right, that is just better because it means you can just spam math functions on the map. All the same things still apply, because instead of tiles you just read collision types from your collision layer. Did I understand you right?

#6 Ahmad239   Members   


Posted 03 March 2014 - 06:53 AM



this is how it looks like

the rectangles and triangles is what i test collision against 

what i understood from your words that unlike using tiles to test collision i will use math instead of pixel position,

did i get it right ?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.