Thread: Creating a map of objects with variable width and height

  1. #1
    Registered User
    Join Date
    Jul 2007
    Posts
    6

    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

  2. #2
    Registered User
    Join Date
    Jul 2007
    Posts
    6
    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!

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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).

  4. #4
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    937
    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....
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  5. #5
    Registered User
    Join Date
    Jul 2007
    Posts
    6
    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

  6. #6
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    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.
    Programming Your Mom. http://www.dandongs.com/

  7. #7
    Registered User
    Join Date
    Jul 2007
    Posts
    6
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Button handler
    By Nephiroth in forum Windows Programming
    Replies: 8
    Last Post: 03-12-2006, 06:23 AM
  2. A bunch of Linker Errors...
    By Junior89 in forum Windows Programming
    Replies: 4
    Last Post: 01-06-2006, 02:59 PM
  3. struct question
    By caduardo21 in forum Windows Programming
    Replies: 5
    Last Post: 01-31-2005, 04:49 PM
  4. Ok, Structs, I need help I am not familiar with them
    By incognito in forum C++ Programming
    Replies: 7
    Last Post: 06-29-2002, 09:45 PM
  5. Outputting String arrays in windows
    By Xterria in forum Game Programming
    Replies: 11
    Last Post: 11-13-2001, 07:35 PM