5/23/2014 - Randomization

Your chance to hear me complain

5/23/2014 - Randomization

PostPosted by Railboy » Fri May 23, 2014 9:08 pm

Hey all - apologies for not showing any signs of life. Development is more fast-paced than ever and it's so, so easy to let days (even weeks!) slip by without realizing it. Thanks to Gazz for poking me and asking for an update.

So what have I been working on? Well now that the issue of memory errors and structure loading is in my rear view mirror I've turned my attention back to the problem of filling out the gameworld with stuff to find. It's all well and good to have hundreds of plants and books and objects to discover, but I can't just dump them into a pile on the player's front lawn. They have to be distributed in a way that makes some kind of sense. But of course like every problem I've encountered this turns out to be trickier to solve than I had anticipated.

(Colors are arbitrary, I just like the way they look.)

Flags

It all starts with object flags. Remember that post about spawning random characters? It's the same basic approach with objects.

Every object in the game has the following flags, which are stored in the WIFlags class.
  • Base Rarity - Common, Uncommon, Rare, Exclusive
  • Wealth - Poor, Middle Class, Wealthy, Aristocracy
  • Alignment - Erasthai, Zenonia, Strata, Bislan, SleepingGod
  • Occupation - Guild, Aristocracy, Priest, Soldier, etc.
  • Region - Benneton, etc.
  • Subject - Business, Personal, Utilitarian, Skill, Scripture, SubjectAgriculture, SubjectArchaeology, SubjectBiology, etc.
  • Faction - Settler, Warlock
All but Base Rarity are implemented using the FlagSet class (also mentioned in the characters post) so these are just integer bitmasks with names attached to make them more human-readable.

Each object also has some basic properties that are used to determine if an object will fit in a container when spawning, or if it's made of an appropriate material.
  • Weight - Weightless, Light, Medium, Heavy, Unliftable
  • Size - Tiny, Small, Medium, Large, Huge
  • MaterialType - Dirt , Stone, Wood, Metal , Flesh, Glass, Liquid , Fabric, Fire, Ice, Bone, Plant
  • CurrencyType - A_Bronze, B_Silver, C_Gold, D_Luminite, E_Warlock
  • BaseCurrencyValue - (0 - x)

Some objects extend the WIFlags class. Books use the WIBookFlags class, which adds the following:
  • SkillSubject - Crafting, Guild, Magic, etc.

So the first step is to go through every object in the game - that's 785 objects not including individual plant species, books or prepared food variations - and set their flags. This takes a long, long time.


Categories

Once all the flags are set the next step is to categorize these objects. This is done using WICategories, which is just a list of objects & spawn probabilities paired with a name. Eg, the 'KitchenUtensils' category might list 'Frying Pan, Fork, Knife, Plate, Cup, Goblet' etc. This may seem unnecessary given that objects already have flags, but context can tie together objects in strange ways that flags can't really describe (at least not without tons more flags). Put another way: Categories describe where you find objects while flags describe what's true about an object regardless of where it's found. (Clear as mud? Good.)

They're also useful for lumping together specific kinds of objects. Instead of creating a 'Table' flag - which would only be used for a dozen or so objects at most - I just throw every table variety into a single category called 'Tables.' Of course tables can show up in other categories too, like 'LargeFurniture' or 'DiningRoomFurniture.' Categories can be as granular as you please. Some contain hundreds of objects, others contain only three or four.

As you can imagine, adding items to categories takes at least as long as setting flags. And I'm constantly creating new categories as I build out the world.


Containers

Between categories and flags we have a pretty thorough description of what an item is and where it ought to be found. This information is used by containers. Containers are objects like chests, bookshelves, barrels, tabletops - anything that can contain other items. This doesn't mean the items have to be hidden from view - in the case of bookshelves and tabletops the stuff that's 'in' the container is in plain view.

Stuff.jpg


If I want a container to spawn objects I attach the FillStackContainer script to it. This script has a couple of different settings. One lets me specify exactly which items will go in the container - useful for quest items and the like. Another lets me specify a category of items, plus a range of total items. A third lets me specify a category, range AND flags for filtering which items can appear. Two barrels can both use the 'FoodStuff' category to fill themselves, but a barrel using the 'MiddleClass' wealth flag may fill itself with tomatoes and parsnips while a barrel using the 'Poor' wealth flag may fill itself with potatoes.

For containers whose objects are hidden from view this script will fill the container the first time the player opens it. Otherwise it will fill the container the moment it becomes visible.

This script will also re-fill containers after a specified interval. By default this setting looks to whether the structure housing the container has an owner (and whether the owner is NOT the player). If it has an owner it will periodically refill the container - the logic being that if somebody lives in the structure their dining room table will eventually be filled with plates and food again even if you've raided the place. There are cases where I'd want a container to re-fill regardless (eg a beehive filling with honey) so I can override this if I like.

