Reitinhaku reaaliaikaisissa simulaatioissa

Abstract

Tässä opinnäytetyössä käsitellään erilaisia reitinhakumenetelmiä keskittyen erityisesti A*-algoritmiin. Toimintaperiaatteiden lisäksi esitetään potentiaalisia lajittelumenetelmiä ja tietorakenteita. Vertailussa on heuristisia funktioita, jotka vaikuttavat merkittävästi algoritmin suoritustehoon ja hakutulokseen. Työssä sivutaan myös reaaliajan ja dynaamisen ympäristön tuomia haasteita.

Lopussa esitellään reaaliaikainen sovellus, joka käyttää A*-algoritmia reitinhakuun sekä binäärikekoa tiedon varastoimiseen ja hakemiseen.

The purpose of this thesis is to represent different methods of pathfinding, specifically A*-algorithm. In addition to the basic functionality, potential sorting methods and data structures are represented. Heuristics, which have significant effects on the performance and search results, are compared. Also, thesis deals with some issues introduced by real-time and dynamic environment.

In the end, the thesis demonstrates a real-time application using A*-algorithm for pathfinding and a binary heap to store and organize data.