Welcome, Guest. Please Login or Register.  • Help
SMF Underground
+ SHMUP-DEV » SHMUP DEV FORUMS » Assistance » Tutorials
|-+ Art Of Collision [part 1] : Gunbird Collision

Pages: [1]   Go Down
0 Members and 1 Guest are viewing this topic. Topic Tools  
Read August 13, 2008, 03:57:09 PM #0
motorherp

Art Of Collision [part 1] : Gunbird Collision

Hello fellow shumpers and welcome to my first tutorial. My name’s Dan, although you probably know me better by the handle Motorherp (if you’re wandering its like another way of saying mechanised reptile, I’m fascinated by snakes and lizards). This series is going to be about collision detection techniques and management and how they relate to shmup games. Rather than create a step by step tutorial focused on one idea I’m going to attempt over the course of the series to cover and compare a selection of methods to give you a better understanding of the problem as a whole. I’ll try to keep this general rather than getting deeply involved in the intricacies of any one language so that everyone can benefit, but I am myself a C++ programmer so please forgive my bias towards that style. I’ll be giving code examples in a C syntax but it will be kept simple. Also to keep the focus on the algorithms I’ll refrain from putting in features I’d ordinarily use which would lead to more efficient or safe code but would complicate matters. Please keep this in mind if you implement this code for yourself. So without further ado let us begin.

I figured the best way to start is with a real life case study so that you can get an idea of how these types of problems are handled in professional games. For this purpose I’m going to be using Psikyo’s Gunbird 2. I chose this game for several reasons, firstly because it’s a game I’ve greatly enjoyed and think it’s a fine example of a good shmup, but more importantly the version I have has a debug mode which allows us to see some of the working underneath. As it turns out the collision detection used in this game is very simple which is great as a starting point for us. I’ll begin by showing some of the tricks they used, followed by looking into the algorithms required to pull them off giving examples of how I think they went about actually implementing this in game (or at least how I would have done it based upon what I’ve observed), and finally finish with a discussion on the limitations of such techniques and how we can expand and improve which should set is up nicely for the next tutorials. Hopefully by the end of this first tutorial you should have all the knowledge you need to implement your own simple yet efficient, if a little limited but perfectly functional collision detection and management system just like that used in Gunbird.

How Psikyo did it

So just how did they do it? In essence it all comes down to 4 little words, “axis aligned bounding boxes” ….. or rather 8 little words, “lots and lots of axis aligned bounding boxes” :p. So just what is an aabb (axis aligned bounding box)? Well as the name implies, it’s a box which is always aligned with the screen’s vertical and horizontal axes and never rotates. To give you the general idea I’ll show you a picture of the game running in debug mode. Please forgive the poor picture quality, I couldn’t find my good digi-cam so had to take the photos on my mobile phone whilst simultaneously trying to play the game. I’ve included a second picture where I’ve gone over the boxes in a paint package to make it clearer.



I bet you didn’t think it was this simple did you? Cheesy. As you can see different boxes have been flagged with different attributes denoted by colour. The white box at the bottom left is the player (pretty hard to see sorry), the green boxes are power-ups, red boxes are land based enemies, and yellow are air based enemies and enemy bullets (ignore the trails behind the bullets, there is just one box for each but due to the slow shutter speed on my camera it shows up as multiples). I’ll come back to this attribute flagging later on when I go on to talk about implementation, but keep it in the back of your minds. For now I just want to concentrate on how they’re using these aabb’s to represent their objects. The trick here is to try and represent the scene using as few aabb’s as possible to reduce the cost of performing the collision detection. As you can see, many objects have seemingly poor fitting boxes with lots of the sprite hanging out of the edges, but given the fast pace of these kind of games its enough to create the illusion of accurate collision. In fact this can even work in their advantage in certain scenarios such as with the walking robot top left in the picture above since they want to give the impression of shooting at the robots torso rather than at his feet. They even go a step further with this simplicity in special cases and use one aabb to represent multiple objects which are always together, like so:



