This thesis details the implementation of a navigation mesh within the interior space planning software CET Designer. The motivation for this is to investigate whether a navigation mesh is a suitable alternative to its current path finding solution which is based on a waypoint graph. An empirical analysis between the navigation mesh and the waypoint graph was also conducted. A navigation mesh is successfully implemented and an alternative triangulation method is also tested. The alternative method which is referred to as "narrowest first-ear clipping" seems to create a navigation mesh that produces slightly shorter paths than a navigation mesh that utilizes an arbitrary triangulation method. It is argued that the navigation mesh alleviates much work from the user since it requires less user input. The mesh is also able to generate paths between any two given points within it. This makes it much more dynamic than the waypoint graph. The conducted analysis shows that the navigation mesh seems to generate paths that are generally shorter than the waypoint graph. The path generation time for the navigation mesh is on average slower than the waypoint graph. We failed to provide an environment where the navigation mesh was faster on average than the waypoint graph. However, the time difference between the navigation mesh and the waypoint graph seemed to reduce as the test environment size increased.

Title: IVA Movement Quality Improvement for the Virtual Environment of Unreal Tournament 2004 Author: Bohuslav Macháč Department / Institute: Department of Software and Computer Science Education Supervisor of the master thesis: Mgr. Jakub Gemrot, Department of Software and Computer Science Education Abstract: PogamutUT2004 is an extension of the Pogamut platform designed for developing intelligent virtual agents (IVAs) in Unreal Tournament 2004. Navigation of IVAs in Pogamut is handled by a navigation system, which uses a navigation graph as an environment abstraction. Navigation mesh is a new, more advanced abstraction, but the existing navigation system is not capable of using its advantages. We created a new navigation system, which exploits advantages of the navigation mesh and solves several other issues of the old one. We show that the new navigation system improves the quality of navigation. To demonstrate the quality improvement, an evaluation framework was created for the comparison of navigation systems. Systems were compared in terms of total number of significant paths on the map, which the system is able to follow, length of the path and time of the navigation. We selected 18 different maps for thorough evaluation and we performed the basic evaluation on 58 other maps. The new system is more...

I nästan alla moderna datorspel så återfinns datorstyrda karaktärer, vilka behöver kunna navigera i spelvärlden. Dessa karaktärer kan vara olika typer av fiender i ett förstapersonskjutarspel, eller motståndare och medhjälpare i ett sportspel (exempelvis fotboll- eller rallyspel) med mera. Det finns många tekniker för att realisera vägplanering och det kan vara stora skillnader, både prestandamässiga och funktionella, mellan dem. Detta arbete jämför två olika sökrymdsrepresentationer för vägplanering, nämligen vägpunktsgrafer och navigationsnät, där sökrymderna automatgenererats. Jämförelsen görs med ett experiment och avser såväl prestanda (tids- och minneskostnad) som funktionalitet (optimal väg och antal svängar). Experimentmiljön stödjer godtyckliga vägar och ger detaljerad statistik för en noggrann jämförelse av vägplaneringsteknikerna. Arbetet visar på att navigationsnätet presterar bäst vad gäller funktionalitet. Vad gäller prestanda så presterar navigationsnätet generellt sett bäst, men vägpunktsgrafen kan ge bättre prestanda om nodavståndet hålls relativt högt. Det finns också många möjligheter att vidareutveckla arbetet, exempelvis förfina vägarna och kombinera vägplaneringsteknikerna med robotik.

No description available.

Navigation mesh is a form of representation of a virtual environment, which allows effective navigation of intelligent virtual agents. This thesis deals with the development of a navigation mesh for the intelligent virtual agents in the environment of the computer game Unreal Tournament 2004. Before the development of the navigation mesh, the navigation graph was the only available representation of the environment that the agents could use for navigation. The navigation graph however provides only limited information about the environment. With the use of the navigation mesh the agents are able to navigate in the environment faster and over shorter paths. Creation of the navigation mesh from the environment's geometry extracted from Unreal Tournament 2004 map files is a part of the thesis. Finally, a new navigation module for Pogamut 3 - a platform that allows creation and controlling of intelligent virtual agents, is implemented. The new navigation module consists of the navigation mesh and a set of navigation algorithms Powered by TCPDF (www.tcpdf.org)

Då artificiella intelligenta agenter försöker navigera i en virtuell värld med statiska hinder så behöver dess väg beräknas. För denna beräkning används ett lager som beskriver hur och vart agenten kan röra sig i världen kallat för sökrymd. Detta kan göras på flera olika sätt vilket ger skillnad i prestanda och minnesåtgång samt indirekta fördelar genom sättet sökrymden är uppbyggd på. Genom att jämföra dessa skillnader i olika miljöer så kan resultatet påvisa vilka egenskaper sökrymdstyperna ger i de olika miljöerna. Rapporten visar att n-sidat polygonbaserat navigationsnät ger mycket bra egenskaper i de olika mätningarna och ger även flera fördelar på grund av dess utformning som gör att det kan anpassa sig bra till olika miljöer.

<p>Då artificiella intelligenta agenter försöker navigera i en virtuell värld med statiska hinder så behöver dess väg beräknas. För denna beräkning används ett lager som beskriver hur och vart agenten kan röra sig i världen kallat för sökrymd. Detta kan göras på flera olika sätt vilket ger skillnad i prestanda och minnesåtgång samt indirekta fördelar genom sättet sökrymden är uppbyggd på. Genom att jämföra dessa skillnader i olika miljöer så kan resultatet påvisa vilka egenskaper sökrymdstyperna ger i de olika miljöerna.</p><p>Rapporten visar att n-sidat polygonbaserat navigationsnät ger mycket bra egenskaper i de olika mätningarna och ger även flera fördelar på grund av dess utformning som gör att det kan anpassa sig bra till olika miljöer.</p>

