Introduction

          Using Unreal Engine with C++ and Blueprints,  me and one other created a pathfinding algorithm. In the scene, there is one steering actor that follows given points using seek. Each of these points are determined based on an orange cursor that the player can control. The player can also control if they are using the Djikstra and A* algorithms, if they want re-randomize the maze, toggle if it uses path smoothing or not, and also if they want to spawn more than one steering actor.

Implementation

          Whenever the player moves, the steering calculates the new path that needs to be taken. Whenever the steering actor reaches the target point (which is always the first point in the array), it will be removed from the array and the steering actor will move on to the next point.

GridGeneration.PNG

Code sample from the grid generation

          For the actual implementation of A*, we created a grid, where each point was separated by around 100 centimeters. In the editor, the developer can actually control how large the grid is and the separation between each point. So when the path is being called to generate, the steering actor goes point by point, trying to find the best value from each point to get to the end point. For the best index calculation, in Djikstra, we just found the point that is the closest to the end point and picked that however for A*, we used a heuristic equation to find the best index. This equation was just simply taking the difference between the grid coordinates of the current location and the end point.  

FindPath.PNG

Code sample from the finding the actual path

Heuristic.PNG

Code sample from the finding the best index

CalculateHeuristic.PNG

Code sample from the calculating the heuristic for A*