Collision-Zones in a Shoot-em-up
BlitzMax Forums/BlitzMax Programming/Collision-Zones in a Shoot-em-up
| ||
| I am making a simple vertical shoot-em-up. I am at an early stage but figuring that there might be a lot of objects on screen by the time it is finished - i have decided to split the screen into collision-zones. Each of these zones is 128 x 128 pixels, and the idea is that everytime i move an alien or bullet, i work out which zone(or zones) it is in and then I add it to a list which is attached to each zone. (one list for player bullets, one list for aliens) I then go through each zone and do collision checks on just the objects in each zone. This saves a lot of collision checks. For example if i have 10 player bullets on screen and 50 aliens. thats 10*50=500 collision checks. but using the zones this would hopefully be cut to maybe 50 collision checks. My question is - is this a good idea? and am i doing it the fastest way? At the moment i automatically remove all instances of an object (using RemoveLink) from the collision-zones and then i calculate which zones it is in its new position. I included a screen shot to show how the screen is split up into zones.  the white bullets are player bullets. Last edited 2011 |
| ||
| I have never used zones myself, I've been making a SHMUP myself(on and off) but I waited my options and decided to keep it simple for starters and if it got too slow I would change it to to zones but so far it is working pretty smoothly as it stands. The biggest FPU consumption is going to be in displaying the sprites(animations,explosion particles and tiles). I don't do pixel perfect collision because "THAT" is really slow instead I do bounding box collision. the way you are handling sound like a good idea. Are you using an array for the list zones? it sounds like you are and it seems like the best way to do it. That of course is just my guess. if you want to check the performance in my game: you can download it from here: windows: http://www.mediafire.com/file/g3qtyvruxc3hcnv/millenia.zip mac: http://www.mediafire.com/file/8nbg887ns6snwav/millenia%20mac.zip |
| ||
| It's a great idea. I found huge speed increases for collision detection when using a grid like this (which I did exactly the same way - a grid of cells and updating a linked list for each grid cell). I only updated the linked lists IF an object changes from one cell to another. You should put objects in the cells based on the coordinate of their TOP LEFT corner, which ensures that you then only need to check the cell to the right, the cell below, and the cell below to the right instead of checking all surrounding cells. Also ideally you want the cell sizes to be as close to (but no smaller than) the size of the largest object you're planning to store in it. If you have a lot of objects of a small size and only a few larger ones it's worth putting all the small ones on a smaller grid by themselves and use a larger grid for the big ones. The `tigher` the cell box can fit around an object the less often you have to waste time testing a collision. I also recommend that if possible, instead of using a linked list in each cell use an associative array, ie one array storing the index/handle of an object and one array implementing a linked list structure of pointers. Another option is to forceably update the whole grid every frame, which would be quick to do using a single array in each grid cell, but wastes time as well due to updating objects which aren't changing cells in this frame, but if you have a lot of movement going on it may help. With a grid you should easily be able to handle 10,000 objects where every object can potentially collide with every other object. However, my question to you is, do your enemy sprites collide with EACH OTHER? If not then the grid is a big waste of time. If the player ship sprite collides with the grid but elements in the grid don't collide with other elements in the grid, then you may as well just check for collision between the player and all enemies (although I suppose a grid would speed that up too). Last edited 2011 |
| ||
| Hehe...just wrote my first quadtree a few weeks ago. Depending on the nature of your object distribution this can be even more effective, but anything that reduces the search helps, of course. Oh, and yes, it only really makes sense if there's a problem with the amount of search necessary to begin with. In my case I've done swarming, where every element had to check with every element. This kinda stuff creates some very exciting motion patterns for enemies, too, by the way. But ordinarily those shooters don't go that far, I think. Last edited 2011 |
| ||
| @Jesse - yes i was thinking of doing without zones but i wanted to see how much faster the zones would be. Its possible it would make it a lot more complicated to write - using zones - because i want some really big beam weapons (like the one in Fast Striker http://www.youtube.com/watch?v=-_tnqgKFnto) which would be lot bigger than the zones. So that would mean extra complication I do pixel perfect collision at the moment, because i heard the ImagesCollide command does a rectangle test before it does a pixel perfect one so i figured it would be fast enough?. Also some of the aliens rotate which makes it hard just checking rectangles. (I use ImagesCollide2 at the moment) I tried your game, its very good! I like the gfx effects in the background too. It didnt drop below 230 fps for me the whole time i was playing , so your method does seem fast enough :) I am using an array like this for the zones @Imaginary Human I am currently putting objects in the cells/zones using the top left corner but i dont understand what you mean by the associative array. could you explain in a bit more detail? thank you very much Here is a little of my programming: al is the alien. rxp and ryp are the real coordinates of the top left of it's bounding box (because its rotating but not about it's centre). I go through the whole aliens list every frame and do this. As you can see i am removing all links every frame so I need to think about how to do it so i only update the ones which change cells/zones. Later I go through the whole Zone array checking the Alien_list against the Player bullet list in each cell. The enemy sprites dont collide with each other, although i did think at some point I might want to have some enemies which bounce off each other. However... there will most likely be the players ship, the player bullets, the enemies, and the enemy bullets. Where 1) the player and his bullets need to be checked against the enemies 2) The enemy bullets and the enemies need to be checked against the Player. Thanks very much to you both for all the help :) Last edited 2011 Last edited 2011 Last edited 2011 |
| ||
| Thanks Taron, sorry your post wasnt there when i started typing :) Well done on making a quad tree, it sounds complicated but i will look it up to see how it can help. I may not need it if the grid method is sufficent, or maybe i dont even need zones as Imaginary Human said might be the case. |
| ||
| you can do box collision even with rotated sprites. I posted a rotated bounding box collision in the code archives when I was helping Hub with his collision. I don't know it this will help but you can check it out: http://www.blitzmax.com/codearcs/codearcs.php?code=2806 |
| ||
| Hehe, yeah, quadtree sounds complicated, because it does much more than what your instructions will look like, due to it being recursive. But once you get a grasp of it, it's kind of straight forward. It will stay spooky for a while, though. Hmmm, maybe I will write a post about it at some point. It's really kinda fun and looks very entertaining on top of it. :o) Good luck with what you're doing. Can't wait to see your first results in action! ;o) |
| ||
| Thanks Jesse - I am probably going to switch to bounding box collisions so that will be very useful. Actually I remember you helped me before doing rotating platforms in my platform game, so i think i have the code in that which did collisions with a rotated bounding box. but thanks for the code, its much neater than mine :) @Taron, thank you :). Recursion always confuses me actually! it is hard to get your head round. I made a video of what i have done so far :) http://www.youtube.com/watch?v=iMPbbvQmOW0 I managed to get my beam weapon in there. I was still able to use zones with the beam because its made up of sections so they easily fit into zones *phew* I did have a question. I know Imaginary Human said earlier about only removing items from zone lists if they move to a new zone. I was wondering is it faster to just remove all links (like i am doing now) or doing checks to see if they have changed zones. (maybe the checks will be slower to do than just one RemoveLink command?) hope you like the video, its very basic with just one enemy. Last edited 2011 |
| ||
| This techique is also implemented in DWLab framework and called Sprite Maps there. You can define grid size and cell size of this map (it's wrapped over whole 2D plane, so it's just a question of speed on how to select those values). And it also works with isometric maps to sort objects while displaying them. |
   |