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.

A drone is an unmanned aerial vehicle with multiple forms of usage. Drones can be programmed to fly with different degrees of autonomous flight. Autonomous controlled flight makes it possible for the drone to fly without human involvement and it is then controlled solely by software. The goal of this project is to program the micro drone Crazyflie 2.1 to autonomously fly through an obstacle course in the shortest amount of time and a predetermined direction. The nature and placement of the obstacles are unknown beforehand. The obstacles are detected and avoided by using the obstacle detection sensor Multi- ranger. To achieve autonomous flight two possible navigation systems were tested, the Loco Positioning System and Flow deck. Flying the Crazyflie while using Flow deck as positioning system performed best, managing to fly through the obstacle course avoiding all obstacles.

Dijkstra’s algorithm used for pathfinding in a grid type setting consisting of forest geodata with multiple attributes. A cost analysis was performed regarding the memory required to run the application. This cost analysis yielded in a space complexity of O(n), and a class structure with focus on low memory usage while still maintaining desired functionality. The test shows a reduction of about 17,9% in memory usage compared to without memory saving measures. The algorithm and class structure are used in a web-based application implemented with JavaScript.

Payment Channel Networks (PCNs) provide a solution to the scalability problem in blockchain technology. They facilitate multiple-hop transactions via payment channels between peers, allowing for the execution of several transactions before updating each node’s balance on the blockchain. However, the performance of the network in effectively routing payments is affected by unbalanced channels. This imbalance reduces the network’s ability to route payments in both directions within a channel, resulting in decreased overall performance. Previous research has identified unidirectional payment flows in the network as the underlying cause of this issue. The payment flow is based on the demand for payments between peers and the paths these payments take. The aim of this study is to investigate the relationship between payment patterns and the average channel imbalance, where the payment pattern is a combination of demand patterns and what pathfinding algorithm is used. The study uses a model of PCNs that allows the relationship of the variables of interest to be measured, while other impacting variables are controlled. A deterministic value of the average channel imbalance for a PCN topology, demand pattern, and pathfinding strategy is achieved by computing the steady-state imbalance. The results show that the less homogeneous the demand pattern is, the more asymmetric the payment flow becomes, and the more imbalanced the network’s channels become. The results confirm what previous research mentions: unidirectional flow causes the payment channel to become imbalanced. The demand pattern that generates unidirectional flow imbalance significantly affects the entire network, regardless of the pathfinding strategy employed. Even with the possibility of a pathfinding strategy influencing payment flow to make it less unidirectional, the inherent unbalanced nature of the demand pattern remains a considerable challenge. The results also show that the pathfinding strategy has a less significant impact than the demand pattern on the balance of the network over time. / Payment Channel Networks (PCN) tillåter fler transaktioner utföras på kortare tid för en mindre kostnad, än att publicera varje enskild transaktion direkt på blockkedja och är en bra lösning på skalbarhetsroblem kopplat till blockedjor som baseras på proof-of-work. PCNs möjliggör för flerhoppstransaktioner via noder som kan vidarebefodra flera betalningar på varje enskild betalningskanal de håller öppna med andra noder. Inte förrän en kanal stängs publiceras den senaste uppdateringen av saldot för enskild betalningskanal på blockkedjan. Trots detta lider nätverkets prestanda av att kanaler blir obalanserade och ökar risken för att transaktioner misslyckas routas. Tidigare forskning nämner att orsaken till att kanaler blir obalanserade är enriktade betalningsflöden i nätverket, vilket beror av betalningsflödet som är en kombination av betalningsefterfråga (vem vill betala vem) mellan noderna och vilka vägar som dessa betalningar tar. Syftet med denna studie är att undersöka sambandet mellan betalmönster och genomsnittlig kanalobalans, där betalmönstret är en kombination av efterfrågansmönster och vägvalsstrategier. Studien använder en PCN-modell som möjliggör att undersöka sambandet mellan de variabler som är tänkt ska mätas, samtidigt som andra variabler kan kontrolleras. Genom att beräkna den stabila obalansen uppnås ett deterministiskt värde för genomsnittlig kanalobalans i varje nätverkstopologi. Resultaten visar att ju mindre homogent efterfrågemönstret är, desto mer asymmetriskt blir betalningsflödet och desto mer obalanserade blir nätverkets kanaler. Resultatet bekräftar det som tidigare forskning nämner: enriktade flöden orsakar obalans i betalningskanalen. Specifikt är det efterfrågansmönstern som skapar enriktade flöden som har de högsta stabila obalansen, oavsett vilken vägvalsstrategi som används. Resultaten visar också att vägvalsstrategin har mindre betydelse än efterfrågemönstret, åtminstone för vägvalsstrategier som leder till liknande valda vägar.