I och med att videospel blir mer avancerade, inte bara grafiskt utan också som konstform samt att dom erbjuder en mer inlevelsefull upplevelse, så kan det förväntas att spelen också ska erbjuda en större utmaning för att få spelaren bli ännu mer engagerad i spelet. Dagens spelare är vana vid fiender vars beteende styrs av tydliga mönster och regler, som beroende på situation agerar på ett förprogrammerat sätt och agerar utifrån förutsägbara mönster. Detta leder till en spelupplevelse där målet blir att klura ut det här mönstret och hitta ett sätt att överlista eller besegra det. Men tänk om det fanns en möjlighet att skapa en ny form av fiende svarar och anpassar sig beroende på hur spelaren beter sig? Som anpassar sig och kommer på egna strategier utifrån hur spelaren spelar, som aktivt försöker överlista spelaren? Genom maskininlärning i spel möjliggörs just detta. Med en maskininlärningsmodell som styr fienderna och tränas mot spelarna som möter den så lär sig fienderna att möta spelarna på ett dynamiskt sätt som anpassas allt eftersom spelaren spelar spelet. Den här studien ämnar att undersöka stegen som krävs för att implementera maskininlärning i Unity motorn samt undersöka ifall det finns någon upplevd skillnad i spelupplevelsen hos spelare som fått möta fiender styrda av en maskininlärningsmodell samt en mer traditionell typ av fiende. Data samlas in från testspelarnas spelsessioner samt deras svar i form av ett frågeformulär, där datan presenteras i grafform för att ge insikt kring ifall fienderna var likvärdigt svåra att spela mot. Svaren från frågeformulären används för att jämföra spelarnas spelupplevelser och utifrån detta se skillnaderna mellan dom. Skalan på spelet och dess enkelhet leder till att svaren inte bör påverkas av okända och ej kontrollerbara faktorer, vilket ger svar som ger oss insikt i skillnaderna mellan dom olika spelupplevelserna där en preferens för fiender styrda av maskininlärningsmodeller kan anas, då dom upplevs mer oförutsägbara och varierande. / As video games become more complex and more immersive, not just graphically or as an artform, but also technically, it can be expected that games behave on a deeper level to challenge and immerse the player further. Today’s gamers have gotten used to pattern based enemies, moving between preprogrammed states with predictable patterns, which lends itself to a certain kind of gameplay where the goal is to figure out how to beat said pattern. But what if there could be more in terms of challenging the player on an interactive level? What if the enemies could learn and adapt, trying to outsmart the player just as much as the player tries to outsmart the enemies. This is where the field of machine learning enters the stage and opens up for an entirely new type of non-player character in videogames. An enemy who uses a trained machine learning model to play against the player, who can adapt and become better as more people play the game. This study aims to look at early steps to implement machine learning in video games, in this case in the Unity engine, and look at the players perception of said enemies compared to normal state-driven enemies. Via testing voluntary players by letting them play against two kinds of enemies, data is gathered to compare the average performance of the players, after which players answer a questionnaire. These answers are analysed to give an indication of preference in type of enemy. Overall the small scale of the game and simplicity of the enemies gives clear answers but also limits the potential complexity of the enemies and thus the players enjoyment. Though this also enables us to discern a perceived difference in the players experience, where a preference for machine learning controlled enemies is noticeable, as they behave less predictable with more varied behaviour.

Over the last years researchers proposed numerous indoor localisation and navigation systems. However, solutions that use WiFi or Radio Frequency Identification require infrastructure to be deployed in the navigation area and infrastructureless techniques, e.g. the ones based on mobile cell ID or dead reckoning suffer from large accuracy errors. In this Thesis, we present a novel approach of infrastructure-less indoor navigation system based on computer vision Structure from Motion techniques. We implemented a prototype localisation and navigation system which can build a navigation map using area photos as input and accurately locate a user in the map. In our client-server architecture based system, a client is a mobile application, which allows a user to locate her or his position by simply taking a photo. The server handles map creation, localisation queries and pathnding. After the implementation, we evaluated the localisation accuracy and latency of the system by benchmarking navigation queries and the model creation algorithm. The system is capable of successfully navigating in Aalto University computer science department library. We were able to achieve an average error of 0.26 metres for successfully localised photos. In the Thesis, we also present challenges that we solved to adapt computer vision techniques for localisation purposes. Finally we observe the possible future work topics to adapt the system to a wide use. / Forskare har de senaste åren framfört olika inomhusnavigations- och lokaliseringssystem. Dock kräver lösningar som använder WiFi eller radiofrekvens identifikation en utbyggdnad av stödjande infrastruktur i navigationsområdena. Även teknikerna som används lider av precisionsfel. I det här examensarbetet redovisar vi en ny taktik för inomhusnavigation som använder sig av datorvisualiserings Structure from Motion-tekniker. Vi implementerade en navigationssystemsprototyp som använder bilder för att bygga en navigationskarta och kartlägga användarens position. I vårt klient-server baserat system är en klient en mobilapplikation som tillåter användaren att hitta sin position genom att ta en bild. På server-sidan hanteras kartor, lokaliseringsförfrågor och mättningar av förfrågorna och algoritmerna som används. Systemet har lyckats navigera genom Aalto Universitets datorvetenskapsbiblioteket. Vi lyckades uppnå en felmarginal pa 0.26 meter för lyckade lokaliseringsbilder. I arbetet redovisar vi utmaningar som vi har löst för att anpassa datorvisualiseringstekniker for lokalisering. Vi har även diskuterat potentialla framtida implementationer for att utvidga systemet.