Originally Posted in the Dev Pub
The content presented below was originally brewed in the oak barrels of the Dev Pub forums. After allowing this thread time to properly age, it is now ready for public consumption and has thusly been moved into this forum for all to enjoy. Please note that finely aged Dev Pub threads may contain outdated designs and information. That said, we still encourage you to leave feedback as we'd love to get some new opinions on all this.
Accessing the Dev Pub
The Dev Pub is available for anyone who backed the Kickstarter at the Land Shaper tier or higher. (If you backed at those tiers but don't yet have access, just head to the
Backer Verification Thread and we'll get you set up.)
In this first code update I thought I'd dive right into talking about what I'm currently working on. Please bear with me as I find the right level of detail for these posts as I do tend to write a lot so would appreciate any feedback if this is interesting or too much info and I'll try to find a balance!
Populating the New Areas of the Vale!
With the prototype we had somewhat of a notion of sims within a level but it was quite hard to work with (individual files per level making it harder to move sims around and having the data spread out). Since the sims are capable of travelling between levels (to go to work/home/gather/leisure/shop) and can also have homes, this meant the system needed some adjusting which led to the following editor:
This image gives a sneak peek into the coder-art map overview, though I've hidden the names of level to avoid certain spoilers for now. ;) The lines represent links between the levels as they currently stand, but it's subject to change. The houses represent places in each level that a sim can live in. Both the houses and sims live outside the level data. This is handy to avoid coupling the data so it is flexible to change and mainly makes it possible to work with at an overview level of the game so as to better understand the big picture.
Sims can be edited on the following screen (text hidden for spoilers):
At the moment there's not a whole lot to it: you choose the type of sim, their level, and their home on that level if they have one. This data will be expanded on to add the custom data for each sim (such as giving them a different look, assigning them different roles, their age, dialogue set, etc.). Additional work will need to be done to save the state of sims during the course of the game and to allow the sim to run their AI (in very very basic form) while the player isn't on their level. With the sim set up, they'll then appear in the correct level when the player visits that area. Although this data is standalone to the level data it does imply some requirements for the level, in that if a sim is to live there they'll need places to sleep/eat/work/play/relax and won't function correctly without them. Part of the code I worked on makes it possible to see anything that is missing and to also quickly jump around the level and edit them. So by in large it should now be possible to populate all the levels of the Vale if it weren't for one small thing...
Worst Case Level Performance
You might have noticed one region is quite large with 7 populated houses and 17 occupants. This is currently our main village level for the Vale. It'll likely be our largest region in Early Access. Currently it's actually
42 times as big as the farm area but that was more just a very rough initial guess in size! Being that big presented some challenges in the code as the prototype was mainly optimised with the farm level in mind. Generally, the farm level is nearly instant to load, run navigation, edit, etc. This new level though has led to finding a fair few slowdowns in all of those angles and more. That's actually quite a good thing in that it gives a good test case to work with and making this faster will likely result in improvements to all smaller levels too!
I'm not sure how interesting this'll be for many people as it's 'programmer talk' but I'll go through a bit of my findings on the slowdowns.
As a small note, generally my way of working is to get something up and running in a simple way first without optimising or overthinking where bottlenecks might be. This is mostly fine in that PCs can cope with a lot of work nowadays! But at some point the limits of this approach can be tested such as with this level where the easiest way makes assumptions that mean it'll be slow on a lot of data! Being relatively simple code though means hopefully it doesn't prove too difficult making adjustments to make it fast enough again.
I do try to be careful of the overall framerate, which at this point has a fair bit of overhead on my 6 year old PC where generally it only uses 3 or so of the 16.67ms maximum to maintain 60fps ingame...
Loading the Level, Editing, and Previewing:
(>3 seconds on each adjustment)
This was in large part due to collision, currently with 640,000 tiles in the level and up to 8 layers of tiles it was looping through all of them every time. Where possible I tried to minimise how much data it was working on to just what had changed (this helped a lot with editing). In addition to the looping, the collision has a somewhat large array to allocate (which it was doing on every change!). In C#, allocating anything during execution can be bad as it can lead to garbage collection (this gets handled automatically which is nice to keep things simple but does lead to unpredictable behaviour and dropped frames when it decides one needs to happen). So to counter this, it's best to allocate upfront or during acceptable points for unresponsiveness (eg. loading). Just doing the one allocation actually helped quite a lot overall as the first load took the hit and then subsequently it had the data in memory to edit. This got the collision generation down to under 1 second. For a quick win I made it start on another thread (the data isn't really used at startup anyway) so now it would be responsive within 1 second or so. I am still planning to go back to it as really it shouldn't need to check all the tiles at once, just say the ones nearest the player and then it could even just lazily fill in the rest only when they become visible or are checked for navigation for example!
The other cause for slow level loading is the size of the level file (currently it's a text file of some 2 million odd characters) and that takes up most of the second of load time. The two speedups I think I can do here are to use shorthand for repetition (if there's 200 tiles in a row that are all grass, then instead of writing that out 200 times I can write it once and put shorthand in to repeat 200 times) and also switching to a binary format. Binary format is something that'll likely be warranted for the game's release but for editing it is rather handy to have it in text as it makes it possible to compare versions of the level and see what has changed. Implementing the shorthand, combined with the save in parsing values, got it down from 1000ms to 200ms for the level which is much more acceptable! It also shrank the file size from 7.5mb to 50kb, albeit that's because the map is still low on data.
Navigation
(Each sim was taking 7 seconds to generate a route halfway across the level!
Currently the navigation uses the A star algorithm for finding a path. This works fine across small areas of levels but in the case of this one with 640k tiles, it can struggle! If this happened in-game you'd see the sims sitting there stuck for quite a while before deciding where to go. There's a lot of different ways to go about speeding this up and I know I've still got a lot of ways that'll need doing to get this working smoothly. What I've done so far is just to approach it from the speed of the algorithm without seeing how to shortcut it (eg. have precalculated routes or dividing up the level into much smaller grids to navigate).
The initial data structures used for the algorithm were a bit naive, using hashset and dictionary. These are reasonable for lookup speed but depends on the key that it is looking up, which in this case meant they were really quite slow. There's 3 different types of data stored for A star, all the places already visited, all places to check out and a built up list showing how to get to the end via the shortest path. I ended up converting two of these to a 1D array covering the map, this helped bring the time down from 7 seconds to 5 seconds or so.
Next was the remaining data store of 'all places to check out'. This was using an unordered dictionary, which meant that after each place was checked out it had to go through the whole list to find out what the next closest place to check out was. Initially I tried changing over to a linked list, which did bring the speed down further (in conjunction with a better way to evaluate distance to the end and caching some data so that it didn't need to be calculated each time) to about 2.5 seconds.
The linked list ended up still being sort of slow, mainly because of having to go over each element to find where to place new ones in sorted order (and also that the data might not be contiguous in memory). I then changed over to a sorted list which is ready made for ordering on the fly. This seems to have worked in that now it's down under 1 second per sim on average!
This is where I've currently got to, which is a good deal faster, though still in need of further tweaking. As mentioned initially, there are likely shortcuts to be made which will get it down further in addition to this level being too large currently! I've also now taken steps to make navigation threaded, making it a background activity which won't delay gameplay (though I still need to address the memory usage of this as, similar to collision, there is a memory hit each time it runs currently).
So after that performance detour, I'm finishing rounding up work on the population so I can then move onto a new area of work: jobs. So hopefully the next update will be a little less text and a little more coder art/GIF's showing the progress on that! Any questions/suggestions/feedback about what you'd like to see in these posts would be very welcome!
