Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

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

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

If you intended to correct an error in the post then please contact us.

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
Advertisement

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!