Login / Register

Latest official blog posts

Save and Load

13th January 2021

Does anyone want to know how save games work in video games? Yeah! of course you do! I've spent the last two weeks working on it. In a simulation game you can't get very far testing things without being able to save. I suppose you can, but you'd spend a lot of time recreating the conditions you need to test a new feature or fix a bug.

The basics of saving are pretty easy. You write out all of an objects properties. What model and materials is the object using? Does it have collision and pathing information? Does it store inventory? What animation is playing? What plan has the AI made? When you read it back in, you just take that data, and setup the object again based on what was stored.

Then it gets harder. Let's say there are several hundred objects. And some of them reference each other. An character might have a target that it is following. When the game is running, this is easy - that character stores the physical (well, technically virtual) address in memory of the item it needs to reference. But when the game goes to write that out, I can't write the physical address. It's meaningless. Because the object is probably going to be in a different place in memory when it's recreated on load.

So I have a system where each object is assigned an identifier. It's just a unique number. The first time an object is written out to a save game, the full object is written, and then its identifier. After that, if the object is referenced again, just the identifier is written. When the save is restored, the object is read in, and while the object gets a new unique identifier, the previous identifier is stored in a dictionary with the objects new address. If references are encountered, the identifier can be looked up and exchanged for the new memory address of the object.

Alright, so now save game works! Well, that was it for my last game. But this one is slightly more complicated, and consists of the bulk of my recent work.

Since the game is going to be open world-ish, saving is harder. The first thing to consider is that when the player is far away from some regions, they don't need to be simulated. So when they go out of range, they get removed. But whatever the player has done in the area needs to be saved. So the same save process happens, but just for that area.

A bit of care needs to be taken here, because to save a group of items together, they can reference each other, but they can't reference things outside the area. So the region is disconnected from the rest of the world. I have some safety code that ensures the disconnection - if something goes to write to the save that isn't in the region, that's a fatal error and needs to be fixed before I can proceed.

The game also can't pause to do these types of saves. So after being disconnected, the save process happens in a background thread. This save data is just kept in memory, rather than being written to disc.

The loading process for this is similar. A background process loads the needed resources, all objects and references are restored, and then the region is connected to the rest of the world and the player can then interact with it. This happens hopefully before the player gets near the area so the world appears continuous. There's some safety code there as well - if the player somehow gets too close to the area before the load and restore is complete, a message appears that loading is occurring and the player has to wait.

So when a normal save comes along, all active game play regions undergo the same process as above, anything remaining goes through the normal save process, and all the chunks of memory that were saved for each region are written to disc.

This whole process took a while to get right, and to get all the bugs worked out. One single piece of information not saved, and really strange things happen when a save game loads. For example, I had a bug where a save game would load and all characters would face east and quickly turn to the direction they were supposed to be facing. I had just failed to save out the current direction they were facing. Another example - I was dealing with objects being duplicated, since multiple areas were referencing the same object. That was before I added the safety checks for objects not being written if they were in different areas.

Dealing with references was tricky too. Since objects depend on each other, loading has to be done in three passes. The first pass restores values for each object. That's generally easy. However, there are internal dependencies in an object. Graphics are totally separate from animation which is separate from audio, but a logic controller might reference all three. Since the graphics component might not be loaded before the controller, anything to configure that uses those dependencies has to be delayed. That's what the second pass is for. Finally a third pass is made once all objects are setup so that external references can be dealt with. Like making sure that an animation of a bow pointing at a specific target can be setup to point that way and the initial animation is in the right pose.

Once save game was working properly, I then wanted to deal with space requirements. The image below has 9363 objects placed on it. You can't see all of them, since small ones disappear when they are far away, but they are there.

135-0.jpg

Saving all of them requires 3.7 megabytes! That's around 400 bytes per object! yikes! It seems like a lot, but each object is storing a lot of gameplay data you don't visually see.

Each object has some overhead making them future proof. Each section of an object, (graphics, audio, collision, animation, ai, etc) has a header and footer, version number, and size. This allows me to make sure when the data is read back in everything is read correctly. It allows me to make additions in future versions, read the old data, and setup any new data. It allows me to skip over any sections that aren't needed anymore. It gives me safety when I change code and forget to update the save function - i'll get a fatal error that the code doesn't match the data written to disc.

This large size doesn't seem a huge deal, until I consider that a player might visit 100 such places. I dont want saves to be 370 megabytes. A player might not go that many places or the save might not total that large, but I need to deal with worst case.

