   Optimizing Collision Detection
  I'm working on a 2D platformer.  I have had collision working for some time, but yesterday I decided I wanted my character to be able to move and jump at higher speeds.Until yesterday, the character simply walked his walking speed (3 pixels per frame), rose or fell his jump/fall speed (maxed out at 8.5 pixels per frame), and then did hit detection.  Obviously, at higher speeds, this system breaks down as you can run through solid objects.So, I just used a few for loops to tell it to check for collision after every pixel of movement, while still moving the right number of pixels each frame.  This makes the collision detection perfect for any speed, but when you are jumping up at a rate of 20 pixels/frame and simultaneously moving sideways at 16 pixels/frame, it is calculating all of the collision detection stuff 36 times per frame.  This quickly brings the game to a crawl, and this is only for a single moving objects (the player).So, what I'm trying to figure out now is the best way to optimize this.  I can either change the way the character moves (maybe check for collisions every few frames?) or I can somehow optimize the collision detection so it can be run potentially hundreds of times a frame without killing the frame rate.I should add that I've got my display frame rate completely separate from my game logic frame rate, so when it slows down it still works great, but the whole things comes to a crawl.   
  Optimizing it enough shouldn't be impossible, but exactly how it's done, and how complicated it will be, depends on how exactly you represent the objects you want to collide with. The most obvious optimization is to only check collisions against close objects. Are you already doing that?If you check collisions against the whole map every frame, then you could potentially speed it up a lot by simply arranging objects in a grid, and only testing against parts of the map that is close to the character.If you want a greater chance of good replies, post the method you use for collision detection, and how your different objects and maps are represented, and what programming language you are using.There is also the possibility of micro-optimizations, simply writing the exact same code faster. This is dependent on the programming language you are using, and is usually not necessary, but can be a last step if algorithmic improvements are not good enough.   ;  I'm using C++.  The whole thing is tile based, with a vector holding all of the Tile objects.A for loop iterates through every tile in the vector.  The first thing done for each tile is that it checks to see if it is within 1 tile of the player.  If not, it skips the rest of collision detection and moves on to the next tile.One thing I've wondered is if the for loop running through every tile (there can be thousands in a level) might slow things down, just by itself.  Other than the for loop, nothing happens during collision detection except for nearby tiles.  Do for loops slow things down much?I think I would do a lot better if I knew some things about C++ in general.  For instance, I have no idea if there is a speed different between different loops, if statements, arithmetic operations, etc.  Are any of these really slow, practically speaking?  I mean, my game is a simple 2D platformer, so I assume that my problem is not something so low-level.  I'm guessing it's more what I'm doing than how I'm doing it with the code.  Does that sound right?   ;Quote:Original post by Dark_Oppressor.....The first thing done for each tile is that it checks to see if it is within 1 tile of the player......Do for loops slow things down much?Depends on how complicated your test to see if the tile is within 1 tile of the player is.Is it a grid of tiles your talking about? it may be possible to work backwards from the player position to find which tiles to check, removing the need to loop over everything.;Quote:Original post by Dark_OppressorSo, I just used a few for loops to tell it to check for collision after every pixel of movement, while still moving the right number of pixels each frame. Why every pixel of movement?  You just need to detect collision with the thinnest object in your game without being able to penetrate it. In other words thinnest object in pixels -1 pixels per movement check.Quote:Other than the for loop, nothing happens during collision detection except for nearby tiles. Do for loops slow things down much?...I have no idea if there is a speed different between different loops, if statements, arithmetic operations, etc. Are any of these really slow, practically speaking?  Sounds like you need to measure.  Try finding a profiler like AMD's code analyst.  Things I would be more concerned about than loop types(they are about the same)  is hardware concerns are you accessing memory in a cache efficient way etc.   ;  Are you compiling in debug mode or release mode?Things are often much much slower in debug mode.If the player position is at X = 1500, and you know each tile is 50 units wide for example, then you can directly calculate X/50 = 30, and know that the player is at the 30th tile in the X-direction. Then you only have to loop from 29 to 31, and not do the test for every tile. Do the same in the Y-direction, and use a 2D-vector (vector of vectors), or similar, to loop only over the necessary tiles in a double loop.for(each tile in Y range) {  for(each tile in X range) {    collision(tiles[Y][X]);  }};  Couldn't you determine how much X and Y movement has happened since the last frame, create a bounding box from the data and check for collisions with that box? Then you can grab the intersection point and reposition the character there.   ;Quote:Original post by Dark_OppressorSo, I just used a few for loops to tell it to check for collision after every pixel of movement, while still moving the right number of pixels each frame.  This makes the collision detection perfect for any speed, but when you are jumping up at a rate of 20 pixels/frame and simultaneously moving sideways at 16 pixels/frame, it is calculating all of the collision detection stuff 36 times per frame.  This quickly brings the game to a crawl, and this is only for a single moving objects (the player).So, what I'm trying to figure out now is the best way to optimize this.  I can either change the way the character moves (maybe check for collisions every few frames?) or I can somehow optimize the collision detection so it can be run potentially hundreds of times a frame without killing the frame rate.I think a good start would be to change the way you're detecting collisions.  You should base the collision detection on frames instead of on pixels.  That way you can project the player's motion into the next frame and see which (if any) tile(s) he'll collide with.  At that point, you can handle the collision -- i.e. move the player so that he no longer collides with the tile(s).What this will mean is that, instead of doing collision detection 36 times per frame(!!!), you'll do it once per frame.  This is a significant optimization as your code will run 36 times faster, all other things being equal.You can also optimize determining which tile(s) the player might be colliding with.  Assuming that you're representing your player as a rectangle, you can take its left, right, top, and bottom coordinates (from the projected position), translate them into "tile coordinates", and find the potentially intersecting tiles that way, discarding any duplicates.Let me know if you need more help.EDIT: Looks like other people have the same idea. :)   