When we started working on Croakwood, programming the villagers seemed to be relatively straightforward - they just have to walk around in whatever environment the player created for them and interact with certain objects. In that sense they are very similar to the guests in Parkitect and so we thought we could easily apply most of what we had learnt there to Croakwood.

This was sort of true, but when we got to the details it turned out to not be quite that easy!

It's a fairly big topic so I've split it into two posts; this one is about movement and the next one will be about interactions with objects.

The first problem we had to solve was the pathfinding, so figuring out which route the villagers should take to get to their destination (ideally taking more or less the shortest possible path).
Initially we thought that, much like the guests in Parkitect, the villagers would mostly stay on the paths that the player builds, so we'd only have to navigate along those paths.
We started with the A* algorithm because it's easy to implement and makes sense to use for a grid-based game.
As a small improvement over Parkitect we allowed the villagers to walk diagonally as well, which helped a lot with making their movement look a bit more natural.

We built some tools to place markers on objects that define where the villagers can't walk through, e.g. the orange box on this shelf is non-walkable:

This worked alright. As towns grew we were looking for some performance improvements and eventually implemented Jump Point Search and that's what has been used in the game until earlier this year.

Here's how it all looked in motion:

Eventually though it became clear that switching to a different pathfinding system would benefit the game a lot because there were situations that we couldn't handle well otherwise. As the game continued developing, our initial assumption that the villagers would stay on the paths most of the time turned out to be wrong. There are a few professions like the forester and woodcutter who need to go off-path to plant and harvest trees, and sometimes villagers need to travel across the terrain for long distances.
This is pretty bad for simple A*, since it might have to search through large parts of the world to find a path, which can take a long time.

The other problem is that our pathfinding obstacles were oftentimes simply not detailed enough.
For example in the building from the earlier video there's some barrels and crates on the floor:

