Sign in to follow this  
lucky6969b

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

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


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this