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:
This is an old recording, there's a bunch of things wrong with the movement here that we don't like.
Notice how sometimes villagers clip through decoration objects or other villagers, how they bump into each other and how jerky their movement is when trying to walk around each other.
The rest of the post explains how we addressed these problems.
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 :)