Hi I have a 2D grid of 128x128 sized cells. Each update, if the position of the entity has moved, it is unoccupied from 9 of its surrounding cells and placed into 9 new cells of its new location. The logic works fine with 2 or 3 entities even with overlap they can go about the place unoccupying and occupying cells and updating the grid accordingly. Now when a 3rd or 4th entity passes across the player the program crashes because I am trying to unoccupy an entity from a position in the cell that is not valid.

Note:

• Each cell contains a vector of entity's CStat class containing the stats (Pos, Oldcell, CurrCell, etc)
• When an entity is removed from a vector all entities positioned above the, to-be-erased-one, need to be decremented in their position in cell.
• The cell are accessed in a strange way I know - but it is optimised trust me - as cells 7 0 3 8 1 2 6 5 4 Middle row, Top row then bottom row. It doesn't matter in the long run.
• The error is: visual studio 11\vc\include\vector line 159 - Expression: vector iterator + offset out of range
• The error is: How I am calculating the offset from the position in cell of the entity to be erased. As said this works as test data below proves but crashes upon the unoccupy function at the first cell (7) calculation.

Here are the 2 functions Please can you tell me where I am going wrong in my logic.

// ********************************************************************* //
// Name: OccupySurroundingCollCells  									 //
// Description: 	     //
// ********************************************************************* //
void CCollisionManager::OccupySurroundingCollCells(CStats* pEntityOne)
{
	// Find out which cell we are upon and if it is not the same as the last frame's
	// tile then save it and occupy cells around the entity
	CalculateCellUpon(*pEntityOne->GetWorldPos()->GetPos(), pEntityOne->m_pvCurrCell);

	if ((pEntityOne->m_pvCurrCell->iRow != pEntityOne->m_pvOldCell->iRow) || 
		(pEntityOne->m_pvCurrCell->iCol != pEntityOne->m_pvOldCell->iCol))
	{
		// Release and aquisition
		UnOccupyLast9Cells(pEntityOne);
		Occupy9Cells(pEntityOne);

		DebugPrint();
	}
} // OccupySurroundingCollCells

// ********************************************************************* //
// Name: Occupy9Cells													 //
// Description: Place this entity into the relevant tiles as follows     //
//              8 1 2													 //
//              7 0 3	But programmed as: 7 0 3 8 1 2 6 5 4			 //
//              6 5 4					   for ease of access			 //
// ********************************************************************* //
void CCollisionManager::Occupy9Cells(CStats* pEntityOne)
{
	stCELLVector2 vCell = *pEntityOne->m_pvCurrCell; 

	// Precalculate
	int a = vCell.iCol - 1; // Left tile (y is col)
	int b = vCell.iCol + 1; // Right tile

	// MIDDLE ROW
	// Cell 7
	m_ppCollMap[vCell.iRow][a].m_vecCollisionEntities.push_back(pEntityOne);
	pEntityOne->m_iPositionInCell[0] = m_ppCollMap[vCell.iRow][a].m_vecCollisionEntities.size();

	// Cell 0
	m_ppCollMap[vCell.iRow][vCell.iCol].m_vecCollisionEntities.push_back(pEntityOne);
	pEntityOne->m_iPositionInCell[1] = m_ppCollMap[vCell.iRow][vCell.iCol].m_vecCollisionEntities.size();

	// Cell 3
	m_ppCollMap[vCell.iRow][b].m_vecCollisionEntities.push_back(pEntityOne);
	pEntityOne->m_iPositionInCell[2] = m_ppCollMap[vCell.iRow][b].m_vecCollisionEntities.size();

	// FIRST ROW
	int iRow = vCell.iRow - 1; 

	// Cell 8
	m_ppCollMap[iRow][a].m_vecCollisionEntities.push_back(pEntityOne);
	pEntityOne->m_iPositionInCell[3] = m_ppCollMap[iRow][a].m_vecCollisionEntities.size();

	// Cell 1
	m_ppCollMap[iRow][vCell.iCol].m_vecCollisionEntities.push_back(pEntityOne);
	pEntityOne->m_iPositionInCell[4] = m_ppCollMap[iRow][vCell.iCol].m_vecCollisionEntities.size();

	// Cell 2
	m_ppCollMap[iRow][b].m_vecCollisionEntities.push_back(pEntityOne);
	pEntityOne->m_iPositionInCell[5] = m_ppCollMap[iRow][b].m_vecCollisionEntities.size();

	// LAST ROW
	iRow = vCell.iRow + 1; 

	// Cell 6
	m_ppCollMap[iRow][a].m_vecCollisionEntities.push_back(pEntityOne);
	pEntityOne->m_iPositionInCell[6] = m_ppCollMap[iRow][a].m_vecCollisionEntities.size();

	// Cell 5
	m_ppCollMap[iRow][vCell.iCol].m_vecCollisionEntities.push_back(pEntityOne);
	pEntityOne->m_iPositionInCell[7] = m_ppCollMap[iRow][vCell.iCol].m_vecCollisionEntities.size();

	// Cell 4
	m_ppCollMap[iRow][b].m_vecCollisionEntities.push_back(pEntityOne);
	pEntityOne->m_iPositionInCell[8] = m_ppCollMap[iRow][b].m_vecCollisionEntities.size();

	// Save
	*pEntityOne->m_pvOldCell = *pEntityOne->m_pvCurrCell;

} // Occupy9Cells