My first fix was to apply a quick LZ compression. Since the trees and rocks save data are self similar, there's a lot of data repetition, so that takes it down to 731 kilobytes. That's 5 times smaller, but still not great, and real game data will have much more variety. I've got some Huffman/Arithmatic encoding I can do as well that brings it down another 50% or so, but I had a better idea.

Items placed on the map are known ahead of time. Even if they are procedural, they can be computed. But a player can interact with every one of them, removing them or changing them, requiring them to be saved. So what if instead, I track if a player has modified one of them. Say cut down one tree. Then I can just procedurally generate all but one of them, skippng over the one that was modified. I can store a single bit per object, which tells if the object is placed as it was on map creation, or it's been modified or removed.

If the tree is in the middle of being cut down it's saved as a full object. If it's gone it costs nothing but 1 bit. If it's there it costs 1 bit. All the sudden 3.7 megabytes becomes just over 1 kilobyte, plus a little for any object that is being interacted with.

As development continues I plan on extending this system a little further. I can precompute objects that aren't there initially. For example if you can plant a forest of trees on a plain, I can have the positions precomputed, but the objects not added. When a tree is planted later, it uses one of the available positions. For a while, the tree grows and is stored as a full object. And when it's reached full growth, the bit is changed to have the tree be there on load, and it costs nearly nothing in save space.

This way the majority of the simple objects in an area cost nothing to save. The save game size will be determined as just what the player builds and by the characters that are walking around. Certainly if a player builds 1000 buildings save games will be bigger, but it's unlikely they will do so across many different places.

Saving is one of those things that's so important, and no one ever notices if it's working like its supposed to. So now saving is out of the way, except for nice menus and interface. Hopefully next time I'll be talking about the beginnings of my new AI simulation.

View comments »

Let’s sum up…

16th December 2020

Do you ever get into working on something, and you're absorbed in it, and you keep putting off telling people about it? I apparently do...

134-0.jpg

So about a year ago I started work on trying to make AI characters more flexible compared to Banished, both in what they do visibly and in the way the code and data are setup. I wanted characters and objects that could be modified by me and by end users easily, because modding is cool. But things spun out of control. A bit.

I started with a text based behavior tree system, which once I got working looked a lot like a scripting language, so I started adding other features that made it a scripting language. (I had a post ready to go about how awesome it was.) It then got more complicated, needed a runtime debugger, and it started running other parts of the game, not just AI. Maintaining it was getting messy. Writing a game in a language that is being modified is not cool. Having script do slow things was not awesome. Not making progress on a game because you're writing something to write the game is not the best.

The only great thing about it was that writing a programming language was personally satisfying. But it just doesn't get other projects done. I could have told you that before all this, but I fell into it a trap I knew about.

One day, I just deleted all the code, and immediately felt better. But don't worry, it's in source control if I want any of it back. There were some cool tangential things in there that I might use one day. It was time to move on and work on something different for a bit.

I tend to turn to graphics related things when I need a change of pace. So...

What I'm working on is now open world-ish. And as I started moving between play areas, which are currently islands, they visibly deformed. Mountains flattened, detail disappeared jarringly, and area near the coast line changed unacceptably. I stopped using a system of regular grids that smoothly changed detail based on distance. I instead switched to a system that is based on binary triangle trees that subdivide detail levels based on an allowed error metric. I'm using simple geo-morphing to smooth out the cracks between detail levels. This allowed islands to keep more detail in rough parts, and at coastlines, and use less detail in flat parts. It also reduces triangle count under water since you never see it. It uses an order of magnitude less triangles for the same and even better perceived detail, so it maybe even renders faster.

134-1.jpg

And, yes, I know the newer hotness is using the tessellation units on the GPU to add detail in areas based on view distance and terrain roughness, and sampling the height on the GPU as well, but I want to keep my shader model on the low side so that the majority of older GPUs out there can run the game.

I also added pre-built low resolution versions of islands with baked textures, so distant views can load them fast and display them in a single draw call without the overhead of having an entire terrain and all textures loaded.

With that out of the way I started filling in some missing parts of the scene, basic sky, simple ocean, and a unified lighting model for everything. It doesn't look the greatest, but for now gets the point across, and is setup to allow for some neat effects. Waves, clouds, time of day, sunsets, etc. All lovely things that will wait until later.

134-2.jpg

Going open world is tricky. I can't load and generate and run everything at once. Some things need to be loaded in a low resolution, some full resolution, some not at all. When you leave one place, everything needs to be saved so that if you come back it's still there.

To assist with this, I changed my game engine from having one scene to multiple scenes. Imagine a scene as a collection of the visual display, the collision data, pathfinding data, and a bunch of objects that do things grouped together. Having multiple of them allows me to load them in the background, perform any expensive setup or shutdown, and then add or remove them from gameplay in an instant as needed.

