Sign in to follow this  

2d sidescroller (collision detection)

This topic is 3805 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

how to make a 2d level (bigger than the screen) and have efficent collision detection. I was originally using a collection class and randomly placing object along the screen and looping through the collection class to see if the player hascollided with any level object in the collection class. I wanted an easier and more efficent way of doing this. I was thinking of making a huge picture and just putting it on the screen and scrolling along it but I would know how to do collision detection since i couldn't put a e.g. square/rectangle around it. p.s. what technique did there use on sonic 2d games? thanks for looking later UF

Share this post


Link to post
Share on other sites
Hi,you may want per-pixel collision detection.Making a masked array of the map and objects,like :1 if there is pixel,0 if there is nothing.
In sonic ,like most 2D games ,they use tiled-base maps.They are squared bitmaps of 16*16 /32*32 pixels for example.You check if the player's bounding box collides with some of the objects' such box,and if it does you may want to perform further per-pixel check .

Share this post


Link to post
Share on other sites
For collision systems, you want the collision checks themselves to be as cheap as possible, but you also want to limit the number of collision checks as much as you can. When there's a thousand objects a mile away, why check against them?

For that reason, people often divide their world into smaller area's, and they then keep track of which object is in which area. This is commonly called 'space division', and for 2D situations, you can use a quadtree or something similar. When you're inside a node, you only check against the objects in the same node and in the parent nodes. Granted, you'll have a few extra checks agains the node boundary boxes, but these checks prevent you from checking against a lot of other objects, which can lead to a good performance gain.

Share this post


Link to post
Share on other sites
Quote:
When there's a thousand objects a mile away, why check against them?... These checks prevent you from checking against a lot of other objects, which can lead to a good performance gain.
Is performance even an issue with 2D games, these days? I agree that a quadtree would definitely improve performance, but isn't that a little bit overkill?

Share this post


Link to post
Share on other sites
Quote:
Original post by KG_Brad
Quote:
When there's a thousand objects a mile away, why check against them?... These checks prevent you from checking against a lot of other objects, which can lead to a good performance gain.
Is performance even an issue with 2D games, these days? I agree that a quadtree would definitely improve performance, but isn't that a little bit overkill?


Depends. Let's say you're creating a real-time strategy game with hundreds, maybe even thousands, of units which all need collision checking and response with the environment and each other.

Share this post


Link to post
Share on other sites
With 100 moving objects, you end up with 10.000 checks per frame already. With 10 moving objects and 1.000 static ones, you end up with 11.000 checks per frame. It depends a lot on the game whether or not it will be an issue, and with somewhat large and complex levels, a platformer can get trouble with this just as well.

But yeah, if collision takes just a few percent of the total frame-time, then implementing a quadtree for a 60% performance gain will only yield you a few percent in total. Profile your code before optimizing it, but also build your code so, that it's not hard to implement such optimizations later, when they're needed.

Share this post


Link to post
Share on other sites
In my games, I store the location of solid tiles in an array. When I move a sprite, it checks if the location the sprite is moving towards is occupied by a solid tile. If so, the sprite doesn't move. If not, it moves to that location. It might not be the best method of collision detection, but it gets the job done.

Share this post


Link to post
Share on other sites
I was thinking of doing a grid-based system. My game (2d) has tiles that are 256x256. The server maintains a list of tiles in the game space, and within those tile squares there is a list of object IDs.

Only those object IDs, if there's more than 1, are tested against each other (and there are more filters from there, certain flags... such as stationary objects or non-collidable objects).

On the side I keep track of player characters (this is an mmo-type game), and only collide objects deemed in their "relevant" range (for replication), otherwise, the server performs no collision checks, since there's no players around to see them.

Well, this is the outline design, it's not in full force... yet.

I think the basic principle is what Captain was saying... use a quad tree, or some other sort of segmentation, to build object relevance... Don't test an object to another object if it doesn't make sense to.

That alone will increase performance tremendously. On top of that, box or sphere collisions are extremely quick if you don't mind them being a bit on the innaccurate side as far as shapes. If you need pixel-perfect collisions, it'll cost a bit more, but it'll look better.

Clanlib has an interesting way to handle collisions, using outlines (scalable and rotatational).

www.clanlib.org

Share this post


Link to post
Share on other sites
Quote:
Original post by KG_Brad
You're making an MMO that's a sidescroller? I've never seen any before, so hopefully you're the first!


I've actually seen a few before. Surprisingly, they work pretty well...

Share this post


