Creating a map of objects with variable width and height

Hey there, new to the forums so hi!

I've been trying to sort this problem out for quite a while - in fact in some forms years...

It's for a game, but is a generic map problem so I'd be interested in how people solve this. I've got an class (cGameObject) that represents any object in the game / system. Each object is positioned at an X and Y coordinate (thankfully only 2D!) with a width and a height.

Currently, I'm using an STL map to handle this, as such:

typedef std::map < int, cGameObject * > MapYAxis;
typedef std::map < int, MapYAxis > MapXAxis;

So, it's a Map of an Int to a Map of an Int to a Game Object Ptr. That gives me things like
For ( x = Map.LowerBound(1); x < Map.UpperBound(100); x++)
(Pseudo, obviously).

However, this doesn't do collision checking. If I wanted to add an object and make sure it did not overlap another object I'd need to check that no other object overlapped any of the 4 corners, by doing a search on X and Y plus the width and height of the biggest object in the game, and THEN I'd still have to compare each object to make sure the points overlapped or not.

How do other people accomplish a similar goal? Or is it really not going to have an elegant solution? What I'd like is a way to do something like this:

OOOOOOOOOOOO
OOOOOOOOOOOO
OXXXXXXOOOOOO
OXXXXXXOOOOOO
OXXXXXXOOOOOO
OOOOOOOOOOOO

Where X's are all pointers to the same object. But, this doesn't work - firstly, it's costly (in inserting, updating, deleting, etc) and secondly because, when iterating through the map to output objects data, I'd get the same data multiple times, so would THEN have to keep track of which objects I've already displayed!!

Any help much appreciated! :-)

Mark

Sorry,

I must add another detail which does affect it somewhat:

We're not talking about a few hundred or thousand 'pixels' / 'points' in either direction; we're talking about a couple of million (for the sake of argument, +/- 1,000,000 in each direction; which is 4,000,000,000,000 'points' in total!) and each 'object' could be, say, 10x10 right through to 400x400 (160,000 points) so storing one entry for every single point isn't feasible.

Cheers!

I would not store each point. Store the objects and have them know where they are at, or store the positions separately if you want. But don't store a value for each point.

To detect collisions, you can loop through all objects and see if they collide. If you sort all your objects by position then you might be able to narrow down the number of comaprisons you have to do. I'm not sure what most games do about this (although you might consider searching the game programming forum here).

Then, as I have seen suggested before regarding 3d environments, store each object with its own point and use formulas to calculate collisions and stuff.

Code:

---

struct point { double x; double y; };
class linear_sort_comp { /*YADDA*/ };

boost::ptr_map< point, cGameObject, linear_sort_comp > world;

---

Code:

---

enum basic_shape { rectangle, ellipse, triangle /* , etc... */ };

class cGameObject
{
      basic_shape shape;
      double height;
      double width;
  public:
      cGameObject();
      virtual ~cGameObject();
};

---

Hmmm... now suppose you wanted to find position given object handle....

The real problem comes from the fact that there's (currently, in testing) 60,000 - 100,000 objects. Iterating through them all is possible - and in fact relatively quick - but it's not an 'idea' solution.

The best I've come up with is being able to iterate - using the STL map's iterators - through objects that are 'close' and then, using standard calculations, work out which are close, which are touching, etc etc. I just wondered if there is a more elegant method - but from the sounds of it there isn't, there's just the method that performs the best given the situation.

Thanks for your input though, and if anyone else can shed light on to alternative ways to do this I'd be grateful.

As it happens, I store each object in a large 1-D array (well, a pointer to that object) - the ID of the object is also the key of the array, making access by ID extremely quick. Access by coordinate takes a map<>.find() to find the X axis and a similar map<>.find() to find the element on the Y axis, but I've found it still to be fast enough. If the exact coordinate is known *and* it's guaranteed to be correct, then of course you can just use [x][y]. Even faster! But otherwise ...

Out of interest - using the STL - if you know the Key but don't know if it exists, what's the quickest way to find out? Just use .find() and check for .end()? Or is there a method like if (Map.isset("key")) ...?

Cheers

If you go with the method, of storing each object, along with its location, instead of storing all locations with objects as you currently do, you do not have to iterate through every object to test for a collision. Instead, you could for example, construct a binary search tree based off of an objects location, and then have a function "bool isObjectAt(int x, int y);" or whatever, which would only take "log n" time.

Then, to see if an object has touching neighbors, just perform one "isObjectAt" for all of the locations "touching" it.

Thanks for the suggestion; although I can't quite see how a binary search tree would be able to know quite the information needed. For one, surely it'd be huge? I mean, each object lies on up to 160,000 'points', and said objects would have 1,600 'points' the touch them directly. Am I missing something here, though?

Cheers!