Welcome, Guest. Please Login or Register.  • Help
SMF Underground
+ SHMUP-DEV » SHMUP DEV FORUMS » Assistance
|-+ Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

Pages: [1]   Go Down
0 Members and 1 Guest are viewing this topic. Topic Tools  
Read August 24, 2011, 01:18:13 PM #0
CrazyFoo

Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

Dear shmup dev community, long time reader first time poster Lloyd Crazyfoo here. Thanks to the excellent tutorials on the site I hatched a plan to make my first shmup by integrating the gunbird-inspired collision management system by Motoherp and the bullet/entity management system by Hornet into an existing basic 2d engine I have concocted. After some teeth gnashing and some playing around with the code systems I have something that is as follows shortly, however collisions very rarely seem to 'register' like they should, and it seems it isn't down to the lack of a dynamic system as even if I use large AABBs to test this there is still no luck.

Entity Management as follows - based largely on Hornet's code from his tutorial:

Code:
//EntityManager.h - this is the interface for the new entity manager class - this is a custom container class that
//can be used to keep tabs on enemies, bullets, whatever. All entities are handled in this class, and all of them
//are updated from this class too the internals use a statically sized array of entities and a statically sized //array of 'indexes' to make it like a linked list
//LAST UPDATE - 23/08/11

#pragma once

#include "Behaviour.h"
#include "Movable.h"
#include "Rect.h"
#include "Sprite.h"
#include "CollisionManager.h"

namespace Advanced2D
{

//The entity struct - contains its own sprite for appearance, position data. Also a 'movable' class for            
        //velocity and direction, a member to show if it is 'active' or not, the 'type' of entity it is determined
        //by the client application and also a Rect to represent a bounding box for collision

struct Entity
{
public:
Movable movement;
Sprite sprite;
bool active;
Behaviour* behaviour;
unsigned int id;
Rect AABB;
unsigned int type;

Entity() {};

//update calls the function that is passed in/or set as a behaviour
void Update()
{
if(!behaviour->Update(this))
{
active = false;
}
}

//sets the behaviour to be called in the update;
void SetBehaviour(Behaviour* behaviour) {this->behaviour = behaviour;}
};


//The actual class itself

class EntityManager
{
public:
//constructor/destructor
EntityManager(int maxEntities);
virtual ~EntityManager();

//Creates an entity, returns the id given to the calling code
unsigned int CreateEntity(Entity& description,bool hasBox = true);

//updates all the arrays and entities contained within
void Update();

//Gets the entity referenced by the object id
Entity& GetEntity(unsigned int id);

//Draws all entities in the entitymanager
void Draw(bool drawRects);

//Sets the collision handler to manage all the AABBS of contained entities
void SetCollisionHandler(CollisionManager* handler) {collisionHandler = handler;}

private:
Entity* entities; //array of entities
CollisionManager* collisionHandler; //the collision handler for aabbs
unsigned int* idToIndexTable; //used to make it a linked list
unsigned int activeEntityCount; //amount of current active entities
unsigned int nextFreeIdSlot; //next free id slot to be used
unsigned int MAX_ENTITIES; // max number of entities
Sprite* box; //a box sprite for debug collision info
};
}

