In dieser Arbeit geht es um die Evaluierung eines effizienten Wegfindungsalgorithmus in einer voxelbasierten 3D-Welt. Ebenso wird auch die Implementierung in einem Beispiel-Projekt gezeigt. Voxelbasierte 3D-Welten tendieren dazu sehr CPU- und Speicherintensiv zu sein, weswegen es umso wichtiger ist, einen ressourcenschonenden Algorithmus zu finden. Die Anforderungen an diesen Algorithmus sind also zum einen, einen plausiblen Weg in einer großen 3D-Welt zu finden und zum anderen kurze Rechenzeiten zu garantieren. Der Algorithmus nutzt hierfür eine 3D-Engine mitsamt Voxel- und NavMesh-Berechnung als Grundlage und kann auf die vorhandenen Datenstrukturen zugreifen und diese weiter verarbeiten. Dabei werden die Vertices und Edges des Navigations Meshes in eine Graphen- Datenstruktur überführt. Dieser Graph wird dann basierend auf rekursiver Partitionierung stufenweise weiter abstrahiert, indem zusammenhängende Knoten des Graphen vereinigt werden und somit die Anzahl der Knoten effektiv verringert wird. Dadurch ist eine Weg- findung auf einer hierarchisch höheren Ebenen mit weitaus weniger zu beachtenden Knoten möglich. Diese Vorgehensweise lässt den Algorithmus in großen 3D-Welten schneller einen Weg finden als der herkömmliche A*-Algorithmus.
Evaluierung und Implementierung eines Wegfindungsalgorithmus in einer voxelbasierten 3D-Welt
Das NavMesh wird auf die erste hierarchische Ebene abstrahiert. Hierbei werden z.B. drei benachbarte Regionen zusammengefasst. Wie viele Regionen zusammengefasst werden, lässt sich einstellen.
This thesis is about the evaluation of an efficient path finding algorithm in a voxel-based 3D world. The implementation is also shown in a sample project. Voxel-based 3D worlds tend to be very CPU and memory intensive, which is why it is important to find a resource efficient algorithm. The requirements for this algorithm are on the one hand to find a plausible way in a large 3D world and on the other hand to guarantee short computing times. The algorithm uses a 3D engine including a Voxel plugin and NavMesh calculation as a basis. It can access the existing data structures and process them further. The vertices and edges of the navigation mesh are converted into a graph data structure. The graph is then further abstracted based on recursive partitioning by merging connected nodes. Thus the number of nodes is effectively reduced. This allows path finding at a hierarchically higher level with far fewer nodes to consider. This way the algorithm finds a path faster than the conventional A* algorithm in large 3D worlds.