Here we see the player’s bullets in a powered up state were they’re shot in pairs and represented by just one white box per pair (again sorry for the trails, there’s not actually as many boxes there as it seems). I imagine this will be handled in the logic such that when a collision is detected with one of these boxes the shot power is doubled, but more of that later. Again we see a fairly poorly fitting enemy box on the right, and the red box top left actually represents the roof section of that house which when destroyed reveals a big bad enemy. Note how although the roof is drawn at an angle an aabb is enough to give the impression of shooting it.

There’s one more case I need to cover which is what happens when you want to represent a large object that is irregularly shaped, or an object with multiple destructible parts. Well again they use exactly the same system but simply represent the object as multiple boxes. Each of these boxes when triggered in a collision event will link back to the same object so in essence the object becomes the concatenation of those boxes. For example here we see aa boss with multiple part and an odd shaped enemy:



Ok, so hopefully now you have a good idea of the kind of system we’ll be aiming to recreate. You’ve really got to admire the simplicity of such a scheme and the effectiveness with which it works. It basically means our collision system is going to boil down to only a few techniques which are repeatedly used for everything. Just one last little observation before I move on though. Notice how they’ve taken care to fully represent the width of objects with the aabb’s were as they’re not too concerned about accurately representing the depth. The reason for this being that the player’s bullets generally move in an upward direction and so missed collisions on the outer widths of objects will be much more noticeable than the outer depths. Ok that’s enough of that, its now time for us to get our hands dirty and examine why they’ve done it the way they have and start discussing algorithms.


Offline  
Read August 13, 2008, 03:57:55 PM #1
motorherp

Re: Art Of Collision [part 1] : Gunbird Collision

The significance of AABBs

There are several reasons why aabb’s are a good choice for a game such as Gunbird. For a start they can be represented compactly thus taking up little memory which can be important when so many objects are involved. All that is needed to fully represent an aabb in 2d is 4 values. This can either be a center pos combined with the width and height, or its 4 extreme values, minX (posX – width), maxX (posX + width), minY (posY – height), and maxY (posy + height). We’ll be using the later representation. Although less intuitive it is better for our means later on. The more important reason for aabb’s though is that collision detection between them is extremely quick and easy as I’ll demonstrate:

Code:
struct AABB
{
    int objId; // the id of the object which owns this box
    float vals[2][2]; // the values of the minimum and maximum extremes of the enpoints in each axis

    // vals[0][0] = minX
    // vals[0][1] = minY
    // vals[1][0] = maxX
    // vals[1][1] = maxY
}


bool Collide(AABB boxA, AABB boxB)
{
    if(boxA.vals[1][0] < boxB.vals[0][0]) { return false; }
    if(boxA.vals[0][0] > boxB.vals[1][0]) { return false; }
    if(boxA.vals[1][1] < boxB.vals[0][1]) { return false; }
    if(boxA.vals[0][1] > boxB.vals[1][1]) { return false; }
    return true;
}

(Please note, like I mentioned in my intro, the code is written in a simplistic way for ease of understanding for those not using C++. If you were to implement this you’d want to use const references to the input aabb’s to the function so that the copy constructor isn’t called. Just thought I’d mention it again since this is the first code example I’ve given, please keep it in mind). Ignore the objId in the aabb structure for now I’ll come back to that later, and I apologise for the confusing layout of values but again this is for a purpose later on. What the collision function here is saying is that if the right most extreme of box A is to the left of the left most extreme of box B then they can’t possibly be colliding so it returns false. The same condition applies for all extremes and so all are tested. If it turns out that none of these tests cause the function to exit then the boxes must be intersecting and hence true is returned. You can try this for yourself by drawing aabb’s on paper or getting two playing cards and moving them around relative to each other. As you can see the maths and logic involved is very simple and there are many early exit opportunities which makes the test very quick. You can even squeeze a little extra performance out of this if you know before hand the type of layouts you’ll be dealing with. For example if your play area is deeper than it is wide and your objects are usually more spread out in the vertical direction, then by placing the height tests before the width tests, on average you will drop out of the function quicker.

