The breakup into small monster groups did use the vector originally, but it created to many monster groups: About every second submap contains a monster groups (mostly woodland critters), this makes OMAPX2OMAPY*2/2 == 64800 entries in the vector.
While moving around, I had to wait several seconds during generating a new submap as the program searched for all the monster groups that had to be put into those submaps. And usually when walking in a straight line (e.g. straight to the north), a row of 11 (=MAPSIZE) submaps had to be generated at once (all the newly used submaps to the north). Even more when moving diagonally or upon initial mapgen. This was simply not playable (and my computer is not actually slow).
The map is not a good solution either, I agree - it duplicates the groups location (inside the map as key and as member of the group). But it makes it reasonable fast.
You run around vector ONCE - in spawn
As explained above, this is often done for several submaps at the same time. Also consider that the vector based solution had to do way more calculations - the distance of the point to the group, than comparing that to the radius. The map based version looks up the coordinate directly, no distance calculation is done there.
Searching in 64800 entries takes about 16 comparisons in a map. Searching the same in a vector takes 64800 comparisons.
You can’t really compare a vector with just a few entries and a map with many entries, that are different scenarios.
You think resorting multimap 100 times better that one integer increment? Are you sick?
That's not how inserting into a map works. Inserting searches (which is fast) for the place to put the new entry and puts it there. Than it does a balancing of the tree, which is just moving the root point around. This is *fast*, not as fast as incrementing an integer but still considerable fast. Especially since this is not done every turn, and not for all groups.
because it's not horde now, but small unlinked zombie groups.
The original hordes where large monster groups, now they are small, that's the only difference. The original hordes where not linked together either. Now it's possible that only a part of the horde follows the player because the other part is further away and did not hear the noise. This means hordes can now split and merge.
I’d love to hear of a better solution than the map, the vector really doesn’t work for that many groups, and the high number of monster groups is kind of a requirement.
You need performance? Are you crazy?
Nobody needs performance. I love to wait for several seconds every 12 steps my characters takes. And when I open the overmap I usually go for a coffee, so wating several minutes there is no problem either. That should also answer the second question.
