surrounding objects algorithm

Question

I'm working on a game where exactly one object may exist at location (x, y) where x and y are ints. For example, an object may exist at (0, 0) or it may not, but it is not possible for multiple objects to exist there at once.

I am trying to decide which STL container to use for the problem at hand and the best way to solve this problem.

Basically, I start with an object and its (x, y) location. The goal is to determine the tallest, largest possible rectangle based on that object's surrounding objects. The rectangle must be created by using all objects above and below the current object. That is, it must be the tallest that it can possibly be based on the starting object position.

For example, say the following represents my object grid and I am starting with the green object at location (3, 4):

Then, the rectangle I am looking for would be represented by the pink squares below:

So, assuming I start with the object at (3, 4) like the example shows, I will need to check if objects also exist at (2, 4), (4, 4), (3, 3), and (3, 5). If an object exists at any of those locations, I need to repeat the process for the object to find the largest possible rectangle.

These objects are rather rare and the game world is massive. It doesn't seem practical to just new a 2D array for the entire game world since most of the elements would be empty. However, I need to be to index into any position to check if an object is there at any time.

Instead, I thought about using a std::map like so:

std::map< std::pair<int, int>, ObjectData> m_objects;

Then, as I am checking the surrounding objects, I could use map::find() in my loop, checking if the surrounding objects exist:

if(m_objects.find(std::pair<3, 4>) != m_objects.end())
{
    //An object exists at (3, 4).
    //Add it to the list of surrounding objects.
}

I could potentially be making a lot of calls to map::find() if I decide to do this, but the map would take up much less memory than newing a 2D array of the entire world.

Does anyone have any advice on a simple algorithm I could use to find what I am looking for? Should I continue using a std::map or is there a better container for a problem like this?

Answer 1

How much data do you need to store at each grid location? If you are simply looking for a flag that indicates neighbors you have at least two "low tech" solutions

a) If your grid is sparse, how about each square keeps a neighbor list? So each square knows which neighboring squares are occupied. You'll have some work to do to maintain the lists when a square is occupied or vacated. But neighbor lists mean you don't need a grid map at all

b) If the grid map locations are truly just points, use 1 bit per grid location. The results map will be 8x8=64 times smaller that one that uses bytes for each grid point. Bit operations are lightening fast. A 10,000x10,000 map will take 100,000,000 bits or 12.5MB (approx)

Answer 2

An improvement would be to use a hashmap, if possible. This would allow you to at least do your potential extensive searches with an expected time complexity of O(1).

There's a thread here ( Mapping two integers to one, in a unique and deterministic way) that goes into some detail about how to hash two integers together.

If your compiler supports C++11, you could use std::unordered_map. If not, boost has basically the same thing: http://www.boost.org/doc/libs/1_38_0/doc/html/boost/unordered_map.html

Answer 3

You may want to consider a spatial data structure. If the data is 'sparse', as you say, then doing a quadtree neighbourhood search might save you a lot of processing power. I would personally use an R-tree, but that's most likely because I have an R-tree library that I've written and can easily import.

For example, suppose you have a 1000x1000 grid with 10,000 elements. Assuming for the moment, a uniformly-random distribution, we would (based on the density) expect no more than, say . . . a chain of three to five objects touching in either dimension (at this density, a chain of three vertically-oriented objects will happen with probability 0.01% of the time). Suppose the object under consideration is located at (x,y). A window search, starting at (x-5,y-5) and going to (x+5,y+5) would give you a list of at most 121 elements to perform a linear search through. If your rect-picking algorithm notices that it would be possible to form a taller rectangle (i.e. if a rect under consideration touches the edges of this 11x11 bounding box), just repeat the window search for another 5x5 region in one direction of the original. Repeat as necessary.

This, of course, only works well when you have extremely sparse data. It might be worth adapting an R-tree such that the leaves are an assoc. data structure (i.e. Int -> Int -> Object), but at that point it's probably best to just find a solution that works on denser data.

I'm likely over-thinking this; there is likely a much simpler solution around somewhere.

Some references on R-trees:

• The original paper, for the original algorithms.
• The Wikipedia page, which has some decent overview on the topic.
• The R-tree portal, for datasets and algorithms relating to R-trees.

I'll edit this with a link to my own R-tree implementation (public domain) if I ever get around to cleaning it up a little.

Answer 4

This sounds suspiciously like a homework problem (because it's got that weird condition "The rectangle must be created by using all objects above and below the current object" that makes the solution trivial). But I'll give it a shot anyway. I'm going to use the word "pixel" instead of "object", for convenience.

If your application really deserves heavyweight solutions, you might try storing the pixels in a quadtree (whose leaves contain plain old 2D arrays of just a few thousand pixels each). Or you might group contiguous pixels together into "shapes" (e.g. your example would consist of only one "shape", even though it contains 24 individual pixels). Given an initial unstructured list of pixel coordinates, it's easy to find these shapes; google "union-find". The specific benefit of storing contiguous shapes is that when you're looking for largest rectangles, you only need to consider those pixels that are in the same shape as the initial pixel.

A specific disadvantage of storing contiguous shapes is that if your pixel-objects are moving around (e.g. if they represent monsters in a roguelike game), I'm not sure that the union-find data structure supports incremental updates. You might have to run union-find on every "frame", which would be pretty bad.

Anyway... let's just say you're using a std::unordered_map<std::pair<int,int>, ObjectData*>, because that sounds pretty reasonable to me. (You should almost certainly store pointers in your map, not actual objects, because copying around all those objects is going to be a lot slower than copying pointers.)

typedef std::pair<int, int> Pt;
typedef std::pair<Pt, Pt> Rectangle;
std::unordered_map<Pt, ObjectData *> myObjects;

/* This helper function checks a whole vertical stripe of pixels. */
static bool all_pixels_exist(int x, int min_y, int max_y)
{
    assert(min_y <= max_y);
    for (int y = min_y; y <= max_y; ++y) {
        if (myObjects.find(Pt(x, y)) == myObjects.end())
            return false;
    }
    return true;
}

Rectangle find_tallest_rectangle(int x, int y)
{
    assert(myObjects.find(Pt(x,y)) != myObjects.end());
    int top = y;
    int bottom = y;
    while (myObjects.find(Pt(x, top-1) != myObjects.end()) --top;
    while (myObjects.find(Pt(x, bottom+1) != myObjects.end()) ++bottom;
    // We've now identified the first vertical stripe of pixels.
    // The next step is to "paint-roller" that stripe to the left as far as possible...
    int left = x;
    while (all_pixels_exist(left-1, top, bottom)) --left;
    // ...and to the right.
    int right = x;
    while (all_pixels_exist(right+1, top, bottom)) ++right;
    return Rectangle(Pt(top, left), Pt(bottom, right));
}