Platformer Collision (Help Reducing Comparisons)

Game Mechanics
#1

Hiya! I’m making a platformer and don’t have any CURRENT problems. I’m a bit afraid of the performance of collision checking in the future, though. In my current game engine, there are collision objects, and moving objects that are affected by collision objects. There is only one player, so each collision object only needs to make one comparison at the moment. The total number of comparisons before each update is equal to the number of collision objects. This is going to change, though, as I’m going to create enemies and possibly npcs. If there are 2 enemies and 1 player, then the number of comparisons that need to be made triples. If I made 50 enemies on a map at once, it could be a disaster depending on how big the map is.

I’m thinking of developing a quadrant based system in which collision comparisons are done independently within each quadrant. Problem is, I don’t really know how to implement something like this. I was thinking that I would make a quadrant class where each instance would hold a set of collision objects. The quadrant itself would make a comparison with the moving objects, and if the comparison passes (the moving object is touching the quadrant…), each collision object within the quadrant would make its comparison. Each quadrant would have to make a comparison with each moving object first after every update.

Would this be a good system to develop? Are there other performance techniques that you can point out? I can’t continue to use the system I have now because I fear that it will take exponentially longer to do collision comparisons in the future.

#2

Best solution I can think of at this late time of night, is to first somehow check if the entity is close to something it can collide with, and if it isn’t it can simply skip the collision-detection. I don’t think it’s a very good idea to have everything in your world checking if they’re colliding with something. You should let their moving counterparts (player, NPCs, monsters, etc.) check whether they’re colliding with something, and then take action.

I made my platformer so things in the world just sit there, and my player and monsters all have collision-detection which determines what is to be done, depending on what they’re colliding with (tiles, moving tiles, monsters, the player etc.). Even with 200 monsters on the screen simultaneously, each checking 8 collision-points and walking on sloping tiles, I am not even close to hitting any performance barrier.

They each check those 8 points every update, and if they don’t collide with anything, they keep going about their business. That’s a lot of points, but as it is just points, and not all the points of a rectangle, I’m guessing I have a tiny advantage there.

I don’t think you’re going to have a problem, but if I were you, I’d whip up a basic monster, and check out what happens if you spawn a lot of them. Another good tip, is to only update (including collision-detection) and draw things that are on the screen +/- 50-100px in each direction. Then as long as you don’t spam 100 monsters on the screen at the same time, you will never have any problems, and the monsters waiting down the road won’t be activated until the player is inside a specific range.

#3

I think my situation may need to be be different because I might have 50 enemies, and hundreds of collision objects on one map. I think I might have just come up with a good solution, however.

Upon reading the tiled map from a file (using Slick2D), I’ll add each unmoving collision object into it’s own quadrant object based on it’s position and dimensions. Then, I’ll loop through every moving object, check to see what current quadrants they occupy, and make comparisons to the unmoving collision objects within the quadrants.

[1------------- ][2-------------]
[ ][ ]
[ Player ]
[ ][ ]
[ ][ ]
[][ ]
[3--------------][4-------------]
[ ][ ]
[ ][ LolEnemy2 ]
[ LolEnemy1 ][ ]
[ ][ ]
[___________ ][___________ ]

So, we loop through Player, LolEnemy1, and LolEnemy2, determine which quadrants they are located in, and compare them to the collision objects located within each quadrant. The Player is located within quadrants 1 and 2, so the comparisons will be restricted to those quadrants. LolEnemy1 is within quadrant 3, and LolEnemy2 is within quadrant 4, so comparisons for those two are restricted to their individual quadrants.

Would THIS be considered a reasonable solution to anyone considering the sheer number of objects that I plan to have on a map at one time?

#4

Well as a suggestion you can directly cross of bounds checking for players/enemies that aren’t moving. In a platformer you can turn off the gravity for an object after he hits the ground and re-enable it once he jumps to avoid checking against ground collision.

The quadrant method you’re talking about looks good.

#5

Oh, the collision objects check for eligibility before actually checking for a collision. That much is true. Just trying to cut down the sheer number of comparisons. I guess I’d better get to making that quadrant system, then. Thanks.

#6

Further, depending on how you handle your collisions, you can ‘prune’ the number of objects for a given moving object by checking the current position VS the object’s movement vector. If you’re moving up, you can ignore objects with that have a lower ‘top’ than the other objects ‘bottom’. Same for moving left/right. (In a way, this is a micro optimization, since it really just cuts a percentage of the checks from each non-colliding object.)

If you expect most enemies will be ‘ground based’, then you can ‘clamp’ them to the object they land on. Then collisions between entities (And not objects) can only occur between entities that are clamped on the same object, or between any entity and an unclamped one. In a way, you can also do a lot of other objects in the same way. For ‘items’ they get clamped when they land on a surface and then can only collide with unclamped entities/objects or things clamped on the same surface.

#7

I think you would benefit from reading this post.

It’s pseudocode showing how to quickly organize all entities into a grid which you can query. It should keep the time the comparison takes a lot more managable. The only way it wouldn’t be, is if you had too many entities in each “box”.

You can put them all into the grid every loop (it doesn’t take too long, it’s like one bit shift per entity) based on their world-coordinate.

Have fun!

#8

