Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Collision Detection crashes SOMETIMES

Credits go to Edgar Reynaldo and ph03nix for helping out!
This thread is locked; no one can reply to it. rss feed Print
Collision Detection crashes SOMETIMES
AmnesiA
Member #15,195
June 2013
avatar

I've deleted my old thread on the same topic because it had 0 replies and I've been doing a lot of testing with my program to get the problem to arise again, so I think it will be easier to help me this time. Here's what I've found out:

{"name":"trHMr8i.jpg","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/6\/96bff340e81e0945d979ba811d43d910.jpg","w":1975,"h":1358,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/6\/96bff340e81e0945d979ba811d43d910"}trHMr8i.jpg
Since it's kind of small on these forums, here are what the captions read from left to right, top to bottom:
"What's supposed to happen: Other plane explodes, you lose health" | "Bad: Tail bounding boxes do not recognize eachother" | "Bad: rear side of wings do not recognize eachother"
"Moving left wing-to-wing causes crash" | "Moving up left wing to right wing causes crash, right side does not do this" | "Moving left with a NEAR collision (enemy plane is not moving) causes crash"

Alternatively you can just view the image at imgur.

This is a screenshot of the bounding boxes drawn around the objects. It seems to only be Character left side to Enemy right side that causes problems. It was harder to get the error to occur in debug mode for some reason (and also explosion animations don't work in debug mode - weird) but I finally got it while driving left straight against an enemy, wing-to-wing.

Just before the error occurs, the error flags on line 42 of object.cpp. The call stack looks like this:

0 00404070 OBJECT::get_x(this=0xfeeefeee) | object.cpp ln 42
1 00404AA4 ROOM::step(this=0x5ea370) | room.cpp ln 81
2 00403BFA game_loop() | main.cpp ln 129
3 00403D6F main(argc=1, argv=0x3015d0) | main.cpp ln 204

Those pieces of code are as follows:
object.cpp

int OBJECT::get_x(){
    return x; //LINE 42!!!
}

room.cpp

#SelectExpand
57void ROOM::step(){ 58 for( OBJECT* i : activeInstances){ //Let each object perform step operation 59 i->step(); 60 } 61 for( auto it = activeInstances.begin(); it != activeInstances.end(); ){ //Delete dead instances 62 if( (*it)->is_dead()){ 63 (*it)->on_death(); //NEW LINE 64 it = activeInstances.erase(it); 65 }else{ 66 it++; 67 } 68 } 69 70 //Create enemies 71 if( rand() % 90 == 1){ 72 instance_create( "objEnemyOlive"); 73 } 74 75 //Collision detect 76 float obj1x, obj1y, obj2x, obj2y; 77 for( auto it1 = activeInstances.begin(); it1 != activeInstances.end() - 1; ++it1){ //Iterator for object 1 78 obj1x = (*it1)->get_x(); 79 obj1y = (*it1)->get_y(); 80 for( auto it2 = it1 + 1; it2 != activeInstances.end(); ++it2){ //Iterator for object 2 81 obj2x = (*it2)->get_x(); //LINE 81!!! 82 obj2y = (*it2)->get_y(); 83 for( RECTANGLE &obj1bb : (*it1)->bb){ //Reference to object 1's bounding box 84 for( RECTANGLE &obj2bb : (*it2)->bb){ //Reference to object 2's bounding box 85 if( obj1x + obj1bb.x1 < obj2x + obj2bb.x2 && obj1x + obj1bb.x2 > obj2x + obj2bb.x1 && 86 obj1y + obj1bb.y1 < obj2y + obj2bb.y2 && obj1y + obj1bb.y2 > obj2y + obj2bb.y2){ //DOES COLLIDE 87 (*it1)->collide( *it2); 88 } 89 } 90 } 91 } 92 } 93}

main.cpp game_loop()

if(event.type == ALLEGRO_EVENT_TIMER){
    redraw = true;
    roomLib.allRooms[currentLevel].step(); //LINE 129!!!
}

The portion of code in ROOM::step that is causing the error is the collision detection portion. For some reason, the second instance that is called for collision testing is throwing the error when its x value is trying to return but this only happens DURING a collision which seems strange because these values are called every single step but only during a collision the object does not want to give up its x value (it doesn't want to die!).

It's not an issue with the array activeInstances changing sizes and accidentally accessing an element out of bounds because in that case it would happen for every collision and, additionally, no elements are deleted from the array during this phase, they are only flagged for deletion by setting their boolean variable <code>dead</code> to true.

Edit: I didn't realize I was changing the size of the vector by creating the explosion object. I've altered the code so that all OBJECTs now have a void OBJECT::on_death(); function that creates the explosion. I've updated the ROOM function above and commented it with //NEW LINE. Unfortunately, this has not eliminated the error.

For reference, here are the functions called by the collision checking:

int OBJECT::get_x(){
    return x;
}

int OBJECT::get_y(){
    return y;
}

#SelectExpand
1void CHARACTER::collide( OBJECT* objOther){ 2 switch( objOther->get_object_id()){ 3 case idEnemyOlive: 4 score += 5; 5 roomLib.allRooms[currentLevel].instance_create 6 ( 7 "objExplosionSm", objOther->get_x(), objOther->get_y() 8 ); 9 objOther->kill(); 10 hp -= 20; 11 break; 12 } 13} 14 15void BULLET::collide( OBJECT* objOther){ 16 switch( objOther->get_object_id()){ 17 case idEnemyOlive: 18 score += 10; 19 roomLib.allRooms[currentLevel].instance_create 20 ( 21 "objExplosionSm", objOther->get_x(), objOther->get_y() 22 ); 23 objOther->kill(); 24 kill(); 25 printf( "%i\n", score); 26 break; 27 } 28} 29 30void ENEMY_OLIVE::collide( OBJECT* objOther){ 31 switch( objOther->get_object_id()){ 32 case idBullet: 33 score += 10; 34 objOther->kill(); 35 roomLib.allRooms[currentLevel].instance_create( "objExplosionSm", x, y); 36 kill(); 37 break; 38 case idCharacter: 39 score += 5; 40 hp -= 20; 41 kill(); 42 break; 43 } 44}

Code called by the collide functions:

int OBJECT::get_object_id(){
    return objectId;
}

void OBJECT::kill(){
    dead = true;
}

And last but not least:
globals.h

enum OBJECT_IDS{
    idObject, idCharacter, idIsland, idExplosionSm, idExplosionLg,
    idBullet, idEnemy, idEnemyOlive
};

=======================
Website
My first game!

Edgar Reynaldo
Member #8,592
May 2007
avatar

Dang there's a lot of code there. BUT, the first thing I saw is this :

AmnesiA said:

0 00404070 OBJECT::get_x(this=0xfeeefeee) | object.cpp ln 42

Make special notice of the address 0xfeeefeee. It's one of the magic addresses compilers use in debugging mode to mark uninitialized memory. Another is 0xdeadbeef. You probably have an uninitialized pointer somewhere that you added to your vector of OBJECT*.

And I'm curious how you deleted your old thread. I love it when people say that, when only the Supreme Loser and his minions have the power to do that. :D

AmnesiA
Member #15,195
June 2013
avatar

Yeah, I actually had PLANNED to delete my old thread after posting the new one only to find out that I can't actually delete it, so I just edited it to point to this thread. Sorry!

As for my issue, I edited my above post to reflect that I realized that I was ADDING an OBJECT* to the activeInstances vector but fixing THAT issue did not solve my problem.

=======================
Website
My first game!

Edgar Reynaldo
Member #8,592
May 2007
avatar

The backtrace is still the same? Then you are still adding an uninitialized pointer to your vector or accessing it somewhere else.

I can't tell where it is in ROOM::step() because you don't have the line numbers lined up properly. Use a start="#" attribute inside your code tag to change the starting line number of the displayed code.

So, what is line 80 of room.cpp?

AmnesiA
Member #15,195
June 2013
avatar

I've added the start=# i didn't know about that, instead I just commented the line :P The error now occurs on line 81 because of the line I added in ROOM::step() ((*it)->on_death();)

It may also be worth noting that I can also get a crash when a bullet collides with an enemy plane if the bullet registers its collision after it reaches the back of the left side of the wing bounding box.

=======================
Website
My first game!

Edgar Reynaldo
Member #8,592
May 2007
avatar

AmnesiA
Member #15,195
June 2013
avatar

That's what I was thinking too but the only place in the code that things are added to the vector is:

#SelectExpand
10OBJECT* ROOM::instance_create( const char* object_type, //TO DO: rearrange vector so 11 float arg1, float arg2, float arg3, //objects draw correctly, lower objects 12 float arg4, float arg5, float arg6){ //at the beginning of the vector 13 if( strcmp( object_type, "objCharacter") == 0){ 14 newObject = new CHARACTER(); 15 }else if( strcmp( object_type, "objIsland") == 0){ 16 newObject = new ISLAND(); 17 }else if( strcmp( object_type, "objBullet") == 0){ 18 newObject = new BULLET(); 19 }else if( strcmp( object_type, "objExplosionSm") == 0){ 20 newObject = new SM_EXPLOSION(); 21 }else if( strcmp( object_type, "objExplosionLg") == 0){ 22 newObject = new LG_EXPLOSION(); 23 }else if( strcmp( object_type, "objEnemyOlive") == 0){ 24 newObject = new ENEMY_OLIVE(); 25 }else{ 26 exit(1); 27 } 28 newObject->init( arg1, arg2, arg3, arg4, arg5, arg6); 29 30 //Time to find out where this fits in according to depth 31 if( activeInstances.size() == 0){ //If no instances exist, use push_back 32 activeInstances.push_back( newObject); 33 }else if( newObject->get_depth() <= activeInstances.back()->get_depth()){ //If the new element is the closest already 34 activeInstances.push_back( newObject); 35 }else{ 36 for( auto it = activeInstances.begin(); it != activeInstances.end(); ++it){ //Find the first element that is further back 37 if( newObject->get_depth() >= (*it)->get_depth()){ 38 activeInstances.insert( it, newObject); 39 break; 40 } 41 } 42 } 43 44 return newObject; 45}

So I don't think it's an uninitialized pointer. I haven't been able to find information with my usual resource, google, on whether or not I can change the size of a vector inside a range based for using that vector. I suppose it comes down to whether or not the vector's size is checked on each iteration or if it's just checked at the beginning.

=======================
Website
My first game!

ph03nix
Member #15,028
April 2013
avatar

Maybe in this case it sometimes doesn't insert into the vector?

for( auto it = activeInstances.begin(); it != activeInstances.end(); ++it){ //Find the first element that is further back
    if( newObject->get_depth() >= (*it)->get_depth()){
        activeInstances.insert( it, newObject);
        break;
    }
}

perhaps try this and see if it prints:

bool inserted = false;
for( auto it = activeInstances.begin(); it != activeInstances.end(); ++it){ //Find the first element that is further back
    if( newObject->get_depth() >= (*it)->get_depth()){
        activeInstances.insert( it, newObject);
        inserted = true;
        break;
    }
}
if(!inserted) cout<<"ERROR\n";

AmnesiA
Member #15,195
June 2013
avatar

I don't think that's possible unless it's due to some error that it doesn't get inserted because the loop before it checks if the depth is <= the last object in the vector and if it's not then it goes into the for loop to find out where it belongs.

Even if for some bizarre reason the object isn't inserted like it should be, I just wouldn't have any way to access that object, it wouldn't cause an error. I'll add a catch just to be safe when I'm back at my computer though.

=======================
Website
My first game!

ph03nix
Member #15,028
April 2013
avatar

why don't you print the memory addresses of activeInstances or look at them through your debugger to see if any of them are invalid

also, are the explosions added to activeInstances?

AmnesiA
Member #15,195
June 2013
avatar

Yes the explosions are added to activeInstances and deleted once their animation completes.

=======================
Website
My first game!

Edgar Reynaldo
Member #8,592
May 2007
avatar

I still can't see why there is an uninitialized pointer in your vector, but you have a memory leak here :

room.cpp#SelectExpand
61 for( auto it = activeInstances.begin(); it != activeInstances.end(); ){ //Delete dead instances 62 if( (*it)->is_dead()){ 63 (*it)->on_death(); //NEW LINE 64 it = activeInstances.erase(it); 65 }else{ 66 it++; 67 } 68 }

You need to call delete (*it); before you remove it from the vector or else your handle disappears and you can never free it.

instance_create is really the only place you add OBJECT* to your activeInstances vector?

Okay - I think I'm getting closer. When two objects collide, you call instance_create to create an explosion. This changes the contents of the vector and invalidates any iterators currently pointing to it. So then when it returns into the doubly nested for loop in ROOM::step, it accesses an invalidated iterator pointing to memory that is no longer in use by the vector.

To solve this problem, use another vector to store all the objects you will add to the activeInstances vector, say addInstances. Then when you're done with collision checking, merge the addInstances vector with the activeInstances vector, and then clear the addInstances vector.

I think that should solve your problem, or at least get you closer to a functioning program.

And by the way, when the vector's size is 0, vec.end() - 1 does not equal vec.end(), nor will you ever reach it by incrementing your iterator from begin().

AmnesiA
Member #15,195
June 2013
avatar

Ahhh, I forgot that adding elements to a vector invalidates iterators. I'll fix that first thing tomorrow. Any idea why those overlapping bounding boxes aren't registering a collision though?

=======================
Website
My first game!

Edgar Reynaldo
Member #8,592
May 2007
avatar

AmnesiA
Member #15,195
June 2013
avatar

It looks like a bug here :
&& obj1y + obj1bb.y2 > obj2y + obj2bb.y2){ //DOES COLLIDE
You're checking if the bottom of 1 is greater than the bottom of 2 but you should be checking against the top of 2.

Edit
Little tidbit of wisdom regarding 0xfeeefeee

Wow most helpful post of all time. I can't believe I missed that obj2bb.y2 was supposed to be y1... so dumb and so easy. That page with all the memory bit patterns is also SUPER helpful. I didn't realize memory addresses could be helpful to me for anything other than comparison. Thank you!

=======================
Website
My first game!

Edgar Reynaldo
Member #8,592
May 2007
avatar

AmnesiA
Member #15,195
June 2013
avatar

Yes everything is working great now. I was adding to the vector inside a loop trying to iterate through the vector so sometimes an object would take 2 steps where it was supposed to take 1 and on rare occasions it would even crash the game. I just created a separate vector called instancesToCreate which holds all of the instances created that step and then at the end of the step I call void ROOM::activateInstances() and that moves all of the contents of instancesToCreate into activeInstances and everything works perfectly.

That collision detection thing was big too :P Thank you again!

=======================
Website
My first game!

Go to: