Open discussion on Collision Optimization
Monkey Archive Forums/Monkey Discussion/Open discussion on Collision Optimization
| ||
| Lets have a chat about collisions and how to optimize them for lots of collide-able objects. To help this chat we can use this basic scenario, Player, Bullet,Terrain and Enemy , these collections would be lists, arrays or maps or any other form of collection we have available in monkey. So with our test scenario we need to check the player against all bullets being shot from the enemy and all enemy and players against the terrain, so the basic idea is then to iterate through these lists checking for collisions, and this is fine when your only dealing with a few objects but as you add more then things will start to really slow down. The Basics For example, if your checking 10 bullets which are flying across the screen from the player toward the enemy and there happen to be 100 enemy on the screen then were checking each bullet against all 1-100 enemy and that's 1-1000 collision checks, and early boost can come from getting out of the loop once a collision is detected, if the bullet hits something there is no point in checking it against everything else in most cases. Bounding Box Assuming that a check is using something more complex and slower than a simple rect overlaps, what you can do is do an initial bounding box check on your objects, if for example the bullet is not inside a bounding box around an alien then there is no point in proceeding with a more complex more accurate check, if however the alien and bullet's bounding box do overlap then checking for a more accurate collision will take place, this alone can drastically speed things up when your dealing with a lot of bullets or a lot of things those bullets can collide with. |
| ||
| Use a quadtree? |
| ||
| Grid system, quadtree, sweep and prune (SAP) are three slightly different ways you can use to reduce checks. sweep and prune is probably the easiest to implement, so i'll describe that (in my own words, may be slightly muddled): 1. sort your main list with respect to x-axis. use either "position minus circle radius" or "bounding box minimum" lowest to highest. 2. compare the first with the next item in the sorted list. what we're doing is checking for overlap with either position + radius or maxx>minx bounding box. 3. does it overlap on that axis? if so, push to a "pairs" stack, and check the first one with the next+1 object. repeat until no overlap. 4. move on to the second object, and now check for overlap on the second+1 object (you already check the first one). repeat step 3. 5. and so on. 6. in your new pairs stack, check each pair for y-axis overlap. if so, push to a final "hit pair" stack. repeat until the first x-axis pair list is done. 7. you now have a stack of objects that have hit either by circle-circle or bounding box. you can do a narrow phase or just accept these results and do your collision response. article on sweep and prune: http://jitter-physics.com/wordpress/?tag=sweep-and-prune i'm developing an octree for miniB3D, so if you want a conversation on quadtrees (similar to octrees), let me know. http://monkeycoder.co.nz/Community/posts.php?topic=6206&post=81107 |
| ||
| Yeah saw your twitter graphic of it, looks really cool, Quadtree was a method I was going to mention but given its the main one used I felt it might end the thread prematurely if I had mentioned it .. glad some one else brought it up. Used quadtree for a few of my max projects but not done any with monkey yet, not really had the need, there is a brilliant quadtree tutorial with a cool particle demo I have bookmarked some where tho that I might try and implement and port to monkey over the next few days or weeks, I have a feeling I might need to use a Quadtree for my little side project if I really want it to be the bullet hell I have in my mind. In regard to quadtree's and monkey I was wondering if its performance boost is actually good given how people have complained about the GC in the past I was thinking that the process of creating short lists or maps could generate a lot of garbage.. ? |
| ||
| In regard to quadtree's and monkey I was wondering if its performance boost is actually good given how people have complained about the GC quadtree is relatively static compared to SAP, so it's better for things like big scrolling levels. more static requires less GC. SAP is probably better for bullet hell, but you may need to sort lists in place to avoid the GC. but don't worry about that at first. |
| ||
| You can also use square bins. Every tick each bullet decides what bin it's in, and then check only objects in the same or neighboring bins. When everything can collide with everything you need a method like binning or quadtrees and binning is easier. You can also do quadtrees semi-manually by having screen quadrant bins which are checked first, then quarters of the screen quadrants, then quarters of the quarters. That's easy because you just have three bin systems and it doesn't require any sort of recursive quad system the way quadtrees typically work. |
| ||
| don't suppose you would go into some more detail with this bin method, I think I get the gist of it in that I may for example like a quadtree split my screen into 4 bins or lists, top left, top right bottom left and right, and then each tick I would remove a bullet from its current bin/list and add it to the correct one if its moved from one region to another, does all that pushing on and off of lists not cause a bit of a bottle neck ? |
| ||
| does all that pushing on and off of lists not cause a bit of a bottle neck ? not compared to the savings. pushing on/off isn't like checking through a collision list at O(n*n). |
| ||
| Doing sorts/quadtree/octree are really faster than using a simple AABB collision check? I don't doubt that for 3D meshes/scenes this is really necessary - but on 2D... ? I'm really serious - I can't see all that extra work, to be faster than this:
If (x < bb.x + bb.w) then
if (x + w > bb.x) then
if (y < bb.y + bb.h) then
if (y + h > bb.y) Then collision = True
If the first comparison fails, the collision check is done, and the game can move on to the next. I never did a "bullet hell" game to stress test this - and I believe it may slow down on a really bad case like that - but otherwise, if you have less than 100 objects on screen, there is no need for such complexity. |
| ||
| if you have less than 100 objects on screen, there is no need for such complexity. yes, less than 100 objects, there's no need. but what if these 100 objects are checking against each other every frame? that's 5000 (100*100/2) bounding box checks . a simple grid/bin phase could cut this down into 900 checks if a 3x3 grid has 10-12 objects if evenly spread. let's say the grid/bin checks are an extra 100 checks, so that's 1000 checks vs 5000 checks. i've tested this out already on a tower defense game i made. it was very slow on android, until i created a grid phase to check for targeting/bullet collisions. |
| ||
| Paul, you got it right. And pushing pointers on and off lists is really quick especially if the list is a pool. With quadrant binning you run into edge cases where two objects might be just on opposite sides of a division line but in practice this is not noticeable at all. If you have physics response to collisions it also acts to limit the numbers of collisions somewhat because the objects crowd each other out of bins so there will be a smaller number in any given bin. When I first ran into the x*x exponential collision problem I was first amazed that only a few thousand objects were bogging my system, then floored by the efficiency of the binning. And as someone said, you have a huge amount of free CPU time to do physics or whatever because anything is better than the high end of that exponential curve. I do it with two if/thens, one for x and then one for y, so many cases fall through and do not need to be tested. Slotman: trust me, it's necessary above trivial numbers of collisions. Code up a basic geometry wars game where all objects can collide with each other and you will very rapidly see your system slow to a crawl. |
| ||
| But what type of game do you have to check everything against everything?!? Really, in tower defenses, you have basically 2 checks: - to see if an enemy is within range of a tower (basic radius check, could also be solved first with an AABB to speed the test up) - if a tower shot hit the enemy You don't check towers vs enemies, you don't check enemies against enemies. And towers don't shoot hundreds of bullets. What you guys didn't see is that AABB collisions works like a grid system. If bullet.x > enemy.x+enemy.width, and it's out of the enemy "grid", no further test is done. The worst case is when there *is* a collision, and you go by 4 "ifs" for each bullet. This system works for something like 20-30 objects on screen on a 3.5Mhz computer (this, I have tested!). Should be pretty fast for 200-300 objects on any cell phone released in the last 5 years or so. |
| ||
| Really, in tower defenses, you have basically 2 checks: you are correct, i did exactly as you described, but yet as soon as i got to android, the game broke down to a crawl. ( 100-200 units+enemies) a simple grid based check helped nicely. |
| ||
| by grid you mean the bin method yeah ? I'm wondering about the bin method and weather or not an overlapping grid might be a good idea, for example imagine a width of 4 hundred pixels, you might normally use two bins 200 pixels each but what if you used 3 with the extra bin overlapping the middle of the first two, which would cover any objects that are on that border line between bins, sure it would add potential double checks on a few objects but it might be worth while in the long run. |
| ||
| For reference: I have a quadtree for monkey on my google code site: https://code.google.com/p/mutated-monkey/wiki/quadtree And indeed it is best for really large levels and stuff like that. You problably will not need this in static screen games and a decent rect check for each object. |
| ||
| I'm wondering about the bin method and weather or not an overlapping grid might be a good idea what if the object is larger than the overlapping bin? another way is to put an object into more than one bin, and remove duplicates during the search. i use a Map (an RB tree) for the octree. it's fast. |
| ||
| I check the current bin and all neighbors of the current bin. If speed is a problem with that, check only the Von Neumann neighborhood of 4 fully adjacent bins. |
   |