Path Planner

During this project I worked to understand the various ways an artificially intelligent enemy would find their way to the player in a game. I implemented various searching algorithms to achieve my result. Each search takes advantage of a node system in which each node may have a child node in any of its 6 sides. This was made my challenging by having the nodes note be directly next to each other. They are offset. Each search test also has a set of impassible nodes shown in the dark grey color. The algorithm cannot pass through these tiles as a character could not pass through a wall during gameplay. Each tile is also assigned a weight used to calculate the best route.

Breadth-First Search

A generalization of the tree traversal method.

Greedy (Best-first) Search

While the breadth-first search algorithm will find the solution path with the least number of planner nodes, it may create an extremely large number of them before it finds the solution. Greedy search orders it’s nodes so that the ones closest to the goal are the nearest to the front of the open list using an open queue. This algorithm is informed because it’s ordering s based on goal information. While this can be extremely fast it’s not an optimal search because while it is effective in certain environments, it is highly dependant on the search space.

Uniform-Cost Search

This is a variant of Dijkstra’s algorithm which handles different tile weights by incorporating them into each planner node’s given cost which the algorithms them uses to order its open nodes.

A* Search

This algorithm incorporates the look-ahead abilities of the greedy search algorithm with the look-behind abilities of the uniform-cost search algorithm by taking into account both the heuristic cost and the given cost of each planner node. When the heuristic used is admissible, A* solution paths are always optimal.