[Solved] [LUA] Best way to approach random unit spawns for large map

[Daoi]

Essentially wondering if anyone has any good advice/experience with randomly populating units in a map.

I have a 512x512 map (probably overly ambitious in hindsight) and wanted to add some randomization to the unit spawns for the map. Started out with Random Groups (under the advanced menu in the world editor) but it seems like the sets only roll once per map. This led to me writing a more or less proof of concept for a Random Unit Spawn system using a similar approach. Unit Spawn groups made up of Unit Spawn Positions (each group has an arbitrary number of positions with an arbitrary number of units allowed to spawn in that position, or whatever lua's table size limit is). The system takes a Unit Spawn Group, an x,y coordinate pair to act as the center of the group, and a shape spawn function (e.g. Square, Polygon, Circle, Triangle) in which to arrange the units.

Anyway, everything with the system works fine so far, however, I've realized that this will likely require a lot of manual recording of my X, Y "unit group center coordinates"
Current thoughts are basically creating a bunch of tiny regions for my center cords and giving them a descriptive name and then matching that name in a lua script with the associated x/y values (Essentially an in memory db) and using those to create the spawn groups.

My question is more or less, is there a better way to go about this I'm not thinking of? Something to simplify/reduce the need for manually creating all these individual spawns. i.e. using convention over configuration? As well as if there are any concerns I should have with generating such a large number of units. My current assumption is that I'll have to use timers to do it over a longer period of time, and maybe have some initial delay at the beginning of the map load to ensure everything can spawn without any issues.

As far as I can tell theres no way to loop through all the regions and their names in the map or get them by name via the Lua api, but maybe having my "in memory db" be a table of descriptions (e.g. EasyBanditGroup# and x/y pairs) and looping over that would allow me to use covention somewhat at least.

Appreciate any feedback/advice.

 

[Uncle]

How about instead of Regions you use a special unit (Circle of Power for example) and add these to a group during the setup process. You can then store their x/y coordinates, remove them, and create the Random Group at these coordinates. You could use a model with high verticality (like a beam coming down from the sky) so it's easy to see in the editor.

Also, the main issue with too many units is when they're all owned by the same player and you try to issue orders to them. This can lead to the "units ignoring orders" or "units freezing/stuttering" issue that many people have made threads complaining about over the years. The solution is fairly simple, create a system which divides your computer units amongst multiple computer players. So if you spawned in 100 Kobolds for the Computer, instead spawn 10 for CPU 1, 10 for CPU 2, 10 for CPU 3, etc... You can give these Computer players the same name/color to trick the users into thinking that they're all owned by the same Computer player.

 

[Daoi]

How about instead of Regions you use a special unit (Circle of Power for example) and add these to a group during the setup process. You can then store their x/y coordinates, remove them, and create the Random Group at these coordinates. You could use a model with high verticality (like a beam coming down from the sky) so it's easy to see in the editor.

I did consider that approach, I think my main concern is then needing many different units to represent different spawns (e.g. circleofpower1 = SmallBanditGroup, circleOfPower2 = mediumBanditGroup). It would save a lot of the configuration/static variables however. Perhaps its worth investigating more though to get a scope of the number of different "Circle of powers" I'd need.

Also, the main issue with too many units is when they're all owned by the same player and you try to issue orders to them. This can lead to the "units ignoring orders" or "units freezing/stuttering" issue that many people have made threads complaining about over the years. The solution is fairly simple, create a system which divides your computer units amongst multiple computer players. So if you spawned in 100 Kobolds for the Computer, instead spawn 10 for CPU 1, 10 for CPU 2, 10 for CPU 3, etc... You can give these Computer players the same name/color to trick the users into thinking that they're all owned by the same Computer player.

This is great to know, thanks. I was aware of the issue somewhat, but didn't realize it was caused by number of units per player as opposed to total units on the map at once. I imagine knowing this will save me some frustration down the line.

 

[Uncle]

I'm almost certain you could get the name of the Region in Lua and use a String comparison to determine it's "category". I'm going to bed but I'll look into it tomorrow if you don't figure it out.

 

[Dr Super Good]

I have a 512x512 map

The map size limit is 480x480?

or whatever lua's table size limit is

Lua tables do not have reasonable limits. Yes they have a limit to how many mappings can be in them, but memory usage will likely be an issue long before hitting that limit.

As far as I can tell theres no way to loop through all the regions and their names in the map or get them by name via the Lua api, but maybe having my "in memory db" be a table of descriptions (e.g. EasyBanditGroup# and x/y pairs) and looping over that would allow me to use covention somewhat at least.

Lua does support iterating through global variables such as those the editor makes for "regions". What you can do is name all regions with the same spawn type in a structured, sequenced, way that you can iterate through. Then in the Lua script you create a table which contains the region name and spawn description. When entries of that table are processed, you iteratively look up the associated region sequence until the sequence end is encountered, and setup your spawn logic. Regions for a spawn type can be added and removed trivially by at most renaming 1 other region to avoid gaps in the sequence. Spawn types can be changed trivially as well by entering or removing unit types from the Lua table for that region. This system could be expanded to support multiple region sequences for the same spawn type to give further potential to reduce data redundancy.


For example, some region sequences could look like.

SpawnsForest1
SpawnsForest2
SpawnsForest3
SpawnsForest4

SpawnsGrass1
SpawnsGrass2

Some tables to configure those regions could look like...

##Possible format for table of spawns.
{Wolves={...},
Bears={...},
RabidCows={...}}

##Possible format for mapping spawn location to region.
{{Regions="SpawnsForest", Spawns={Wolves, Bears}},
{{Regions="SpawnsGrass", Spawns={Wolves, RabidCows}}}

This data would then be processed when setting up the spawn system into a machine friendly form, such as mapping an individual spawn point to a list of possible unit types to spawn there. An example of what such generated tables might look like...

{SpawnRegion=gg_rct_SpawnsForest1, SpawnTypes={FOURCC("H000"), FOURCC("H001"), ...}, SpawnedUnit=nil, SpawnTimeRemaining=69}

To increase the performance of your map you can only spawn units when they are relevant to players. For example, if your map is an RPG and all players are only fighting in the starting zone, then there is no need to spawn units in any other zone as the players cannot interact with them. When 1 of those players moves out of the starting zone into the a forest, then the spawns for the forest turn on and it looks to the player that the spawns were already there for them to fight. This logic could be entirely proximity driven, with a polling, possibly quad tree based logic turning spawns on and off as players move around.

 

[Daoi]

The map size limit is 480x480?

You are correct, I misremembered the numbers, 416x416 map size.

Lua does support iterating through global variables such as those the editor makes for "regions". What you can do is name all regions with the same spawn type in a structured, sequenced, way that you can iterate through. Then in the Lua script you create a table which contains the region name and spawn description

I had thought of this right before I went to sleep last night, I feel extra dumb because I already use something similar for a different system.

Then in the Lua script you create a table which contains the region name and spawn description...
...SpawnedUnit=nil, SpawnTimeRemaining=69}

This is pretty much exactly what i had in mind

To increase the performance of your map you can only spawn units when they are relevant to players. For example, if your map is an RPG and all players are only fighting in the starting zone, then there is no need to spawn units in any other zone as the players cannot interact with them. When 1 of those players moves out of the starting zone into the a forest, then the spawns for the forest turn on and it looks to the player that the spawns were already there for them to fight.

This is a good idea and what I will likely go with.

This logic could be entirely proximity driven, with a polling, possibly quad tree based logic turning spawns on and off as players move around.

Would you mind elaborating on this part? Are you suggesting breaking up each region (e.g. "Forest") into 4 subregions and spawning units as the players progress through them? Are you thinking the parent would be the entry point cordinates and leaves would be the 4 regions to spawn? Iterate over the child nodes when the parent is entered, get all regions within the cordinates of that child node and run the spawn logic?

Thanks for the very detailed response!

 

[Dr Super Good]

Would you mind elaborating on this part? Are you suggesting breaking up each region (e.g. "Forest") into 4 subregions and spawning units as the players progress through them? Are you thinking the parent would be the entry point cordinates and leaves would be the 4 regions to spawn? Iterate over the child nodes when the parent is entered, get all regions within the cordinates of that child node and run the spawn logic?

I was referring to using a quadtree data structure for proximity based lookup. This would let you efficiently find nearby spawns to enable them in a way that could scale to many units. For example, enabling all spawns within 2,400 range of the player's hero in an RPG map, disabling any that fall outside that range. Without using a quad tree like data structure, you would need to iterate through all possibly spawn points on the map and perform a distance comparison, which will not scale very well.

Technically something like a k-d tree would likely be best.

k-d tree - Wikipedia

en.wikipedia.org

 

[Daoi]

I was referring to using a quadtree data structure for proximity based lookup. This would let you efficiently find nearby spawns to enable them in a way that could scale to many units. For example, enabling all spawns within 2,400 range of the player's hero in an RPG map, disabling any that fall outside that range. Without using a quad tree like data structure, you would need to iterate through all possibly spawn points on the map and perform a distance comparison, which will not scale very well.

Technically something like a k-d tree would likely be best.

k-d tree - Wikipedia

en.wikipedia.org

Hopefully this doesn't count as necroing, but I was away for a couple weeks. I got back recently and got around to finishing the system. I did end up going with a quadtree data structure and its working out quite nicely. Using region names to store the spawn meta data does the trick, even if it's a bit messy. Overall it accomplishes everything I need to and some additional metadata allows me to attach random bonuses to units (i.e. diablo affixes), set weightings for individual units (e.g. "bandit" has a 1.5x higher chance to spawn at a point then a higher level "rogue") and even easily apply scaling based on player number or potentially difficulty settings or both.

I'd love to share the system but unfortunately the vast majority of the work isn't super generalizeable and relies tons of data setup, but maybe I'll clean it up overtime and get it to a more generally useful point.

Here's a quick demo for anyone who might be interested, the spawn frequency is longer than it needs to be for this, can probably watch the video on 1.5/2 speed safely. There's nothing too interesting going on.