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

This topic is 1176 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

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

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

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.

1. 1
2. 2
Rutin
19
3. 3
4. 4
khawk
14
5. 5

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633743
• Total Posts
3013643
×