I’m getting to the point where I want to start sending the game out to the wider world. If I send someone a link to the game, I’d like them to be able to start playing right away.
Unfortunately, the game is primarily multiplayer which means it requires extra effort to find someone to play with you. So I’m investing a bit of work into making AI players. They don’t need to be particularly skilled, just able enough to let a new player can try out the game on their own.
A particular challenge for an AI in Stone Monarch is how to build a base. Since there are so many building blocks and bases can be built in 3D, an AI can’t just randomly place buildings on the map and expect them to fit in with other stuff they have built.
To solve this, I first built an AI Editor that allows a designer to specify how buildings should fit together. The designer can define “tiles” that consist of several buildings, and then can specify how those tiles are allowed to connect to other tiles .
The AI Editor
Initially, to fit these tiles together I tried using a greedy algorithm. The AI would just build one tile first and then randomly attach matching tiles until it couldn’t find anything that fit anymore.
Unfortunately, the greedy algorithm doesn’t do a great job of producing coherent bases. In particular, walls don’t end up enclosing anything. Often the AI “paints itself into a corner”. The overall effect doesn’t look very planned.
(I wish I had a screenshot of this but apparently I never saved one)
After some more research, I’ve switched to a constraint propagation approach. In constraint propagation, the AI maintains a list of all potentially valid tiles at any particular location. When it builds a new tile, this counts as a new constraint on what is allowed to be built nearby. The AI updates all adjacent locations to narrow down their list of valid tiles. Then, it updates all locations adjacent to those locations and so on, propagating the constraint through the entire space.
An example of constraint propagation. The numbers are the possibilities for each location. Green is the location that will be built next, and blue are the updated constraints.
The end result is that each location stays up to date about what tiles can possibly be built there in the future. Armed with this information, the AI always chooses the most constrained location (the location with the fewest possible tiles) to build next. This goes a long way towards preventing the AI from trapping itself into a bad design.
Constraint Propagation
As the video shows, the bases look logical and are satisfying to watch being built!
It’s also possible to specify an initial set of constraints on the base, for example, that the edges of the base all count as “outside” and that locations with resources in them need to be kept clear. The AI will naturally take this into account.
Note: This approach is very similar to the popular “wave function collapse” algorithm. Although I haven’t examined the code for it, it’s a great example of constraint propagation producing beautiful results.
Stone Monarch has supported multiplayer games from the start, but over time the networking model has gone through several iterations. I initially implemented a peer-to-peer lock step model based on this famous Age of Empires article.
Peer-to-peer lock step has some well known issues. The peer-to-peer aspect makes it hard for players to connect with each other and increases the network load with each new player. The lock step aspect is prone to tricky bugs where the game state gets out of sync between players. My current architecture introduces a server and also relaxes some of the deterministic requirements of lock step. It still uses the lock step concept of ‘turns’ to ensure that each client runs the same simulation and does not proceed without receiving the orders of all players.
Client-Server Lock Step
The game is divided into a series of ‘turns’ of a set duration. The first step at the start of the game is to determine the length of 1 turn. This is done by measuring the round trip time of a message from each client to the server. The server picks the longest time as the turn length. During the game the turn length can be adjusted based on observed network performance.
Whenever a player wants to perform an action, the requested action is immediately sent to the server. The server aggregates all actions it has received until it reaches the next turn boundary. At this point the server sends a turn message to all clients with the actions to be executed 1 turn in the future. By the time the clients are ready to execute the following turn, they should have received all the information necessary to simulate the turn.
In the example above, the turn length has been set to 100ms. The server receives actions during turn 1, and at the start of turn 2 it sends out a turn message with actions for turn 3. This should arrive at the clients in time for them to execute turn 3.
Handling Delays
If one of the clients does not receive a turn message by the time it is ready to execute that turn, it must pause the simulation until it receives the turn from the server. Once it receives the turn, it can immediately start executing again. At this point the client will lag slightly behind the server’s simulation, so it is more likely to receive turns in time. However, there will be increased latency between when the player’s commands are issued and when they are executed.
To prevent a client from lagging too far behind the server’s simulation (and suffering from high command latency), the server can attempt to detect this and pause its own simulation. To do this, the client can include the current game time with each action that it sends to the server. The server then compares this time with the current game time in its own simulation. If the difference is greater than the length of 1 turn (or any arbitrary length), the server can pause to allow the client to catch up. If any other clients are further ahead in their simulations, this is likely to cause them to pause too until all clients are more in sync with each other.
In my original implementation I made every pause be equal to the length of 1 turn, which seemed logical to keep clients from slipping ahead or behind each other in their simulation. However, the current method has dramatically reduced the duration of pauses when they do occur. Often they are not even noticeable to the player. Now that a slow client can be allowed to lag slightly behind other clients, they could theoretically be at a disadvantage as their actions will take longer to execute. However, this can be capped by the server so I can always tune it to the find the right balance.
Adjusting Turn Length
If too many pauses are observed by the server, it can increase the turn length by including a new turn length within a turn message. All clients will apply this when they begin executing the new turn. This will increase command latency equally for all players.
Conversely, if the server does not observe any pauses over a certain period of time, it can decrease the turn length to give all players lower command latency.
Non Deterministic Events
In traditional lock step networking, only player commands are issued for each turn, and the rest of the simulation is expected to proceed deterministically between clients. However, some game logic is very hard to keep deterministic, especially in Unity where the game engine does not provide any such guarantees.
In such cases, I ensure that the non-deterministic game logic only gets executed once, and issue the result as its own action along with the actions requested by the players.
For example, let’s say a player attacks a bomb which causes it to explode. The player issues an attack action which all clients execute. At the point where the bomb will explode, it needs to check the surrounding area to see which units will be hit. This is done using a Unity API which is not deterministic. Thus, only one client (maybe the client that owns the bomb) will do this simulation and send the result (the list of units who should take damage) as a new action to the server. In this way the simulation continues to be identical across each client
If cheating is a concern, the server can be the one to compute these actions instead of the clients. This would require the server to be running the same simulation as the clients are. This is the direction I’m moving in, although some non-deterministic decisions are currently still made by clients.
The advantage to this approach is that additional data only has to be sent when some particular game logic is expected to be non-deterministic. Anything deterministic (for example a villager continuing to gather until their resources are full) does not use any additional network resources. It’s also much easier to implement than re-writing Unity features to be deterministic, especially with respect to physics.
The downside is that if I am wrong and think something is deterministic when it isn’t, it will still cause the game to go out of sync.
The current game mode plays a lot like a standard RTS game, with the added objective of killing the opponent’s king. It’s fun but I’m experimenting with other modes that can take more advantage of the ability to construct complex structures.
One of the issues with the standard game mode is that there’s no reason to ever have the king move around, so it’s a pretty viable strategy to just encase the king in a giant block of stone.
That’s not very interesting! I’d rather force people to defend an entrance to the king’s chambers. The other issue is that because you have to build so fast to stay competitive, speed ends up trumping layout even though there are strategic advantages to designing a good castle layout.
A variation I’m trying is to divide the game into a series of rounds. You get a ‘build’ phase where you can build anything within the boundary of your territory, but you can’t send enemies into others’ territories. At this point you don’t have a king yet so you have to build with the king in mind for later.
Secondly, there is a short ‘place your king’ phase. Your king spawns at the outside of your territory and you have to move him inside to a safe place. At this point it’s no longer possible to build so there has to be a path into the castle for the king to follow.
Finally there is an ‘attack’ phase where you attempt to kill your opposing king. During this phase you are still not allowed to build, so you have to have created a strong enough defensive structure during the build phase. Because it’s not possible to quickly replace structures, it’s more important to think about a good defensive layout during the build phase.
I haven’t had a play test yet with this mode so I’m looking forward to finding out if it achieves my goals! If not, I’ll keep experimenting with other ideas.
Recently I’ve been play testing more often, and I’ve been playing more games with people who are new to the game. Overall it’s been a really rewarding experience to see people getting having so much fun, laughing and yelling at each other while playing the game. I keep getting asked when the next play test will be!
It’s also been really good for identifying things that are unclear, frustrating or not matching player’s expectations.
Some types of building blocks need to have connections to other blocks in order to make things work. For example, hydrogen pipes are used to pipe hydrogen gas into buildings that can use it. Railway tracks also need to connect with each other to allow trains to travel between them.
I found that hydrogen and rail units weren’t being used very much, even though they have cool abilities. The reason was that players found it frustrating to build connections piece by piece. It takes a lot of time, and meanwhile players still need to focus on attacking and defending. This is especially true for hydrogen pipes because they can move freely through 3D space.
I think this kind of mechanic adds depth to the building aspect of the game, but I wanted to make it easier and faster for players to build what they want. To do this I decided to add an assist feature that finds a path between the start and end points selected by the player.
UX wise, I’m using double height buttons to visually distinguish buttons that build many building blocks at once, while single height buttons build a single building block. The player clicks once to set the start point, and then moves their mouse to the end point while seeing a preview of what will be built.
To implement the feature, I used A* to search for a path between the start and end points. I already have an A* implementation for unit pathfinding, but it’s optimized for very different conditions. In the unit movement case, it makes sense to have relatively slower graph updates when buildings are built in order to make the pathfinding really fast. In this case, the ‘graph’ will update much more frequently than the pathfinding will ever occur, so I decided to construct the graph on the fly during pathfinding. I also wanted to make the implementation generic so that I could plug in different functions for the pipes vs rail case (and other future cases).
The AStar class accepts any type of object as a graph node. It also doesn’t know anything about the relationship between nodes. Instead it requires that 3 delegate functions are passed in. NeighboursDelegate is used during pathfinding to get all the nodes connected to an already explored node. ScoreDelegate is a heuristic function that informs the direction to look, and ActualCostDelegate computes the true cost of a path.
In my implementations for pipes and rails, NeighboursDelegate builds up a graph on the fly by searching the adjacent locations on the map for empty space. It also takes into account the shapes of building blocks that are available, to know what locations are candidates. For example, tracks use curves that are several units long, so it’s not possible to move a single unit to the left or right.
I also use custom cost functions to do things like preferring straight lines over curves, and preferring to have pipes above the ground so that they don’t obstruct units.
Since implementing this system, tracks and hydrogen have been a lot more fun to build, and have been getting a lot more use in competitive play.
It’s been a long time since I posted here! I’ve still been making solid progress on the game, and there have been a lot of changes that I hope I can cover in the future. One of the problems I’ve started running into is that there are too many types of building blocks and they don’t always fit in the current user interface. Some of my testers with lower resolution screens have complained they can’t see all the buttons. Here’s what the current building UI looks like:
Other than getting too wide at the bottom, I don’t like the way the buttons look. The bevel on them doesn’t look very modern and the square corners don’t fit with the rest of the UI. Everywhere else I use flat buttons with rounded corners.
Here’s what the new building UI looks like:
I moved the categories to a bar along the bottom of the screen which frees up space for the buttons on top. There can also be more categories now when one category becomes too big. The new buttons look a lot more consistent with the rest of the UI. I also made some minor changes like aligning the edges of the tool tip to the edges of the buttons.
I drew a quick mock-up before I made the change:
You can see that this concept includes some features that haven’t made it into the UI yet. One thing I was thinking of was having extra-large buttons for ‘templates’ which combine a bunch of building blocks together. Some of these exist today but they don’t look any different than individual blocks in the UI. As I add more of these I might make the change to differentiate them more. The topic of ‘templates’ probably deserves its own post.
There’s also room for a mini-map. I’m still on the fence about whether or not to include a mini-map. The other possibility would be to have units get replaced by icons as you zoom out far enough, so effectively the main view becomes a mini-map.
Above is another quick mock up I did of how the UI would look when you select a unit. I’m planning to use the bottom bar to include stats about the unit, which aren’t accessible currently. You can also see how it might look if zooming out were to replace units with icons.
One of the main design goals of Stone Monarch is to allow free-form 3D construction. People should be able to build castles, walls and villages however they want. It’s very important that the construction system works well. I had these goals in mind for the construction system:
It should enable creative freedom
It should have strategic value
It should be easy to use quickly
Creative Freedom
Building a castle entrance
The game provides many small building blocks that players can use to build their base. I tried to avoid any unnecessary restrictions on building. Building segments are allowed to overlap each other, and there aren’t any rules for which segments can connect with which other segments. Segments can attach to existing solid surfaces in any direction, so it’s possible to have giant overhanging structures even if they wouldn’t be entirely plausible in real life.
An example of a more unusual castle
Strategic Value
The design choices that a player makes should not be purely cosmetic. They should have a strategic impact on the game.
Structures that are larger get stronger, so it will be harder to get through a tall wall than a short one. Units that are higher up get an increase line of sight, and they are more easily able to attack enemies below them. This gives an advantage to posting guards on walls and towers (at the risk of reduced mobility). Solid obstacles block attacks, so it makes sense to do things like build a roof over very sensitive locations.
Various structures give additional benefits, such as line of sight (torches), population benefits, resource storage, and transportation (rail, pipes).
Archers wait on top of towers to defend against any enemies coming up the ramp
Speed and Ease of Use
Since this is a real-time game, it can’t be too cumbersome to build things under time pressure. Over rounds of user testing I’ve gradually simplified the building process.
Originally, I followed the traditional RTS building system where villager units need to stand next to a building and construct it. This ended up being impractical in a 3D world. It was too difficult for villagers to reach anything high up in order to build it. Although it was still possible to make this work by building a bunch of temporary scaffolding, it was too slow and cumbersome to do that during an RTS game. Maybe in a different sort of game it would be an interesting challenge on its own.
I fixed this problem by only requiring villagers to be within a certain radius of the buildings being constructed. This greatly simplifies building things but it still doesn’t break the game by letting people build anywhere at any time.
After further testing, I still found that it was difficult for people to build complex bases. The reason was that I was forcing people to wait for segments to build, which took several seconds. This is a good mechanic in traditional RTS games because it forces people to plan ahead and be ready before an enemy arrives at their doorstep. It didn’t work in Stone Monarch because you need to have segments already built before you can build other things on top of them. It’s very difficult to plan a base when you have to keep waiting for each ‘brick’ to appear.
Instead, I allowed instant building, but restricted building when enemy units are too close. This lets people build easily during peace time, but doesn’t break the game during battles.
One challenge I’ve encountered while working on Stone Monarch has been the implementation of pathfinding. Unity comes with a built-in pathfinding solution, but it really only works on static environments. In an RTS game, the environment is procedurally generated before each game and it is constantly changing as players build new buildings.
One of my guidelines while working on this project has been to re-use existing frameworks whenever they fit my needs instead of writing everything from scratch. Although it’s rewarding to build your own game engine from scratch, my goal is to finish the game and I don’t have enough free time to do unnecessary work.
I decided to use Aron Granberg’s A* Pathfinding Project as the basis for the pathfinding engine for the game. If it had worked out of the box, this would be a pretty boring blog post, but there were a lot of challenges to overcome to adapt the project to fit my needs.
A* Pathfinding Project comes with it’s own navmesh implementation, but like Unity’s implementation it doesn’t work well when the environment is constantly changing.
The fastest graph type to update is the grid graph, but it wouldn’t work for Stone Monarch because I need pathfinding to work in 3D space. The layered grid graph might have worked in a sort of OK way, but it still doesn’t allow for arbitrary elevation changes and it would have really limited the game design.
This left the most generic graph type, the point graph. It uses a Unity GameObject to represent each point in the graph. This allows for enough flexibility to represent pretty much any pathfinding scenario, and it would allow me to easily store pathfinding points along with prefabs for buildings.
Unfortunately, when I first did a test generating a point graph, the game took several minutes to start, and thereafter it ran at an extremely poor frame rate. I needed to use around 16,000 pathfinding nodes to represent just the points for the starting terrain and apparently that was too much for my computer to handle. After a bit of debugging, I figured out that the slowdown wasn’t so much from the pathfinding algorithm itself as from having so many GameObjects in the scene. There is a lot of overhead that comes with a GameObject that isn’t really being used when it represents a pathfinding node.
An example of pathfinding nodes in the game. Note the ability to go up ladders and walk on the top of structures.
Instead, I modified the point graph to accept lists of Vector3s as nodes instead of GameObjects. I still wanted to be able to position the graph nodes as GameObjects in my prefabs, to keep the workflow for adding new buildings simple. To do this, I made buildings read in the positions of their pathfinding nodes when they are instantiated, and and then destroy the corresponding GameObjects. Over time, this keeps the number of GameObjects low. The terrain, as a special case, generates all its pathfinding points from the terrain data and never creates GameObjects.
Each building has a unique id, and it passes that id to the pathfinding graph along with its list of points when it is instantiated. The graph keeps track of this mapping in a dictionary, so that when a building gets destroyed it can easily find the graph nodes that need to be deleted along with that building.
The pathfinding set up for one building. The blue dots are pathfinding points that will get deleted after they are ingested into the system.
This method was really effective in reducing the cost of using a point graph. I was able to eliminate frame rate issues and significantly reduce the time taken for the initial scan and subsequent updates.
As the game keeps getting more complex, I’ve continued to run into issues with update speeds from time to time. Aron Granberg has done a good job of optimizing the hottest paths of the code, but as I keep getting more nodes in the scene I keep finding new areas that need to be optimized. Since I only have to support this one game (and not a framework for anyone to use), it’s easier to find performance shortcuts that fit my specific use case.
Despite my continued modifications, having a working system from the start that I can swap parts out of as I go has been a big advantage in keeping the game playable. I can iterate on it when necessary without getting distracted for too long. It also really helped to have a working example of a pathfinding system to learn from.
When I was a kid I loved playing with Playmobil Castle. My siblings and I would spend hours inventing kingdoms before acting out battles between them. While the battles were fun, we always spent the longest building our castles.
The great thing about Playmobil was it’s modular construction. We could combine pieces any way we wanted to create our own designs for walls, towers, gates and prisons. This creative expression was what made it interesting to keep playing over and over.
Once we were a little older, we discovered Age of Empires 2 when my cousin got it for christmas. I remember spending all afternoon in my grandparents’ basement gathered around their computer, making decisions together to fight a computer player.
What I loved about Age of Empires and other RTS games were the elements of strategy and competition. I still play it with my family today, because the replay value of coming up with ways to counter someone else’s strategy is so high. However, the creative construction element that I used to love from playing Playmobil is somewhat lost. Castles and buildings are all pre-built rectangles and laid out on a 2D plane. There’s no opportunity to build freeform structures of your own devising.
This is what I want to do with my own game, tentatively titled Monarchs & Masons. My goal is to make a medieval RTS game with freeform 3D construction to enable both strategy and creative building design. Here’s a screenshot of the game so far:
In this example, I used simple building blocks to build up a castle on a hill. Ramps create an easy to defend entrance surrounded by guard towers. I’ve sent some archers to the tops of the towers to provide protection. Further back, I built a large keep to add a second level of defense for the king.
The game in it’s current state already works for multiplayer battles and I’ve been regularly playing games with friends and family. It’s already possible to build, fight and manage resources, and I’ve already been impressed with some of the crazy castle designs that other people have come up with.
There’s still a long way to go though. It’s an interesting challenge to balance fine grained control with the time pressure of competition. I want to make something that enables and rewards finding interesting new uses of structures and units.
Ultimately, I want to make a game that lives up to my vision and that I can enjoy playing for years in the future. Of course I hope that other people will be interested too. As I make progress I’ll post updates here.