When I'm editing a structure in Unity I simply place containers where I want them to appear in the game - wine barrels in the kitchen, chests of gold in the attic, etc. The flags specified in the FillStackContainer script are added to the flags specified in the structure. If no flags are specified then the structure flags will be used exclusively.

And as I discussed in the character spawning posts, structure flags are mixed and matched with city flags, chunk flags, and so on. The result is that a middle-class barrel filled in Riverbog might be full of mushrooms while a middle-class barrel filled in Apple Valley might be filled with Apples, even though the FillStackContainer script uses the same settings in both cases.


Structure Templates

Things get a little weird when I'm using the same structure template for two different structures. A structure template is like a blueprint for the structure - it tells the game where to put walls, ceilings, characters and items. It also tells what materials to use for each part of the structure. What it doesn't specify is flags - that's the job of the structure using the template.

There are over a hundred structure templates, but there are many more times that number of actual structures in the game. So in many cases I'm using the same structure template for multiple buildings. Some variation would be nice in those cases. We've already got some when filling containers, but what about the containers themselves? What if I use the same structure template in a poor neighborhood and a rich neighborhood? If the blueprint just calls for four walls, a roof and a floor, the furnishings and materials can mean the difference between a nasty-looking shack in a bad neighborhood and cute little lakeside cabin in a nice neighborhood. But if the furnishings are the same in both cases that's going to look a little strange.

The solution is world item placeholders. These are similar to containers, but instead of containing objects they just spawn a single object. If I know a structure template will be used once I can drop in a specific bed or chair and arrange it just so. But if I suspect it will be used multiple times I'll drop in a placeholder and tell it to spawn something from the 'Chairs' or 'Tables' category. When the structure is built the structure builder looks at these placeholders, then pulls an object from the category based on the placeholder/structure/city/regional flags. So in a nice neighborhood that bedroom will have silk sheets and the chest a the foot of the bed will be gold plated, and in a bad neighborhood the bed will have burlap and the chest will have spikes.

But this is only a partial solution. When I don't use placeholders I have a great deal of control over the FillStackContainer script. I can tell a barrel spawned in the kitchen to spawn kitchen-related goods. But if I spawn that barrel at runtime, even if it matches the flagset of the spawner, it will fill itself with items from the default 'CommonItems' category. Sure it inherits some information from the structure's flags, and that helps, but we've lost the fine-tuning. I'm working on ways to fix this.


Semi-Randomness

If we were in single-player land I'd make spawning purely random. (Or near enough, anyway - results would be weighted by rarity.) But since this is a multiplayer game spawning has to be reproducible, meaning that the same container spawning on two separate computers has to spawn the same items in the same order. Otherwise the server would have to be solely responsible for spawning objects / distributing that information to every other player - laborious, slow and prone to error.

So instead of using System.Random with the current time as salt to pull a random index from a WICategory, or something along those lines, I pre-generate a lookup table in each WICategory:

Objects in category: [A],[B],[C],[D],[E]
Lookup table: [4],[0],[0],[2],[4],[0],[3],[4],[0],[1],[1],[1]

Each entry is an index for the objects array. The number of times that index shows up in the table is determined by its rarity. The lookup table is generated in order, then shuffled using a function that accepts a System.Random. To ensure the shuffling is always the same, I use the hashcode of the category name as salt.

You might think that's enough - each time I ask for an object from that category it just sends the next index in the lookup table - but because we can't guarantee that the same containers will ask for objects in the same order we need to go a little further. (Plus, a repeating linear sequence of random numbers eventually starts feeling stale. I was surprised at how quickly I noticed repeating patterns on bookshelves and the like.)

To make sure request order isn't an issue - and to avoid noticeable patterns - I generate a third table. This time each entry is an index for the lookup table, and it includes each index [x] times. (So far x is 3; that seems to work.)

Random index table: [5],[11],[10],[0],[5], etc.

Then when containers request an item from the category, they're required to pass a hashcode and an index along with it. This is used to determine where to start looking in the random index table:

Code: Select all
public bool GetWorldItem (WIFlags flags, int hashCode, int index, out WorldItem worlditem)
{
     ...

     int randomIndex = (Mathf.Abs (hashCode) + index) % RandomIndexTable.Length;
     int itemIndex = RandomIndexTable [randomIndex];     

     ...
}


In 99% of cases categories are used in a loop, so there's usually a unique index handy. If we're just pulling one item 0 obviously works fine. As for the hashcode, the full path of the WorldItem making the call is guaranteed to be unique, so I typically use the hashcode for that string. But it doesn't really matter what I send to the function as long as a) it's relatively unique and b) it's always consistent.

Add this all together and you get a stream of items that looks totally random, but ends up being exactly the same each time you do it.


To-Do List:

