Town Alight Dev Diaries – The Big Refactoring

Hello everyone!

Welcome back to The Big Refactoring, where I explain the significant changes we’ve made to Town Alight since we published its first version. Feel free to ask any questions about the development process in the comments! Today, I’m going to talk about improving how navigation works in the game.

Chapter 2: Navigating new horizons

When we think about navigation, we often picture the idea of moving through space or sailing toward new horizons. In game development, and computer science in general, navigation is much more complex. Let’s take Town Alight as an example.

Imagine you’re in a labyrinth. In real life, if you want to get out of the labyrinth, you might pick a path at random, and if it doesn’t work, you’d go back and try again. But our poor villagers don’t have that luxury. If one of them takes what seems like the shortest path to a fire, only to find a lake blocking the way and must backtrack, players start being mean to the brilliant developers and their beautiful game. (We don’t want that!)

To avoid this, our villagers need to be smart. They need to understand their surroundings from the start and find the best route to their target. This is where a popular path-finding algorithm called A* comes to the rescue. In simple terms, A* evaluates the best direction to take every few steps, considering obstacles like lakes or buildings, and keeps adjusting until the character reaches the goal. Luckily for us, Godot already implements A* natively, so we didn’t have to code it from scratch. Phew!

I know what you’re thinking: “Is this guy going to tell me he didn’t know about this algorithm when he coded the game jam version?” For your information, there’s a first time for everything, and this time I did implement A* in the jam version of Town Alight, and it worked perfectly! Well… kinda.

Remember how everything in Town Alight used to be a tile? The entire navigation system relied on the TileMap, where each tile had a specific shape for its navigation path. So, what happened when we wanted to create a big structure, such as the mayor’s house? Well, tiles didn’t know they were part of a larger object. We had to manually set the navigation path for each one individually.

After painstakingly assigning the navigation paths for every tile, the complete navigation mesh was constructed like a puzzle. In this image, everything marked in red is the navigation mesh—the areas where characters can move:

And to be fair, it did work. Villagers could navigate around obstacles and find the best path to their destination. You can even see in this image how a villager avoids the lake and gets where they need to go:

However, the main goal of this refactoring is to increase modularity, and this solution wasn’t in line with that goal. Here’s why:

• If we wanted to slightly change the color of a tree’s trunk, for example, we would have to create a whole new tile and set its navigation path.
• If we wanted one particular path area to behave differently, we couldn’t, because all tiles of the same type shared the same navigation path.

When we decided that many of the objects in the game would no longer be tiles, we had an opportunity to improve the navigation system. However, a new challenge arose: we needed to make the navigation system independent from the TileMap, while still considering the navigation data for tiles that remained.

The solution was to remove navigation from the TileMap and extract the navigation paths of every remaining tile to integrate them into a new, independent navigation system. This new system also accepted navigation data from newly created structures. Instead of worrying about individual tiles, we could now assign navigation information to entire objects—like this (already deprecated) tree:

Let’s look at a real issue we solved during development. Imagine a tree that slightly blocks the villagers’ path to a fire. In the new system, we can:

• Move the tree a few pixels up or down to redirect villagers to a new area.
• Change the collider of the tree to adjust how it interacts with the environment, without affecting other trees.

          Original position                    Move tree a few pixels             Change the tree's collider

In the old system, none of these changes were possible:

• Moving the tree meant shifting it an entire tile.
• Changing the tree’s collider affected every tree in the game. (Can you imagine the chaos of every structure sharing the exact same behavior?!)

With this new system, future levels will have fewer limitations and allow for more interesting details!

That’s it for today. I hope you enjoyed this peek into how navigation works in Town Alight. If you have any questions, feel free to leave a comment. See you in the next one!

-Anthuulos