Hello

I want to know more about how to effectively index players by ID.

Suppose I have a vector that store all players in one place (yes I can break them apart for ECS but for the purpose of the question I have them together):

struct player
{
	unsigned int ID;
	char name[32];
	float xpos, ypos, zpos;
	float xvel, yvel, zvel;
	int health;
	// more to come
};

std::vector<player> m_Players; 

Each player has a unique ID of type unsigned int which can be anything. If there are 6 players and one of them has for some reason has the highest ID value: 9999, then I don't want to have an allocated array of players of size 9999 where 9993 of them are unused to address them directly by ID(myPlayer = m_Players[9999]). I want a array of players of size 6, and I want an array of indices mapping IDs to their position in the player array, such that I can access each player by ID. The reason I don't directly want to use a std::map<id,player> is that I want to effectively traverse the player array in another places.

std::unordered_map<unsigned int, unsigned int> m_Index;

bool update(const unsigned long ID, float xvel, float yvel, float zvel)
{
	auto search = m_Index.find(ID);
	if (search == m_Index.end())
		return false;

	auto index = search->second;
	if(index >= m_Players.size())
		return false;

	auto& myPlayer = m_Players.at(index);
	if(ID != myPlayer.ID)
		return false;

	myPlayer.xvel = xvel;
	myPlayer.yvel = yvel;
	myPlayer.zvel = zvel;

	return true;
}

void advance(const float timeDelta)
{
	for(auto& myPlayer : m_Players)
	{
		myPlayer.xpos += xvel*timeDelta;
		myPlayer.ypos += yvel*timeDelta;
		myPlayer.zpos += zvel*timeDelta;
	}
}

/*
void advance_parallel(const float timeDelta)
{
	parallel_for(auto& myPlayer : m_Players)
	{
		myPlayer.xpos += xvel*timeDelta;
		myPlayer.ypos += yvel*timeDelta;
		myPlayer.zpos += zvel*timeDelta;
	}
}
*/ 

Now, different players can be in different situations, for example, some players might be culled away, some players might be on differnt teams and so on. So I want to know if index maps could be suitable for these purposes:

std::unordered_map<unsigned int, unsigned int> m_Index_inactivePlayers;
std::unordered_map<unsigned int, unsigned int> m_Index_renderablePlayers;
std::unordered_map<unsigned int, unsigned int> m_Index_redTeamPlayers;
std::unordered_map<unsigned int, unsigned int> m_Index_blueTeamPlayers;

void redTeamHealthBoost(int health)
{
	for(auto& [ID, index] : m_Index_redTeamPlayers)
	{
		if(index >= m_Players.size())
			continue;
		auto& myPlayer = m_Players.at(index);
		if(ID != myPlayer.ID)
			continue;

		myPlayer.health += health;
	}
} 

Any thoughts, input or comments is much appreciated.

I'd use the player index (ie the index position in the vector) to point to players everywhere. The ID is then external, which you eliminate as soon as possible, and retrieve again just before you send something out.

The index is as small as it can be, and you can use bit-sets to represent player membership, although looking up the flag in the player is likely easier and less error-prone.

The unique ID is supposed to be global for all entities, not just players. Over a network in client-server-client situations IDs would be consistent.

If I reserve the ID #42 for "m_Players[42]" then what would then happen if I want to to something with "m_SomeObjects[42]", for example: m_Players[13]->shoot(42,9000)? Should someObjects[42] be hit or should "m_Players[42]"? I would between different types of entities have to translate first from local ID(index) to a global ID then back down to the appropiate entity container.

Another situation for example is when a large number of players or entities are spawned, such that you end up with IDs with values in the thousands. Then later on most of them could be cleared away leaving behind some entities with large ID values. I'm thinking I could be making more problems then I solve.

Sure. You're just reinventing databases, where you add an index or a view to be able to look up rows more quickly, while accepting that keeping those indices and views in sync makes writes slower.

Personally I find it funny when people twist their game engines to try and put everything into contiguous arrays, only to later discover that they really do need an extra level of indirection for most useful operations anyway.

If I reserve the ID #42 for "m_Players[42]" then what would then happen if I want to to something with "m_SomeObjects[42]"

If you reserve global ID #42, and you get that number from outside, the first thing you do is get the index associated with that player (assuming you know that else your search needs to be different) for your local system. Say, it's 18. Then use players[18] in your local game.