We think this kind of clutter is important for the look of the game, so removing it is not an option. We could simply let the villagers walk through the clutter as if its not there at all (like in the video at the start of the post), but that doesn't look very nice and we also think it breaks the players immersion and simply doesn't feel very nice (what's the point of nicely decorating a house if the villagers ignore the existence of the decoration?).

Ideally, we want the villagers to be able to navigate around the clutter, but our obstacle system only allowed to mark fairly large grid cells as non-walkable. This is problematic for small objects:

The collision box is blocking a lot of empty looking space around the object, and if the villagers can't walk in areas that look empty that's very confusing for players.
We could make the grid cells smaller to improve this, but that would increase pathfinding costs further and would make manually marking blocked cells require more time as well. It wouldn't scale well with the system we had.

So, we had to look for a different approach that could calculate more detailed paths, require less manual work, and have better performance, especially for long distances.

A very common solution that fits these requirements quite well are navmeshes.
They are a pretty nice general solution that you can pretty much put into any 3D game and get decent results.
So we gave them a try in a test project - here's a debug view showing the surfaces it found that the villagers can walk on as a blue overlay:

It looked promising! However, after testing this for a few days we came to the conclusion that this was not the best solution for our game. We might have been able to make it work, but it would always have been a suboptimal compromise.

One problem is that calculating and updating the navmesh can be quite slow, which is bad in a game where players frequently place and remove obstacles.
The other problem is that it's kind of hard to control the shape of the mesh - you never really know what you'll get,
You can work around that in a game where all the levels are pre-designed by manually fixing the problematic spots, but in a game that's entirely user-generated content that doesn't work.

So we continued looking for something that would give us similarly good results as navmeshes without their downsides.
Eventually we found Hieararchical A* (here's also some good articles about the implementation in Red Alert 3 and Factorio).

It is a grid-based system where the core idea is that instead of having to search through all of the tiny cells you combine them into way fewer clusters of bigger cells, then search through those first to figure out which of the tiny cells have a chance to be a part of the path at all. Then to get the detailed path you search through the tiny cells belonging to the big clusters along the path you found. If your world is really big it might make sense to have multiple levels of this, e.g. combining the clusters into even bigger clusters that you search through first (the Factorio blog post does a much better job explaining this and has some nice visualizations, check it out!).

This turned out to work really well and perfectly matched all of our requirements!

Instead of using giant voxels to mark areas as non-walkable, we switched to using polygons that can match the shape of our objects much more closely. To reduce the amount of manual work required we created tools that automatically generate these polygons; we only had to manually adjust them for a handful of objects.

When a player places an object, we rasterize the obstacle polygons to figure out which grid cells it blocks (so we still navigate through a grid, but the cells are much smaller now). Here's a debug view highlighting locations where the villagers can't walk in red:

(A nice side-effect of using polygons is that it's easy to arbitrarily rotate and scale them, which means in the future we should be able to allow scaling deco objects and rotating them more freely than currently possible)

Unlike our initial system the hierarchical pathfinding is able to quickly find long paths across the terrain. Here's a debug view with a labyrinth test map:

One last puzzle piece to make the villagers move nicely is the steering. We want them to walk smoothly around each other. They should recognize that they are going to bump into someone quite some time before it happens, and then adjust their trajectory to prevent the collision.
There's an algorithm called RVO2 that handles this very well, so that's what we're using. One benefit of our obstacle polygons is that we can also feed them into RVO2, so our villagers are able to also smoothly steer around any static objects.

Finally, here's the initial scene from this blog post with all of the improvements in place:

No more clipping through decorations or other frogs when it can be avoided, no more awkwardly bumping into each other, and much more natural looking movement.
We're pretty happy with this :)

This post is about a few different aspects regarding how the game is being rendered. It's mostly technical but I figured it might still be interesting to see behind the scenes a bit.

We're using Unity as the engine for this game. A game engine is a piece of software that provides various features for you, such as systems for animations, the UI, or how things get drawn (rendered).
This brings a bunch of benefits for game developers - creating all of this yourself is a big non-trivial task, so using an existing engine can save a lot of time. Plus if it's an engine that's already been used by many other games that probably means it comes with many helpful features have been proven to work well.

On the other hand, using something that has been created by others to work across a wide variety of games can also mean that despite being adaptable to your needs it's probably not going to be a 100% perfect match. If you need a feature to work slightly differently you might be out of luck, especially if it's an engine like Unity where you can't change the source code yourself. Also, since the features were designed to work for many different purposes and to have as few limitations as possible, they are probably doing things that you never need, or are doing things in a way that aren't necessarily the most optimal performance-wise for your specific game.

This is why we're not using many of Unitys default features and are developing our own solutions instead. One big area where we're doing a lot of custom work is rendering.

Frustum culling

You don't want to tell the graphics card to render things that aren't visible on screen, so you need to check if your object would be visible or not.
Unity does this on the CPU, which can have some benefits. For the type of games that we're making that's not great though, because:

• we have lots of objects (e.g. a single house is not "one object" but created from hundreds of individual pieces).
  Checking them individually one after another is slow.
• our games are more CPU-intense than most. Simulating all the little people running around needs to happen on the CPU, so ideally we want to avoid keeping it busy with other tasks as much as we can.

So we're doing this on the GPU instead. This is great because GPUs can easily do these visibility checks for many objects in parallel, and since we're not going for AAA graphics we can afford moving some tasks to the GPU.

LOD

Usually it's a good idea to draw things that are appearing tiny on screen at a lower level of detail.

Unity unfortunately doesn't have a tool to automatically generate lower level of detail versions of your objects (it looks like they're adding one soon though).
Building these manually is a mind-numbing task, and while there are some commercial tools for creating them automatically the ones we found are either super expensive or not very good, so we built this ourselves.

Postprocessing

Postprocessing layers effects on top of the rendered image, which can change the look of the game quite significantly.
Here's a look at some of our most important postprocessing effects.

Forest shadows

We want to give the feeling that the town is located in a clearing somewhere deep within an ancient, dense forest.
To emphasize this we gradually darken anything outside the area you can build in. It's essentially the same as a distance fog effect, just using the distance to the playable area instead of the distance to the camera.

Apart from looking nice this effect has the additional benefits of making it a bit more clear where you can't build, and it nicely hides the seam that would otherwise be visible where our terrain ends.

Volumetric light rays

These light rays add a lot to the atmosphere of the scene.
They are ray marched. We tried a few ways to fake them with geometry which would be cheaper performance-wise but it didn't give us results we were satisfied with.

This effect only appears at the edge of the playing area. It would be a bit distracting if it appeared everywhere.

Voxel AO/GI

This one seemed a bit crazy to do, but it's working really well.
Nice lighting is one of the most important things for making a game look good. In games with predesigned levels it's achieved by doing some heavy pre-calculations that can take many hours to complete.
In our games the players place all of the objects, so we can't pre-calculate anything. To still get nice lighting in Parkitect we used screen space ambient occlusion (SSAO), which is an effect that tries to darken areas that less directly exposed to light. There can be some artifacts such as some flickering when objects disappear or dark halos around objects where it doesn't make much sense but overall it works reasonably well.

I've been keeping an eye on better methods for the past few years and one called Voxel Cone Tracing was looking quite promising, so we tried building something based on that for Croakwood.
This article gives a pretty good overview for the technical details, but in short, we first create a voxel representation of our scene. This means rendering any contributing object a second time (at a lower LOD level) in a special way, which gives us this slightly Minecraft-looking version of the world:

This can then be used to fairly efficiently calculate ambient occlusion and color bounces:

Here's a comparison how this looks in-game with the effect turned on/disabled:

We think the AO we get from this looks nicer and more "correct" than SSAO, without any of its artifacts. Additionally we get a light color bounce along with the AO more or less for free, as a sort of very basic GI approximation.
Some open areas for improvements that we still want to investigate is doing more light bounces, and using the voxel representation for real-time reflections on shiny materials.

Another benefit that's quite specific to our game is that it allows us to still get AO from objects that aren't visible, which is quite nice when looking into a building.
Note how in this example the roof is hidden, but you still get a color gradient on the wall in the corner where the roof would be:

A big part of Croakwood is providing cozy little houses that your frog villagers can live and work in, so let's take a look at how the houses work!

All of the buildings are created from individual pieces, so every wall, furniture item and decorative object is an individual object that you can place.
This is a system that's similar to the one we used in our previous game, Parkitect. We really like that it allows a lot of creative freedom while still ensuring that houses a pretty quick and easy to design due some restrictions on what you can and can't do.
Paths, walls and furniture objects are locked to a grid so they always fit together nicely, and to make sure that things the frogs need to interact with are accessible. Purely decorative objects like lamps or potted plants can be placed freely.

One somewhat annoying thing with the building pieces in Parkitect were doors and windows. In Parkitect the doors and windows were part of the wall piece, so for each wall style we had to add special wall pieces with holes cut out for doors and windows, or alternatively there were doors and windows that you could stick onto the wall, but they would just sit on top of it without creating a hole.
We couldn't figure out a better solution at the time, but now for Croakwood we came up with a way of putting holes into walls using shaders. This gives you more freedom for placing doors and windows and we have to create fewer building pieces, which is a nice win-win.

It took a few tries to figure out how to do this but wasn't too difficult in the end.
Our first approach was to create our textures in grayscale and then multiply in the custom colors, which gave pretty flat results because it doesn't allow for any variations in color value.

We divide our textures into different sections that should be recolorable and pick one of the most prominent colors in that section as its "base color". Then we generate a new texture where each pixel contains the delta in Oklch color space from its original color to the base color.

To apply the customized colors we submit the chosen custom color for each section to the shader, add the L/c/h values from the delta texture to it and convert back to RGB.
This gives pretty nice results even if pixels in a section have color values that are very different from the base color.
Also our artists can simply create their textures in the way they are used to without having to do anything special to make a texture recolorable.

Of course houses can also be saved and shared, so you won't have to design a complete new house every time. We're storing them in PNGs again since that worked quite nice :)

Objects have resource costs, so once they are placed construction materials arrive and the builder frog constructs the objects to make them useable.

Once the house is complete you can always peak inside and see what its inhabitants are up to :)

