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