Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


AABB Collision Detection


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
10 replies to this topic

#1 Silgen   Members   -  Reputation: 178

Like
0Likes
Like

Posted 30 September 2012 - 03:29 PM

I have started working on a simple 2D tile based platformer (C++ & SFML), and I've made a reasonable start. At present, the character can walk around the map (loaded from a text file), jump and collide with solid tiles. The tiles are held in a two dimensional array, and accessed through a manager class, that can return pointers to individual tiles, render the tiles that are currently onscreen, and load a map from a text file.

Firstly, I was wondering if my method of collision detection was appropriate:

For each axis, I am moving the player according to its velocity, then checking if it collides with any solid tiles (Two tiles are checked per axis.) If a collision has occured, I move the player back by exactly the distance it has overstepped.

I feel that the code is a little heavy handed in places - e.g. passing the tile manager as an argument.

This is an example:

[source lang="cpp"]float cPlayer::collisionCheckX(cGraphicalObject A, cGraphicalObject B) { sf::FloatRect intersectionRect; if(A.returnBounds().intersects(B.returnBounds(), intersectionRect)) { return intersectionRect.width; } else { return 0; }}[/source]

[source lang="cpp"]void cPlayer::moveObject(cTileManager* TM) { getSprite()->move(_velocity.x, 0); if(_velocity.x > 0){ float a = collisionCheckX(*this, *TM->getTile((int)getPosition().y / 32, (int)getPosition().x / 32 + 1)); float b = collisionCheckX(*this, *TM->getTile((int)getPosition().y / 32 + 1, (int)getPosition().x / 32 + 1)); if( (a && TM->getTile((int)getPosition().y / 32, (int)getPosition().x / 32 + 1)->getSolidity() ) || ( b && TM->getTile((int)getPosition().y / 32 + 1, (int)getPosition().x / 32 + 1)->getSolidity() )) { //std::max is being used in case only one of the tiles is solid getSprite()->move(-std::max(a, b), 0); }}//...[/source]

Another issue that I need to resolve is animated sprites. Currently, I have the clipping of sprite sheets being handled by the movement functions in the player class (as a temporary measure) - could anyone reccomend a solid method of handling animations? I will need animations for most non-tile objects.

Edited by Silgen, 30 September 2012 - 03:32 PM.


Sponsor:

#2 thok   Members   -  Reputation: 693

Like
1Likes
Like

Posted 01 October 2012 - 07:56 AM

I have started working on a simple 2D tile based platformer (C++ & SFML), and I've made a reasonable start. At present, the character can walk around the map (loaded from a text file), jump and collide with solid tiles. The tiles are held in a two dimensional array, and accessed through a manager class, that can return pointers to individual tiles, render the tiles that are currently onscreen, and load a map from a text file.

Firstly, I was wondering if my method of collision detection was appropriate:

For each axis, I am moving the player according to its velocity, then checking if it collides with any solid tiles (Two tiles are checked per axis.) If a collision has occured, I move the player back by exactly the distance it has overstepped.

I feel that the code is a little heavy handed in places - e.g. passing the tile manager as an argument.

This is an example:

[source lang="cpp"]float cPlayer::collisionCheckX(cGraphicalObject A, cGraphicalObject B) { sf::FloatRect intersectionRect; if(A.returnBounds().intersects(B.returnBounds(), intersectionRect)) { return intersectionRect.width; } else { return 0; }}[/source]

[source lang="cpp"]void cPlayer::moveObject(cTileManager* TM) { getSprite()->move(_velocity.x, 0); if(_velocity.x > 0){ float a = collisionCheckX(*this, *TM->getTile((int)getPosition().y / 32, (int)getPosition().x / 32 + 1)); float b = collisionCheckX(*this, *TM->getTile((int)getPosition().y / 32 + 1, (int)getPosition().x / 32 + 1)); if( (a && TM->getTile((int)getPosition().y / 32, (int)getPosition().x / 32 + 1)->getSolidity() ) || ( b && TM->getTile((int)getPosition().y / 32 + 1, (int)getPosition().x / 32 + 1)->getSolidity() )) { //std::max is being used in case only one of the tiles is solid getSprite()->move(-std::max(a, b), 0); }}//...[/source]

Another issue that I need to resolve is animated sprites. Currently, I have the clipping of sprite sheets being handled by the movement functions in the player class (as a temporary measure) - could anyone reccomend a solid method of handling animations? I will need animations for most non-tile objects.


I can't answer your question about the animation, because this is something that I have yet to tackle my platformer project. But maybe I can help with the collision detection.

It seems fine to pass in the cTileManager; using dependency injection in this way should make things easy to mock and test. The alternative would be to just pass in the 2D array of your tiles, instead of the entire tile manager. But it probably doesn't matter for now.

From your post, I didn't really see any question about AABB collision, except for the worry about heavy-handedness, so you still have questions about the collision bit, please clarify. For reference, here is how I implemented AABB collision detection/response in my project. (It's Java, not C++, but maybe you'll find something useful in here.)

Collision.java - Contains utils for tracing the path an entity has taken during a given update (on both the X and Y axes), as well methods for calculating the correction delta when a collision/intersection occurs. It also covers the case where an entity is moving _so_ fast during a given update that it passes completely through a tile. Check it out: https://github.com/larsbutler/gamedemo/blob/opengl/src/com/larsbutler/gamedemo/math/Collision.java

These are used in the move() method, which is responsible for moving entities for the given tick and checking for/responding to collisions: https://github.com/larsbutler/gamedemo/blob/opengl/src/com/larsbutler/gamedemo/core/GameState.java#L94

Disclaimer: This code may be rather rough and inefficient (especially with a large number of tiles), but it works fine for small cases and it's reasonable well tested: https://github.com/larsbutler/gamedemo/blob/opengl/tests/com/larsbutler/gamedemo/math/CollisionTest.java

#3 Silgen   Members   -  Reputation: 178

Like
0Likes
Like

Posted 01 October 2012 - 11:45 AM

Thanks for your reply thok.

After looking at your code (which was really helpful, thankyou) I think that I would benefit from making my code more general.

For various reasons, I need to hold tiles, objects and enemies in seperate managers - but what if I had a manager for all physical objects (that contained pointers to said objects) - did a quick broad phase test, then proceeded to run a more fine grain AABB check?

#4 thok   Members   -  Reputation: 693

Like
1Likes
Like

Posted 01 October 2012 - 01:23 PM

For various reasons, I need to hold tiles, objects and enemies in seperate managers - but what if I had a manager for all physical objects (that contained pointers to said objects) - did a quick broad phase test, then proceeded to run a more fine grain AABB check?


Sure, sounds reasonable. That's pretty much I'm doing with the GameState class, except there's no broad phase collision testing yet, and I don't plan to add it until I start seeing performance issues with many many many objects in play.

I say, stick with one manager. It would probably make sense to keep different kinds things (tiles, enemies, etc.) in separate lists/arrays, but this is kind of a trivial detail. Let the manager handle it's own internal state. Just do whatever works and keep it simple.

#5 Matt-D   Crossbones+   -  Reputation: 1467

Like
1Likes
Like

Posted 02 October 2012 - 09:40 AM

The tiles are held in a two dimensional array, and accessed through a manager class, that can return pointers to individual tiles, render the tiles that are currently onscreen, and load a map from a text file.


Just a quick note -- consider whether the above-mentioned class doesn't do too much?
Some context:
http://c2.com/cgi/wi...erHandlerOrData
http://c2.com/cgi/wiki?GodClass
http://wiki3.cosc.ca...oid_god_classes
http://en.wikipedia....wiki/God_object
Refactoring it into simpler, single-responsibility classes might be one way to go.

Two guidelines from the above I'd keep in mind:
1. "Don't use the nouns "Object", "Manager", "Handler", or "Data" in class names. These words say nothing about the responsibility of the class, leading maintenance programmers to lump all kinds of irrelevant crap into the class. Think instead about what the class is actually supposed to do and name it after that."
2. "Let's put this constructively. Name your classes anything you want. Then delete words that don't add any meaning. Examples of words that are unlikely to add meaning are Object, Manager, Handler, Data, Entity, Component, Element, Item, and Thing. If deleting a nothing word would result in a clash (Drawing and DrawingObject?), find a SystemOfNames that helps you resolve the conflict (Drawing and Figure)."

Another way is to have a family of free functions, with each performing the respective operation (C++ is multiparadigmatic for a reason -- and if you have multiple-responsibility "Object", "Manager", "Handler", or "Data" class, chances are this might be a better design anyway):
http://steve-yegge.b...m-of-nouns.html
http://zaemis.blogsp...g-with-oop.html

This may or may not be the case in your project, depending on the details such as the way you need to inter-operate with the other components, but names like "manager" often (although not always, it's not exactly a black vs white thing) suggest a possible violation of the single responsibility principle (again, you still might have a good case to do that, and if you know what and why you're doing then it might be fine -- just make sure you do).

Edited by Matt-D, 02 October 2012 - 03:37 PM.


#6 slicksk8te   Members   -  Reputation: 191

Like
1Likes
Like

Posted 02 October 2012 - 10:16 AM

Managers in my opinion are fine but if you have a manager for everything then it is really easy to get in trouble. For example if you have a manager for enemies, tiles, players, platforms, items, etc. then your code would get very complicated very quickly (i.e. game object that belong in two managers, how to iterate through all collisions efficiently,etc.). I would suggest having only a couple of managers such as sprites and maybe tiles. It is important to group as many objects as possible into as few managers as possible.

I feel that the code is a little heavy handed in places - e.g. passing the tile manager as an argument.


The code that you presented is not that heavy handed except that you need to be careful passing by value rather than passing by reference. For instance, passing the tile manager here:

void cPlayer::moveObject(cTileManager* TM)


is ok because it is a pass by reference, but here:

float cPlayer::collisionCheckX(cGraphicalObject A, cGraphicalObject B)


it may hurt you because you are passing by value.
Another option is to let the manager deal with the collision code and report it to the object through a callback or message and the object can choose to act or not. This makes it so that the objects do not have to know about any managers and only have to implement a couple of callback functions like TileCollision or SpriteCollision.

Also, checking for just a set number of tiles, 2 in your case, can cause problems with objects moving through tiles. For instance if the speed of your object causes it to move more than 2 tiles, the object would pass right through the tile. The solution to this is to get all tiles that the object moves through and checking from closest to farthest if there are any collisions.

Hope this helps

#7 Silgen   Members   -  Reputation: 178

Like
0Likes
Like

Posted 02 October 2012 - 01:58 PM

Thanks for all of the replies so far.

After reading the posts, I think it would be wise to spend a little bit of time refactoring my code, but in order to do this most effectively I need to know how I will ultimately handle collisions.

It seems fairly straightforward if there is only one moving solid object (the player):
1. Produce bounding box for the path taken (seperately for x and y)
2. Obtain intersected tile indexes, and request those tiles be added to a vector of objects that have to be checked for collision with the player (which would include any other solid object on the screen currently.)
3. Look through the vector of objects, checking for intersections on the x axis, and returning the distance overlapped - updating this value with the current highest value.
4. Move the player back by this maximum penetration value (and repeat 2->4 for y)

Does the above seem reasonable?

What I am unsure of, is how this could be best made to working with moving solid objects (other than the player.)

#8 slicksk8te   Members   -  Reputation: 191

Like
1Likes
Like

Posted 02 October 2012 - 02:54 PM

What I am unsure of, is how this could be best made to working with moving solid objects (other than the player.)


This is a big issue in games and there are many ways to solve this based on how accurate you want it to be. I would suggest checking out this article first.

#9 Silgen   Members   -  Reputation: 178

Like
0Likes
Like

Posted 02 October 2012 - 03:14 PM

That is an excellent resource, thankyou. The only solid moving objects I am likely to want are moving platforms, and possibly pushable blocks - so that article clears that up quite nicely. Does seem like it would be a lot harder to deal with multiple moving (solid) objects.

As for dealing with checking if the player collides with an enemy (not solid), for example - is that just a matter of creating the path boxes for both, and checking for an intersection?

#10 slicksk8te   Members   -  Reputation: 191

Like
0Likes
Like

Posted 02 October 2012 - 03:39 PM

The short answer is yes but there are many different ways to solve for this and some can get very complicated.

In most cases it is be best to keep the collision detection system as simple as possible. Usually this involves just a check for if two rectangles overlap.
This breaks when you have fast objects going through thin objects. This is called "tunneling" and can be really hard to stop. Most games avoid this by not having really fast objects colliding with thin objects.

If you are ambitious about collision detection however, you can try to use more advanced techniques shown here. But this increases development time and takes a while to understand completely.

What I would suggest is keep it simple and only do what your game requires.

#11 thok   Members   -  Reputation: 693

Like
0Likes
Like

Posted 02 October 2012 - 04:25 PM

This breaks when you have fast objects going through thin objects. This is called "tunneling" and can be really hard to stop. Most games avoid this by not having really fast objects colliding with thin objects.


The collision code I linked above should solve this problem, at least for simple AABB collision. In my case, it wasn't actually that difficult. All I have to do is keep track of the previous state; then, when I got to do physics updates and check collisions, I do it one axis at a time.

So for each axis, I do physics updates, then I create a rectangle representing the path that the entity (or the entity's bounding box) took between the previous update and the last update. The I check if _that_ rectangle intersects with anything. If so, I make a correction based on the direction the entity was moving (determined by the current velocity on that axis).




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.



PARTNERS