This project represents my exploration of pathfinding solutions within a 3D environment, specifically Minecraft. The objective was to efficiently discover short paths across extensive areas. This endeavor holds versatile applications, including facilitating navigation in RPG adventure maps, enhancing mob AI, improving transportation, and streamlining automated base planning and construction.
The project involved researching various pathfinding solutions, with a focus on two implementations. The first solution employs the A* (A-star) algorithm, which efficiently finds the shortest path by considering both the actual cost of reaching a point and a heuristic estimate of the remaining cost to the destination. The second solution adopts a greedy algorithm, which provides a suboptimal path in less time. A time comparison between the two (shown below) revealed that A* is not suitable due to its speed limitations.
A* algorithm (top) takes 2027ms to find the shortest path while Greedy algorithm (bottom) takes 90ms to find a slightly suboptimal solution. A* takes too long to be useful, so greedy implementation is used.
To enhance the greedy algorithm's shortcomings, a post-processing step was introduced, allowing manual adjustments to the path after its initial discovery. This project showcases my commitment to optimizing pathfinding in complex 3D environments, addressing a range of real-world applications.
This project represents my exploration of pathfinding solutions within a 3D environment, specifically Minecraft. The objective was to efficiently discover short paths across extensive areas. This endeavor holds versatile applications, including facilitating navigation in RPG adventure maps, enhancing mob AI, improving transportation, and streamlining automated base planning and construction.
The project involved researching various pathfinding solutions, with a focus on two implementations. The first solution employs the A* (A-star) algorithm, which efficiently finds the shortest path by considering both the actual cost of reaching a point and a heuristic estimate of the remaining cost to the destination. The second solution adopts a greedy algorithm, which provides a suboptimal path in less time. A time comparison between the two revealed that A* is not suitable due to its speed limitations.
To enhance the greedy algorithm's shortcomings, a post-processing step was introduced, allowing manual adjustments to the path after its initial discovery. This project showcases my commitment to optimizing pathfinding in complex 3D environments, addressing a range of real-world applications.
A* algorithm (left) takes 2027ms to find the shortest path while Greedy algorithm (right) takes 90ms to find a slightly suboptimal solution. A* takes too long to be useful, so greedy implementation is used.
Path post-processing optimizes length if a shorter route is found