Making a change like this to an existing engine is painful. In theory it sounds simple, like, just create another one of what's already there and be done! But all the separate scenes need to work together when running - they aren't always isolated regions.

And each scene has its own transformation, which can make thinking about where objects actually are slightly more difficult. At a high level I treat everything as being in world space, but each scene has its own local transform that it works in.

I broke everything temporarily and had to modify almost every underlying system that runs the game. That's graphics, hierarchy and animation, audio, pathing, collision, entities, background loaders, and the core engine loop. Phew.

To be fair, I did it piecemeal, and wrote a test app that didn't use most of the engine at the same time so I could test the change to each system. Changing 100's of files without regular testing is just disaster. Once put all together, debugging was a fun few days of mysterious problems and errors. All seems well now.

With that out of the way, it's time to start implementing things that the AI does again. Anything that was behavior tree/script just doesn't exist anymore. So a bit needs to be redone. It's a bit like coming full circle and sort of starting over.

I hope you are all well, hugs to all this year, it's been crazy, and thanks for reading!

View comments »

Small Ideas, Big Changes

1st October 2019

As I've been working lately, I've been very aware that seemingly simple things I wanted to have in a new game have huge implications on the difficulty of making a game and engine.

The first thing I wanted to change from the previous game was the ability for the camera to look up toward the horizon. In Banished the camera always looked down, and the higher the camera got, the more the ability to look up was limited.

This was great for performance - it limited the number of objects drawn, and no graphics models needed simpler level of detail (LOD) versions. The terrain was simple. I didn't have to have a fancy sky drawn, nothing had to be drawn past the mountains at the edge of the map. The drawback was that you couldn't ever see the whole settlement once it got large. You also couldn't move around very quickly.

Now with that simple change - looking up, and zooming farther out there's more work to do. All models need some of LOD to keep the triangle count down and keep highly detailed objects from aliasing in the distance. The terrain now has LOD as well. Having LOD on the terrain makes texturing it and having decals on it harder. And brings in other problems like objects disappearing or floating because the terrain is less detailed in the distance. I also have to draw to the horizon, ocean or mountains, the sky, the sun.

Drawing shadows also takes more time. Instead of a single shadow map based on what's visible, to draw to the horizon takes multiple shadow maps, various tricks for distant shadows, and more complex pixel shaders. This also increases CPU load as 4 shadow maps are drawn instead of 1.

The renderer also has to change to handle this. While it works just fine, it's slow. Instead of dealing with say 4000 visible objects in view, my current test scenes are dealing with 40000. So the renderer has to be changed to handle culling away and drawing 10 times the number of objects in the same amount of time as before. Granted GPUs are a bit faster than before, but CPU time hasn't increased the same way.

After the camera change, the next change I thought wouldn't be so bad is arbitrary layout of buildings. No grids. Grids were great in Banished because it made lots of things simple. Pathfinding was on a grid, placement of objects was on the grid, everything used the grid.

But I want to see organic layouts. I'd like farmed land to follow terrain and butt up against a river. I'd like buildings and roads to placed in whatever natural way they end up being.

But with the grid gone, lots of things are more complicated. Placing objects now requires checking an arbitrary shape against everything else already placed. This requires a spacial subdivision structure to be fast. It's also harder to visually convey the overlap and how far you might have to move something to get it to fit.

It also adds a little friction to placing buildings. With a grid, you might place 2 buildings and leave space inbetween for something else - because you know its size. With arbitrary sizes, rotations, and shapes this can get harder, and potentially frustrating. When you do want to line up objects, its not as easy either.

Because things are arbitrary, I'm no longer limited to square regions - players can create any shape for an area - which is great, but makes the user interface more complicated. At the same time it can add friction to the experience because you have to spend time layout out areas if you don't want the results of a quick click-and-drag.

I've been working on making placing arbitrary objects and regions as painless as possible, but it's challenging.

As I wrote about last month, pathfinding has also gotten more complicated. However with the complexity comes flexibility. I have pathing setup such that characters can always walk between buildings, reducing the chance of getting stuck, and decreasing search time while running the A-Star algorithm. Search time is also decreased due to much more open area.

Thankfully, graphics doesn't get anymore complicated, it was written to handle things in any orientation from the start.

These two seemingly simple changes have caused my game engine to get slightly more complicated. What is hardest is that there's even more tiny details than I've written about that I keep running up against that were unknowable until I ran into them. I've spent more time making the features work than expected.

In the end, these changes are good - even I went back to building a grid based game with limited camera. It's just surprising to see how far reaching a simple design decision can be.

View comments »