C++ MMO: Best approach to store creatures in a multi-level world map for the purpose to find spectators

I'm developing a game which is a multi-level game, my game can have a maximum of 15 floors, and a fixed amount of tiles width/height.

Each tile in the map can have a creature. All fine until here; I need to find spectators within a range / radius of the map, and sometimes within specified floor ranges, this can happen multiple times per second (players interacting with the world)

Currently this is how I search for lets say all spectators in all floors:

for (int floor = 0; floor != 15; floor++)
{
for (int x = posx - range; x != posx + range; x++)
{
for (int y = posy - range; y != posy + range; y++)
{
Tile* ....
}
}
}


As you can tell, this isn't the best approach, I've thought about using a hash / chain of creatures on which each hash entry points to a X-Y coordinate in the world map, this would take a lot of trouble to worry about floors, and it's also more performance-friendly.

How can I achieve this?

"Spectators" is just the list of nearby enemies, right?

Anyways, I can think of 2 good ways to do this: Look at nearby tiles to see if they have monsters, or look at monsters to see if they're on a nearby tile.

If you are going to choose the route of looking at tiles for monsters (better for densely populated levels), your existing code can be made cleaner:

• Make sure to specify the floor on which you are looking. I doubt that there's generally a need to loop through all 15 levels.

• If levels are sufficiently large that the radius/range is a small percentage of the total space, consider only checking tiles within a square around the central point: from x / y minus the range to x / y plus the range.

In this case, I'd suggest continuing to store monsters as you seem to be doing, assigning each tile a slot for a monster.

If you want to check monsters to see if they're nearby (better for a sparsely populated map), store separate lists (in whatever data structure) of monsters per-level. Loop through the list and test each monster against whether or not it is in range of the target. This way, the X/Y coordinates would be stored more directly as a property of the monster.

If you want, you could combine both of these strategies for the final implementation. Divide the total floor space into a 2d array of smaller chunks, and store a list of monsters in each chunk. For checking which monsters are in range of the given point, just look at the monsters in the nearby chunks. That way you can quickly eliminate looking at monsters or tiles which are obviously in chunks too far away, and then

Also: Your code is going to try to loop through 16 floors. It'll stop on floor=16, but floor=0 to floor=15 is 16 times looping.

Let the info about its position in the world be part of the monster class. Then you are only searching all the monster, when deciding if they are in the range, not all the tiles.

Also take in consideration, that if your map has floors, you need 3D coords: x,y,z...

• Thats also performance kill, given there can be over 50k creatures. X/Y coords would only be needed, since then I'd check if the spectators obtained in the chain are within the floor ranges required. – Raúl Sanpedro Jul 19 '16 at 6:04
• Without the Z coord, how can you decide on which floor the creature stays? Also the 50k creature count..is it realy needed? That will kill the performance in every case, considering the need to render it also... – Viktor Podlipský Jul 19 '16 at 6:06
• Creature coords are handled on every creature struct. It's a game server, not a game client, – Raúl Sanpedro Jul 19 '16 at 6:28
• You need to clarify your asking: what are the "spectators"? The player characters observing the creatures or the creatures observing player character? Also if you say that you need to "find spectators within specified range" then there is no need to search through all the floors and all the map tiles, just search within the given range. And also, looking at the code sample, your map has 16 floors...because you start with zero. – Viktor Podlipský Jul 19 '16 at 6:38
• I've edited the sample pseudo code, it really didn't point what I said in the requirement, but it was understandable. It doesn't matter which side it is, there is no point it, the main problem is finding spectators (creatures). – Raúl Sanpedro Jul 19 '16 at 6:56