space shooter collision detection
BlitzMax Forums/BlitzMax Beginners Area/space shooter collision detection
| ||
| hi guys. i'm making a space shooter w/minib3d (irrelevant to my issue). i have two types of objects: enemies and bullets. ideas how i would go about doing collision detection? i have the following code but on the school macs (which is what i have to work with), well, it really sucks. i know it's not efficient too ( O(n^2) ), which is why i'm asking if anyone has any better ideas? enemies and bullets are TLists storing...enemies and bullets. thanks in advance! |
| ||
| chop you playfield up into a grid, if two objects are in the same grid then perform a collision check, if not then ignore them. You may also want to flag an object as "CHECKED ALREADY" to save further iterations. |
| ||
| If you go the route Indiepath suggests, be sure to reset that flag after each flip cycle. That way it could eventually be checked for collisions. |
| ||
| Most shooters use a rectangle slightly smaller than the player ship. Games like DoDonPachi did this and they were not a problem at all. If you are going to be spewing out hundreds of shots at once, go for a simple algorithem like rect collision or circular collision. It's traditional not to use sprite based collisions. Sprite perfect collsions are often a waste. What kind of shooter are you making? If you're going with a bullet hell or danmaku shooter you just use point distance sice the hitbox is tiny. If you are going with a horizontal shooter like R-Type or Gradius go with the rectangle method. Same with vertical. Here is a good link from our shooter creation forum... http://www.shmup-dev.com/forum/index.php?cat=18 |
| ||
| If it's a 2d on a 3d plane shooter like Ikaruga, i would suggest just doing rect collisions. simple and works. Cheers Charlie |
| ||
| Along the lines that Indiepath suggests, a method I often use is similar but also checks adjacent grid zones for those times when the objects being tested are near the boundaries of the zones. This may result in a few more checks but should not be enough to impact performance I would think. |
| ||
| i have two types of objects: enemies and bullets. ? I would like to help. could you elaborate? are the enemies firing bullets too? how many player bullets are on screen at once? no matter what, collisions are expensive to compute. using the grid idea will speed things up. i think using sphere to sphere collisions are fastest too. (you lose some granularity, but make up alot in speed) can you post some code? |
| ||
| "i know it's not efficient too ( O(n^2)" The only way it should be O(n^2) is if you were checking bullets vs bullets. If you're just checking player vs enemy bullets, and enemy vs player bullets, then it should be O(n). If you MUST check bullets vs bullets, then one way as others have mentioned is to use a grid to speed things up. The grid would be an array of pointers to lists. (You could use a 3D array but it might require a lot of ram if you have a lot of bullets) Create the array then create a list for each square. Clear the grid each frame by clearing the lists, then determine which squares a bullet overlaps and stick a pointer to it in the list for each square it overlaps. Then go through the array and for each square test all objects in that square that may collide with one another against eachother. (A typical square might have no bullets, one bullet, or two bullets, though many more are possible.) For each pair that collides, place that pair in a list. Once you have all the colliding pairs, go through the list, and for each pair, swap their pointers so the smaller pointer is the first one. Then sort the list such that you sort first by the pointer of the first object in the collision, and second by the pointer to the second object. Ie, if we use letters to represent pointers, then your collision list initially might look like this: D-E B-C A-D A-C C-B A-D After swapping it would look like this: D-E B-C A-D A-C B-C <- This one changed A-D And after sorting it would look like this: A-C B-C A-D A-D B-C D-E Now, go through the list, and check each pair with the next pair in the list. If the pair is the same as the next pair, then remove it from the list, leaving only one copy. (You could have three copies in a row, so don't skip checking slot 2 against slot 3 if slot 1 matched slot 2 and you removed slot 1.) NOW we have a list where we have each pair of objects that are potentially colliding listed only once. We can now loop through this list and do a pixel perfect comparison between each pair of objects, or test their bounding rectangles or whatever you want to do, but there'll only be a few objects to test so the complexity of the test won't be so important, and there won't be millions of possible combiations to look at. You might ask how many tiles you should have in your initial array. A good place to start would be making the grid squares twice the size of a bullet. This would give you a reasonably fine grid, and reduce the number of bullets that end up in more than one square by quite a bit. Four times the size of a bullet might be better. The only way to know is to test. There may be no noticable speed difference between the two though. If four is no faster than two, then you don't need to bother testing eight. Btw, the reason you can't just stick each bullet in one square is if you do that, two bullets might be overlapping, but be in different squares so they wouldn't be tested. Or a large object might overlap many squares on the screen but would only end up in one. You can just use the objects bounding rect to decide which squares to put it in. If the top left corner is at 0,0 and the bottom right is at 2,3 then loop x 0 to 2 and loop y 0 to 3 and stick it in each of those squares. |
| ||
| Regarding the grid method: You don't have to clear the grid each frame. Another way is to simply remove objects from a grid square when they move out of it or are eliminated and then to add objects to a grid square when they are created or move across a grid boundary. |
| ||
| To remove objects when they move out of a grid square if you're using a linked list for each square would require you to either search that list to find the object's pointer, or store the link to the object within the object itself. Which you would have to store in a list. Which you would have to search to find the right link for that grid square's linked list... Which would defeat the purpouse of saving the list pointer. :-) So to avoid the cost of the search, just null the grid. It'll probably be less expensive, and it's a lot simpler. |
| ||
| sswift - not really, I use this method all the time in blitzplus in the following manner: All objects, bullets, space craft, big green aliens etc, are part of a single 'type' structure, with similar properties (movement speed, collision radius, hit points etc). Each frame you are going to iterate through each object and perform actions on it such as moving it in the case of bullets (and checking for collisions when the bullets move), or responding to player input (detected earlier) in the case of player controlled objects. So you are already going to be going through their list each frame anyway. When an object moves across a boundary (simple math check detects this) simply reference the appropriate grid square, either in a bank or an array which holds a reference to a bank which contains the handles (does Blitzmax use handle/object commands? maybe that's why it wouldn't work) of the objects within that zone/grid square. Simply run through the list of handles within that bank and remove the entry as well as moving all the following handles down one slot in the bank and resizing it so that it is 4 bytes smaller (size of a handle=int). If there are no objects left in that grid square then free the bank as well. Then proceed to go to the grid square that is being moved to and add the object's handle to the bank for that grid square. One of the points I don't really like about refreshing the list at the start of the next frame is that if an object moves out of the grid square, or into the grid square during the 'updatebullets' section of the code then the data being held in the grid square is suddenly out of date/incorrect. Whereas with the method I outlined above it is always accurate. In some ways it can be quicker too as you are only modifying the bank when movement occurs rather than refreshing every grid square every frame - a bit of a waste if most of them are empty or if most of the objects are slow moving/stationary. I don't know how much difference it would make with a low end PC since that is what Pragun is running it on. |
| ||
| wait just wondering matty why wouldn't this be O(n^2) (i dont have the code on front of me but...) for each bullet in the bullet tlist for each enemy in the enemy tlist check if the bullet and enemy are within a certain distance of each other if so, remove both next next |
| ||
| "Each frame you are going to iterate through each object and perform actions on it such as moving it in the case of bullets (and checking for collisions when the bullets move), or responding to player input (detected earlier) in the case of player controlled objects. So you are already going to be going through their list each frame anyway. When an object moves across a boundary (simple math check detects this) simply reference the appropriate grid square," I don't think you understand the method I've outlined. In the method I've outlined, there is no single "appropriate grid square" per object. There can be two. Or four. Or many. To do what you suggest, each object would need to keep a list of all the link pointers in the grid that point back to it. Then you would iterate through each object, and each item in that object's list, and remove the links those items point to in the grid square lists. This is a lot more complicated and unlilkely to be significantly faster than simply nulling all the lists on the grid. As for the data being out of date at the start of the frame, why do you care? If you move a bullet, why do you care if you know where the other bullets are currently, which is to say, where they were last frame, or where they have been moved to this frame before you got to moving this bullet? You can't act on that information. That way leads to madness. :-) If you want to act on the information from a previous frame, then you should copy that information to a scratch buffer that won't get modified as you iterate through it. Only in rare cases have I needed to modify a buffer whilst simultaneously reading the data from said buffer. And that wa when doing a box blur on an image. I can't imagine why you would need to do that in this case. I could see why you might want an enemy's prior position, to say, draw a motion blur, but why would you care what squares it occupied when testing for collisionsm, which you finished doing last frame? In some ways it can be quicker too as you are only modifying the bank when movement occurs rather than refreshing every grid square every frame - a bit of a waste if most of them are empty or if most of the objects are slow moving/stationary. The amount of data we are talking about here is so small that even a "low end pc" would have no difficulty dealing with it. We're talking about the equivalent of clearing a 64x64 image to black, in software. I drew screens full of sprites with alpha in software at 60fps in Blitplus. And that was slowed down by readpixels. You're just talking about a miniscule amount of data. It wouldn't make a lick of difference in speed to do it the more complicated way. The method I outlined is already complicated enough. :-) |
| ||
| I don't think either of us understands the method the other is suggesting (well I am certainly confused with how yours works - and mine is a lot more simple than what you seem to think), but that's okay if Pragun has found a method that works I guess. |
| ||
| Here you go. |
| ||
| This might be useful and not too difficult to convert from BB to Bmax. |
| ||
| I just thought of something... Weren't the internal BlitzMax collision commands designed to get around the issue with colliding lots of onscreen objects with one another? I don't know how it is supposed to work, because it seems too simple to work properly, but it seems like you're able to call collide image multiple times to add images to a collision buffer and then check an image against the end result. If I understand what it's doing correctly, then only the topmost image at the first detected colliding pixel would be returned, (Ie, if two bullets overlapped one pixel, and that pixel was overlapped by your ship, then only the last bullet drawn at that pixel would be returned.) but this may be enough for your purpouses. It probably won't be as fast as the method I outlined, (since you're drawing each object in software, rather than just those ones that collided to do the pixel perfect test) but it would be linear time, and should be fast enough. |
| ||
| here's my code: http://www.mytempdir.com/1300200 download password: bmax if you hold down spacebar and move around a bit...every few seconds or so the game crashes for a split second. any ideas? the collision code is there too now. i was able to get to my code again (classes alternate at school..diff on diff days and my flashdrive is broken...so i just got access to my code). if anyone can help w/the freezing issue/can tell me a way to speed up the collision detection, thanks in advance! |
| ||
| bump, anyone? |
| ||
| Hi Pragun, although I use blitzplus not blitzmax I tried downloading your file from the site listed above but it just goes to some 'party poker' ad. |
| ||
| I tried downloading your file from the site listed above but it just goes to some 'party poker' ad Yep, same here. |
   |