Figuring out which objects to hide when peeking into a house is a bit tricky. We don't want to obscure the view of anything important, but also want to show as much of the inside as possible and not unnecessarily hide things that could stay visible.
We tried a few different approaches for this but what worked the best in the end was to simply check if the bounds of an object are in front of the volume defined by the paths of the currently viewed floor.
This alone would result in a lot of "visual noise" when rotating the camera caused by individual objects appearing and disappearing which doesn't feel very nice, so we're grouping nearby objects together and then decide the visibility for the whole group, so that we're always changing the visibility of a larger chunk of the building at once where possible.

Hi everyone!
To celebrate Parkitects 6th anniversary, we’ve got a new free update for the game along with some exciting news to share!

Custom Campaign Editor

This update adds a new custom campaign editor to the game in addition to the scenario editor.
Now you’ll be able to create and play your own custom campaigns, just like the ones that come with the base game and the Taste of Adventure DLC.
The campaigns can also be shared online through Steam Workshop and mod.io, so you're able to play the custom campaigns created by others.

The amazing AstroTron has already turned some of his scenarios into the brand new custom campaign that you see in the video above.
It's available on Steam Workshop here.
Big thanks to AstroTron for testing the campaign editor and allowing us to use the campaign in our showcase video!

New DLC Incoming

We’re also very excited to finally announce that a new content DLC is in the works and should be released in a few months. We know many of you have been asking for this, and we’re excited to have the opportunity to make it happen!
Work on it started fairly recently so there's nothing to show yet, but so far we know that it'll be a smaller DLC than the existing ones that'll focus on new deco themes.
We’ll be sharing more details later as development progresses.

AMA today

To top things off, we thought it would be fun to run another AMA (ask me anything) over on Reddit to mark this occasion. If you have any questions for us about Parkitect, Croakwood or game development in general, head over to Reddit and we’ll answer as best we can. The AMA starts at 6pm CET / 9am PST.

A big thanks to our amazing community and our sincere thanks to all our players, for all these wonderful years! Happy anniversary everyone!