Urho3D: Boids
The aim for this project was to implement a boids algorithm and critically analyse and optimize the algorithm by improve memory and time complexity, and to develop a production quality game which included a basic combat mechanic, and finally, to add networking. This was achieved by using the open-source C++ engine called Urho3d. To begin with, the algorithm could only handle about 100-250 boids, because of how inefficient it is. The end result was very positive; the game compute forces for about 2,5000 - 5,000 boids with an average of 30FPS, by using industry standard optimization techniques. When analysing the algorithm, stopwatches were implemented to calculate the overall time it takes for the algorithm to compute the boids' forces. I used extreme cases, ranging from 100 to 5,000 boids so the results would represent how well the optimizations worked by using tables and graphs in the final report.
When the program is computing forces for boids, the main issue is that the algorithm complexity would be quadratic O(n^2); the original code would loop through all the boids twice in a single update function. When optimizing the boids, three improvements were made; The first optimization was to have a limit on how many boids influenced the others forces; thus decreasing the number of iterations. The second was to implement a "Spatial Grid", which essentialy decreases the amount of boids even further, because the algorithm will check neighbouring cells for boids and use them to calculate forces. The final optimization was implementing multi-threading; this was a major boost to performance, including memory and time complexity, and the boids were split depending on the amount of threads, as boids would sometimes fail to update before the main thread does the game loop update function and cause jittering effects on the boids. Other optimization techniques were also considered; such as splitting the boids into smaller groups in a thread, copying forces from nearby boids and only computing forces for the boids in the players view. However, the level is so small that two players could probably see all boids, therefore was not worth implementing.
During this assignment, I wanted to make it feel more like a production worthy game, so an extra level was added, a main menu, options with a working configuration file and a level select screen. For gameplay, I made a basic turret defense where players can take control of turrets and target the boids in the sky. These were done using Urho3D's componenet system, was transferring data over the network is really easy to do. Sadly no animations were found for the dinosaur.
Developed Skills
- Further knowledge of C++.
- Developed experience using an existing codebase and use it develop a game.
- Debugging and analysing optimisations such as spatial grids and threading.
- Analysing optimisations with qualitative and quantitative terms in mind.