Efficient way to handle large-scale unit-terrain interactions?

[RoachForge]

Hi. I started recently working on a Warcraft 3 map inspired by Dominions and Age of Wonders games and I decided to implement biomes which apply different penalties on units passing through them. Currently I use neutral dummies with auras to make this happen, but after snooping around a bit in the trigger editor I decided I could be a bit more ambitious. If I could apply buffs to units based on the terrain they stand on with triggers, I could add exceptions (like a unit being immune) and maybe add mechanics that alter terrain tiles and so on, making things infinately more fun and interesting. So now I think my approach should involve periodically checking unit positions and applying abilities to simulate environmental adaptation. However, my map could have over 1000 active units at peak gameplay on 364x364 size map with 30 - 40% of it covered in the biomes.

I feel like it would be audacious to ask for more experienced people to trigger this for me (unless you feel like it, then please do haha) so I'm asking for opinion. Is this method viable performance-wise (even with using hashtables, indexing and other stuff), so that I could either rethink it or scale down the unit count. I'd hate to run into issues when I'm already deep in it.

I appreciate any insights from experienced map developers. Thanks!

 

[Uncle]

I would try to leverage game memory and spread the "terrain check" logic over time as opposed to doing it all at once. What you don't want to do is loop over a Unit Group with all 1000 units inside, get each unit's position, and then check the terrain type at said position. That'll create a noticeable spike in performance since it's such a large task to process. By doing that you've essentially dropped 1000 "reports" on the desk of your CPU and asked it to have them all "filed" immediately. Instead, you can give your CPU 10 "reports" to handle every 0.04 seconds. That way you'll end up with roughly the same outcome without the massive spike in performance.

So with that in mind, here's what I would do (not saying this is the best solution):
1) Create an Array of Unit Groups.
2) Add units to the Unit Groups as they come into play. Never exceed more than 10 units per group.
3) Ensure dead units are Removed from their Unit Group. To be efficient, link them to their group by using Unit Indexing or a Hashtable for quick access.
4) Avoid using the "Count units in group" function and track the group sizes yourself using an Integer array. (I believe the original function is slow)
5) Run a Timer that periodically increments an Integer which represents the active Unit Group. Then loop over said Unit Group and handle your Terrain-Type logic for each unit inside. So if you had 30 units spread between 3 groups then you would cycle from group 1 to group 3 then back to 1 again (rinse and repeat). The shorter the timer's expiration the more responsive but also more expensive the whole process will be.

Here's an example of Adding a new unit to a Unit Group, minus the "Never exceed 10 per group" stuff:

• Actions
  • Set Variable New_Unit = (Entering unit)
  • Set Variable Group_Index = (Group_Index + 1)
  • Set Variable Unit_Group_Index[(Custom value of New_Unit)] = Group_Index
  • Unit - Add New_Unit to Unit_Groups[Group_Index]

 

[RoachForge]

Thank you for the ideas. I've messing around with these triggers for quite a while now and every working iteration feels clunky. Sometimes a unit among several doesnt get a buff or something along those lines. So I started thinking. What if instead of using groups I assign all the rects with a terrain type to a single all biome encompassing regions (forest, desert etc) at map init, which adjust during game to spells, season change events and other stuff that change terrain. I could just use Unit enters Region, remove all other biome related spellbooks, check for exceptions and give entered unit biome spellbook. Is this possible?

 

[Uncle]

You have to be careful with excessive Region usage, but of course it's possible.
Here's some info about limitations although I'm sure your map won't be nearly as heavy in the Region usage:

[Trigger] - Creating regions: optimization required.

Context: I'm using either hand-placed (for small maps) or generated regions for TBS gameplay. When I worked with tiny maps, everything was rather easy and done via several loops within loops. However, now I'm working with the largest map (3 500 640 regions) and can't use Wc3 in-built loops...

www.hiveworkshop.com

Anyway, you have an Event for when a unit Enters a Region and you have an Event for when a unit Leaves a Region.
Add/Remove abilities as they Enter/Leave.

This thread contains information and a "fix" that may or may not be required:

[Solved] - Any better solution for the detect leaving region?

Description: When unit leaves the region, triggering units orders center of the leaving region. OrmanRegen Events Unit - A unit leaves NcUstCheck6 Unit - A unit leaves NcUstCheck5 Unit - A unit leaves NcUstCheck4 Unit - A unit leaves NcUstCheck3...

www.hiveworkshop.com

Also, I have a feeling that you implemented my suggestions incorrectly if a unit "doesn't get a buff". Worst case scenario the unit will get the buff ~1-2 seconds late but it should always get one.

 

[Retera]

Hmm. If we use the philosophy that wc3 is a lame C++ blackbox and everything is about leveraging what is already there, I wonder if it would be efficient to do something like this:

Identify the list of "ground effects"/"biome" types that you have. So for example, if Lava does damage over time, or Vines causes slow, they would be one distinct "type".

Make one trigger and one tiny offscreen region for each biome like this:

• Event: A unit enters (Lava region)
• Action: Add (damage over time spellbook thing whatever) to (Entering unit)

Then a second trigger for the same region:

• Event: A unit leaves (Lava region)
• Action: Remove (damage over time spellbook thing whatever) from (Leaving unit)

Then, make a Map Initialization trigger which loops over every cell of terrain on the map, and use the RegionAddRect / RegionAddCell or whatever natives to append any area of the map that is Lava to the region named (Lava region) and any area of the map that is Vines to the region named (Vines region). If you hit the iteration count limit or a lag spike, split this loop out across the first few seconds of gameplay. (So if your map is 480x480 maximum size, you would have 230400 cells each the size of a farm, and each of those is 16 pathing cells. So, we might be looping 3686400 cells, which is more than a million. Maybe divide it by 5 and split it over the first 5 seconds of play.)

If a unit casts a spell that changes an area of ground to be Lava, include in the spell or action to do RegionAddRect or whatever to add the affected area into (Lava region).

It's been a while, but I'm pretty sure this would work because under the hood, Regions on Warcraft 3 are a distinct code type from Rects. Regions, if I recall, can have any shape or size. Additionally, you can express 90% of this interaction as non-leaking GUI - quite literally, "When a unit enters Lava, give him Lava Buff." By keeping it simple in this way instead of dealing with bunk timers and other complexity, we leverage the game's blackbox to detect what we need. If the game is to slow and can't process what we need, then, I don't know... let's get a better one.

Edit:
Nevermind, now that I think about it, TriggerRegisterEnterRectSimple is lame, does leak, and will not do what we want. So, you can still do what I'm saying I'm pretty sure, but do it in JASS/lua instead of in GUI, since GUI cannot express it.