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.
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.
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.
