Název:
Navigácia Hierarchickým Navmeshom založená na analýze geometrie
Překlad názvu:
Pathfinding within a Hierarchical Navmesh Based on Geometry Analysis
Autoři:
Chomut, Miroslav ; Plch, Tomáš (vedoucí práce) ; Bída, Michal (oponent) Typ dokumentu: Diplomové práce
Rok:
2014
Jazyk:
eng
Abstrakt: [eng][cze] Title: Pathfinding within a Hierarchical Navmesh Based on Geometry Analysis Author: Miroslav Chomut Department / Institute: Department of Software and Computer Science Education Supervisor of the master thesis: Mgr. Tomáš Plch, Media and Communications Office Abstract: Pathfinding is a common problem in the computer science dealing with navigation from a starting point to a destination point. Common algorithms today are mostly based on A* search on a graph representation of navigated world. Another common approach is creation of navigation structure of convex navigation meshes and navigating on them. Our goal is to propose pathfinding algorithm on hierarchical navigation meshes, based on the terrain geometry, which benefits from complexity of hierarchical search yet provides paths comparable in length to reference ones. This thesis analyses and describes our proposed approach of navigation including generation of the navigation structure. Keywords: navmesh, pathfinding, A*, hierarchy, terrain analysis, geometryNázov práce: Navigácia Hierarchickým Navmeshom založená na analýze geometrie Autor: Miroslav Chomut Katedra / Ústav: Kabinet software a výuky informatiky Vedúci diplomovej práce: Mgr. Tomáš Plch, Oddelenie mediálnej komunikácie Abstrakt: Pathfinding je známy problém informatiky, zaoberajúci sa navigáciou zo štartového do cieľového bodu. V súčastnosti používané algoritmy sú prevažne založené na A* prehľadávaní grafu reprezentujúceho navigovaný svet. Ďaľším bežným prístupom je vytvorenie navigačnej štruktúry z konvexných navigačných meshov a navigácia na nej. Naším cieľom je návrh navigačného algoritmu na hierarchickom navigačnom meshi, využívajúcom geometriu terénu, s časovou zložitosťou hierarchického prehľadávania a vzdialenosťami porovnateľnými s referenčnými. Táto práca analyzuje a popisuje navrhnutý algoritmus, vrátane generácie navigačnej štruktúry. Kľúčové slová: navmesh, pathfinding, A*, hierarchy, terrain analysis, geometry
Klíčová slova:
A*; geometry; hierarchy; navmesh; pathfinding; terrain analysis; A*; geometry; hierarchy; navmesh; pathfinding; terrain analysis