The real significance of the collision scheme in Gunbird however is that there are aabb’s and nothing but aabb’s. This lets us use a special technique called “sweep and prune” rather than just colliding every box against every other box each frame. I’ll give an overview of the technique first before I delve into specifics to give you a better idea of what we’re trying to achieve. First of all we need to think of our aabb’s a little differently. Rather than a box, think of them as spanning an interval along the x axis between their left most extent to their right most extent, and similarly spanning an interval along the y axis. The problem of colliding all our boxes can now be reduced to two one dimensional problems across each axis. If the intervals of two boxes overlap on both axes simultaneously then they pass all the conditions in the aabb collision test in the code example above and hence they are intersecting. In order to do this we put all our boxes’ x interval endpoints (minX and maxX) into one array and all our y interval endpoints (minY and maxY) into another and sort those arrays so the values are arranged in numerical order. This is where the power of the technique really starts to shine through. We know each frame that each box is only going to move a small amount, and hence re-sorting these arrays each frame is very quick since values only need to check those next to them in the array to see if they need to swap places and these swaps will only happen infrequently. As well as this we know that the collision state of the scene only changes when endpoints do these swaps and so we can completely ignore most of our boxes each frame, only dealing with those corresponding to swaps. By taking advantage of this coherence between frames we have drastically reduced the amount of work we need to perform. It really doesn’t get any faster than this.

So how do we implement this technique? I’ll give you a code dump since that can explain the implementation much more efficiently than I could do with words. Don’t worry; I’ve included plenty of comments which should explain everything you need to know. All the mundane and easy management type stuff I’ll leave for you to fill in though. The best thing is probably to have a quick scan over it and then read the rest of the article before studying it in detail.

Code:
struct Encounter
{
    int objIds[2]; // the id’s of the objects which are colliding
}


struct Endpoint
{
    int type; // 0 = startPoint (min extreme), 1 = endPoint (max extreme)
    int boxId; // id of the box this endpoint belongs to
}


struct SweepAndPrune
{
    Encounter encounters[MAX_ENCOUNTERS]; // a store of encounters this frame
    AABB boxes[MAX_BOXES]; // our boxes
    Endpoint endpoints[2*MAX_BOXES][2]; // our endpoint arrays –> 2 endpoints per box per axis

    int numEncounters; // current number of active encounters
    int numBoxes; // current number of boxes we have

    void Update();
    void ResolveEncounters();

    void AddEncounter(int objIdA, int objIdB);
    void RemoveEncounter(int objIdA, int objIdB);

    int AddBox(int objId, float minX, float maxX, float minY, float maxY);
    void RemoveBox(int boxId);
    void UpdateBox(int boxId, float minX, float maxX, float minY, float maxY);
}



void SweepAndPrune::Update()
{
    // sort lists on each axis
    for(int axis = 0; axis < 2; axis += 1)
    {
        // go through each endpoint in turn
        for(int j = 1; j < numBoxes*2; j += 1)
        {
            int keyType = endpoints[j][axis].type;
            int keyBoxId = endpoints[j][axis].boxId;

            // get the min val if this is a startPoint else get the max val
            float keyVal = boxes[keyBoxId].vals[keyType][axis];

            // Compare the keyval to the value one before it in the array (our comparison value) and swap places if need be.
            // Keep doing this until no more swaps are needed or until we reach the start of the array
            int i = j-1;
            while(i >= 0)
            {
                // get our comparison value in the same way we got the key value
                int compType = endpoints[i][axis].type;
                int compBoxId = endpoints[i][axis].boxId;
                int compVal = boxes[compBoxId].vals[compType][axis];

                if(compVal < keyVal)
                {
                    // these values are in the correct order so break out of this while loop
                    break;
                }

                // these vals are swapping places which relates to a change in the state of the scene
                // so update our encounter list accordingly

                // if and endpoint is swapping to the left on a startpoint then we know these objects are leaving contact
                // so remove any encounters relating to these objects
                if((compType == 0) && (keyType == 1))
                {
                    RemoveEncounter(compBoxId, keyBoxId);
                }
                else
                {
                    // else if a startpoint is swapping to the left of an end point, these object might be colliding
                    if((compType == 1) && (keyType == 0))
                    {
                       // this only tells us that they overlap on one axis
                        // to be sure of collision we must do an intersection test
                        if(Collide(boxes[compBoxId], boxes[keyBoxId]))
                        {
                            AddEncounter(compBoxId, keyBoxId); // these AABBs now intersect
                        }
                    }
                }

                // finaly we must swap the points
                endpoints[i+1][axis].type = compType;
                endpoints[i][axis].type = keyType;

                endpoints[i+1][axis].boxId = compBoxId;
                endpoints[i][axis].boxId = keyBoxId;

                // we must decriment i so that we continue searching down the array
                i -= 1;
            }
        }
    }
}



