The general subject of this thesis concerns different weightings applied to Dijkstra’s pathfinding algorithm to balance performance versus accuracy in a simulated realistic environment. The algorithms used in this study are Dijkstra's pathfinding algorithm and A*. When evaluating paths in the opposite direction of the goal the path length is multiplied by a heuristic coefficient. Thus giving preference to the path in the general direction of the goal. The results derived from this testing show that for each usage case that does not disregard either path length or computation time there is a heuristic coefficient for which the pathfinding calculations will require the least amount of computation power in relation to the accuracy of the resulting paths. ; Denna avhandling avser påvisa hur olika viktningar applicerad på Dijkstras Pathfindingalgoritm balanserar prestanta och precision i en simulerad realistisk miljö. Algortimerna som används är Dijkstras och A*. När vägar i motsatt riktning mot målet övervägs multipliceras dessa med en heuristisk koefficient. Därmed premieras vägar som generellt går rakt mot målet. De härledda resultaten påvisar att för varje användningsfall som inte ignorerar varken prestanta eller precision finns det en heuristisk viktningskoefficient där minsta möjliga mängd prestanta relativt precision krävs.


    Access

    Download


    Export, share and cite



    Title :

    Comparative Analysis of Weighted Pathfinding in Realistic Environments ; Komparativ Analys of Viktad Pathfinding i Realistiska Miljöer


    Contributors:

    Publication date :

    2017-01-01


    Type of media :

    Theses


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629




    Building Digital Maps for Pathfinding

    Angwin, G. T. / Heideman, M. T. / Intelligent Vehicle Highway Society of America | British Library Conference Proceedings | 1993


    Discretized Quaternion Constrained Attitude Pathfinding

    Kjellberg, Henri C. / Lightsey, E. Glenn | AIAA | 2015


    PATHFINDING IN FUELS AND ENGINES

    BOYD, T. A. | SAE Technical Papers | 1950


    PATHFINDING SYSTEM, METHOD AND PROGRAM

    MUTSUGA KATSUHIKO / MOCHIZUKI ATSUSHI | European Patent Office | 2016

    Free access