Spatial partitioning not being calculated correctly

[theweirdn8]

Hello,

 

For my game engine I'm using the spatial-partitioning method to optimize collision checks.

 

I am using a 1d array to represent a 2d grid. Al of the grid creation appears right, however; objects are not being placed inside of the grid properly.

 

Can you see the below functions and help me detect what is going wrong?

 

This is done every game-loop with this function first:

//Used to separate level into zones for collision checks

this.begin_spatialpartioning = function( cLevelWidth, cLevelHeight)

{

this.COLLISION_AREA_OUTOFLEVEL.empty_list();

this.spatialGridBoxSize = 512; //default size of one grid

this.spatialGridWidthSize = 512; //default size of one grid in pixels

this.spatialGridHeightSize = 512; //default size of one grid in pixels

 

if( typeof cLevelWidth!="undefined" && typeof cLevelHeight!="undefined")

{

//Restarts the collision spaces grid.

this.COLLISION_AREA_SPACES.clear();

 

if( cLevelWidth>0 && cLevelHeight>0)

{

this.spatialGridWidthAmount = Math.ceil(cLevelWidth/this.spatialGridWidthSize);

if( this.spatialGridWidthAmount<2)

{

this.spatialGridWidthSize = cLevelWidth/2;

this.spatialGridWidthAmount = 2; 

}

this.spatialGridHeightAmount = Math.ceil(cLevelHeight/this.spatialGridHeightSize);

if( this.spatialGridHeightAmount<2)

{

this.spatialGridHeightSize = cLevelHeight/2;

this.spatialGridHeightAmount = 2;

}

//smallest size possible is 2x2

var iGrid, jGrid;

var xStart=0, yStart=0;

var newSpace;

for( iGrid =0; iGrid < this.spatialGridWidthAmount; iGrid+=1)

{

for( jGrid=0; jGrid < this.spatialGridHeightAmount; jGrid+=1)

{

newSpace = new this.SuperSpatialPartition();

newSpace.set_space(xStart,yStart,this.spatialGridWidthSize,this.spatialGridHeightSize);

yStart+=this.spatialGridHeightSize;

newSpace.spaceName+="testrun_"+i+"_"+j+"_test";

this.COLLISION_AREA_SPACES.push_back(newSpace);

}

yStart = 0;

xStart+=this.spatialGridWidthSize;

}

}

else

{

console.log("Unable to create spatial partitioning. Map to small.("+cLevelWidth+","+cLevelHeight+").");

}

}

else

{

console.log("Unable to create spatial partitioning. Invalid dimensions given.("+cLevelWidth+","+cLevelHeight+").");

}

}

 

Then this function:

//creates all of the collisions

this.parse_spatial_collisions = function()

{

//rest collision tree

this.collisionsCheckedCount = 0;

this.colisionObjectLoops = 0;

 

var foundGameObject = IS_NULL;

var foundOtherGameObject = IS_NULL;

var foundGameObjectHolder = IS_NULL;

var foundOtherGameObjectHolder = IS_NULL;

var iObjectHolder = IS_NULL;

var jObjectHolder = IS_NULL;

var OBJECT_LIST = IS_NULL;

var iObject = IS_NULL;

var jObject = IS_NULL;

var objectTypeCollidedBefore = false;

var otherObjectType;

var jObjectStart;

 

var objPartition = [-1, -1, -1, -1];

objPartition[0] = -1; //top-left corner

objPartition[1] = -1; //top-right corner

objPartition[2] = -1; //bottom-left corner

objPartition[3] = -1; //bottom-right corner

var iCtrPartition = 0;

var foundPartitionSpace = IS_NULL;

this.parsed_objects  = 0;

//check for collisions with grids 

//iterates through each object holder

//Correct for later optimizations with this.GAME_OBJECTS made into this.GAME_OBJECTS_WITH_COLLISIONS

for (iObjectHolder = 0; iObjectHolder < this.GAME_OBJECTS.length; iObjectHolder += 1)

{

foundGameObjectHolder = this.GAME_OBJECTS[iObjectHolder];

if( typeof foundGameObjectHolder!="undefined")

{

//iterates through the object's holder list

for (iObject = 0; iObject < foundGameObjectHolder.size(); iObject += 1)

{

foundGameObject = foundGameObjectHolder.at(iObject);

//makes sure object still exists

if( typeof foundGameObject!="undefined")

{

if( foundGameObject!=IS_NULL)

{

objPartition[0] = -1; //top-left corner

objPartition[1] = -1; //top-right corner

objPartition[2] = -1; //bottom-left corner

objPartition[3] = -1; //bottom-right corner

 

//makes sure the object has collisions(To be edited out on new update )

//OBJECT_LIST = foundGameObject.OBJECT_COLLISION_LIST;

//if( foundGameObject.isInit )

{

//&& OBJECT_LIST.size()> 0

//places objects in up to 4 spatial grids.

objPartition[0] = Math.floor( (foundGameObject.collisionBox.xPos*this.spatialGridHeightAmount / this.spatialGridWidthSize) +(foundGameObject.collisionBox.yPos / this.spatialGridHeightSize) );

objPartition[1] =Math.floor( ( foundGameObject.collisionBox.x2Pos*this.spatialGridHeightAmount / this.spatialGridWidthSize)+( foundGameObject.collisionBox.yPos / this.spatialGridHeightSize) );

objPartition[2] =Math.floor( (foundGameObject.collisionBox.xPos*this.spatialGridHeightAmount / this.spatialGridWidthSize)  +(foundGameObject.collisionBox.y2Pos  / this.spatialGridHeightSize) );

objPartition[3] =Math.floor( (foundGameObject.collisionBox.x2Pos*this.spatialGridHeightAmount / this.spatialGridWidthSize) +( foundGameObject.collisionBox.y2Pos / this.spatialGridHeightSize) );

objPartition = this.make_array_unique(objPartition);

for( iCtrPartition = 0; iCtrPartition < objPartition.length; iCtrPartition+=1)

{

this.parsed_objects+=1;

if( objPartition[iCtrPartition] < 0 || objPartition[iCtrPartition] >= this.COLLISION_AREA_SPACES.size()  )

{

this.COLLISION_AREA_OUTOFLEVEL.add_object(foundGameObject);

}

else

{

foundPartitionSpace = this.COLLISION_AREA_SPACES.at( objPartition[iCtrPartition] );

foundPartitionSpace.add_object(foundGameObject);

}

}

}

}

}

}

}

}

}

 

 

Also here is the function for unique array maker:

 

this.make_array_unique = function(arr)

{

var result = [];

for (var i = 0; i < arr.length; i++) 

{

if (result.indexOf(arr[i]) == -1)

{

result.push(arr[i]);

}

}

return result;

};

 

[theweirdn8]

I have solved this.

 

It seems like it was an order of operations flaw mixed with possible variables not becoming floats for the division calls.

 

Added 4 more lines of code and it works.