Development Blog

Posts in category AI

AI Base Building Using Constraint Propagation

February 20, 2020 Leave a Comment Written by Evan

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.

Development

Play Testing Feedback: Pipes & Rail

June 17, 2017 Leave a Comment Written by Evan

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.

Development, Game Design, UI

3D Pathfinding in Unity for Procedural Environments

May 30, 2016 Leave a Comment Written by Evan

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.

AI Paths

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.

AI Pathfinding Points

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.

Development