void SweepAndPrune::ResolveEncounters()
{
    // Iterate through your encounter list and trigger collision resolution code
    // for each pair of objects in there
}


void SweepAndPrune::AddEncounter(int objIdA, int objIdB)
{
    // Add encounter between the inputted objects to the list
    // being careful not to duplicate existing ecounters
}


void SweepAndPrune::RemoveEncounter(int objIdA, int objIdB)
{
    // Remove encounter between the inputted objects from the
    // list if it exists
}


int SweepAndPrune::AddBox(int objId, float minX, float maxX, float minY, float maxY)
{
    // I'll fill this one out since it shows how to set up the various structures

    // add box
    boxes[numBoxes].objId = objId;
    boxes[numBoxes].vals[0][0] = minX;
    boxes[numBoxes].vals[0][1] = minY;
    boxes[numBoxes].vals[1][0] = maxX;
    boxes[numBoxes].vals[1][1] = maxY;

    // add endpoints
    endpoints[2*numBoxes][0].type = 0;
    endpoints[2*numBoxes][0].boxId = numBoxes;
    endpoints[2*numBoxes+1][0].type = 1;
    endpoints[2*numBoxes+1][0].boxId = numBoxes;
    endpoints[2*numBoxes][1].type = 0;
    endpoints[2*numBoxes][1].boxId = numBoxes;
    endpoints[2*numBoxes+1][1].type = 1;
    endpoints[2*numBoxes+1][1].boxId = numBoxes;
    // note that its not important to insert these in their correct sorted value position
    // as I havn't since the next call to Update() will sort that out for us.

    numBoxes += 1;

    // return the id of this box so that objects know which box to update when they move
    return numBoxes-1;
}


void SweepAndPrune::RemoveBox(int boxId)
{
    // Remove the box with the corresponding id being careful to remove all its
    // endpoints as well as any encounters relating to this boxes object
}


void SweepAndPrune::UpdateBox(int boxId, float minX, float maxX, float minY, float maxY)
{
    // Replace the vals of the box with the inputted boxId
    // Whenever an object moves it should call this to update its collision box(es)
    // Each object will know which boxId to pass in since it should store the boxId value
    // returned when AddBox() is called.
}

So the general idea here is that as objects such as enemies, power-ups, and bullets are created, they add their collision aabb’s to the sweep and prune system and store the returned box ids. Each frame, after each object updates its position it also updates the collision box in the sweep and prune system using the stored id. Once all objects have finished, the sweep and prune Update() method is then called which works out all collision encounters. You then call the ResolveEncounters() method which will call the collision resolution code for each pair of colliding objects that frame for you to respond to as you wish. As you can see, once implemented the system becomes very simple to use and is very ‘black box’, i.e. we can interface with it and use it without really having to worry about what goes on inside. Because of this you should be able to re-use this system to quickly get collision detection and management running in any of your future projects as well as this one.

As a quick aside, the sharp minded amongst you are probably asking, “If the sort method on each axis is used to detect the collisions, then why is there a call to an explicit collision function in there?” Well the reason is that we can only be sure there is a collision when the box intervals overlap simultaneously on both axes like I mention above. Now we could try and be clever and implement some sort of method with counts and keeps track of end swaps and overlaps on each axes for each object so that we can detect when this is the case. However given the simplicity of the explicit collision test you’ll likely find using a clever technique gives no speed advantage and hence we might as well keep it simple and use the explicit test to check for this when we need to. The reason the interval sorting gives us such a performance boost is not because it completely replaces the explicit test, but severely reduces the number of times we need to call it.

