Vectors are nice..and useless at times

Quote:

---

Originally Posted by Bubba

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

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

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.

Quote:

---

Originally Posted by Bubba

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.

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.

Quote:

---

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.

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

Quote:

---

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

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

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.

Quote:

---

Originally Posted by Bubba

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.

Quote:

---

fragging a variable

---

LOL! I've never heard it put that way before :)

Nice pic btw!

Quote:

---

Originally Posted by Bubba

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

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?

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.

I could change the function to check the range first.

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.