Arbetet undersöker prestanda och estetik hos A*PS och Theta* inom olika miljötyper, där miljötyper är ett generaliserat begrepp för spelmiljöer och innefattar en struktur samt ett antal blockerande objekt. Båda teknikerna är varianter av A*-algoritmen och används för att åstadkomma estetisk vägplanering. Vägplanering innebär att finna en kortaste väg från en punkt A till en punkt B i en graf. En populär grafrepresentation i spel är rutnät med blockerande och icke-blockerande noder. Ett problem med rutnät är att algoritmerna tenderar att planera sina vägar längst med kanterna och därav resultera i sicksackformade vägar. A*PS och Theta* löser detta genom att utföra estetiska optimeringar som tillåter vägplaneringen att göras längst med grafens kanter, men samtidigt inte låta vägarna begränsas till att direkt följa dessa. Med experiment visar arbetet att Theta* i majoriteten av fallen hittar kortare och mer realistiska vägar. Vidare föreslås framtida arbeten inom området.

<p>Förstudien är det första steget i projekteringsfasen, där det ges förslag på åtgärder. I Vägverkets arbete med åtgärder tas det fram förstudier, för att se vilka problemen är och vilka åtgärder som kan tänkas vara möjliga. Den här rapporten kommer att granska arbetet med förstudier. Under arbetets gång har vi använt oss av litteraturstudier, intervjuer samt en enkät. Arbetet inleds med att beskriva vad en förstudie är samt hur arbetet går till i teorin. Sedan följer en empirisk del, där berättas det om de intervjuer som gjorts och där presenteras även resultatet av enkäten. Efter det analyseras resultaten från den empiriska delen, och i de sista kapitlen diskuteras problem och förändringar. Först kommer en beskrivning kring hur arbetet med förstudier fungerar idag, och sedan ges förslag på hur arbetet kan förändras. Som ett exempel kan nämnas ett av de problem som finns idag. Det är hur de behandlar ekonomin, i många fall är redovisningen bristfällig. De som läser förstudien får inte veta hur kostnaderna har räknats fram. Den förändring vi kom fram till är att problemet kan lösas om det finns mer dokumentation kring arbetet som görs innan en förstudie påbörjas. Detta skulle öka tydligheten och ge en ökad förståelse.</p>

Förstudien är det första steget i projekteringsfasen, där det ges förslag på åtgärder. I Vägverkets arbete med åtgärder tas det fram förstudier, för att se vilka problemen är och vilka åtgärder som kan tänkas vara möjliga. Den här rapporten kommer att granska arbetet med förstudier. Under arbetets gång har vi använt oss av litteraturstudier, intervjuer samt en enkät. Arbetet inleds med att beskriva vad en förstudie är samt hur arbetet går till i teorin. Sedan följer en empirisk del, där berättas det om de intervjuer som gjorts och där presenteras även resultatet av enkäten. Efter det analyseras resultaten från den empiriska delen, och i de sista kapitlen diskuteras problem och förändringar. Först kommer en beskrivning kring hur arbetet med förstudier fungerar idag, och sedan ges förslag på hur arbetet kan förändras. Som ett exempel kan nämnas ett av de problem som finns idag. Det är hur de behandlar ekonomin, i många fall är redovisningen bristfällig. De som läser förstudien får inte veta hur kostnaderna har räknats fram. Den förändring vi kom fram till är att problemet kan lösas om det finns mer dokumentation kring arbetet som görs innan en förstudie påbörjas. Detta skulle öka tydligheten och ge en ökad förståelse.