Note that the above code is the simplest implementation I could give so that you can focus on the important elements without getting bogged down by the details. There’s no error checking or anything like that for a start which you should definitely include for yourself. This means that there’s plenty of room for improvements. Here are some ideas:

Many encounters that are reported you’ll no doubt be uninterested in such as enemy bullets colliding with each other etc. Remember the attribute flagging I talked about in the first section where each box was given a colour? Well if you give each aabb an additional member which stores its type, such as player, power-up, ground enemy, etc, then you could implement a collision map. This will simply be a little matrix which stores a yes/no value for each object type when cross referenced with another object type. Then in the sweep and prune Update() method, just before the collision test is performed when endpoints swap position, you can check the collision map to see if this is something you’re interested in reporting. If not then simply assume the collision test returns false without performing it. Not only will this remove those encounters you’re not interested in it will also give you a performance boost.

Secondly you’ll find that encounters keep getting reported for as long as two objects are in contact. This is likely not the type of behaviour you want, or at least you want the option to ignore this after the first report. For example, in Gunbird when you collide with a flying enemy it powers you down one level but neither you nor the enemy is destroyed. In such a system this collision will get reported every frame and you’d very quickly power down to the minimum level rather than just loosing the one. To give a bit more flexibility on how you want to respond to collisions I recommend you double buffer the encounter list. By comparing the current encounter list with the last frame’s you’ll be able to report events only at the time of first collision as well as time of first leaving collision if you so desire. You can then have objects query the sweep and prune system each frame if they wish to know about continuous collisions. Keep in mind though that when swapping buffers we can’t just discard the contents like we do with a render buffer for example, since these results are important. After all, the reason we get continued reporting of encounters is not because they are redetected each frame, in fact the collision is only detected once when the initial endpoint swap that puts it in a colliding state takes place. Rather the encounters simply aren’t removed from the encounter list until a separation event is detected. Therefore it’s probably easier if the sweep and prune works on the same current frame buffer each frame rather than swapping buffers, but at the start of the Update() function you copy the buffer to a separate buffer for comparison purposes.

Another area which will likely need to some extra thought is when adding and removing objects since this will happen fairly frequently. Although this can be handled nicely for the box arrays since we don’t need a continuous array and can instead track empty slots, there is the seemingly unavoidable situation that removals will need to be made in the interior of the endpoint arrays (note that insertions can be avoided by tagging additions onto the end and letting the update method sort it out). This kind of stuff can hit you pretty hard if not handled well since you’ll be copying memory around all over the place to create space for taking out gaps for removals. You can limit the damage caused by storing desired endpoint removals in separate arrays until you’ve collected them all for that frame and then do the work in one big batch so that this array shuffling only happens once a frame for any frame were removals are requested. Alternatively you could try replacing the endpoint arrays with linked lists which will solve this problem but in general are slower to traverse (I don’t really recommend this). If you do though then I suggest implementing your own linked list class which allocates itself a block of continuous memory to work with at initialisation so you don’t thrash the cache. There is however a rather sneaky alternative I’ve thought of. When you wish to remove a box, set all of the box vals to a high value off the edge of your playing area (eg 1e22f) and set the box type to one you’ve created specifically for this purpose that has no positive entries in the collision map. What happens now is that after the next Update call, all the endpoints you wish to remove will get pushed to the end of the arrays without triggering any collision tests or generating encounters and removing them simply becomes a matter of looking at the last entries in the arrays and popping them off the end if they has this special box type (or decrementing your numEndpoints counter if you don’t use stl – note that number of boxes and number of endpoints will need to be tracked separately). This way no separate memory shuffling is required at all, it becomes a natural process of the algorithm. Ingenious Cheesy.

