Hello, I'm building a simple spatial partitioning grid for an isometric 2D virtual world (~1k players). I want to handle it the simplest way possible and optimize later if necessary, but I'm trying to avoid putting work into an architecture that will clearly not work, so I could use some input.

I have something sort of like this right now:

// My world map is a tile map, tiles are grouped into 16x16 chunks.
// EntityID is entt::entity
// TileExtent is just a rect (x, y, xLength, yLength).

class EntityLocator
{
public:
    // Sets the entity's location to the tiles that contain the given AABB.
    void setEntityLocation(EntityID entity, BoundingBox boundingBox);

    // Returns all entities that are located within the given extent.
    std::vector<EntityID> getEntitiesInExtent(const TileExtent& tileExtent);

private:
    // The outer vector is a 2D grid stored in row-major order, corresponding
    // to the tiles in the tile map.
    // Each element in the grid is a vector of entities--the entities that
    // are currently located in that tile.
    std::vector<std::vector<EntityID>> entityGrid;
    
    // A map of entity ID -> the tiles that the entity is located in.
    // Used to easily clear out old entity data before setting their new
    // location.
    std::unordered_map<EntityID, TileExtent> entityMap;
}

Is this along the lines of how you build one of these things? Adding/removing entities from the vectors in each of the grid tiles takes a lot of operations, but it seems manageable. The grid will take up a decent amount of RAM on the server side (for a large 100x100 chunk world it'd be ~51MB), but it isn't that much relative to the 4GB that my server has.

Net_ said:
I want to handle it the simplest way possible and optimize later if necessary, but I'm trying to avoid putting work into an architecture that will clearly not work

If you optimize later, things would change. Here's what i'd expect if optimizing to the max…

First, we have two options: Put one entity into multiple cells (usually 4 at most). Or put it only into a single cell which covers its center, but traverse adjacent cells when finding nearby entities (again usually just 4).
In my experience the latter is usually faster because it avoids lists of variable size. But if your entities can be larger than a single cells, you need a multi resolution grid, and finding nearby entities of a large one also requires traversing multiple levels, so complexity goes up.

std::vector<std::vector<>> is really slow. Slow enough i try to avoid it even for offline needs. Ofc. it's not that bad for you because size of the outer vector won't change.
But anyway, here an example of binning to avoid dynamic allocation completely, assuming we put each entity only into one cell:

// data we need to allocate once at startup; i consider them global variables to keep it simple
constexpr int size = 100;
std::array<int, size*size> cellCounters = {};
std::array<int, size*size + 1> cellListBegin;
std::vector<Entity::ID> compactLists (MAX_ENTITY_COUNT);

void BuildGridFromEntities (const std::vector<Entity> &entities)
{
	// we do two passes, fist to count how many entities go into each cell
	cellCounters.fill(0); // EDIT: note clearing should not be necessary because after the function is done the array is all zeroes again
	for (const auto &entity : entities) 
		cellCounters[CalcCellIndex(entity)]++;
	
	// do a prefix sum over the counts to pack lists of entities per cell
	cellListBegin[0] = 0;
	for (int i=0; i<size*size; i++)
		cellListBegin[i+1] = cellListBegin[i] + cellCounters[i];
		
	// second pass over entities to put them into our compact lists
	for (const auto &entity : entities) 
	{
		int cellIndex = CalcCellIndex(entity);
		int listIndex = cellListBegin[cellIndex] + (--cellCounters[cellIndex]);
		compactLists[listIndex] = entity.getID();
	}	
}

Assuming i did this correctly, we could now find all entities of a cell this way:

int listBegin = cellListBegin[cellIndex];
int listEnd = cellListBegin[cellIndex+1];
for (int i=listBegin; i<listEnd; i++)
{
	Entity &entity = FindEntityFromID(compactLists[i]);
	entity.DoSomething();
}

As you see, there is no dynamic allocation to build the grid, and memory access when traversing it is linear.
So that's fast and also convenient to work with. If you decide to do it this way, your interfaces change so decide early.
No idea how many entities you need so it's worth it, and the prefix sum is a downside if grid is large and number of entities is low.

JoeJ said:

As you see, there is no dynamic allocation to build the grid, and memory access when traversing it is linear.
So that's fast and also convenient to work with. If you decide to do it this way, your interfaces change so decide early.
No idea how many entities you need so it's worth it, and the prefix sum is a downside if grid is large and number of entities is low.

I see, thanks for the example! Some more info about my setup:

• Entities can be larger than 1 tile.
• Entities have continuous movement (they don't discretely move between tiles), so they can be in multiple tiles at once, even if they're 1 tile large.
• My benchmark has been 1,000 player entities connected at once, spread out over the map in small groups.
• On top of the 1,000 players, there will be maybe up to 1,000 NPC entities.
• I was leaning towards putting each entity in every cell that it occupies, but I'm not against the “1 cell, traverse the adjacent” approach if it's better.

Does your solution still seem reasonable?

JoeJ said:

std::vector<std::vector<>> is really slow. Slow enough i try to avoid it even for offline needs. Ofc. it's not that bad for you because size of the outer vector won't change.

Yeah, it would be nice to avoid if possible. I figure that the dynamic allocations on the inside vectors are only happening when tiles get more traffic than they previously had seen, so would maybe not be so bad. Would be nice if I'm able to go with a solution like yours that doesn't have this to worry about, though.

Edit: Since I'm going to have the whole (potentially large) map loaded in the server, should I just jump to spatial hashing? I imagine there will be a lot of empty tiles in the world on any given tick.

Net_ said:
Does your solution still seem reasonable?

Surely yes, but with larger entities its much more complex to implement, and 2000 entities is a small number. So if i have to guess, i'd say go with putting entity into multiple cells and see if something like collision detection is fast enough.

Closest thing i have here is a particle fluid simulation with 30000 particles. I use sparse grid, which is a small uniform grid at the top, then a tree where each node is a cube of 4^3 cells. Updating this acceleration structure takes 4ms on Ryzen 2700. The update is multithreaded, but 30k is not enough particles to saturate my CPU. I need millions of particles and large grids so the complex implementation becomes worth it.
Now that's a bad comparison, but my belly feeling tells me you could just implement what feels most natural to you and performance would not differ much because your numbers are small (speaking of one vs. multiple cells). Maybe somebody else can tell from better experience…

Net_ said:
I figure that the dynamic allocations on the inside vectors are only happening when tiles get more traffic than they previously had seen, so would maybe not be so bad. Would be nice if I'm able to go with a solution like yours that doesn't have this to worry about, though.

I think the binning method would work with multiple cells too, but never did it this way. I would try it. With std::vector per cell there is little control about when reallocations happen, how much unused memory can grow, and if there are eventual runtime spikes.

Btw, how would it look if you make your grid cells larger, so even the largest objects fit in? This probably means many objects per cell, so potential collisions increase exponentially, but memory access becomes more cache friendly, which often gives surprisingly big advantages. Maybe the lowest effort solution is also the fastest one.

As you see, there is no dynamic allocation to build the grid, and memory access when traversing it is linear.

You've optimized building the grid, but you also made it necessary to rebuild the entire grid repeatedly, which requires iterating over every entity every frame. Surely that's a net loss?

My approach is to only rebuild the grid from scratch when loading a saved game. Otherwise I only reindex individual entities, and only when they cross grid lines (which happens relatively rarely). I never iterate over my complete list of entities (which can be in the millions, or in theory even in the billions) excepts when saving or loading the game. Entities outside the “active zone” centered on the player do not get updated at all.

a light breeze said:
You've optimized building the grid, but you also made it necessary to rebuild the entire grid repeatedly, which requires iterating over every entity every frame. Surely that's a net loss?

Depends. You need to check if each entity still is in the same cell anyway, so you need to process each one no matter what (assuming all are active and may move). Removing only some entities from a list and adding them to another would be cheap only if you have a kind of linked list, which means cache misses while iterating such list. What i tried to optimize here is iterating objects per cell, not really the grid update. But for 2000 objects i see no problem with either approach.

It's often necessary to reorder the objects in memory as well, so not only the IDs/indices but also the objects themselves can be iterated quickly per cell without cache misses. Makes little sense with ECS where components are scattered across memory for good reasons, but does make sense for fluid particles for example. In this case objects remaining in the same cell give no potential wins. But if most objects only move to an adjacent cell of the current we can have lockfree multithreading for the grid update, which is a big win then.

But just saying. Ofc. my context differs from what's asked here, which you surely know better about.