Cutlass & Compass

Cutlass & Compass

Well, it’s about time I started showing off some of this side project. I’ve been working on it casually for about a year now, there’ve been a few halts in the development due to life and work though… but here we go:

Overview:
Cutlass & Compass (I sometimes refer to it as Coin & Compass) is a pirate sandbox game. The idea is to build up and manage a pirate crew, eventually building a pirate town (or several). The project itself was started by a couple of friends/coworkers (Ben Rodgers and Allen White). During it’s initial development I strictly provided advice and later I inherited the project and began rebuilding large chunks of the project… I started the development with world generation, as it’s pretty much the fundamental thing that nearly every other part has to interact with in some way.

World Generation:
So, the world is procedurally generated and toroidal… So, if the player travels far enough in a single direction they will return to where they started. The world wrapping is actually handled using extra cameras. Basically, the extra cameras render the other end of the map and we simply rendering them on top of each-other to create a seamless appearance. The game is tile-based, so the internal workings of the map are just arrays (split into chunks). If we decide to make things even bigger, I’d have to consider a different method of containing the map.

The world generation is totally modular in nature. I can add/remove/swap parts as needed and it makes for easy debugging (I can easily just load the parts I wanna check, or check them sequentially). I don’t use Perlin or Simplex noise in this, but rather I built a system that is roughly based on Funstorm’s Procedural Island method. We get pretty good looking results using this technique. As I said, the system is modular, so the process of generating the actual world is as follows:

  1. We start by generating island data. We do this by establishing parameters for different island sizes and how many of each island size we want. We also assign each of these islands a Voronoi index. We don’t plot the islands completely at random, instead we plot the islands using Voronoi (this is where the index comes in). The Voronoi index determines which of the graphs the islands are plotted on. We do this so that large islands don’t overlap, but we allow for small and medium islands to enhance the larger islands. So, after plotting points we apply some Lloyd Smoothing and then assign the new point data to each island. Prior to the addition of Voronoi, we just plotted islands at random, and it didn’t create a very “islandy” world.
  2. The initial map generation is just the Ocean and Sea Floor… We’re basically setting the map to a default setting.
  3. At this point we begin generating the islands on the map itself. We use a splat-map to handle the texturing and a tile system for the 3D aspects. This is where the spiral method from Funstorm comes into play.
  4. So, we’ve got a basic island shape in place… Now we need to set the beaches and fill in the tiny holes that sometimes appear with the spiral generation. So, if a tile has 3 neighboring island pieces, it becomes an island (it would have been ocean)… and, of course, we paint the sand around the edge.
  5. Since we generate the base of the island without edge-tiles we need to fit these in. Simple rules dictate what edge piece is used, we just set the tile as an edge piece and the underlying system will select the corresponding model based on neighboring tiles. Basically, we’ve created the edge of the island and the initial shallow waters around the island.
  6. Now that we’ve formed a basic island, we need to lay down some shallows… We quite simply repeat the previous island generation method (steps 3 through 5) but only replace deep floor with shallow floor (and apply some shallow water colors to the splat-map).
  7. This last part isn’t a visual element… What we do at the end is perform a flood-fill operation to construct a data map for navigation. We mark tiles based on traversal methods and we apply IDs to tiles to track connected spaces. The IDs aren’t island specific, but rather based on the current flood-fill operation. So, when we attempt pathfinding we can compare the navigation IDs and see if it’s possible to get from point A to point B (if they have a different ID, then it’s not possible).

The current map generation is far from complete, as we still need to place NPCs and their cities/towns/etc.
Note: The Voronoi code is not my creation, but rather an open-source solution: PouletFrit/csDelaunay

Pathfinding:
Alright, as I mentioned, the system stores IDs for tiles to create “traversal islands” so that we don’t have to perform pathfinding for unreachable destinations. I’ll even be able to portray this to the user like old-school RTS games did by changing the cursor. The actual pathfinding in C&C is a standard A* system, with the only thing of note being that it takes advantage of C#’s IEnumerator functionality. This means, the path can be generated over multiple frames… In the future I might convert this to a multi-threaded system.

AI:
So, I opted to go with behavior trees for the AI in C&C. I looked into a variety of options and decided that this was the best… Here’s a good list of reasons to go with behavior trees over state-machines. Admittedly, I’m pretty new to behavior trees and so I’m still learning and building the system for C&C. This system takes advantage of IEnumerator as well, allowing me to step through the behavior over multiple frames. Eventually, I plan to build a node-based editor for the construction of new behaviors… but initial development will simply involve manual construction via code. Each entity won’t have it’s own behavior running. The behaviors are self-contained and designed to take the entity and process it.  The idea is that we’ll have a “task master” managing the various tasks to complete a specific job. This “task master” will delegate tasks to entities that have been assigned to the job (like constructing a house) and this will be done by pushing the entity through the corresponding behavior. This approach means that some entities might be running resources to a build site while others are performing the actual construction.

My primary resources for behavior tree development are Game AI Pro and AI Game Dev.

Evolution of the map:
First up we have some early terrain generation. We didn’t use Voronoi at this point and the early method had some problems with shearing (notice the flat sides at the top of each island).TERRAINGEN

We fixed the previous problem by changing from a box-shaped spiral to a circular spiral. You can almost see the color variation on the islands… This was done to help identify how each of the island types (small, medium, large) we merging together.TERRAINGEN2

A close up of the island looks nice, but we did have some issues with seems appearing in the oceans (tweaks to the wave motion shader helped resolve this issue). TERRAINGEN3

Hey, we’ve finally got Voronoi in place and you can see the small/medium islands merging with the larger islands to create some believable landmasses. We’ve also changed the way our splatmap works, allowing for a much greater variety of tile colors (not demonstrated here). TerrainGen - Improved