Overmap mongroup rework

Game Talk The Toolbox
1

Say me for what you change from Vector to multimap<tripoint, mongroup>? You want better performance? Where? In overmap::draw? Cache result for hordes and you get better performance. You run around vector ONCE - in spawn, and ONCE if NPC check safety place. It is not so much CPU work. Now you do multimap with mongroups with radius 1 and broke hordes, because it’s not horde now, but small unlinked zombie groups. You need performance? Are you crazy? You had 1 large horde, now you had 100 small hordes instead it. For EACH you need calculation for move and signals as result - 100x more CPU work for hordes. And you to move do not just posx++ for horde, you remove it from list and puts it back. You think resorting multimap 100 times better that one integer increment? Are you sick? You get better performance in one place and bad in two another. This is true way?
And i not talk about realization of scent track…

2

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.
3

The fundamental misunderstanding here is that BevapDin broke up the monster groups for performance reasons, that’s not the case. He broke up monster groups as a means of tracking them properly on the overmap until they spawn as part of a set of changes to make tracking monsters on the overmap consistent. As a result of that, the vector storing them became a bottleneck, which is why the change to multimap happened.

By the way, do they ever need a consistent ordering? If not we can make that an unordered_multimap and it might be even faster.

4
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 OMAPX*2*OMAPY*2/2 == 64800 entries in the vector.
And for what it? One monster group to one submap. I not see much profit for it. Also you broke ant and other groups, who die if they queen is dead. Now you must do ID for mongroup and link it to queen.
While moving around, I had to wait several seconds during generating a new submap ...
Before it all be ok. For what you break large monster groups to small i don't have any idea.
This is *fast*, not as fast as incrementing an integer but still considerable fast.
Really? Are you think about scent track/light signals/noise? You must calc distance to EVERY small horde/write cache/write noise/scent/light signal map. You think it most better that use vector? More complex code->more bugs->more hard debug->more hard balance.
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.
Horde is it HORDE dammit. If few zombies moves to noise other also moving not because they hear something, because they are horde. It is herd instinct.
Nobody needs performance. I love to wait for several seconds every 12 steps my characters takes.
If someone not broke old code all be ok. For what it change?
5

Reading is fundamental! :smiley:

6

And so what? Check distance for 200 mongroups it is so big problem? For what you do 64800 monster groups instead 200-300?

7
By the way, do they ever need a consistent ordering? If not we can make that an unordered_multimap and it might be even faster.

I always forget the unordered containers. I had the idea of only processing nearby groups (in response to a signal) and that could use the ordering. But it probably won’t work with the coordinates being 2D and the ordering in the map being 1D. Therefor I have no objections.

And for what it? One monster group to one submap. I not see much profit for it. Also you broke ant and other groups, who die if they queen is dead. Now you must do ID for mongroup and link it to queen.
This is also the same as before, it just has to process more groups.
Really? Are you think about scent track/light signals/noise? You must calc distance to EVERY small horde/write cache/write noise/scent/light signal map. You think it most better that use vector? More complex code->more bugs->more hard debug->more hard balance.
In the case of signals, one has to calculate the distance to every group anyway, map or vector has no effect here.

It might be possible to reduce the number of groups by moving the spawn of forest/river/swamp creatures into the submap generation. Instead of generation overmap groups for natural wildlife, generate it during mapgen:

  • if overmap terrain is thick forest - add spawn points for some woodland critters
  • if overmap terrain is forest/field - add spawn points for few woodland critters or maybe not all the time, but one_in(3).
  • if overmap terrain is swap/river - spawn other appropriate critters.
8
map or vector has no effect here.
Really? 200 groups instead 10 - no effect? Ok. What about ability for huge horde to compress to a single point? There is too many problems for this way.
This is also the same as before, it just has to process more groups.
And where is profit? You want to process less groups, but now you must process more with move difficultly code, debug, future development etc. Keep it simply.

I have suggestions. Static mongroups (forest/river/swap…) keep in map/multimap/etc. Hordes, ants, fungaloids, triffids - in vector. In overmap::monster_at add vector check. Vector or map has no effect here right? Excellent there is hybrid model. For groups who not move use map. Who can move/grow/die - vector. I accept this: for static mongroup better - use map, but for dynamic using map is very awkward.