1.9 KiB
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
BenchMarkclass, die gebruik maakt vanSFML/System/Time.hpp).
De instellingen variëren nogal in effectiviteit. De instellingen waarmee de eerder genoemde resultaten zijn gemeten zijn:
16hash grid divisions (dus een vlakkenverdeling van 16x16).255hash 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.