2D konvoliucija paremtų metodų, skirtų apytikslio trumpiausio maršruto radimui, tyrimas
| Autor: | Teleiša, Marius |
|---|---|
| Přispěvatelé: | Čalnerytė, Dalia |
| Jazyk: | litevština |
| Rok vydání: | 2023 |
| Předmět: | |
| Popis: | Darbe apžvelgiami įvairūs hierarchinės kelio paieškos ir randamo kelio ilgio gerinimo metodai. Analizės metu įgytos žinios pritaikytos projektuojant patobulinimus konvoliucinės hierarchinės paieškos A* (CHPA*) kelio paieškos algoritmui. Pirmas pakeitimas – pataisomos abstrakcijos sluoksnio klaidos panaikinant kraštines vedančias iš segmento, kur algoritmas mato kelią iš viršaus ir kairės į segmentą, tačiau įstrižai segmento kelio nėra. Toliau pateikiamas naujas optimalesnis koordinačių perskaičiavimo metodas, kuris nutraukia tarpinių taškų kelio paiešką pasiekus bent vieną segmento viršūnę ir geba rasti trumpiausią kelią tarp segmentų. Trečias pakeitimas – algoritmo pritaikymas 8-ių krypčių jungimo kvadratinio tinklo grafui. Eksperimentinių tyrimu metu lyginami A*, Jump Point Search (JPS) ir CHPA* rezultatai atsitiktinai generuotuose, labirintų, kvadratinių kambarių bei strateginio žaidimo žemėlapiuose. Nustatyta, kad CHPA* algoritmo patobulinimai gerina randamo kelio ilgį ir reikšmingai nepaveikia greitaveikos. The paper reviews various methods for hierarchical pathfinding and path optimization. The knowledge gained from the analysis is applied to the design of improvements to the Convolutional Hierarchical Path A* (CHPA*) algorithm. The first change corrects abstraction layer errors by removing edges leading out of a segment, where the algorithm sees a path from the top and left segments, but there is no diagonal path across the segment. Second, a new more optimal method of coordinate translation is presented, which stops the search for intermediate paths when at least one segment vertex is reached and is able to find the shortest path between segments. Third, the algorithm is adapted to work on octile grids. Experimental studies compare the results of A*, Jump Point Search (JPS) and CHPA* on randomly generated, maze, square room and strategy game maps. Results show, that the enhancements to the CHPA* algorithm improve the path length and do not significantly affect the search time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|