Lastly a short and special note for c++ users. If you wish to implement this for yourself, there’s much better ways to do it than I have here by using c++ style functionality. Again remember that I’ve kept it simple and c++ free like this on purpose. You should bare in mind that stl is your friend. There’s lots of members in that code that would be much better implemented as vectors or lists, not to mention that you can put the built in stl sorting algorithms to good effect. Also instead of linking back to objects through ids for the encounter resolution phase you may want to inherit all your objects from a common base class with pure virtual functions built in to handle these complications for you.
« Last Edit: August 13, 2008, 03:59:59 PM by motorherp »

Offline  
Read August 13, 2008, 04:00:10 PM #2
motorherp

Re: Art Of Collision [part 1] : Gunbird Collision

Limitations

Ok last section I promise. I was going to give a pretty in depth discussion of the limitations of such a system but this tutorial is really starting to get long so instead I’ll keep it brief (maybe I’ll go into this in detail in another tutorial). As you can probably imagine, the main limiting factor here is that the system can only handle aabb’s. Depending on what you want to do you might find this gets very restrictive. For example, although you can get away with using aabb’s for small circles, as the circles grow this becomes increasingly difficult. Large explosions or boss style charged plasma bolts etc you have to dodge which you can find in quite a few games become almost impossible to represent in this system. Beam weapons will require many boxes strung together and if they shoot at angles their collision will be irregular along their length. Any long or narrow object that rotates and also articulated bodies will be very awkward to implement. If you want collidable scenery you’ll be restricted to blocky shapes. This will be especially noticeable if it’s the type the player can slide along without being destroyed. Etc etc.

There are ways around these issues by introducing new shapes whilst keeping such a system as described above but they all involve quite a bit of extra complication and begin to destroy the elegance and efficiency of the system. I’ve thought about the issue quite a bit and although the above system is often employed as an initial pass which leads onto a more complex system (I use the same technique professionally) this is usually implemented to deal with much more complex scenes than we will face in shmups. Given the scenarios we’re likely to encounter I have to conclude that it isn’t really worth it. Instead if you need it I recommend implementing an entirely different system with more flexibility built in, and in fact this will be the subject of future tutorials in this series, so stay tuned.

Let me wrap this up with a few final words. What we have here is a very elegant and efficient collision system which should be sufficient for many shoot em up games, including some professional ones as we’ve seen. It has its limitations, but as a rule I say if you can get away with using it I really recommend you do so. In particular this system deals extremely well with situations were we have to collide two very large groups of objects with each other, such as when the player is allowed to shoot a hail of enemy bullets out of the sky with a rapid firing weapon, although in most shmups we only have to deal with fairly linear collision detection.


Anyway, I really hope you enjoyed this tutorial and learned something from it. If you spot any errors, have any suggestions, or simply want to ask questions or discuss anything I’ve mentioned, then please don’t hesitate to contact me. (If you go to the Training Grounds section of the forum of this website you'll see a thread I've set up for such a purpose).

Good luck with your own projects.

Dan.


Offline  
Read August 14, 2008, 07:13:33 PM #3
motorherp

Re: Art Of Collision [part 1] : Gunbird Collision

[reserved]


Offline  
Read August 14, 2008, 07:35:01 PM #4
motorherp

Re: Art Of Collision [part 1] : Gunbird Collision

You can find previous replies to this tutorial posted in the following thread:

http://www.shmup-dev.com/forum/index.php?topic=1076.0

That topic has now been locked.  Please continue any discussions or add any further questions in this thread.  Many thanks.


Offline  
Read September 04, 2009, 02:57:17 PM #5
Korenn

Re: Art Of Collision [part 1] : Gunbird Collision

I've run into a performance wall using this method:

When adding a 100 or so new bounding boxes in a single frame (think boss bullet-stream), the bubble sort in the list update will then take way too long (several draw frames get dropped). how should I approach this?

try and do some sort of block insertion in the endpoint list at the right place?
Offline  
Read September 05, 2009, 04:58:31 AM #6
Hornet600S

Re: Art Of Collision [part 1] : Gunbird Collision