// ********************************************************************* //
// Name: UnOccupy9Cells													 //
// Description: Remove this entity from the relevant tiles. Must be      //
//              called before Occupy9Cells except the first time.        //
//              Pos -1 because they are derived from vector::size()      //
//              where the lowest is 1 not 0.                             //
//              Each cell has a for loop that performs a -1 for each     //
//              entity's pos above the erased one.                       //
//              Its (begin+PosInCell) is not -1 because the entities     //
//              above the erased are to be decremented.                  //
// ********************************************************************* //
void CCollisionManager::UnOccupyLast9Cells(CStats* pEntityOne)
{
	stCELLVector2 vCell = *pEntityOne->m_pvOldCell;

	// Precalculate
	int a = vCell.iCol - 1; // Left tile
	int b = vCell.iCol + 1; // Right tile

	// MIDDLE ROW
	// Cell 7
	m_pVec           = &m_ppCollMap[vCell.iRow][a].m_vecCollisionEntities;
	assert((m_pVec->begin() + (pEntityOne->m_iPositionInCell[0] -1)) < m_pVec->end());
	m_itToBeErased   = m_pVec->begin() + (pEntityOne->m_iPositionInCell[0] -1);
	for (m_it = m_itToBeErased + 1; m_it != m_pVec->end(); ++m_it)
		if (m_it > m_itToBeErased)
			(*m_it)->m_iPositionInCell[0] -= 1;
	assert(pEntityOne->m_iPositionInCell[0] <= m_pVec->size());
	m_pVec->erase(m_itToBeErased);

	// Cell 0
	m_pVec = &m_ppCollMap[vCell.iRow][vCell.iCol].m_vecCollisionEntities;
	assert((m_pVec->begin() + (pEntityOne->m_iPositionInCell[1] -1)) < m_pVec->end());
	m_itToBeErased   = m_pVec->begin() + (pEntityOne->m_iPositionInCell[1] -1);
	for (m_it = m_itToBeErased + 1; m_it != m_pVec->end(); ++m_it)
		if (m_it > m_itToBeErased)
			(*m_it)->m_iPositionInCell[1] -= 1;
	assert(pEntityOne->m_iPositionInCell[1] <= m_pVec->size());
	m_pVec->erase(m_itToBeErased);

	// Cell 3
	m_pVec = &m_ppCollMap[vCell.iRow][b].m_vecCollisionEntities;
	assert((m_pVec->begin() + (pEntityOne->m_iPositionInCell[2] -1)) < m_pVec->end());
	m_itToBeErased   = m_pVec->begin() + (pEntityOne->m_iPositionInCell[2] -1);
	for (m_it = m_itToBeErased + 1; m_it != m_pVec->end(); ++m_it)
		if (m_it > m_itToBeErased)
			(*m_it)->m_iPositionInCell[2] -= 1;
	assert(pEntityOne->m_iPositionInCell[2] <= m_pVec->size());
	m_pVec->erase(m_itToBeErased);

	// FIRST ROW
	int iRow = vCell.iRow - 1; 

	// Cell 8
	m_pVec = &m_ppCollMap[iRow][a].m_vecCollisionEntities;
	assert((m_pVec->begin() + (pEntityOne->m_iPositionInCell[3] -1)) < m_pVec->end());
	m_itToBeErased   = m_pVec->begin() + (pEntityOne->m_iPositionInCell[3] -1);
	for (m_it = m_itToBeErased + 1; m_it != m_pVec->end(); ++m_it)
		if (m_it > m_itToBeErased)
			(*m_it)->m_iPositionInCell[3] -= 1;
	assert(pEntityOne->m_iPositionInCell[3] <= m_pVec->size());
	m_pVec->erase(m_itToBeErased);

	// Cell 1
	m_pVec = &m_ppCollMap[iRow][vCell.iCol].m_vecCollisionEntities;
	assert((m_pVec->begin() + (pEntityOne->m_iPositionInCell[4] -1)) < m_pVec->end());
	m_itToBeErased   = m_pVec->begin() + (pEntityOne->m_iPositionInCell[4] -1);
	for (m_it = m_itToBeErased + 1; m_it != m_pVec->end(); ++m_it)
		if (m_it > m_itToBeErased)
			(*m_it)->m_iPositionInCell[4] -= 1;
	assert(pEntityOne->m_iPositionInCell[4] <= m_pVec->size());
	m_pVec->erase(m_itToBeErased);

	// Cell 2
	m_pVec = &m_ppCollMap[iRow][b].m_vecCollisionEntities;
	assert((m_pVec->begin() + (pEntityOne->m_iPositionInCell[5] -1)) < m_pVec->end());
	m_itToBeErased   = m_pVec->begin() + (pEntityOne->m_iPositionInCell[5] -1);
	for (m_it = m_itToBeErased + 1; m_it != m_pVec->end(); ++m_it)
		if (m_it > m_itToBeErased)
			(*m_it)->m_iPositionInCell[5] -= 1;
	assert(pEntityOne->m_iPositionInCell[5] <= m_pVec->size());
	m_pVec->erase(m_itToBeErased);

	// LAST ROW
	iRow = vCell.iRow + 1; 

	// Cell 6
	m_pVec = &m_ppCollMap[iRow][a].m_vecCollisionEntities;
	assert((m_pVec->begin() + (pEntityOne->m_iPositionInCell[6] -1)) < m_pVec->end());
	m_itToBeErased   = m_pVec->begin() + (pEntityOne->m_iPositionInCell[6] -1);
	for (m_it = m_itToBeErased + 1; m_it != m_pVec->end(); ++m_it)
		if (m_it > m_itToBeErased)
			(*m_it)->m_iPositionInCell[6] -= 1;
	assert(pEntityOne->m_iPositionInCell[6] <= m_pVec->size());
	m_pVec->erase(m_itToBeErased);

	// Cell 5
	m_pVec = &m_ppCollMap[iRow][vCell.iCol].m_vecCollisionEntities;
	assert((m_pVec->begin() + (pEntityOne->m_iPositionInCell[7] -1)) < m_pVec->end());
	m_itToBeErased   = m_pVec->begin() + (pEntityOne->m_iPositionInCell[7] -1);
	for (m_it = m_itToBeErased + 1; m_it != m_pVec->end(); ++m_it)
		if (m_it > m_itToBeErased)
			(*m_it)->m_iPositionInCell[7] -= 1;
	assert(pEntityOne->m_iPositionInCell[7] <= m_pVec->size());
	m_pVec->erase(m_itToBeErased);

	// Cell 4
	m_pVec = &m_ppCollMap[iRow][b].m_vecCollisionEntities;
	assert((m_pVec->begin() + (pEntityOne->m_iPositionInCell[8] -1)) < m_pVec->end());
	m_itToBeErased   = m_pVec->begin() + (pEntityOne->m_iPositionInCell[8] -1);
	for (m_it = m_itToBeErased + 1; m_it != m_pVec->end(); ++m_it)
		if (m_it > m_itToBeErased)
			(*m_it)->m_iPositionInCell[8] -= 1;
	assert(pEntityOne->m_iPositionInCell[8] <= m_pVec->size());
	m_pVec->erase(m_itToBeErased);

} // UnOccupy9Cells

