I picked up SFML and C++ and started developing Archapolis from ground zero. I found a simple city builder tutorial using the same tools which helped me understand how to put all the graphics infrastructure together. SFML tutorials were also helpful, but I also had to unlearn everything because tutorials don't cover the efficient methods needed to create a real video game.

The first major upgrade was utilizing SFML's Vertex Arrays. Essentially, you store all the game tiles in an array of vertices (containing texture coordinates, output coordinates, and color). That way you only need to call the window's draw() function once per vertex array, as opposed to once per tile. The draw call is resource intensive and the game will begin to slow down around hundreds of draws per frame.

That's really nice, but it's not enough. I'm making a city builder game and I expect there to be lots of updates all over the map at any given time. The next step was to implement a staging container to store all tile updates before pushing them to the main one. That way I only need to loop through the tiles in the staging container to update their Vertex Array information.

Starting in December I began working on path finding. Traffic is the most important part of my game. The player will see and interact with the transportation the most. Throughout the course of development I have sunken several months on the path finding code, to great success. I want to have real time traffic, much like Cities: Skylines. I set this is the minimum bar to pass, because it will separate Archapolis from all other city builder games.

I read about Dijkstra's algorithm and began implementing it from scratch based on what I've read. It is really important for me to understand what my code is doing. That's why I didn't copy an existing solution. Through deep understanding, I can modify the functionality as I see fit. And I did (more later).

The downside of using Dijkstra's algorithm or its variants (like A*), is that it only returns one shortest part between two nodes, and always the same path. For a city builder, I think this is extremely limiting. It is unrealistic if all the units used the same road to get from point A to point B.

Over the course of two weeks, I developed a new algorithm that solves this problem. The first iteration was not space-efficient, but I knew there was a way around this. It just eluded me for 4 months. Now the units can choose a path from all the available shortest paths between two points. What's more, paths can have preference weights. For example, I can assign a beauty, culture, or tourism weight. Units that have one of these preferences will choose the shortest path (from all available shortest paths) that matches that preference.

Published Date: 06/13/2022
Total Development Time: 2 months