Thread: Vectors are nice..and useless at times

  1. #16
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Bubba View Post
    • Random access - very important for finding the sprite to remove and/or use
    • Easy and quick iteration - very important for the manager so it can draw all the sprites
    • Insertion is not important since order has nothing to do with render speed.
    • Quick removal that does not affect other items in the container.
    A hand-coded hash table with linear probing ought to suffice.

    EDIT: Actually, on second thought, there may be performance issues depending how you assign sprite IDs. Suppose you remove a sprite and then insert it again. Does the sprite have the same ID as it did before? Then it will always land in the same bucket of the hash table, or in this case, starting position. So some sprites might be penalized by slow lookup since they always land in "bad" places in the table.

    You could salt them with a random value.
    Last edited by brewbuck; 12-21-2007 at 07:37 PM.

  2. #17
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    What about creating a vector of iterators?
    Code:
    std::list<sprite> spriteList;
    std::vector<std::list<sprite>::iterator> vecIter;
    When you delete a sprite in spriteList, it won't cause all the iterators in vecIter to move down, so those iterators wouldn't be invalidated, and by using a list as the main container, only the iterator you're deleting will be invalidated. You can either use the list iterators to move from the beginning to the end, or you can use the vector's operator[] to go right to the place you want...

  3. #18
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Well right now I'm just crashing everywhere so nothing to show yet. Somedays I suck at code.

    I got it working with the vector and a delete mark. It just tracks the last known deletion and uses vector::size() to iterate. It seems to work ok. Memory clean up is the responsibility of the class using the vector if the objects are created on the heap.
    Last edited by VirtualAce; 12-22-2007 at 12:22 AM.

  4. #19
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Bubba View Post
    I don't want to use a map since with my system it will degrade into a linked list. I may in the future use my random class to generate unique IDs for the objects in the map and then store the IDs of those objects. This may prove to be the best option.
    Wait - what!?
    A map never degrades to a linked list. A map guarantees O(log n) search time, typically by using a self-balancing red-black tree (or similiar).

    an unordered_map can however, if the hash is extremely poor.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #20
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    I thought about it some more, and I think a hybrid of a hash table and a doubly linked list would work. The hash table could be very simple, of fixed size. You simply take the hash code modulo the table size to get an index. If there is already a sprite at that index, you search forward with any reasonable deterministic method to find an empty location and insert the sprite there.

    This solves the issues of: fast insertion, removal, and lookup (if the table is not too full). However, you have no good way of iterating over the sprites. You could scan the entire table looking for spots with sprites in them, but if your table is sparse, which is what you want for purposes of speed, then this is going to waste a lot of time looking at empty locations.

    To solve that problem, you also insert the sprite into a circular linked list when you place it in the hash table. You can drop it into the cycle at any point you want. Now, your sprite iterator is just a pointer to a node of this list. You can follow the links forward until you re-arrive at your starting point, at which point you know you're done. Inserting new nodes at any point of the ring will not break the cycle so you can't get an infinite loop unless the point you started at is deleted. So how do you avoid deletion of the starting point? Insert a single dummy node into the cycle and use this as the starting point for all iterations. The dummy node can't get deleted, so you can never get an infinite loop.

    But suppose you have some iterator P which started out at a spot on this ring and advanced forward several positions, and you now insert a new node between its original starting spot and its current position. This node will not be seen during the traversal of the links by iterator P.

    So you can just specify that iterators are not guaranteed to iterate over EVERY element in the list if some insertion operation occurs between an iterator instantiation, and that iterator reaching end(). This doesn't seem too onerous a limitation...

    It's not really possible to implement this with straight STL, though. The links of the sprite nodes have to be embedded in the hash table records themselves. That is, if you want to get an iterator to a specific node or erase a node through an iterator -- if you never do that, you could implement this all in plain STL.
    Last edited by brewbuck; 12-22-2007 at 01:32 AM.

  6. #21
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    an unordered_map can however, if the hash is extremely poor.
    And mine is.


    Well here is the result so far:

    Everything in the scene is animated and controlled by several instances of a SmartVector template class.

    The bounding boxes are already implemented here so all that's left to do is a hit test, which is already coded, and then fire off the right explosion animation and/or split the asteroid into smaller ones or remove it completely.

    I'll add some scoring to the bottom as well as some lives and maybe a front end menu later. The plan is to add some baddies to shoot and have different backdrops and asteroids for different levels. I'd also like to throw in some random comets in the background and other items just to improve the space atmosphere.
    Last edited by VirtualAce; 03-12-2011 at 11:41 AM.

  7. #22
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    This is very strange but the program is crashing on array access to the SmartVector. But it only happens every so often so this is going to be a fun bug to track down.

    It bails on:

    SmartVector.h - SmartVector::operator []
    Code:
      
        T &operator[] (const size_t &index)
        {
            return m_vVector[index];
        }

    The debugger says that index cannot be evaluated. Nice. So now I have an error that is fragging a variable.

    It has something to do with this code:

    LaserMgr.cpp - LaserMgr::CheckHits()
    Code:
    void LaserMgr::CheckHits()
    {
        for (size_t i = 0;i < m_vLasers.GetSize(); ++i)
        {
            //If current laser 'slot' is valid
             if (m_vLasers[i])
            {
                //Grab the sprite so we don't have to constantly call GetSpriteMgr()
                Sprite *pSprite = X3DGetApp()->GetSpriteMgr()->Get(m_vLasers[i]->SpriteID);
    
                //Grab sprite position and LOCAL/MODEL min/max boundaries
                D3DXVECTOR3 vecLaserPos = pSprite->GetPos();
                D3DXVECTOR3 vecLaserMin = pSprite->GetMin();
                D3DXVECTOR3 vecLaserMax = pSprite->GetMax();
    
                //Transform min/max to WORLD sprite location
                float LaserLeft = vecLaserPos.x + vecLaserMin.x;
                float LaserTop = vecLaserPos.y + vecLaserMin.y;
                float LaserRight = vecLaserPos.x + vecLaserMax.x;
                float LaserBottom = vecLaserPos.y + vecLaserMax.y;
    
                //Grab the asteroid manager for use later
                AstMgr *pAstMgr = X3DGetApp()->GetAstMgr();
    
                for (size_t j = 0;j < pAstMgr->GetSize(); ++j)
                {
                    //Grab an asteroid
                    Asteroid *pAst = pAstMgr->Get(j);
    
                    //Is it valid?
                    if (pAst)
                    {
                        //Check for collision
                        int hit = pAst->Collide(LaserLeft,LaserTop,LaserRight,LaserBottom);
                        
                        if (hit > 0)
                        {
                            //We have a collision so remove laser from laser mgr and sprite mgr vectors
                            X3DGetApp()->GetSpriteMgr()->Remove(m_vLasers[i]->SpriteID);
                            m_vLasers.Remove(i);
    
                            //Let the asteroid manager decide what to do with the doomed asteroid
                            pAstMgr->Destroy(j);
                            
                        }
                         
                    }
                }
            }
        }
    }
    SpriteMgr.cpp - SpriteMgr::Remove()
    Code:
    bool SpriteMgr::Remove(const size_t &index)
    {
        //De-allocate memory
        delete m_vSprites[index];
    
        //Remove from vector (only nullifies, does not actually remove)
        return m_vSprites.Remove(index);
    }
    SmartVector.h - SmartVector::Remove()
    Code:
        virtual bool Remove(const size_t &index)
        {
            //Check for out of range
            if (index > (m_vVector.size()-1))
            {
                return false;
            }
            
            //Nullify current 'slot'
            m_vVector[index] = NULL;
    
            //Set cache index to this index (this will be used on next Add() operation)
            m_CacheIndex = index;
    
            //Cache value is now valid
            m_CacheValid = true;
            return true;
                    
        }
    Yes that's an ugly collision test but it's fast enough for now and I'll improve it later. It doesn't like me removing the lasers from the the laser mgr smart vector after I remove the laser sprite from the sprite mgr smart vector.

    Call stack on access violation
    > Astroids.exe!SmartVector<Sprite *>::Remove(const unsigned int & index=) Line 53 + 0x11 bytes C++
    Astroids.exe!SpriteMgr::Remove(const unsigned int & index=) Line 64 + 0x17 bytes C++
    Astroids.exe!LaserMgr::CheckHits() Line 63 C++
    Astroids.exe!LaserMgr::Update(float fTimeDelta=0.019000001) Line 115 C++
    Astroids.exe!AstroidsApp::Update(const float fTimeDelta=0.019000001) Line 163 C++
    Astroids.exe!D3DApp::EnterMsgLoop() Line 303 + 0x16 bytes C++
    Astroids.exe!WinMain(HINSTANCE__ * hInstance=0x00400000, HINSTANCE__ * prevInstance=0x00000000, char * cmdLine=0x00151f14, int showCmd=1) Line 119 C++
    Astroids.exe!__tmainCRTStartup() Line 589 + 0x35 bytes C
    Astroids.exe!WinMainCRTStartup() Line 414 C
    Check out index's value in Remove(). It's garbage right there and should not be. Index is just an integer that is actually the j variable in the LaserMgr::CheckHits() nested loop. Very strange. I've highlighted the important portions that I believe are bailing.

    Any ideas?
    Last edited by VirtualAce; 12-22-2007 at 11:39 AM.

  8. #23
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    This looks dangerous to me.
    Code:
            if (index > (m_vVector.size()-1))
            {
                return false;
            }
    if m_vVector.size() returns a size_t this test fails if the vector is empty.
    I'd use
    Code:
            if (index >= m_vVector.size() )
            {
                return false;
            }
    Kurt

  9. #24
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I think I found it: it's in the inner j loop.

    Code:
    ...
    for (size_t j = 0;j < pAstMgr->GetSize(); ++j)
    {
       //Grab an asteroid
       Asteroid *pAst = pAstMgr->Get(j);
    
       //Is it valid?
       if (pAst)
      {
        //Check for collision
        int hit = pAst->Collide(LaserLeft,LaserTop,LaserRight,LaserBottom);
                       
        if (hit > 0)
        {
          //We have a collision so remove laser from laser mgr and sprite mgr vectors
          X3DGetApp()->GetSpriteMgr()->Remove(m_vLasers[i]->SpriteID);
          m_vLasers.Remove(i);
    
          //Let the asteroid manager decide what to do with the doomed asteroid
          pAstMgr->Destroy(j);
                       
        }
             
      }
    }
    There is a serious problem here. I'm deleting a laser inside of the asteroid loop. This nullfies the laser data. But if we are not done with the asteroid loop, it will ASSUME m_vLasers[i] is still valid, which it's not.

    Since I'm checking one laser against multiple asteroids it would do just as well do bail out of the inner loop if I remove the laser since I know 100% sure that testing an asteroid against an invalid laser is always going return false for hit detection. I'm essentially continually testing a dead laser against all asteroids. Not good.

    EDIT:

    This fixed it. Game works good now and no mem leaks from crtdbg.

  10. #25
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Bubba View Post
    And mine is.
    Yeah but you wouldn't pick a terrible hash function on purpose. No matter what the data is, you can always come up with a decent hash function.

    fragging a variable
    LOL! I've never heard it put that way before

    Nice pic btw!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #26
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by Bubba View Post
    This is very strange but the program is crashing on array access to the SmartVector. But it only happens every so often so this is going to be a fun bug to track down.

    It bails on:

    SmartVector.h - SmartVector:: operator []
    Code:
      
        T &operator[] (const size_t &index)
        {
            return m_vVector[index];
        }
    If you use m_vVector.at( index ); instead of [index] then the vector should throw an out_of_bounds exception instead of just crashing.

    Quote Originally Posted by Bubba View Post
    SpriteMgr.cpp - SpriteMgr::Remove()
    Code:
    bool SpriteMgr::Remove(const size_t &index)
    {
        //De-allocate memory
        delete m_vSprites[index];
    
        //Remove from vector (only nullifies, does not actually remove)
        return m_vSprites.Remove(index);
    }
    SmartVector.h - SmartVector::Remove()
    Code:
        virtual bool Remove(const size_t &index)
        {
            //Check for out of range
            if (index > (m_vVector.size()-1))
            {
                return false;
            }
            
            //Nullify current 'slot'
            m_vVector[index] = NULL;
    
            //Set cache index to this index (this will be used on next Add() operation)
            m_CacheIndex = index;
    
            //Cache value is now valid
            m_CacheValid = true;
            return true;
                    
        }
    Shouldn't you check if the index is valid (i.e. in range) before deleting it?

  12. #27
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Out of curiosity, why do you pass the size_ts by reference? They're a machine word large, so passing them by value should me more efficient.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  13. #28
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I could change the function to check the range first.
    Last edited by VirtualAce; 12-22-2007 at 04:24 PM.

  14. #29
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Just an update here. The data structure I chose to use is a hybrid. It is a static array with a stack for 'remembering' empty slots. When an element is removed it's index in the array is pushed onto the stack. When an element is added the stack is checked. If it's not empty, the top item is popped off and used as an index for the element to be added. A cleanup function is ran periodically to ensure the array is being used effectively.

    Because this structure re-uses so many empty elements it's size grows marginally. After 20 levels of asteroids it was only about 400 elements. On the first few levels big asteroids only spawn about 1 to 2 asteroids. On later levels they spawn 4 and 5 with each one of those spawning the same.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Useless RLE?
    By VirtualAce in forum Game Programming
    Replies: 17
    Last Post: 03-08-2005, 04:16 PM
  2. useless post just saying thanks
    By Chaplin27 in forum C++ Programming
    Replies: 3
    Last Post: 02-08-2005, 10:27 PM