What collision detection to use for a 2d mario brothers esk game?
Author
I know there has to be a better way to do this. In my game it is very important to not only tell when a collision occurs, but what wall it happens on. Ex, stopping on an enemy kills it where were running into it kills you. Right now, I have every wall (top, bottom, right, left) coordinate in an array, and I take mario's x/y from the last frame and mario's new x/y then if then compare all the walls in the area to see if they fall inbetween. If a wall is between the old x/y and the new x/y then there was a collision, and I do the correct event for that type of wall.
This seems very basic. I would like to rewrite my whole collision detection function and use something that is a little more advanced and efficient. Any ideas on which method I should use?
Each object is only one square box. All I need to know is if they collide, and which wall they collide on.
[Edited by - hoihoi8 on January 20, 2006 12:59:46 AM]
Are you planning on strictly square levels (Mario 1 & 2)? Or are you planning on implimenting slopes like Mario 3?
Essentially collision detection for the first two is painfully easy. For terrain, you can either denote a tile as solid, non-solid, dangerous, etc. If the player gets within range of this (touching it from some direction) it acts accordingly, based on where it hit (ie, jumping into a solid block knocks you down, etc, while jumping ON a solid block stops you from falling). You could also split each tile into a 4 or so quadrants, so you could have slightly better resolution in terms of "odd" looking shapes.
For enemeies, it's pretty much a position thing. If you run into a turtle from the side (ie, your y coordinates are relatively the same) - it counts as a hit against you. But if your x coordinate is relatively the same as the turtles' position, and your y coordinate is above the turtle, it counts as a hit against the turtle.
These types of collision are painfully easy, it's slopes and more advanced collisions that really try to tear into you.
I'm slightly tired, so if my explination sounds weird, it would be because of sleep deprevation :) If you don't understand, I'll explain better tomorrow sometime.
Essentially collision detection for the first two is painfully easy. For terrain, you can either denote a tile as solid, non-solid, dangerous, etc. If the player gets within range of this (touching it from some direction) it acts accordingly, based on where it hit (ie, jumping into a solid block knocks you down, etc, while jumping ON a solid block stops you from falling). You could also split each tile into a 4 or so quadrants, so you could have slightly better resolution in terms of "odd" looking shapes.
For enemeies, it's pretty much a position thing. If you run into a turtle from the side (ie, your y coordinates are relatively the same) - it counts as a hit against you. But if your x coordinate is relatively the same as the turtles' position, and your y coordinate is above the turtle, it counts as a hit against the turtle.
These types of collision are painfully easy, it's slopes and more advanced collisions that really try to tear into you.
I'm slightly tired, so if my explination sounds weird, it would be because of sleep deprevation :) If you don't understand, I'll explain better tomorrow sometime.
I would say that when the collision occurs, compare their positions like this:
If the slope is greater than (or equal to) one, then it's obviously a steep collision, therefore a stomp. If Gy<My then the Goomba is getting stomped.
If the slope is greater than or equal to 0 but less than 1, then it's a flat collision, and therefore lights out for Mario.
Mx,My Mario's x,yGx,Gy Goomba's x,yslope = abs((Gy-My)/(Gx-Mx));if ((Gx == Mx)|| ((slope >= 1)&&(Gy<My))) mario_wins();else mario_dies();If the slope is greater than (or equal to) one, then it's obviously a steep collision, therefore a stomp. If Gy<My then the Goomba is getting stomped.
If the slope is greater than or equal to 0 but less than 1, then it's a flat collision, and therefore lights out for Mario.
Author
Hi guys, thanks for the responses. My collision detection is already spot on perfect in terms of functionality with projectile, tiles and enemies. It's correct down the the pixel. It's just done in a really ineffient and rudimentory way with a zillion compares between each wall of mario and each wall of every tile and enemy. I don't want to do any guestimations with enemies, since I want to use the same collision algorithm for both the enemies and the tiles/walls/floors.
Flimflam - I am planning on making slopes. I might fudge it a little though, but haven't implemented it yet. I was thinking about treating the floor as a flat surface, then fudging the Y coord according to a slope formula. Not sure if this would be as hard as doing it the right way (whatever the right way is).
I have read about a couple different ways to do collisions, like seperating axis, some 3d methods and a couple more mentioned on this site, but I am not sure if those methods would be overkill for simply comparing boxes colliding and which wall (top,bottom,left,right) it collided with.
Flimflam - I am planning on making slopes. I might fudge it a little though, but haven't implemented it yet. I was thinking about treating the floor as a flat surface, then fudging the Y coord according to a slope formula. Not sure if this would be as hard as doing it the right way (whatever the right way is).
I have read about a couple different ways to do collisions, like seperating axis, some 3d methods and a couple more mentioned on this site, but I am not sure if those methods would be overkill for simply comparing boxes colliding and which wall (top,bottom,left,right) it collided with.
I'm currently working on a project called Bug Warz: http://www.flatredball.com/forum/viewtopic.php?t=249
It's a 2D platform fighter, much like Smash Bros., so naturally, I've spent a considerable amount of time working on this problem. Here are a few tips to help organize your code and also make your game run faster.
1. Separate collision functions from the actual game. You might already be doing this, but I saw one of the suggestions about testing to see if you stomp on an enemy with the actual collision test implemented next to the behavior code. Methods (or functions) you should have are methods to test if things collide, methods to tell you which side one object is compared to another object (done by testing the distances between their sides), and also what I call a "move" collision, which guarnatees that objects don't overlap. If you have those done outside of the context of your game, you can focus more on the behavior than the implementation every time you need them.
2. DON'T tie collision to individual tiles. Consider Super Mario Bros 1: The game begins on a flat ground. you run to the right, jump over some goombas, get the mushroom, jump over a few pipes, and encounter your first pit if you didn't go down the pipe. By this point, the character has just passed over perhaps a few dozen or even hundred tiles. But everything is just one continual solid area. You can reduce the number of collisions GREATLY by replacing groups of tiles with just one solid rectangle. Of course, this won't work with groups of tiles which the player can interact with individually like blocks you can break or question blocks you can hit for items.
3. By grouping your collisions, you should not have any problems with performance related to collision. You should literally lbe running maybe 10 or 20 collisions per frame. However, if you are still having problems, or you feel that overlapping solid rectangles over your tiles is too much of a headache, consider the following method. First, determine which axis is most distributed in your game. Since it's 2D, it's either x or y; probably x if you're doing a side scroller. Next, sort all of your collidable tiles in some data structure and perform an insertion sort every frame on all objects. in fact, if they're stationary, you'll only have to do it once. Now that your objects are sorted on the X axis, you just have to drop into the array (either binarily or even bettery by making assumptions about the distribution), then test "outward" by traversing the list forward and backward from a point where the tiles overlap the character on the X axis. Assuming you have constant tile sizes, as soon as you move beyond a certain point, you should know when you will no longer trigger any collisions. If you are loading entire Mario levels at once, this method will remove 99.99% of all collisions, and even if you have to sort every frame for moving objects, insertion sort becomes a linear time operation on a nearly-sorted list which your objects will always be.
Hope my long-winded response helps,
--Vic--
It's a 2D platform fighter, much like Smash Bros., so naturally, I've spent a considerable amount of time working on this problem. Here are a few tips to help organize your code and also make your game run faster.
1. Separate collision functions from the actual game. You might already be doing this, but I saw one of the suggestions about testing to see if you stomp on an enemy with the actual collision test implemented next to the behavior code. Methods (or functions) you should have are methods to test if things collide, methods to tell you which side one object is compared to another object (done by testing the distances between their sides), and also what I call a "move" collision, which guarnatees that objects don't overlap. If you have those done outside of the context of your game, you can focus more on the behavior than the implementation every time you need them.
2. DON'T tie collision to individual tiles. Consider Super Mario Bros 1: The game begins on a flat ground. you run to the right, jump over some goombas, get the mushroom, jump over a few pipes, and encounter your first pit if you didn't go down the pipe. By this point, the character has just passed over perhaps a few dozen or even hundred tiles. But everything is just one continual solid area. You can reduce the number of collisions GREATLY by replacing groups of tiles with just one solid rectangle. Of course, this won't work with groups of tiles which the player can interact with individually like blocks you can break or question blocks you can hit for items.
3. By grouping your collisions, you should not have any problems with performance related to collision. You should literally lbe running maybe 10 or 20 collisions per frame. However, if you are still having problems, or you feel that overlapping solid rectangles over your tiles is too much of a headache, consider the following method. First, determine which axis is most distributed in your game. Since it's 2D, it's either x or y; probably x if you're doing a side scroller. Next, sort all of your collidable tiles in some data structure and perform an insertion sort every frame on all objects. in fact, if they're stationary, you'll only have to do it once. Now that your objects are sorted on the X axis, you just have to drop into the array (either binarily or even bettery by making assumptions about the distribution), then test "outward" by traversing the list forward and backward from a point where the tiles overlap the character on the X axis. Assuming you have constant tile sizes, as soon as you move beyond a certain point, you should know when you will no longer trigger any collisions. If you are loading entire Mario levels at once, this method will remove 99.99% of all collisions, and even if you have to sort every frame for moving objects, insertion sort becomes a linear time operation on a nearly-sorted list which your objects will always be.
Hope my long-winded response helps,
--Vic--
Author
Grouping similar walls seems like a great idea. Maybe on my level loader I will have to make a wall optimizing function. Good tips Roof Top.
[Edited by - hoihoi8 on January 20, 2006 3:24:24 PM]
[Edited by - hoihoi8 on January 20, 2006 3:24:24 PM]
Just to jump in here, what you want is a quadtree, there are various articles on gamedev.net, divide all the objects into 'quads' and you only need check for collisions in all of the 'quads' that the player is in -- this may even be overcomplicating things as quadtrees implies you have quads of varying sizes, the original mario bros. used quads the size of 'one screen' fixed throughout, only two quads were ever loaded at any one time, walking to the right would unload the earlier quad and load a later one, hence why you could only walk backwards through the level so far (up to one screen).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