Background. The A* algorithm is a well-established pathfinding technique frequently used in video game development. However, a disadvantage of the A* algorithm is that it becomes computationally inefficient and impractical to utilize whenthousands of agents demand an optimal path. A solution to mitigate this issue isthe use of the flow field algorithm. This algorithm employs a goal-based pathfindingstrategy, which allows for the movement of a large number of units through the useof a single direction map (flow field map) that indicates the direction units must take to progress toward their goal. Objectives. The main objective of this study is to examine the performance and scalability of precomputed flow field maps with regard to execution time and memory utilization, with the objective of determining the feasibility of precomputed maps as an alternative to maps generated at runtime. Furthermore, the study implements and investigates compression techniques to minimize the memory footprint of precomputed flow field maps. Methods. The study adopts an experimental research design to assess the performance of the two implementations under various conditions of grid size and movement system. Performance evaluation is accomplished through the measurement and comparison of execution time and memory consumption. Additionally, a directional accuracy test is performed to quantify the potential loss of accuracy in the vectors stored in the precomputed flow field maps. Results. The precomputed flow field maps provide constant access time, with a time complexity of O(1), regardless of the grid size and the type of movement system. The memory usage of these maps increases significantly with the growth of the grid size. A doubling of the grid size leads to a more than fifteen-fold increase in memory usage. The techniques proposed in the study significantly reduced the memory footprint by a factor of thirty-two and by a factor of eight, depending on the selected movement system. The average loss in accuracy was approximately 0.35 degrees for the proposed any-angle compression technique. Conclusions. The use of precomputed flow field maps has limitations, including being limited to static environments and having high memory requirements. On the other hand, they provide constant access time for pathfinding information, independent of the grid dimensions, movement system, and the number of target nodes. Whether precomputed flow field maps are better than the traditional runtime implementation depends on the intended use.

No description available.

Effektiva lärosätt för algoritmer är inte alltid det enklaste att hitta. Algoritmer somanvänds inom området för artificiell intelligens kan ofta vara svåra att förstå och ta långtid att lära sig. Uppsatsen handlar om hur det kan vara möjligt att effektivisera lärandet av pathfindingalgoritmer genom att använda ett visuellt stödverktyg. Lärometoden som uppsatsen använder sig av är att genom en kombinationen av självimplementation och visualisering av pathfinding-algoritmer kunna öka effekten av dessa algoritmer. Användaren ges möjligheten att implementera fyra grundläggande pathfinding-algoritmer men även möjlighet att konstruera och implementera sina egna algoritmer. Studien som utförts i uppsatsen syftar åt att visa att det kan bli lättare att förstå pathfinding-algoritmer visuellt jämfört med till exempel med penna och papper, där dessa algoritmer ritas ut steg för steg. Studiens resultat visar att ett effektivare lärande kan uppnås om det finns en applikation tillgänglig som ger användaren ett visuellt stöd på hur en pathfinding-algoritm arbetar. / Effective ways of learning algorithms is not always easy to come by, especially withincomputer science. Algorithms used in the field of artificial intelligence can often be verydifficult to understand and may require a lot of effort to learn. This thesis tries to cover the possibility of streamlining the learning process of pathfinding algorithms by supporting the learning process with visual aid. The learning method that this thesis uses is a practical approach of learning pathfinding algorithms followed by visualization of said algorithms. The user is given the opportunity to implement four basic pathfinding algorithms including the possibility to construct and test their own. An application has been developed to facilitate the possibility of visualizing these algorithms. The study carried out in this thesis shows that it may be easier to understand pathfinding algorithms visually than with pen and paper where the user has to write the algorithms search-pattern step by step. The research performed in this thesis demonstrate that it would provide a more effective learning process if the user has access to an application that visually shows how a pathfinding algorithm works.

Software engineering projects that utilize inappropriate pathfinding algorithms carry a significant risk of poor runtime performance for customers. Using social network theory, this experimental study examined the impact of algorithms, frameworks, and map complexity on elapsed time and computer memory consumption. The 1,800 2D map samples utilized were computer random generated and data were collected and processed using Python language scripts. Memory consumption and elapsed time results for each of the 12 experimental treatment groups were compared using factorial MANOVA to determine the impact of the 3 independent variables on elapsed time and computer memory consumption. The MANOVA indicated a significant factor interaction between algorithms, frameworks, and map complexity upon elapsed time and memory consumption, F(4, 3576) = 94.09, p < .001, h2 = .095. The main effects of algorithms, F(4, 3576) = 885.68, p < .001, h2 = .498; and frameworks, F(2, 1787) = 720,360.01, p .001, h2 = .999; and map complexity, F(2, 1787) = 112,736.40, p < .001, h2 = .992, were also all significant. This study may contribute to positive social change by providing software engineers writing software for complex networks, such as analyzing terrorist social networks, with empirical pathfinding algorithm results. This is crucial to enabling selection of appropriately fast, memory-efficient algorithms that help analysts identify and apprehend criminal and terrorist suspects in complex networks before the next attack.

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>