//Constructor - takes a max number of entities to be handled
EntityManager::EntityManager(int maxEntities) :
        entities(NULL), idToIndexTable(NULL), nextFreeIdSlot(0), activeEntityCount(0), MAX_ENTITIES(maxEntities)
{
//create the array of entities and id table
entities = new Entity[MAX_ENTITIES];
idToIndexTable = new unsigned int[MAX_ENTITIES];


//initialise the indexes in the table
for(unsigned int t = 0; t <  MAX_ENTITIES; ++t)
idToIndexTable[t] = t + 1;

//create the box sprite, assign the texture
box = new Sprite;
box->LoadImg("hilight.tga");
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Destructor
EntityManager::~EntityManager()
{
//delete the two statically sized arrays
delete [] entities;
delete [] idToIndexTable;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Create an entity and pass the obj id back to the calling code
//for use for look up later. It takes in a 'description' of the entity as an argument
//that dictates its behaviour/type etc. It also takes a bool to say if this is a collidable
//entity or not

unsigned int EntityManager::CreateEntity(Entity& description,bool hasBox)
{
 //Take a reference to the next free entity slot
 Entity& l_new_entity = entities[activeEntityCount];

 //assign the passed in description
 l_new_entity = description;

 //make sure it is active
 l_new_entity.active = true;

 //get an id using the next free id slot
 unsigned int id = nextFreeIdSlot;
 l_new_entity.id = id;

 // we update the next free id slot for use by the next entity
 nextFreeIdSlot = idToIndexTable[id];

 //set the id in the index table to the next one to be used
 idToIndexTable[id] = activeEntityCount++;

 //if there is a need for an aabb - create it and add it to the collision manager
 if(hasBox)
 {
 int left   = l_new_entity.sprite.GetX() + l_new_entity.AABB.vals[0][0];
 int right  = left + l_new_entity.AABB.vals[1][0];
 int top    = l_new_entity.sprite.GetY() + l_new_entity.AABB.vals[0][1];
 int bottom = top + l_new_entity.AABB.vals[1][1];

 //also add the box to the collisionHandler if there is a collision box
 l_new_entity.AABB.vals[0][0] = left;
 l_new_entity.AABB.vals[1][0] = right;
 l_new_entity.AABB.vals[0][1] = top;
 l_new_entity.AABB.vals[1][1] = bottom;

 //add the box to the collision handler - assign the returned box id for later use
 //for lookup/removal
 l_new_entity.AABB.boxID = collisionHandler>AddBox(l_new_entity.id, left, top, right,  
                                                                            bottom,l_new_entity.type);
 }

  return id;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//Update - this updates all of the the entities contained in the main array, updates the main array by
//sorting out any 'inactive' entities and finally update the the associated aabbs
void EntityManager::Update()
{
//index used for going through the array of entities
unsigned int l_new_index = 0;

//go through all the currently active entities
for(unsigned int t = 0; t < activeEntityCount; ++t)
{
//get a ref to the current entity being perused
Entity& l_entity = entities[t];

//take the xpos
int xPos = l_entity.sprite.GetX();
int yPos = l_entity.sprite.GetY();

//call the update code
l_entity.Update();

//take new x/y pos
int xDiff = l_entity.sprite.GetX() - xPos;
int yDiff = l_entity.sprite.GetY() - yPos;

//use the above to update its AABB accordingly
l_entity.AABB.vals[0][0] += xDiff;
l_entity.AABB.vals[1][0] += xDiff;
l_entity.AABB.vals[0][1] += yDiff;
l_entity.AABB.vals[1][1] += yDiff;


//use the new data to update this entity's box
collisionHandler->UpdateBox(l_entity.AABB.boxID, l_entity.AABB.vals[0][0],              
                                                    l_entity.AABB.vals[0][1], l_entity.AABB.vals[1][0],
                                                    l_entity.AABB.vals[1][1]);
      
//if the entity is active update it's position in the array
if(l_entity.active)
{
 if(t != l_new_index)
 {
// if a bullet was destroyed before adjust the index-tables
// and move the bullet down in the array accordingly.

entities[l_new_index] = l_entity;
idToIndexTable[l_entity.id] = l_new_index;
 }

 ++l_new_index;
}
else
{
 // when a bullet is removed we have to "fix" the free-IDs-pseudo-linked-list.
 // that's easy: we just let the bullet's slot point to the known next free ID
 // which we stored during bullet creation...

 idToIndexTable[l_entity.id] = nextFreeIdSlot;

 //also remember to remove it's box from the collisionHandler
 collisionHandler->RemoveBox(l_entity.AABB.boxID);

 //and make that slot the new "next_free" slot (like adjusting the head of a linked list)
 nextFreeIdSlot = l_entity.id;
}
                 }
                  
                  activeEntityCount = l_new_index;
}

//Get the entity using its id and the idToIndexTable lookup
Entity& EntityManager::GetEntity(unsigned int id)
{
return entities[idToIndexTable[id]];
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////

//draw all of the entities -
void EntityManager::Draw()
{
//for each entity that is active
for(unsigned int entity = 0; entity < activeEntityCount; entity++)
{
//if it is actually active try and draw it
if(entities[entity].active)
entities[entity].sprite.Draw();

}

}

};


AS in the above the entity manager takes a 'collisionhandler' pointer to the object that represents all the collision handling for the entities with AABBs. When an entity is created it the passed in description of an AABB that describes the x and y offset of the aabb relative the the top left hand corner of the sprite as well as its height and width. This is used to create a new AABB to add to the collision handling system and stores the resulting boxID created for look up and updating later. This corresponding box ID is used to update the same aabb in the update entities function. For completeness the Rect class that describes this is below:

Code:
class Rect
{
public:
Rect(){};
Rect(int left,int top,int width, int height);
virtual ~Rect(){};

//a 2x2 array of min and max x/y vals where 1st dimension is min/max and the 2nd is
//x/y
float vals[2][2];
unsigned int boxID;
unsigned int objID;
unsigned int type;
};

And also here is the code for the sweep and prune collision system, mainly identical to Motoherp's beautiful implementation, except with his suggestions of a 'collision map' to look up encounters we are interested in and encounters we are not interested in.

Code:
const int MAX_BOXES = 1000;
const int MAX_ENCOUNTERS = 1000;
const int COLLISION_MAP_SIZE = 5;

//two structs used for collison handling
//An encounter to hold the ids of the two entities colliding
struct CollisionEncounter
{
int objIds[2];
};

//end points for the min and max of the aabb to be tested
struct EndPoint
{
int type;
int boxID;
};

class CollisionManager
{
public:
CollisionManager();
virtual ~CollisionManager(){};

void InitMap(unsigned int map[][COLLISION_MAP_SIZE],unsigned int size);

void Update();

void ResolveEncounters();
void AddEncounter(int objID1,int objID2);
void RemoveEncounter(int objID1,int objID2);

int  AddBox(int objID,int left,int right, int top,int bottom,int type);
void RemoveBox(int boxID);
void UpdateBox(unsigned int objId,int left,int top, int right,int bottom);

bool Collide(const Rect& boxA,const Rect& boxB);

inline bool CheckMap(int type1,int type2);

Rect GetBox(int index) {return AABBs[index];}
private:
//array of AABBS used for collison
Rect AABBs[MAX_BOXES];

//array of 'encounters' to be held  
CollisionEncounter encounters[MAX_ENCOUNTERS];

//Array of endpoints
EndPoint endpoints[2*MAX_BOXES][2];

//variables to keep track of encounters and boxes
unsigned int numEncounters;
unsigned int numBoxes;

unsigned int collisionMap[COLLISION_MAP_SIZE][COLLISION_MAP_SIZE];
};




Offline  
Read August 24, 2011, 01:18:43 PM #1
CrazyFoo

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

Code:
CollisionManager::CollisionManager()
{
numBoxes = 0;
numEncounters = 0;
}

void CollisionManager::InitMap(unsigned int map[][COLLISION_MAP_SIZE],unsigned int mapSize)
{

for(int y = 0; y < COLLISION_MAP_SIZE; y++)
{
for(int x = 0; x < COLLISION_MAP_SIZE; x++)
{
collisionMap[x][y] = map[x][y];
}
}
}

void CollisionManager::Update()
{
//sort through lists on the x and y axis to employ the sweep and prune strategy

for(int axis = 0; axis < 2; axis++)
{
//go through each box, and go through both the max and min
//endpoints for each box in the current axis so this will need
//twice the amount of normal tests
for(int box = 1; box < numBoxes * 2; box++)
{
int keyType = endpoints[box][axis].type;
int keyBoxId = endpoints[box][axis].boxID;

float keyVal = AABBs[keyBoxId].vals[keyType][axis];

//use the above keyval to the value before it in the array - swap if necessary
//it's basically a bubblesort
int index = box-1;

//now go backwards to the start of the array to make sure it is all in the right  
                                //order
while(index >= 0)
{
int compType = endpoints[index][axis].type;
int compBoxId = endpoints[index][axis].boxID;

int compVal = AABBs[compBoxId].vals[compType][axis];
int objType1 = AABBs[compBoxId].type;
int objType2 = AABBs[keyBoxId].type;

if(compVal < keyVal)
{
//this is in order so break the loop
break;
}

//if an endpoint is leaving to the left of the an endpoint this is an
//encounter not happening anymore
if((compType == 0) && (keyType == 1))
{
if(CheckMap(objType1,objType2))
                                               {
                                                 RemoveEncounter(AABBs[compBoxId].objID, AABBs[keyBoxId].objID);
                                               }
}

//otherwise this is a new encounter
else
{
if((compType == 1) && (keyType == 0))
{
//is this an encounter we're interested in?
if(CheckMap(objType1,objType2))
{
if(Collide(AABBs[compBoxId],AABBs[keyBoxId]))
{

                                                                     AddEncounter(AABBs[compBoxId].objID,
                                                                                  AABBs[keyBoxId].objID);
}
}
}//end if
}

//swap the points
endpoints[index+1][axis].type = compType;
endpoints[index][axis].type = keyType;

endpoints[index+1][axis].boxID = compBoxId;
endpoints[index][axis].boxID = keyBoxId;

index--;
}//end while

}//end inner for loop

}

ResolveEncounters();
}

void CollisionManager::ResolveEncounters()
{
//will have to be done later - pass the owner entities of these rects to the
//collision resolution code in the actual game - call this code by going
//through the list of encounters one by one
for(int encounter = 0; encounter < numEncounters; encounter++)
{
int id1 = encounters[encounter].objIds[0];
int id2 = encounters[encounter].objIds[1];
g_engine->DealWithCollision(id1,id2);
RemoveEncounter(id1,id2);
}
}

void CollisionManager::AddEncounter(int objID1,int objID2)
{

for(int encounter = 0; encounter < numEncounters; encounter++)
{
//add a new encounter to a list
//make sure it doesn't sit in the list already
if((encounters[encounter].objIds[0]  == objID1 && encounters[encounter].objIds[1] == objID2) ||
(encounters[encounter].objIds[0] == objID2 && encounters[encounter].objIds[1] == objID1))
{
//if it does exist return from the function
return;
}
}

        //otherwise it obviously doesn't sit in the encounters list yet, so add it!

encounters[numEncounters].objIds[0] = objID1;
encounters[numEncounters].objIds[1] = objID2;
numEncounters++;
}

void CollisionManager::RemoveEncounter(int objID1,int objID2)
{
//remove the encounter
//search through and look for it
for(int encounter = 0; encounter < numEncounters; encounter++)
{
//if encounter found, remove it
if((encounters[encounter].objIds[0] == objID1 && encounters[encounter].objIds[1] == objID2) ||
(encounters[encounter].objIds[0]== objID2 && encounters[encounter].objIds[1] == objID1))
{
for(int index = encounter; index < numEncounters-1; index++)
{
encounters[index] = encounters[index+1];
}
numEncounters--;
return;
}
}
}

int CollisionManager::AddBox(int objID,int left,int top, int right,int bottom,int type)
{
//will need to add some code re obj id
//may have to get entities involved
//add AABB


//add the aabb
AABBs[numBoxes].vals[0][0] = left;
AABBs[numBoxes].vals[1][0] = right;
AABBs[numBoxes].vals[0][1] = top;
AABBs[numBoxes].vals[1][1] = bottom;
AABBs[numBoxes].objID = objID;
AABBs[numBoxes].type = type;
AABBs[numBoxes].boxID = numBoxes;

//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;

numBoxes++;
return numBoxes-1;
}

void CollisionManager::RemoveBox(int boxID)
{
//this removes the box with the passed in id from the list - from the encounters list,
//the endpoints list and also the AABB list itself

//this is done simply by swapping the contents of a 'dead' entry with the currently highest indexed
                //entry, then decrementing the current number of entries by 1.

                int objId = -1;

for(int box = 0; box < numBoxes; box++)
{
if(AABBs[box].boxID == boxID)
{
//get the obj id
objId = AABBs[box].objID;
//shuffle the rest of the array
for(int index = box; index < numBoxes - 1; index++)
{
AABBs[index] = AABBs[index + 1];
}
break;
}
}

for(int box = 0; box < numBoxes * 2; box += 2)
{
if(endpoints[box][0].boxID == boxID)
{
for(int index = box; index < numBoxes * 2; index += 2)
{
//x axis
endpoints[index][0] = endpoints[index+2][0];
endpoints[index][1] = endpoints[index+2][1];
//y axis
endpoints[index+1][0] = endpoints[index+3][0];
endpoints[index+1][1] = endpoints[index+3][1];
}
}
break;
}

//do the same for the encounters
for(int encounter = 0; encounter < numEncounters; encounter++)
{
if(encounters[encounter].objIds[0] == objId || encounters[encounter].objIds[1] == objId)
{
for(int index = encounter; index < numEncounters - 1; index++)
{
encounters[index] = encounters[index+1];
}
numEncounters--;
}
}

numBoxes--;
}

bool CollisionManager::Collide(const Rect& rect1,const Rect& rect2)
{
if(rect1.vals[0][0] > rect2.vals[1][0]) return false;
if(rect1.vals[1][0] < rect2.vals[0][0]) return false;
if(rect1.vals[0][1] > rect2.vals[1][1]) return false;
if(rect1.vals[1][1] < rect2.vals[0][1]) return false;

return true;
}

void CollisionManager::UpdateBox(unsigned int boxID,int left,int right, int top,int bottom)
{
for(int box = 0; box < numBoxes; box++)
{
if(AABBs[box].boxID == boxID)
{
//update the box
AABBs[box].vals[0][0] = left;
AABBs[box].vals[1][0] = right;
AABBs[box].vals[0][1] = top;
AABBs[box].vals[1][1] = bottom;
}
}
}

bool CollisionManager::CheckMap(int type1,int type2)
{
return (collisionMap[type1][type2] == 1);
}


As stated previously, the main problem is that entities that should collide 'pass through' one another. The main important parts of the client code is below (as if this hasn't been overloaded with code already!)

Code:
//constant values for 'types'
const int PLAYER_BULLET = 0;
const int PLAYER = 1;
const int ENEMY = 2;
const int ENEMY_BULLET = 3;
const int POWER_UP = 4;

unsigned int collisionMap[COLLISION_MAP_SIZE][COLLISION_MAP_SIZE] = { {0,0,1,0,0},
                                                                        {0,0,1,1,1},  
                                                                        {1,1,0,0,0},
                                                                        {0,1,0,0,0},
                                                                        {0,1,0,0,0}};
.
.
.
Rect enemyAABB(0,0,32,32);

Behaviour* straightBullet = new StraightBehaviour;
Behaviour* staticEnemy = new StaticBehaviour;
entityManagement = new EntityManager(1000);


bulletDescription1.behaviour = straightBullet;
bulletDescription1.movement.velocity = Vector2(gameScript.GetGlobalNumber("PLAYERBULLETXSPEEDUP"),
gameScript.GetGlobalNumber("PLAYERBULLETYSPEED"));
bulletDescription1.AABB = enemyAABB;
bulletDescription1.type = PLAYER_BULLET;

enemyDescription1 = bulletDescription1;
enemyDescription1.sprite.SetPosition(240,30);
enemyDescription1.AABB = enemyAABB;
enemyDescription1.type = ENEMY;
enemyDescription1.movement.velocity.SetY(0.1f);
enemyDescription1.behaviour = straightBullet;
.
.
.
entityManagement->SetCollisionHandler(g_engine->p_collisionManager);
enemyId = entityManagement->CreateEntity(enemyDescription1);
g_engine->p_collisionManager->InitMap(collisionMap,COLLISION_MAP_SIZE);
.
.
.
entityManagement->Update();
.
.
.
void GameEntityCollision(unsigned int id1,unsigned int id2)
{
unsigned int type1 = entityManagement->GetEntity(id1).type;
unsigned int type2 = entityManagement->GetEntity(id2).type;

if((type1 == ENEMY && type2 == PLAYER_BULLET) ||
(type2 == ENEMY && type1 == PLAYER_BULLET))
{
entityManagement->GetEntity(id1).active = false;
entityManagement->GetEntity(id2).active = false;
}
}

//when bullets added to the entity manager the code is called like this...

Vector2 pos = player->GetPosition();
bulletDescription1.sprite.SetPosition(pos + Vector2(0,-30));
entityManagement->CreateEntity(bulletDescription1);

I've spent hours pouring over the code, found a few gotchas and corrected them but still no joy.
If anyone has any suggestions at all, thanks in advance

Respect
Lloyd
Offline  
Read August 24, 2011, 04:36:21 PM #2
Hornet600S

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

I just took a quick look at your code.
Looks like the second break in CollisionManager::RemoveBox is not where it should be. Maybe that's the reason for your collision checks failing.

Besides that: your code suffers from the fact that the AABBs are seperated and cannot be indexed. Therefore much looping/housekeeping is needed just to update/remove an entity's box.

It's actually most likely more efficient to rebuild the whole CollisionManager::AABB array etc. each frame before computing the collisions by looping through all active entities once.


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read August 24, 2011, 06:30:56 PM #3
CrazyFoo

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

Thank you for the helpful suggestions. I have corrected the problem with the break statement. However I am curious as to how exactly change the system to 'rebuild' the AABB array each frame and keep the boxes indexed as you suggested. I am also wondering about the existence of an alternative approach to the ways the entity manager and the collision system could communicate with one another.
Offline  
Read August 25, 2011, 10:32:06 AM #4
motorherp

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

Thank you for the helpful suggestions. I have corrected the problem with the break statement. However I am curious as to how exactly change the system to 'rebuild' the AABB array each frame and keep the boxes indexed as you suggested. I am also wondering about the existence of an alternative approach to the ways the entity manager and the collision system could communicate with one another.

It's not necessary to loop through your AABB's or perform housekeeping, neither do you need to rebuild your AABB list each frame.  The reason being that the AABB index is the same as it's position in the AABB array.  Rather than comparing index values to find the correct index, just jump straight to that offset into the array to find the correct AABB.  Indeed it is not needed to store this index in the AABB at all.  For example your UpdateBox function should look like:

Code:
void CollisionManager::UpdateBox(unsigned int boxID,int left,int right, int top,int bottom)
{
//update the box
AABBs[boxID].vals[0][0] = left;
AABBs[boxID].vals[1][0] = right;
AABBs[boxID].vals[0][1] = top;
AABBs[boxID].vals[1][1] = bottom;
}


Offline  
Read August 25, 2011, 10:44:37 AM #5
Hornet600S

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

It's not necessary to loop through your AABB's or perform housekeeping, neither do you need to rebuild your AABB list each frame.  The reason being that the AABB index is the same as it's position in the AABB array.
Are you sure? I didn't look to close but right now it looks to me like he's using the entity-ID to link to an AABB inside the manager. And the AABB's index inside the manager has nothing to do with the entity-ID, so he needs to search the coresponding AABB there. And when an AABB is removed the collision manager's list also changes, no simple direct indexing possible.

So if he'd use the boxID as direct index into the collision manager's AABB list as you suggest, then he must not shuffle that list on object removal AND needs to check for "dead"/unused AABBs during CollisionManager::Update and skip those.

Or he could extend the collision-manager to use a similar index-to-ID mapping as the entity-manager does.

Or he could reset and rebuild the collision-info each frame, effectively not using any linking at all.


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read August 25, 2011, 11:01:51 AM #6
CrazyFoo

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...


So if he'd use the boxID as direct index into the collision manager's AABB list as you suggest, then he must not shuffle that list on object removal AND needs to check for "dead"/unused AABBs during CollisionManager::Update and skip those.

Or he could extend the collision-manager to use a similar index-to-ID mapping as the entity-manager does.

Or he could reset and rebuild the collision-info each frame, effectively not using any linking at all.

What Hornet has observed is true, I thought about using the boxID as a direct index but when I thought about it the boxIDs do indeed change as they are shuffled when 'dead' ones are removed, effectively changing the ids. Thank you for the suggestion though.

Motoherp, how exactly did you use your AABB system in a project? I completely understand how it works in isolation but as a component of a larger system how have you 'slotted it in' to a working engine? Don't get me wrong, I don't want to be a pain in the butt and expect everything to be 'spoonfed' to me and I'm grateful for the stellar work in the tutorial, but a slice of the 'bigger picture' would give me (and the community) a point in the right direction.
If it's more appropriate perhaps the answer could be added to the end of the existing tutorial thread?

Mega Respect
Lloyd
Offline  
Read August 25, 2011, 11:03:10 AM #7
motorherp

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

It's not necessary to loop through your AABB's or perform housekeeping, neither do you need to rebuild your AABB list each frame.  The reason being that the AABB index is the same as it's position in the AABB array.
Are you sure? I didn't look to close but right now it looks to me like he's using the entity-ID to link to an AABB inside the manager. And the AABB's index inside the manager has nothing to do with the entity-ID, so he needs to search the coresponding AABB there. And when an AABB is removed the collision manager's list also changes, no simple direct indexing possible.

So if he'd use the boxID as direct index into the collision manager's AABB list as you suggest, then he must not shuffle that list on object removal AND needs to check for "dead"/unused AABBs during CollisionManager::Update and skip those.

Or he could extend the collision-manager to use a similar index-to-ID mapping as the entity-manager does.

Or he could reset and rebuild the collision-info each frame, effectively not using any linking at all.

Ah ok, I'm afraid I didn't have time to go over the code dump in detail.  It was never my intention in the tutorial that the AABB list should ever be shuffled, I dont remember doing that in the write up.  The idea is that each object outside of the collision system holds its corresponding boxId which relates directly to that AABB's position in the array for quick indexing.  Therefore when removing boxes, the AABB array should be kept as is rather than being shuffled so that these boxId's dont get messed up.  Having holes in the AABB array is fine since it is never necessary to directly loop through the array or anything like that, so there is no unwanted consequence of having gaps.

Perhaps were the confusion has krept in is because in the tutorial it seems I've only really half implemented the AddBox function.  I only filled this one out since I wanted to demonstrate how to correctly fill out the structures, I wasn't really thinking about management issues at the time.  In reality you could keep a record of which AABB's are free to keep track of gaps in the array and asign out free ones when AddBox is called.  This way you can directly index into the AABB array and never need to shuffle or search or do housekeeping.
« Last Edit: August 25, 2011, 11:05:00 AM by motorherp »

Offline  
Read August 25, 2011, 12:31:38 PM #8
motorherp

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...


So if he'd use the boxID as direct index into the collision manager's AABB list as you suggest, then he must not shuffle that list on object removal AND needs to check for "dead"/unused AABBs during CollisionManager::Update and skip those.

Or he could extend the collision-manager to use a similar index-to-ID mapping as the entity-manager does.

Or he could reset and rebuild the collision-info each frame, effectively not using any linking at all.

What Hornet has observed is true, I thought about using the boxID as a direct index but when I thought about it the boxIDs do indeed change as they are shuffled when 'dead' ones are removed, effectively changing the ids. Thank you for the suggestion though.

Motoherp, how exactly did you use your AABB system in a project? I completely understand how it works in isolation but as a component of a larger system how have you 'slotted it in' to a working engine? Don't get me wrong, I don't want to be a pain in the butt and expect everything to be 'spoonfed' to me and I'm grateful for the stellar work in the tutorial, but a slice of the 'bigger picture' would give me (and the community) a point in the right direction.
If it's more appropriate perhaps the answer could be added to the end of the existing tutorial thread?

Mega Respect
Lloyd


Hopefully my post above answers some of your questions.  With regards to how I've used such systems myself in games there isn't really much more to tell, I've used them pretty much like described.  My intention is that such a system is pretty much a self contained 'black-box' which can just be dropped into projects and re-used over and over.  Each game object interfaces with the collision black-box by storing the index of its assigned AABB which is passed into the black-box when game objects wish to influence their collision counterpart such as in the UpdateBox function.  Similarly, the collision black-box interfaces with the rest of the game by storing some form of reference to game objects which it passes out when collisions occur in order for the rest of the game engine to handle these collision events. 

In the tutorial I've used int id's as the reference to game objects to keep things simple.  Using such a scheme, in your game you'd need to make sure each object is assigned a unique id and keep a map which links these id's back to the game objects so you can handle collision events when they are reported by the collision system. 

If your game contained an entity system where each object derived from the same base entity class and implemented function overrides, then you could create a nicer implementation.  The collision system could store base entity class pointers and when a collision occurs it would call the OnCollision function of each object passing in the pointer to the other collision object.  Each game entity implementation could then respond to collision however it wished by overriding the OnCollision function.  This would create a dependancy between you collision engine and game engine making it not truely a portable black-box but you could get around this with templating.


Offline  
Read August 25, 2011, 12:47:03 PM #9
CrazyFoo

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

So with regards to Adding Boxes, currently the 'numBoxes' variable is used as an index for the new box and subsequently the endpoints. If I were to change the system so that it uses boxIds exclusively to update and remove boxes this index will need to be taken from an updated list of 'free' slots, I'll get cracking on this but  have a couple of things I want to do in the meantime as a little break from working on this so it should be posted in a couple of days.

Also, as endpoints have a boxID as a member and they are constantly shuffled there is not much I can do apart from loop through them searching using the boxID when removing them is there?

In response to your suggestion regarding pointers to the entities, the thing that appealed most about Hornet's management system is that all the entities sit in contiguous memory, if pointers were used I'd have to also write a custom allocator to avoid thrashing the cache when going through them all. The entity struct as it stands is good enough for my uses but thank you again for the suggestions.
Offline  
Read August 25, 2011, 02:28:49 PM #10
motorherp

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

So with regards to Adding Boxes, currently the 'numBoxes' variable is used as an index for the new box and subsequently the endpoints. If I were to change the system so that it uses boxIds exclusively to update and remove boxes this index will need to be taken from an updated list of 'free' slots, I'll get cracking on this but  have a couple of things I want to do in the meantime as a little break from working on this so it should be posted in a couple of days.

That's correct.  I wouldn't pay much attention to the 'implementation' of AddBox in the tutorial.  I deliberately avoided showing the implementation of these sorts of functions since I didnt want the tutorial to get bogged down with management details so the focus could remain on the collision detection technique and algorithm.  Looks like I did sort of fill out the AddBox function though just so I could demonstrate what to put into the struture parameters but I clearly wasn't thinking about management at the time so dont infer anything from that implementation.


Quote
Also, as endpoints have a boxID as a member and they are constantly shuffled there is not much I can do apart from loop through them searching using the boxID when removing them is there?

Endpoints aren't directly referencable from outside the collision system and only during the RemoveBox call do they need to be linked from an outside object, so its not really necessary to be able to index them efficiently.  If you wanted a quick way of removing end-points I'm sure you could come up with another clever indexing system but its not really worth the effort or the memory.  This is because RemoveBox should only really be called infrequently.  If you find you are constantly and frequently removing and adding lots of objects to the collision system, for example in a bad implementation of a bullet manager, then you'd be better off creating a persistant pool of those objects rather than creating and destroying them all the time.  Thus you would only need to add each object to the collision system once when the pool is created, and remove them once when the pool is destroyed.  The important thing about not shuffling the AABB array is that it must be referenced frequently from outside the system which is why having a direct reference is important in that case unlike for end points.
« Last Edit: August 25, 2011, 02:38:20 PM by motorherp »

Offline  
Read August 26, 2011, 12:22:27 AM #11
CrazyFoo

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

I've solved the problem. It was one of those d'oh moments that I regularly have. When updating the entities and thusly their boxes, I was passing in the arguments in the wrong order, so the 'top' y coordinate became the 'right' x coordinate after the first frame. A bug that is easy to overlook as the array indexes were passed in as values. Moral of the story? Test ship - to ship collisions, as I only noticed the cause of the bug when I would move my player ship to the bottom right hand corner of the screen and a crash (not a pc crash) would occur, although the test enemy ship was in the top centre of the screen.

Silly mistakes are always the worst in programming for me.

Thanks for looking over the code and all the suggestions. I will see how robust this system is now it is up and running with a few hundred bullets on screen and let you guys know  Smiley
Offline  
Read August 26, 2011, 07:32:42 AM #12
motorherp

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

Cool, glad you found the problem mate.  One thing I like to do to prevent these sorts of mistakes and make things easier to understand at a later date when you come back to the code is you use enums to give labels to indices.  So for example in this case you could use something like:

Code:
enum E_AabbIndex
{
    E_AabbIndex_Min = 0,
    E_AabbIndex_Max = 1,

    E_AabbIndex_X = 0,
    E_AabbIndex_Y = 1
};

void CollisionManager::UpdateBox(unsigned int boxID, int minX, int maxX, int minY, int maxY)
{
//update the box
AABBs[boxID].vals[E_AabbIndex_Min][E_AabbIndex_X] = minX;
AABBs[boxID].vals[E_AabbIndex_Max][E_AabbIndex_X] = maxX;
AABBs[boxID].vals[E_AabbIndex_Min][E_AabbIndex_Y] = minY;
AABBs[boxID].vals[E_AabbIndex_Max][E_AabbIndex_Y] = maxY;
}


Offline  
Read August 26, 2011, 10:37:26 AM #13
CrazyFoo

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

That's very true! I overlooked that, its more or less software engineering lesson 1: avoid 'magic' numbers in code and use enums or even const values declared in a header!

const int X_INDEX = 0;
const int Y_INDEX = 1;
const int MIN_POINT = 0;
const int MAX_POINT = 1;
Offline  
Read August 27, 2011, 01:22:16 PM #14
CrazyFoo

Re: Integration of the "Bullet Management" and "Gunbird Collision" tutorials...

I had another bunch of bugs, but then fixed them myself - took a little time this morning but I think I'm getting better at this! I'll post about it in more detail soon, I just need to make some tweaks right now  Smiley
Offline  
Pages: [1]   Go Up
Jump to:  

Page created in 0.088 seconds with 18 queries.