Pathfinding: En rapport om grafer og algoritmer

Jonatan Emil Rytter, Lars Morten Bek, André Sandgreen Jensen, Emil Møller Pedersen & Ali Hassan Raza

Studenteropgave: Fagmodulprojekt

Abstrakt

This report focuses on pathfinding and more specifically how to implement it. Random generation of environments have been made with both a NavMesh and Waypoint graph environments. Other than the Random Environment Generation, the Dijkstra's algorithm and the A* (A star) algorithm are the other two algorithms explained in this report and they are used to find the shortest paths through different graphs. There have been considerations on how to make the application user friendly and there have been made tests to see what algorithm is faster in certain environments. Besides this UML have been used to illustrate the program structure, and different aspects on how the program functions. Finally, as a result of our testing and experience writing this report and the program is working very great and we’re happy with the results. The testing while doing the project documented how finished the program is in terms of the requirement specification. The A* and Dijkstra returned the shortest path correctly.
The things we didn’t get to cover in this report like incremental heuristic search are very interesting topics, that easily could get elaborated on in future projects.

UddannelserDatalogi, (Bachelor/kandidatuddannelse) Bachelor
SprogEngelsk
Udgivelsesdato17 dec. 2019
Antal sider52
VejledereLine Reinhardt

Emneord

  • Pathfinding
  • Dijkstra
  • A*
  • AStar
  • Software Development
  • Software Testing
  • Graph Theory
  • UML
  • Java
  • JavaFX
  • FXML
  • NavMesh
  • Map Generation
  • Waypoint
  • JUnit
  • Line Intersection
  • Collision Detection
  • Computer Science
  • Mathematics
  • Informatics
  • Shortest path