Development Blog

Monthly archives for May, 2016

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.

AI, Development

Combining Creativity and Strategy

May 15, 2016 Leave a Comment Written by Evan

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.

playmobilCastle

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:

base34

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.

hero8

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.

Game Design