is Íslenska en English

Lokaverkefni (Meistara)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > MSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/23741

Titill: 
  • Titill er á ensku Using Map Decomposition to Improve Pathfinding
  • Svæðaskipting korta til að bæta leit að stystu leið
Námsstig: 
  • Meistara
Leiðbeinandi: 
Útdráttur: 
  • Útdráttur er á ensku

    Artificial intelligence in games performs computationally expensive searches in large state spaces, i.e. for pathfinding and strategic decisions. Breaking the state space down into regions, with clear connections, can greatly benefit these algorithms, allowing decision making on a higher level and guiding searches in a more focused way through the search space. We present an improved heuristic for pathfinding search that takes advantage of such decompositions, as well as a fully automated method for identifying meaningful strategic regions in game maps. Empirical evaluation shows that our automatic decomposition method results in intuitive regions of comparable quality to the current state of the art, when run on game maps taken from commercial video games. Its implementation also runs faster than the current standard and the approach is conceptually intuitive and readily understandable. Furthermore we show that significant improvement can be made to pathfinding search effectiveness using an algorithm that takes advantage of the map decomposition.

  • Gervigreind í leikjum inniheldur stórar leitir í sérhæfðum leitarrýmum, m.a. til að finna stystu leið í korti og við áætlanagerð. Niðurbrot leitarrýmisins niður í svæði með skýrar tengingar getur bætt slík reiknirit verulega með því að leyfa ákvarðanatöku á hærra plani og stýra leitum á nákvæmari hátt gegnum leitarrýmið. Við kynnum bætt matsfall fyrir leit að stystu leið sem notfærir sér slík niðurbrot, og auk þess alsjálfvirka aðferð til að skipta leikjakortum upp í svæði á skilmerkilegan hátt. Tilraunir keyrðar á kortum úr tölvuleikjum sýna að sjálfvirka niðurbrotsreikniritið skilar skýrum svæðum af sambærilegum gæðum og það sem best þekkist. Útfærslan okkar keyrir líka hraðar en núverandi aðferðir og er þar að auki auðskiljanleg og einföld í útfærslu. Ennfremur sýnum við fram á að hraða leitar að stystu leið í korti má bæta umtalsvert með reikniriti sem tekur mið af slíku niðurbroti korts.

Styrktaraðili: 
  • RANNIS
Samþykkt: 
  • 11.2.2016
URI: 
  • http://hdl.handle.net/1946/23741


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
KariHalldorsson_2015_MSc_Thesis_S.pdf1.65 MBOpinnHeildartextiPDFSkoða/Opna