I would address this that way:

1. keep an additional array large enough to hold the maximum amount of colliders that can be added per frame.

2. when adding new colliders in a frame then don't add them directly to the end of the "normal" array, but take the above.

3. when it comes to the Update() method then do the following before the bubble-sort:

3.1. do a quick-sort on the add-array. Asuming that those objects are totally unsorted quick-sort should perform well.

3.2. take the first new object (which is now sorted as being the "smallest") and check where it would fit in the normal collider-array. Do a binary search for this. You can stop early maybe if the search-sub-array becomes small enough, since the full list is later resorted by the bubble-sort anyway. Just get a rough "good" position.

3.3. do the same for the last new object, but don't start with the array-range [0..NUM_COLLIDERS-1] but use [(found_index_in_3_2+1) - NUM_COLLIDERS-1] instead (remember, it's already sorted to be the largest of your new objects, so no way it will ever be inserted BEFORE found_index_in_3_2+1).

3.4. now you got 2 indices representing the sub-array-bounds were all your new objects should be inserted.

3.5. do the same for the remaining new objects, always taking one from "the left" and one from "the right" while always decreasing the potential target bounds until you got indices for all your new objects.

4. now to actually INSERT your objects in the array do the following:

4.1. start from the right with the last new object and step down to the first.

4.2. you know how many objects you are going to insert. This means the objects after the target-index for your last object have to be memmoved (sizeof(collider-struct)*(number_of_new_colliders)) bytes to the right, because during the insertion process (number_of_new_colliders) colliders will be inserted.

4.3. do that memmove.

4.3. decrease number_of_new_colliders by 1.

4.4. write your current last new object to (target_index+ number_of_new_colliders), exactly before the memmoved other colliders.

4.5. do the same thing for all the remaining colliders. The key is this way you have the perfect amount of memmoves necessary to insert the new objects, because you are creating large gaps for the remaining memmoves.

5. when done, do the normal update method with its bubble-sort.

Note 1: I'm asuming that the "normal" array is preallocated to hold the maximum amount of colliders allowed. Otherwise the memmove will crash.

Note 2: Perhaps it's faster to do the binary search exactly (no "rough" early stop) and do the bubble-sort before adding, so it runs on a smaller array.

I hope it's clear enough... Kind of difficult to explain.
« Last Edit: September 05, 2009, 05:11:02 AM by Hornet600S »

"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read September 05, 2009, 07:50:06 AM #7
Korenn

Re: Art Of Collision [part 1] : Gunbird Collision

No, that's clear enough, thanks Grin I didn't think about using an approximate binary search to find the insertion point, that should indeed help things along.

But the elaborate pre-sorting seems unnecessary since large amounts of newly added bounding boxes in a single frame tend to be bullets from emitters, and thus start with the same coordinates. This reduces the problem to finding a single insert point for the min endpoints and one for the max endpoints (for each axis, ofcourse).

The only problem with a manual insert like this is that if a valid collision box exists at the spawning coordinates, an encounter is not established. A manual encounter detection is possible, but would require a linear search of the insertion points (to keep track of min-max pairs). Or I'll just have to make sure this can't happen  Smiley


[Update]
Well it's been implemented and it works like a charm. My solution is in C#, so memcpy is out of the question but there is a way to copy from array to array. In the end I'm using two parallel endpoint arrays and copy from one to the other, and then afterwards pageflip the reference being sorted.

But now that insertions are silky smooth, I noticed that similar hitches occur at the end of the bounding box life time. Turns out that setting the value to max and then letting it bubble out is just too slow if a bunch of bounding boxes get deleted in one frame. So I'm solving that by instead introducing a new endpoint type (-1), setting unused endpoints to that, and doing a once over pass before the sort that removes the unused endpoints alltogether. The sort runs over a smaller array, the remove action is O(n) and all is good in the end \o/
« Last Edit: September 05, 2009, 12:08:30 PM by Korenn »
Offline  
Pages: [1]   Go Up
Jump to:  

Page created in 0.166 seconds with 19 queries.