28 lines
1.9 KiB
Markdown
28 lines
1.9 KiB
Markdown
# Optimalizaties
|
|
|
|
## Spatial Hashing
|
|
|
|
In 2d, is de meest efficiente spatial-hashing strategie vlakkenverdeling. Het is simpel voor hashing en map searches om een ruimte op te delen in gelijkmatige vlakken.
|
|
|
|
Voor hashing moet een datastructuur worden teruggebracht naar een nummer. Mijn implementatie brengt de locatie van een object terug tot een 8-bit unsigned int, die over 2 nibbles is verdeeld. de meest significante nibble word gebruikt door de x coordinaat, en de minst significante nibble de y coordinaat.
|
|
|
|
Het systeem waar deze coordinaten naar verwijzen is de het vlak in de vlakkenverdeling waarin een object zich bevind.
|
|
|
|
> (Met 8 bits hebben we 255 mogelijke opties, dit betekend dat de grootste vlakkenverdeling mogelijk 16x16 is.
|
|
> Een andere grootte van hash zou mogelijk zijn, maar groter bleek niet nodig om de bedoelde verbetering binnen te halen).
|
|
|
|
## Performance
|
|
|
|
De performance-verbetering door deze hashing-strategie is stevig. Gemiddelde frametime valt van `0.08...` naar `0.005...` op mijn AMD Ryzen 9 HX 370 met `2500` particles (de standaard hoeveelheid waarmee de voorbeeldimplementatie is aangeleverd).
|
|
|
|
> (Benchmarks verzameld met de `BenchMark` class, die gebruik maakt van `SFML/System/Time.hpp`).
|
|
|
|
De instellingen variëren nogal in effectiviteit. De instellingen waarmee de eerder genoemde resultaten zijn gemeten zijn:
|
|
|
|
* `16` hash grid divisions (dus een vlakkenverdeling van 16x16).
|
|
* `255` hash buckets.
|
|
|
|
Hoe meer grid divisions hoe beter blijkt volgens mijn tests. 16 is de max voor mijn hashing-strategie, dus 255 is de max voor hashbuckets. De impact op ram blijkt ook minimaal te zijn voor verschillende hoeveelheden, dus alles op maximum zetten is optimaal.
|
|
|
|
De belangrijkste limitatie van de hashingstrategie is dat het complex is om de wereld-grootte aan te passen in runtime. Dus de `worldBounds` worden in `initialize` vastgezet en daarna niet meer aangepast.
|