Here is the test data showing the cell's vector size (the number of entities occupying each cell) remember 1 entity occupies 9 cells around it.

CCollisionManager::DebugPrint() Printing contents of collision map 
CCollisionManager::DebugPrint() Collision grid size = 128 
CCollisionManager::DebugPrint() World Row Max       = 13 
CCollisionManager::DebugPrint() World Col Max       = 18 
CCollisionManager::DebugPrint() [0]    = (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [128]  = (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [256]  = (0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [384]  = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [512]  = (1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [640]  = (1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [768]  = (1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [896]  = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [1024] = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [1152] = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [1280] = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [1408] = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )
CCollisionManager::DebugPrint() [1536] = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, )

Great and profuse thanks in advance...

I think

m_itToBeErased = m_pVec->begin() + (pEntityOne->m_iPositionInCell[6] -1); these similar lines i thinkthis is the problem

example: if your cell ocupied by 6 objects, one of objects positionincell is 6 and and other objects was erased and left just 1 object,

there are no position 6 and its offset out of range.

You have misunderstood. Each entity contains a list of 9 cells to which it 'remembers' which position in the cell it currently occupies. It is not amended 'til the occupy9cells function. Until then the data would indeed be invalid. But it is not needed 'til then anyway. 'Position 6' does not get deleted. It is its contents that refer to the contents of the vector in the 6th cell that is used.

Also note that I understand that if I delete at position '2' in the vector then all above that position would render the m_PositionInCell[n] invalid by 1. Which is why I added a for loop to each cell in the unoccupy function to minus 1 to each of them.

other probem

int a = vCell.iCol - 1; // Left tile
int b = vCell.iCol + 1;

whats it?

if your vCell.iCol ==0 so a==-1 . out of rabge

Its a precalculation. vCell.iCol will never = 0 as it is bounds corrected in CalculateCellUpon - (Right at the top).

I think the way you want run your grid is very poor, is it your first grid?

I appreciate that it is my, more or less first attempt, at running a collision grid. I do believe its quite an efficient one at that. If anybody differs I humbly ask if they could detail what corrections I could make.

It was a kind of a meaty problem to get my head around. Im trying to think of a way(excuse) to implement function pointers to race through the Broad Phase part - Does anyonme have any ideas?. I haven't been able to test how entities my program can handle yet because of this vector + iterator crash. Others have been getting juicy numbers way in the thousands...!!!

Thanks Seramus, I obviously talking to someone experienced here.

Unfortunately I am at a failiure to understand your code. I dont understand the overall concept of what you are trying to do. Are you building some sort of implicit grid? The _loop (your explaination doesn't account for all parameters). I'm having a little difficulty with what mechanism is. Maybe it's your entities. Why do you sort things.

Maybe if I could have a generic understanding of what you are trying to do. Although I can follow the program flow. I'll keep scanning it...

next possible error

m_pVec = &m_ppCollMap[iRow][vCell.iCol].m_vecCollisionEntities;
assert((m_pVec->begin() + (pEntityOne->m_iPositionInCell[7] -1)) < m_pVec->end());
m_itToBeErased = m_pVec->begin() + (pEntityOne->m_iPositionInCell[7] -1);
for (m_it = m_itToBeErased + 1; m_it != m_pVec->end(); ++m_it)
if (m_it > m_itToBeErased)
(*m_it)->m_iPositionInCell[7] -= 1;//this line , why [7] for other entities that cell can be 5th 2nd 3rd ....

Great work - I just drew some diagrams to depict the problem and you're right. There is no way of telling which cell that particular entity overlaps...! Hmm how do I get over that problem...?

I am working on reducing the 9 cells down to 4...! changing CalculateCellUpon to calc the NW cell of 4 cells. Which should speed it up. I would use your code if I could understand it - Im just scared of using black boxes.

If I did use a list instead of a vector won't the addresses all change when I add a new element to the list causing it to be remade...?