Tank simulatie optimalisatie

In dit project kregen we een bestaande tanksimulatie in C++ aangeleverd die te traag werd zodra er veel objecten tegelijk actief waren. De opdracht was om de simulatie in twee stappen te optimaliseren: eerst door algoritmische verbeteringen toe te passen en daarna door concurrency te gebruiken op de delen waar parallelisatie zinvol was.

De kern van het project was meten waar de tijd verloren ging en daarna gericht optimaliseren. Daarom begon het traject met diagnostische sessies en individuele timings van functies. Op basis daarvan kon ik bepalen welke onderdelen de grootste bottlenecks vormden en in welke volgorde de optimalisaties het meeste effect zouden hebben.

De video laat het eindresultaat van de simulatie zien nadat zowel de algoritmische als de concurrente optimalisaties zijn toegepast. De gemeten functionaliteitstijd is sterk verlaagd en de praktische uitvoertijd van de simulatie is duidelijk teruggebracht.

Uit de eerste diagnostische sessie bleek dat 96,41% van de tijd in de game-logica zat en maar een klein deel in overhead. Binnen de update-fase waren vooral vier onderdelen belangrijk: collision detection, het updaten van raketten, het sorteren van levens en het bepalen van routes.

Het grootste probleem zat in collision detection. Daar werd in feite een benadering met een complexiteit richting O(N²) gebruikt, doordat tanks telkens met alle andere tanks werden vergeleken, ook wanneer ze zich aan de andere kant van de map bevonden. Een vergelijkbaar probleem zat in de raketlogica, waar iedere raket met alle tanks en met punten van het forcefield werd vergeleken.

Daarnaast gebruikten andere onderdelen ook niet de meest geschikte aanpak: het sorteren van tanklevens gebeurde met insertion sort en routebepaling gebruikte breadth-first search. Beide zijn functioneel correct, maar in deze simulatie niet optimaal wanneer het aantal objecten toeneemt.

De eerste verbeterslag zat volledig in algoritmiek. Om collision detection en buurtberekeningen efficienter te maken, heb ik een grid toegevoegd dat de kaart opdeelt in blokken van 20 bij 20. Per gridcel wordt bijgehouden welke tanks daarin zitten. Dat maakt het mogelijk om alleen nog te vergelijken met objecten in dezelfde of aangrenzende cellen in plaats van met alle objecten op de kaart.

Voor routebepaling is breadth-first search vervangen door A*. Die keuze was logisch omdat A* met heuristics veel gerichter naar de eindbestemming zoekt en daardoor minder onnodige paden doorloopt. Het sorteren van levens is vervolgens vervangen door countsort, omdat de waarden in de simulatie in een beperkt bereik en in vaste stappen voorkwamen. Daardoor kon een relatief dure algemene sorteerstrategie worden vervangen door een lineaire aanpak.

Ook het vinden van de dichtstbijzijnde vijandige tank is aangepast. In plaats van breed zoeken over alle tanks, werd iteratief gezocht in steeds grotere ringen rond de huidige gridcel. Daarmee werd de zoekruimte veel kleiner en sloot het algoritme beter aan op de ruimtelijke structuur van het speelveld.

Deze stap leverde de grootste winst op. Volgens de tussenanalyse daalde de totale tijd van ongeveer 54 seconden naar ongeveer 2 seconden, een reductie van 96,22%. Vooral collision detection en raketupdates profiteerden sterk van de nieuwe grid-structuur.

Nadat de zwaarste algoritmische bottlenecks waren opgelost, is de simulatie verder versneld met concurrency. Daarvoor is een threadpool gebouwd, zodat threads niet steeds opnieuw aangemaakt hoefden te worden. Taken konden daardoor als lambda's in een queue worden geplaatst en vervolgens over meerdere cores verdeeld worden uitgevoerd.

Een belangrijk technisch probleem zat in het thread-safe maken van het A*-algoritme. De oorspronkelijke implementatie gebruikte gedeelde data in terreinobjecten, waardoor meerdere threads elkaar zouden blokkeren of dezelfde data tegelijk zouden aanpassen. Om dat op te lossen is een aparte AstarData-structuur gemaakt waarvan per thread een eigen kopie beschikbaar was. Beschikbaarheid werd bijgehouden met booleans en beschermd met een mutex.

Voor andere delen van de simulatie is een split-task functie gemaakt waarmee werk over lijsten kon worden verdeeld. Daarbij is steeds beoordeeld of een taak voldoende runtime had om de overhead van threading terug te verdienen. Dat bleek bijvoorbeeld niet nuttig voor rook en explosies, maar wel voor collision detection en raketupdates.

Na deze concurrency-stap kwam daar nog eens ongeveer 0,8 seconde winst bovenop. In de eindanalyse leidde dat tot een extra reductie van 38,69% ten opzichte van de al geoptimaliseerde versie en een totale reductie van 97,68% ten opzichte van de oorspronkelijke situatie.

Het sterkste resultaat van dit project is dat de simulatie niet met een losse tweak is verbeterd, maar systematisch is teruggebracht van een trage basisimplementatie naar een versie waarin zowel algoritmiek als concurrency aantoonbaar effect hebben. De grootste winst zat in het eerst terugdringen van onnodig werk, waarna parallelisatie pas echt waarde begon toe te voegen.

Dat maakt dit project inhoudelijk interessant: de oplossing was niet simpelweg "meer threads toevoegen", maar eerst de juiste datastructuren en algoritmen kiezen. Daarna kon concurrency gericht worden toegepast op de delen die lang genoeg draaiden om de extra overhead te rechtvaardigen.

De combinatie van metingen, algoritmische verbeteringen en concurrency maakte dit voor mij een sterk technisch project. Juist omdat het resultaat meetbaar was, kon ik steeds onderbouwen welke keuzes daadwerkelijk effect hadden.

• Dat je eerst moet meten waar de echte bottlenecks zitten voordat je begint met optimaliseren.
• Dat algoritmische verbeteringen vaak veel meer effect hebben dan meteen naar multithreading grijpen.
• Hoe datastructuren zoals een grid directe invloed hebben op de praktische performance van simulaties.
• Hoe je concurrency veilig toepast met een threadpool, mutexes en thread-safe data in plaats van gedeelde mutable state.
• Dat concurrency alleen nuttig is als de runtime van een taak groot genoeg is om de overhead terug te verdienen.