This project was created in a team of 4 computer science students as the foundation of their bachelor’s thesis. It took us about 5 months of quite consistent work under the supervision of developers from Noobz from Poland studio.
The game was created from a blank project to a ready-to-publish product. We did everything by ourselves with the guiding light of Monday checkup meetings and the team of graphic designers who helped us with creating assets.
The main idea of the arising battle simulator genre is the indirect control of your army facing the opponent. You act as a general who decides on the initial selection and placement of the units and everything else is at the mercy of an AI. Our project was an attempt to build such a game for a hardware limited platform - Nintendo Switch.
We split the responsibility between people according to their interests. As an algorithms enthusiast I was generally working on AI and some random stuff like designing maps, UI or progression system later on.
The essence of the unit’s AI is rather simple, choose the closest enemy (according to some metric), move to it along the shortest path and start shooting if it is close enough. Having the pathfinding system was vital for the game. There are some ready-to-use solutions but mostly paid and we wanted to have it tailored to our needs. I also wanted to finally make a good use of my algorithmic experience!
The task was not easy because our game had to have destructible obstacles implemented. That completely increases the level of complexity of the problem - now environment changes dynamically throughout the game. If it hadn’t been for that, we could somehow preprocess all the paths before the battle and voilà. Also keep in mind that we are running it on a console, not a regular PC.
Finally we ended up with a global system serving shortest paths between arbitrary positions on the map with lazy updates of destroyed obstacles. Wow. Thanks to grid-based placement of the unit, it works on a 320-vertex lattice graph presented below. Each vertex has its weight assigned based on how hard it is to destroy an obstacle on the corresponding tile. The core of the system is the 320x320 array which stores information about the shortest path between each pair of vertices. Not only the length but also the path itself. It was a tricky thing to reduce memory complexity from O(n^3) to O(n^2) for storing those paths, n is the number of vertices. In regards to building destruction, we store such events in a separate queue. If a query from the unit comes in for a specific path, then we check if this path can be shortened by going through the lastly destroyed obstacles. The eventual improvement is cached. That’s known as a lazy approach and is inspired by lazy propagation in data structures
That was not only my first experience with game development but also with working with a team on a large project. Efficient communication is as important as the clean code and architecture. I could profoundly experience the latter trying to change some minor details in the late stages of development ;)
My additional takeaway was a better understanding of the Unity engine, C# and git. Sadly, the game has not been published yet (and probably never will) but I remember these few months really well.
Saying I make soldiers not walk into walls as my bachelor’s thesis was funny too :)