Fast path finding algorithm for dynamic environments.
This algorithm is based on an ocrtree structure combined with an A star path algotithm. It is designed to quickly find a path through a 3d point cloud.
- Debug/ConsoleApplicationTree.exe is the working winows application
- ConsoleApplicationTree/ConsoleApplicationTree.cpp is the main source code file
- ConsoleApplicationTree/Window.cpp is the code for displaying graphics
It is a Visual studio project written in C++
SDL library is already included in externals folder
Tutorial of how to add SDL lib to vs project can be found here https://www.wikihow.com/Set-Up-SDL-with-Visual-Studio-2017 (from part 4)
SDL is used for visualization purposes. By default program is set to solve a task of finding a path in a 3d cube-like environment. X and Y coordinates of the start point can be set dynamically by aiming cursor on a preferable spot and pressing "s" button. Z coordinate is fixed on the upper edge of the the cube and the goal point is set to the top right corner on the bottom edge of the cube. By pressing "a" you add 300 random obtacle points in the center part of the cube. To add single point in a specific spot press "o", default z will be set to 10
Class "manager" recieves 1 integer (depth, default 6) that means how many times you can divide the environment in half, increasing the accuracy of its construction. Class "AStar" receives the root node, minimum precision of search (integer = depth) and maximum precision of search (integer from 1 to depth)
Resulting path is saved to pathset array in AStar class.
2D version
In order to use algorithm in 2D spaces, replace ConsoleApplicationTree/ConsoleApplicationTree.cpp file with ConsoleApplicationTree2D.cpp file from the root directory
Blue dots are path vectors, right crosses show occupied space, green crosses show free space.
2D variant representation, depth = 4
2D variant representation, depth = 6