So basically, after each update, I should add objects to a certain quadrant in a grid, then run the game logic only considering the objects within that quadrant? I like the idea, but wouldn’t that take a lot of lists that would have constantly changing content? I’m not a huge fan of constantly resizing arrays, you see. Is this not an expensive routine? If it’s not, then it sounds like something that I can implement.

#9

ArrayList only grows. It does not shrink. Unless you tell it to. So once it’s grown to be able to hold enough values for your inputs, then it will remain the same size rather than increasing.

#10

What about just considering and checking objects in a certain distance from the player or NPC ?
Then there would no need for static precalculated quadrants.

#11

Then you would have to calculate Math.sqrt((x2-x1)^2+(y2-y1)^2) for every single object.

Or calculate the distance separately for horizontal and vertical components, but the collision bounds checking already does that. I feel like that would be an unnecessary and arguable optimization. I like the quadrant method still.

#12

Remember that you don’t need the sqrt for comparisons…only if you want to know actual distance.

#13

[quote=“DrewLols,post:8,topic:39460”]
Well, it does seem like quite a mess of data structure. That’s why I pointed you to that pseudocode.
It takes relatively few entities to make up for the time spent on assigning entities to cells. It’s how Revenge of the Titans does it, and it’s pretty efficient.

Else, as pointed out earlier: You’ll have to do a sqrt (or a comparison) on the coordinate set of all your entities every time you want to locate something. That’s expensive.

With the cells implementation, you order everything in cells once (per game loop), and you can query entities within a specific area very fast, and as many times as you want to. It doesn’t hurt performance as much as the sqrt’s (comparisons), when you’re scaling up the amount of entities.

Remember that you don’t necessarily have to use ArrayLists. There are plenty of other collections that’re designed in a way that makes it easy to clear, and fill in objects from the end. Like the LinkedList. In that specific case though, it may not actually be a performance gain, because of the implementation of LinkedList, but in theory in holds water.

#14

I was WONDERING if ArrayLists shrank or not! So, an ArrayList will probably be much more efficient that a LinkedList unless I’m constantly removing elements from the middle or beginning of the list. Calling “clear()” won’t resize the array within the ArrayList, correct?

I think I get what you’re saying… So, I can just consider r^2 = x^2 + y^2 and leave it at that as long as I’m not asking for the exact distance. I can still determine if something is within the radius or isn’t. Course, I still can’t implement something like this. It wouldn’t reduce the sheer number of comparisons. Just the amount of time each would take. If I wanted 100 objects to all interact with each other, that would still be 10,000 comparisons. Some would just take less time. I want to split all objects into smaller boxes, and then run the boxes independently from each other. I never actually thought of something like what you mentioned, though, so thanks!

[quote=“Mads,post:13,topic:39460”]

Cool enough, cool enough… I think I may have underestimated the efficiency of ArrayLists. I guess I can fool around with different types of lists and see which one performs the best for a variety of situations as long as I treat the lists used in an abstract manner. Yeah, it only takes one pass through all of the moving objects after each update to limit the number of comparisons made when dealing with collisions, so it can’t be all that expensive. I’m probably only going to have the quadrant system be relevant to collision checking with specific types of objects that absolutely REQUIRE optimization. Forcing all game logic to function independently within each quadrant seems a little inflexible. Well, I guess that about wraps it up then. Thanks, guys! ;D

#15

Sadly, in general, the ArrayList implementation is going to be faster/better than the LinkedList implementation no matter what you do. (Object creation isn’t free and the LinkedList implementation has to create/manage the LinkedListEntry object that forms each link in the list.)

No, it clear does not resize the array. Instead, it just iterates through the array and sets each entry to null. If you’re using a modern IDE, you should be able to view the code for ArrayList through it, so you can find out which one’ll work better for your needs yourself. :smiley:

#16

I don’t mean to post on a thread that is complete, but I’d just like people to know something. Before I added the newly implemented quadrant system, there were 398 comparisons each update. Now with the quadrant system, there are 50 comparisons or less! (I’ve even seen 9 comparisons on occasion) That’s NOTHING! Just wanted to post this in the hopes that it helps someone in the future. Ok, NOW I’m done!

#17

How do you handle the quadrant edges? I suppose a collision taking place on an edge might be missed? I’ve thought about doing something like this before and hadthe idea to make the quadrants overlap - slightly less efficient, but you avoid edge errors.

#18

For anything uniform grid like the easiest solution is to sweep-and-prune.

#19

Not necessarily. Obviously a large rectangle on the edge on a quadrant could leak over to the next.
How you wish to handle this is up to you, but I wouldn’t add each vertex to quadrants right away. That would make this much less efficient. Instead, find the center-point of your polygon/shape/rectangle and add it to the quad it’s supposed to be in. Obviously, this way you can’t find the very edge of it. However, you can query into more quadrants than just one, if you want to know whatever else is nearby. Even though the quads are… square, you can still query a pentagon region. Then only inaccuracy (which could prove important) is that you’ll find objects that’re 50% or more into the area you query before they show up. For tower-defence and such, it doesn’t really matter. For accurate collision detection, you should probably add more than one position vector.

I realize now that you might be asking A, and I’m answering B. My bad, if that’s the case.

Well, that makes clear use O(n) time. That is not the intention, at least not for me. That sucks.
Making a new instance takes O(1) time, but that could still be slower than clear, if the list is very short. Silly clear. Plain silly.