Polunetsintä ruudukkokartoilla
Oinas, Pekka (2020)
Oinas, Pekka
2020
Tietojenkäsittelytieteiden kandidaattiohjelma - Bachelor's Degree Programme in Computer Sciences
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2020-05-18
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202004294590
https://urn.fi/URN:NBN:fi:tuni-202004294590
Tiivistelmä
Tässä kirjallisuuskatsauksessa tutustutaan säännöllisillä ruudukkokartoilla tapahtuvaan polunetsintään. Ruudukkokartat ovat yleisiä monilla polunetsinnän sovellusalueilla, kuten robotiikassa ja videopeleissä, ja niiden sisältämien polkujen korkea symmetria muodostaa haasteellisen ongelman perinteisille polunetsinnän ratkaisuille, kuten A*-algoritmille, hidastaen sen toimintaa; tästä syystä on olemassa monia ruudukkokartoille optimoituja algoritmeja, jotka suoriutuvat A*:ä nopeammin.
Tutkielmassa perehdytään ensin polunetsinnän relevantteihin perusteisiin, Dijkstran algoritmiin ja sen jälkeläiseen, A*-algoritmiin, tarkastelemalla niiden pseudokooditoteutusta sekä suoritusaikaominaisuuksia. Tämän jälkeen esitellään kolme ruudukkokartoille erikoistunutta algoritmia: Hierarchical Path-Finding A*, Rectangular Symmetry Reduction ja Jump Point Search. Esiteltyjen algoritmien toiminta kuvaillaan ja niiden suorituskykyä vertaillaan suhteessa A*:een ja muihin algoritmeihin.
Tutkielman lopussa esitetään johtopäätös, jonka mukaan tarkastelluista algoritmeista Jump Point Search vaikuttaa suorituskykynsä ja muiden ominaisuuksiensa puolesta olevan paras ratkaisu ongelmaan. Se suoriutuu jopa monikymmenkertaisesti lähtökohtana käytettyä A*-algoritmia nopeammin ja on kaikissa tarkastelluissa tilanteissa yhtä nopea tai nopeampi kuin muut vertaillut algoritmit, eikä sillä ole mainittavia varjopuolia. Lisäksi ehdotetaan kahta mahdollista suuntaa jatkotutkimukselle. This literary review examines pathfinding on regular grid maps. Regular grid maps are common in many applications of pathfinding, such as robotics and video games, and they pose a challenging problem to traditional solutions such as the A* algorithm, slowing down its execution. For this reason there are many algorithms optimized for grid maps to yield better performance than A*.
In this paper we first go over the relevant basics of pathfinding --- Dijkstra's algorithm and its extension, A* --- by examining their pseudocode representations and running time properties. We then introduce three algorithms optimized for pathfinding on grid maps: Hierarchical Path-Finding A*, Rectangular Symmetry Reduction and Jump Point Search. We describe the operation of these algorithms and compare their performance to A* and other algorithms.
We conclude that out of the presented algorithms, Jump Point Search appears to be the best choice considering its performance and other properties. It performs an order of magnitude faster than the A* algorithm used as the baseline, it is faster or at least as fast as the other examined algorithms, and it has no appreciable downsides. We also suggest two possible directions for further research.
Tutkielmassa perehdytään ensin polunetsinnän relevantteihin perusteisiin, Dijkstran algoritmiin ja sen jälkeläiseen, A*-algoritmiin, tarkastelemalla niiden pseudokooditoteutusta sekä suoritusaikaominaisuuksia. Tämän jälkeen esitellään kolme ruudukkokartoille erikoistunutta algoritmia: Hierarchical Path-Finding A*, Rectangular Symmetry Reduction ja Jump Point Search. Esiteltyjen algoritmien toiminta kuvaillaan ja niiden suorituskykyä vertaillaan suhteessa A*:een ja muihin algoritmeihin.
Tutkielman lopussa esitetään johtopäätös, jonka mukaan tarkastelluista algoritmeista Jump Point Search vaikuttaa suorituskykynsä ja muiden ominaisuuksiensa puolesta olevan paras ratkaisu ongelmaan. Se suoriutuu jopa monikymmenkertaisesti lähtökohtana käytettyä A*-algoritmia nopeammin ja on kaikissa tarkastelluissa tilanteissa yhtä nopea tai nopeampi kuin muut vertaillut algoritmit, eikä sillä ole mainittavia varjopuolia. Lisäksi ehdotetaan kahta mahdollista suuntaa jatkotutkimukselle.
In this paper we first go over the relevant basics of pathfinding --- Dijkstra's algorithm and its extension, A* --- by examining their pseudocode representations and running time properties. We then introduce three algorithms optimized for pathfinding on grid maps: Hierarchical Path-Finding A*, Rectangular Symmetry Reduction and Jump Point Search. We describe the operation of these algorithms and compare their performance to A* and other algorithms.
We conclude that out of the presented algorithms, Jump Point Search appears to be the best choice considering its performance and other properties. It performs an order of magnitude faster than the A* algorithm used as the baseline, it is faster or at least as fast as the other examined algorithms, and it has no appreciable downsides. We also suggest two possible directions for further research.
Kokoelmat
- Kandidaatintutkielmat [7045]