If you need to send out something about player 18 over the network or so, use players[18].ID . The remote side then converts #42 back to whatever index it uses for that ID, and handles the code with it.

Sure. You're just reinventing databases, where you add an index or a view to be able to look up rows more quickly, while accepting that keeping those indices and views in sync makes writes slower.

Personally I find it funny when people twist their game engines to try and put everything into contiguous arrays, only to later discover that they really do need an extra level of indirection for most useful operations anyway.

I can see that it is slow doing random array access on entities using indices to update data in response to unpredictable input. But there is only one way to layout data in memory at one time without duplication, and it seems reasonable to me that the data layout should best suit the heaviest workload for the most gains in terms performance(fps).

I thought that when doing heavy CPU calculations such as physics/collision, it is preferable to streamline dataflow from memory to cpu cores/threads. Meaning we want to structure and pack data only relevant for those operations as closely and as contiguous as possible, am I missing something?

If the point is only to iterate over a small number of players, I'd use a std::vector with something to point me out the memory position of each player data (or set of data, or anything that can return it). Maybe handles, or weak_ptr? I'd rather make things easier to test and change and suffer optimizing at the end of it all, than making it fast now and risking making myself afraid of refactoring entire modules.

Also, contiguous memory is a chance of optimization. With bad luck, misaligned memory and even heavier memory footprints it might even backfire and make no difference in performance at all...

I thought that when doing heavy CPU calculations such as physics/collision, it is preferable to streamline dataflow from memory to cpu cores/threads. Meaning we want to structure and pack data only relevant for those operations as closely and as contiguous as possible, am I missing something?

Yes, an actual performance problem and profiling data.

Seriously, this is leading you nowhere. Start with the simple case and if the data tells you it's not up to your standards, start making it more complex with informed decisions. There are cases where you can make a good guess about needing a more complex system for performance reasons or where putting everything in a contiguous array makes sense, this is not one of them. I mean, it might or might not be, there are too many parameters and unknowns.

How you identify an entity, and how you store an entity, are two separate concepts.

You may try to leverage the fact that an entity ID also happens to be an index into contiguous memory somewhere, but ultimately this will only work in a limited few places, and certainly not in a client/server architecture where the server is generating a lot of entity IDs and has absolutely no clue how clients are storing them.

Even then, it often makes sense for the server and the clients to have their own separate ID "pools". Not all entities the server creates will need to be replicated to clients (i.e. pure game logic with no client representation), and not all entities a client creates will need to be communicated to the server (i.e. visual effects, sounds). The IDs for both entity types can clearly overlap at times, yet your code will still need to be able to work with and identify them in the appropriate contexts. It's likely that each game-relevant object on the client will actually have 2 (or more) IDs, one used only by that particular client, one used by the server, and possibly more depending on whatever else has entity identification needs (world servers, etc.). You can even go so far as to strongly type your IDs, making it impossible to mix-and-match them accidentally in code.

Storage is a problem you can solve separately; an std::vector is definitely the simplest starting point. You then need a mechanism to translate from IDs to index/pointer/etc.; again, std::unordered_map sounds like a good fit.

Efficient traversal of entities for the purpose of performing operation X is actually a third problem that combines intimate knowledge of entity storage schemes along with the identification of which entities need that particular operation. Depending on the operation, there are several ways to approach this (assuming you stick with the aforementioned vector and map strategy):

1. Iterate all entities. If an entity ID is in the "do it" list, do the thing. Works best when a majority of your entities need the thing, most of the time.
2. In a first pass, transform all entity IDs in the "do it" list to their storage index, and add them to a sorted vector. Iterate the index vector, and only do the thing on those entities. Works best when a minority of your entities need the thing, most of the time.
3. Manage multiple separate entity ID lists (active/inactive, visible/invisible. etc.) that you move IDs between as entity state changes. A variant of the last approach that takes advantage of entity state stability (i.e. edge transitions), and isn't as great for "one-offs".

This is by no means an exhaustive list, and as always you'll need heavy profiling to determine which method works best for you. You may even use a combination of several approaches, depending on what you need to do. There's no way to know until you try.

I'd forego the indexes and loop over a std::map if this is your first stab. Store active/renderable/red as members on player. It won't be slow, unless you have like, a WoW sized player base. Problem solved. If/when you hit a performance issue, then make those index maps.