Pathfinding through conformal mapping
Master thesis
Permanent lenke
http://hdl.handle.net/11250/2625691Utgivelsesdato
2019Metadata
Vis full innførselSamlinger
Sammendrag
I denne oppgaven er konforme avbildninger er brukt for å løse stifinningsproblemer. Ved å konformt transformere 2D planet til en enklere representasjon, blir kostnaden av å gjennomføre stifinning redusert. Hovedfordelen av prosedyren er at hele stien ikke trenger å beregnes for å garantere at den er korrekt. Dette medfører at stien kan beregnes i sanntid. Siden ikke hele stien må beregnes før agenten kan agere, er responstiden til den konforme stifinningsalgoritmen raskere enn hvis den måtte bergnet hele stien. En annen fordel med konform stifinning er at ingen beregninger er bortkastet på å generere en sti som ikke vil bli fulgt, i tilfeller der agenten endrer destinasjon før målet er nådd.
En algoritme blir her foreslått for å finne konforme avbildninger som er velegnet for stifinning. Kart med ulike topologier, med og uten hindere, er vurdert.
Praktiske eksperimenter blir utført i Unity3D, som er en kommersiell spillmotor og i MATLAB, for å demonstrere og sette mål på algoritmen. Kildekoden er skrevet i C# og kan bli kjørt i sanntid. In this thesis, conformal mappings are used to solve pathfinding problems. By conformally mapping the 2D plane to simpler representations, the cost of pathfinding is reduced. The main benefits of this procedure is that the full path is not required to be computed to guarantee completeness, which means that the path can be computed in real-time. This means that the computational cost for calculating the path can be spread out in time, which increase the responsiveness of the pathfinder. Another benefit of this approach is that because the entire path is not computed ahead of time, there are less wasted computations if the agent changes destinations prematurely.
An algorithm is proposed for finding one or more conformal maps that are well-suited for pathfinding. Various map topoligies with, -and without obstacles are considered.
Practical experiments are conducted in Unity3D, a commercial game-engine, and in MATLAB, to demonstrate and benchmark the algorithm. The source-code is written in C# and can be executed in real-time.