Algoritmer för vägplanering används ofta i dataspel för att navigera datorstyrda enheter. En av de vanligaste algoritmerna som används i samband med vägplanering är A* algoritmen, som kan användas för att effektivt hitta den kortaste vägen mellan två positioner i spelets nivåer. Algoritmen har dock inget stöd för att producera estetiskt tilltalande vägar, vilket kan leda till att spelets enheter rör sig som robotar genom spelnivån. Detta arbete tar upp och analyserar algoritmer som kan användas i kombination med A* algoritmen för att göra vägarna rakare, mjukare och mer direkta. Algoritmerna implementeras i ett program där deras minnesanvändning, tidseffektivitet och väglängd beräknas när de körs genom en spelnivå med väggar och hinder. Resultaten från slutet av rapporten visar att de estetiskt förbättrande algoritmerna kan implementeras för att göra stora förbättringar av A* algoritmens estetiska prestationer, utan större påverkningar på A* algoritmens minnesanvändning, tidseffektivitet och väglängd. Resultaten från både produkt och utvärderingen skulle kunna användas i framtida spelprojekt.

Den här undersökningen har jämfört ifall ett gemensamt dynamiskt flödesfält som fylls allteftersom kan prestera bättre än när varje agent måste fylla sitt eget flödesfält. Ett antal scenarion har skapats för att ta reda på vilket sätt teknikerna skiljer sig. Ett scenario utvärderas genom att automatiskt placera ut en stor mängd agenter och notera FPS under testets gång. Dessa data presenteras sedan i en gemensam graf för de två teknikerna där skiljaktigheterna går att observera. Efter testning visar det sig att de två största anledningarna till skillnaden i prestanda är beroende på storleken av agenternas sökrymd samt hur många spridda mål det finns. En stor sökrymd försämrar den icke dynamiska tekniken medan den dynamiska presterar bra. Många spridda mål försämrar den dynamiska teknikens prestanda på grund av att fältet inte kan återanvändas. Resultatet diskuteras kunna användas i en hybridlösning för vektorfält, samt kunna jämföras med ett komplett flödesfält.

Detta arbete undersöker om en Evolutionär Algoritm (EA) kan användas fördelaktigt för vägplanering i datorspel genom att utvärdera den mot industristandarden A*. Den valda algoritmen är utvecklad med syftet att planera vägar för robotar. Ett område som anses snarlikt till vägplanering för virtuella karaktärer i datorspel. Genomförandet av arbetet har visat att flera av de algoritmer som övervägdes innehåller brister som gör implementation av dem problematisk. Därför har flera avvikelser från algoritmens specifikation gjorts. Trots detta så har arbetet givit intressanta resultat. Endast i extremfall av mycket stora nivåer med få hinder så kan EA:n prestera bättre än A*. Däremot producerar EA:n vägar som är intressanta från ett utseendemässigt perspektiv. Den icke-deterministiska naturen hos EA:n resulterar även i olika vägar vid varje exekvering. Slutsatsen för arbetet är därmed att intresset för fortsatt forskning sannolikt finns i utseendet på de vägar som EA:n beräknar snarare än dess prestanda.

Detta arbete undersöker möjligheten att reducera minnesanvändningen av Ozcan och Haciomeroglus (2015) navigationsmodell genom att byta den underliggande grafen. Navigationsmodellen baseras på A* men lägger till potentialvärde för cellerna samt riktningsvektorer som visar hur cellerna används och med dem beräknar fram en väg som följer flödet i cellerna. Arbetet försöker reducera minnesanvändningen genom att byta från en rutnätsgraf till en navigationsgraf med bibehållen funktionalitet. Undersökningen jämför mängden minne som allokeras för de två graferna samt tiden och längden det tar för agenterna att ta sig från start till sin slutpunkt på de två olika miljöerna. Resultaten visar att det går att reducera mängden minne som allokeras genom en navigationsgraf samt att tiderna och längderna för agenter är lika mellan graferna vilket visar att funktionaliteten kvarstod efter grafbytet. / <p>Det finns övrigt digitalt material (t.ex. film-, bild- eller ljudfiler) eller modeller/artefakter tillhörande examensarbetet som ska skickas till arkivet.</p><p>There are other digital material (eg film, image or audio files) or models/artifacts that belongs to the thesis and need to be archived.</p>