World Seeds - It would be nice if a single number (derived from the character's name, say) could influence every other element of randomization a la Minecraft. I haven't quite figured out where to put that yet.

Flag-based materials - Earlier I talked about swapping out materials in a structure template based on flags. This works for items but not for the components that make up the actual structure - floors, walls, etc. I can already swap materials manually so tying it to flags shouldn't be difficult.

Restore the ability to fine-tune - Using placeholders in structure templates is useful as hell but I need a way to control the containers that are spawned at runtime. This is currently my top priority.
Language is to the mind more than light is to the eye.
User avatar
Railboy
Developer
Developer
 
Posts: 1845
Joined: Mon Jul 15, 2013 10:46 pm
Location: Seattle, WA

Re: 5/23/2014 - Randomization

PostPosted by Thundercles » Fri May 23, 2014 9:52 pm

My brain is full.
Thundercles
Apprentice
Apprentice
 
Posts: 21
Joined: Thu May 08, 2014 12:54 pm

Re: 5/23/2014 - Randomization

PostPosted by bgivenb » Fri May 23, 2014 9:57 pm

Interesting read. Keep up the good work :D
User avatar
bgivenb
Artisan
Artisan
 
Posts: 63
Joined: Thu Jul 18, 2013 6:21 pm

Re: 5/23/2014 - Randomization

PostPosted by SignpostMarv » Fri May 23, 2014 10:04 pm

Can a barrel be flagged to spawn mouldy potatoes in a poor neighbourhood and gold-plated potatoes in a high-class neighbourhood? :P

Does the structure generator have much of a concept of "rooms" ? Just thinking that if the placeholder spawner has some awareness that it's in a space with a certain level or above of kitchen items, it probably wants to use kitchen items ?
User avatar
SignpostMarv
Alchemist
Alchemist
 
Posts: 307
Joined: Thu Jul 18, 2013 2:28 pm

Re: 5/23/2014 - Randomization

PostPosted by anemation » Fri May 23, 2014 11:05 pm

I beg of you Lars, PLEASE put in an easter-egg where there is a gold potato.
Don't start a fire, you never know how many bridges you'll burn.
User avatar
anemation
Dungeon Crawler
 
Posts: 127
Joined: Fri Jul 19, 2013 6:01 am

Re: 5/23/2014 - Randomization

PostPosted by Railboy » Sat May 24, 2014 12:52 am

anemation wrote:I beg of you Lars, PLEASE put in an easter-egg where there is a gold potato.


*sigh* alright, why not. :)

SignpostMarv wrote:Can a barrel be flagged to spawn mouldy potatoes in a poor neighbourhood and gold-plated potatoes in a high-class neighbourhood? :P


Rooms were an idea I explored a while back (remember the post about door triggers?) and I decided they were more trouble than they were worth. Plus you'd still have to deal with rooms containing objects that aren't 'appropriate' for that room type, which happens more often than you'd think, so we're just back where we started.

This may work in dungeons, which are broken into occlusion groups / modules. Each module could have its own flagset. But that setup doesn't carry over to structures.
Language is to the mind more than light is to the eye.
User avatar
Railboy
Developer
Developer
 
Posts: 1845
Joined: Mon Jul 15, 2013 10:46 pm
Location: Seattle, WA

Re: 5/23/2014 - Randomization

PostPosted by anemation » Sat May 24, 2014 12:56 am

**** YEAH!!! You're awesome!
Don't start a fire, you never know how many bridges you'll burn.
User avatar
anemation
Dungeon Crawler
 
Posts: 127
Joined: Fri Jul 19, 2013 6:01 am

Re: 5/23/2014 - Randomization

PostPosted by SignpostMarv » Sat May 24, 2014 8:42 am

Railboy wrote:
anemation wrote:I beg of you Lars, PLEASE put in an easter-egg where there is a gold potato.


*sigh* alright, why not. :)

SignpostMarv wrote:Can a barrel be flagged to spawn mouldy potatoes in a poor neighbourhood and gold-plated potatoes in a high-class neighbourhood? :P


Rooms were an idea I explored a while back (remember the post about door triggers?) and I decided they were more trouble than they were worth. Plus you'd still have to deal with rooms containing objects that aren't 'appropriate' for that room type, which happens more often than you'd think, so we're just back where we started.

This may work in dungeons, which are broken into occlusion groups / modules. Each module could have its own flagset. But that setup doesn't carry over to structures.


What about objects on the same surface ? i.e. placeholder object looks for coplanar objects within a bounding area of (X * obx, Y * oby) ?

e.g. small placeholder container on the surface of a table that has a ladel on it is more likely to spawn a bowl of fruit than a pot of paint brushes.
User avatar
SignpostMarv
Alchemist
Alchemist
 
Posts: 307
Joined: Thu Jul 18, 2013 2:28 pm

Re: 5/23/2014 - Randomization

PostPosted by Starfia » Sat May 24, 2014 6:02 pm

Wow, thanks for that – this was the most interesting of the dev-related mini-posts. I still wonder about how games from decades past have dealt with Schrödinger's proverbial treasure chests and so on.
User avatar
Starfia
Bard
Bard
 
Posts: 158
Joined: Thu Jul 18, 2013 5:57 am
Location: Bellingham, Washington


Return to Dev Logs

Who is online

Users browsing this forum: No registered users and 1 guest

cron