Denna studie jämför effektiviteten hos grafsökningsalgoritmerna Dijkstra, dubbelriktad Dijkstra, A*, dubbelriktad A*, och Jump Point Search (JPS) i en tvådimensionell rutnätsbaserad miljö. Genom att analysera deras prestanda baserat på exekveringstid och antalet expanderade noder syftar studien till att identifiera vilken effektivitetskillnad dessa förbättringar medför. Resultatet visar på signifikanta skillnader i prestanda mellan algoritmerna där JPS är 7235% snabbare än Dijkstra på en karta av storlek 1000x1000. Detta understryker att förbättringarna som kan appliceras på Dijkstra är högst relevanta inom spel där millisekunder spelar stor roll. Dubbelriktade versioner av Dijkstra och A* visar sig också vara mer effektiva än deras enkelriktade motsvarigheter med en förbättring som motsvarar ca hälften av exekveringstiden, vilket bekräftar värdet av dessa förbättringar. Framtida forskning kan inkludera utforskning av ytterligare algoritmer och förbättringar samt deras tillämpning och testning i realtidsscenarier för att ytterligare validera och utveckla dessa resultat.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:his-23710 |
| Date | January 2024 |
| Creators | Esst, Maximilian, Skoglöv, Demian |
| Publisher | Högskolan i Skövde, Institutionen för informationsteknologi |
| Source Sets | DiVA Archive at Upsalla University |
| Language | Swedish |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0025 seconds