# Don't want to iterate the cells in order to find one?

## Recommended Posts

lucky6969b    1330

Currently, when I look up a cell in the grid, I iterate thru it,

and I compare it with the x and z or id.

But is there a quicker way of doing it?

For example,

There are 2 vectors representing the bmin and bmax of the bounding box.

How can I quickly get there without iterating the whole map?

Thanks

Jack

##### Share on other sites
Spidi    2823

I hope I get what you are trying to do ?! Is it a spacial partitioning system, like a cell grid or a quad tree ?!
In this case, if you put objects into a cell based on the minimum and maximum values of the their bounding box/rectangle (I guess center of it), than simply the same way as you put in, calculate the center of the box and divide these values with the width and height of the cells.

Pseudo warning (generally the same in 3d with one extra scalar calculation):

// The grid:
Cell[][] cells;
int cellWidth, cellHeight; // in world size!

// Get a cell based on the bounding box/rectangle of an object:
Rectangle r = object.getBoundingRectangle();
Vector2 center = (r.Minimum + r.Maximum) / 2;

// Here you get the location in the cell coordinate system:
int x = center.X / cellWidth;
int y = center.Y / cellHeight;
if ((x < 0 || x > cells.GetDimension(0)) || (y < 0 || y > cells.GetDimension(1)))
{
// it's center is not in any cells, oops...
}
Cell cell = cells[x][y];

If you are looking for all the cells the rect/box overlaps, do the same division for the minimum and maximum coordinate. That way you get the cell with the minimum and maximum indices from the overlapping cells...

Edited by Spidi

##### Share on other sites
lucky6969b    1330

Hello Spidi,

In the following code, I want to bypass the loop, and want to retrieve the cell with one hit

Like

Cell* cell = grid[id];

But in this case, as I've to test if the D3DXVECTOR3 intersects with the "current" bounding box.

I need to iterate it. Just like want to get a O(1) access to the grid cell.

Thanks

Jack

bool Coordinater::Convert_D3D_To_ID(D3DXVECTOR3 vec3, int& id)
{
for (auto& g : NavmeshSingleton::GetNavMesher()->GetWalkables())
{

if (g->Intersect(vec3))
{
id = g->m_time_independent_id;
return true;
}
}
return false;
}


##### Share on other sites
BitMaster    8651
You can gain O(1) access if there is a suitable formula to map positions to grid identifiers. For example if your grid consists of unit length cells, starting at at (0, 0, 0) and extending in the direction of the positive axis you can trivially extract intermediate X, Y, Z integer identifiers for that cell. Mapping those three identifiers to a grid identifier should be easy then (for example Z * width * height + Y * width + X but there are other possibilities).

Depending on what exactly you are doing that might not be possible and you rather want to look at spatial partitioning, for example via octrees which gives you O(log n). Edited by BitMaster

##### Share on other sites
Stainless    1875

create a hashmap using the id of the cell

Implementations will vary based on setup but in general this is the best way of solving these sort of issues.