This report investigates how the construction and query time of multiple spatial partitioning data structures is impacted by spatial distribution of and number of agents in a crowd simulation. In addition a method is investigated for updating the data structures less frequently at the cost of increasing the radius queried, without affecting the correctness of the queries. The data structures are tested in a simulation using a Boids model and update and query times are measured. It is found that the performance of the grid is better than the quad tree and the kd- tree for low number of agents, but deteriorates more quickly when the number of agents increase. It is also found that this approach can decrease the sum of time spent updating and the time spent querying in the simulation. The effectiveness of this method is highly dependent on the update of the data structure. / Denna rapport undersöker hur konstruktion och grannsökning av flera datastrukturer för spatial partitionering påverkas av spatial fördelning av simuleringens agenter och antal agenter i simuleringen. Dessutom undersöks en metod för att uppdatera datastrukturerna mindre ofta, på bekostnad av att utöka grannsökningens radie, utan att påverka grannsökningens korrekthet. Datastrukturerna testas i en simulering baserad på Boids och uppdaterings- och frågetider för datastrukturerna mäts. Det visar sig att prestandan av grid är bättre än prestandan av quad tree och kd- tree för ett litet antal agenter, men att prestandan för grid försämras snabbare när antalet agenter ökar. Dessutom visar sig denna metod kunna ge en minskning i den totala tiden som går åt till att göra grannsökningar och uppdateringar av datastrukturen. Hur effektiv denna metod är beror i hög grad på hur lång uppdateringstiden är för den använda datastrukturen.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-302340 |
| Date | January 2021 |
| Creators | Kratz, Jakob, Luthman, Viktor |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2021:442 |
Page generated in 0.0024 seconds