Trafiksimulering är vanligt förekommande i stadsbyggarspel, som t.ex. SimCity (2013), och innebär att bilar färdas mot ett bestämt mål, istället för endast visuellt presenterat utifrån statistik, som i tidigare stadsbyggarspel. Problemet med denna simulering är att antalet bilar ökar i takt med att staden växer, vilket innebär att simuleringen måste vara optimalt effektiv för att kunna köras i realtid. För att bilarna ska hitta till målet genomförs vanligtvis en genomsökning av vägnätet med en algoritm som heter A*, som lägger upp en väg till målet.Detta kan vara tidskrävande att simulera i realtid med många bilar. Detta arbete tar fram en ny metod som liknar hur data navigeras på Internet, kallat routing. Denna metod benämns Internet Routing. Metoden testades mot A* algoritmen och sedan jämfördes deras simuleringseffektivitet (FPS). Resultaten visade att det blev nästan samma FPS för båda. Slutsatsen är att den är likvärdig men mer komplex att implementera.

Detta arbete jämför Theta* och en genetisk algoritm för att undersöka ifall en genetisk algoritm ger mer förutsägbara vägar i dynamiska miljöer än en deterministisk sökteknik. Den valda genetiska algoritmen är inte begränsad till vägval till närliggande noder, den nod som är näst i tur kan ligga var som helst i miljön. Theta* valdes för att matcha detta beteende och anses vara en bra representation av en deterministisk sökteknik då den är en vidareutveckling av standarden A*. Resultaten angående förutsägbarheten samlades in genom en enkätundersökning där fyra aspekter efterfrågades i jämförelser mellan Theta* och den genetiska algoritmen: vilken väg är mjukast, vilken väg är rakast, vilken väg är mest direkt, och vilken väg är kortast. Resultaten visade att den genetiska algoritmen presterat 0,6-2,0% bättre än Theta* och anses därför kunna ge mer förutsägbara vägar. Dock krävs mer forskning för att fastställa hur väsentliga de olika kriterierna är för förutsägbarheten. / This work compares Theta* and a genetic algorithm in order to investigate whether a genetic algorithm gives more predictable paths in dynamic environments than a deterministic search algorithm. The chosen genetic algorithm is not restricted to moving to nearby nodes - the next node may be located anywhere in the environment. Theta* was chosen to match this behaviour and is considered to be a good representation of a deterministic search technique as it is based upon the industry standard A*. Results related to the predictability were collected through a survey where four aspects were asked in comparisons between Theta* and the genetic algorithm: which path is smoother, which path is straighter, which path is more direct, and which path is shorter. The results showed that the genetic algorithm performed 0,6-2,0% better than Theta* and is thereby considered to be able to give more predictable paths. There is however a need for further studies in order to establish how important the criteria are for the predictability.

Detta examensarbete tittar närmare på vägplaneringsproblemet som är ett vanligt förekommande problem inom datorspel. Arbetet skall försöka besvara följande frågeställning: Vilka kombinationer av styrbeteenden och beräkningsmodeller kan användas för större grupper av autonoma agenter som navigerar i en miljö med avseende på prestanda och estetik? För att besvara frågeställningen så skapades en applikation där fyra olika styrbeteenden implementerades. Vägföljningsbeteendet är grundbeteendet för agenternas navigering och flockbeteendet används för att ge ett bättre resultat. Resultatet av arbetet visar på att de fyra styrbeteendena som omfattas av arbetet är tillräckligt i de flesta fall; även om det finns brister. De fyra styrbeteendena hade med god anledning kunnat kombinerats med andra styrbeteenden som inte tas upp i arbetet för att ge en mer komplett navigering. Styrbeteenden kan även användas utanför datorspel, så som inom robotik eller för att simulera agenter i en trafikmiljö eller agenter som evakuerar en byggnad.