Link to post
Share on other sites
If looping costs N^2, an quicker way would be to keep the objects sorted, on tile id or x or y or both. Sorry tile_id wont help!

Sorting will cost nlogn, better than N^2, lookup for collision will cost you log_2(n), using binary search.

Are my log bases correct anyone?

Share this post


Link to post
Share on other sites
Quote:
Original post by KG_Brad
You're making an MMO that's a sidescroller? I've never seen any before, so hopefully you're the first!

Maple Story, and it's pretty good for about 5 hours (until you realize just how damned long it takes to level).

Share this post


Link to post
Share on other sites
Quote:
Original post by Captain P
With 100 moving objects, you end up with 10.000 checks per frame already.

It isn't quite 10,000. It's about half that. That's because if Object A has been checked against Object B, then Object B doesn't need to do the check again against Object A. So for 100 objects the number of checks would be 5050.

Share this post


Link to post
Share on other sites
Quote:
Original post by catch
I was thinking of doing a grid-based system. My game (2d) has tiles that are 256x256. The server maintains a list of tiles in the game space, and within those tile squares there is a list of object IDs.

Only those object IDs, if there's more than 1, are tested against each other (and there are more filters from there, certain flags... such as stationary objects or non-collidable objects).

The problem with this method is when objects start to overlap multiple tiles. Do you add them into multiple tile lists? Possible, but tricky and time-consuming to manage. Or you can check in a fixed radius of tiles around each object, but that puts an upper limit on the size of any object within your world.

You could try putting objects that don't fit into another list, one covering several tiles at a time. But you'd still end up with cases where they don't fit all the time, so you'd have to do it again recursively. And then what you've got is a regular quadtree. [grin]

As a side note, pixel-perfect collision is overrated and creates a nasty dependancy between your gameplay and your art. You really don't want an artist to draw you a nice new sprite with a big fancy hat/haircut and suddenly find that the collision area stops you walking into confined spaces. If you must do pixel based collision, then use an entirely separate, non-visible, set of images.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sc4Freak
Quote:
Original post by Captain P
With 100 moving objects, you end up with 10.000 checks per frame already.

It isn't quite 10,000. It's about half that. That's because if Object A has been checked against Object B, then Object B doesn't need to do the check again against Object A. So for 100 objects the number of checks would be 5050.


Depends on how you approach it. When you're moving objects and immediatly check if they can move, you'll get 10.000 checks, because you can't ignore any objects: there's no guarantee about their current position. A can move into B, and get pushed out. B can then move into A, and B needs to be pushed out as well. It needs to check against A in order to do so.

Only when you're moving all objects first, and then check if they're stuck and need to be moved out, you'll get a lot less checks, true. I'm not sure what implications that would have on the design of a collision system, but it's worth a look. Thanks. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by OrangyTang
Quote:
Original post by catch
I was thinking of doing a grid-based system. My game (2d) has tiles that are 256x256. The server maintains a list of tiles in the game space, and within those tile squares there is a list of object IDs.

Only those object IDs, if there's more than 1, are tested against each other (and there are more filters from there, certain flags... such as stationary objects or non-collidable objects).

The problem with this method is when objects start to overlap multiple tiles. Do you add them into multiple tile lists? Possible, but tricky and time-consuming to manage. Or you can check in a fixed radius of tiles around each object, but that puts an upper limit on the size of any object within your world.

You could try putting objects that don't fit into another list, one covering several tiles at a time. But you'd still end up with cases where they don't fit all the time, so you'd have to do it again recursively. And then what you've got is a regular quadtree. [grin]

As a side note, pixel-perfect collision is overrated and creates a nasty dependancy between your gameplay and your art. You really don't want an artist to draw you a nice new sprite with a big fancy hat/haircut and suddenly find that the collision area stops you walking into confined spaces. If you must do pixel based collision, then use an entirely separate, non-visible, set of images.


I had thought of that same issue. My initial thought would be to yes, check the surrounding tiles if they contained an object. I'm (hopefully) not looking at much of a density problem, so the checking overall would be fairly small.

I wouldn't worry about recursive tests since testing will occur by the other objects shortly anyway, and I'd process per actor, per update, so I don't believe there would be a loss in visual accuracy. The order of checking would also make so each tile would only check four surrounding tiles, not all 8.

I'm sure there's faster or more organized methods. This is what I came up with.....


+1 on the per pixel thing... I think a combination of sphere/square bounds tends to be accurate enough, especially if you allow rotations (for boxes).

Share this post


Link to post
Share on other sites

This topic is 3805 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this