Pathfinding Sample

This sample demonstrates how AIs can use algorithms to navigate a map using waypoints.

Sample Overview

To create realistic enemy movement AI, implementing Pathfinding algorithms becomes necessary. The goal of pathfinding is to explore possible routes to get from one point, or node, to another, often with the goal of finding the quickest route. To get started, this sample demonstrates three common pathfinding algorithms: Breadth-First, Best-First and A* (A-Star). To illustrate the logic behind these algorithms, the searched nodes are represented as red dots, while the nodes available to search are represented as green dots. Once the algorithm has found the end, the tank travels the path to its destination.

This sample uses the following controls.

Action Windows Phone Windows - Keyboard Control Windows/Xbox - Gamepad Control
Start the pathfinding algorithm TAP "Start/Stop" button A A
Reset the map TAP "Reset" button B B
Switch the map TAP "Next Map" button Y Y
Switch the pathfinding algorithm TAP "Pathfinding Mode:" button X X
Change the time step DRAG "Time Step" slider LEFT ARROW, RIGHT ARROW D-Pad LEFT, D-Pad RIGHT
Exit the game. BACK ESC or ALT+F4 BACK

How the Sample Works

 

Pathfinding Behavior

All of the pathfinding algorithms below rely on searching a graph of nodes, named waypoints for the purposes of our sample, to get from a start point to a goal. The algorithms described below can be useful in different situations, and so it is important to understand the way in which your algorithm will be used. Adding cost to your nodes is a prime example. For instance, if you had a game where traveling over mountains resulted in a slower movement speed than traveling over a plain, the cost of a particular mountain node might be 5, where a plain node would be 1. This will allow certain pathfinding algorithms to determine whether it is more efficient to over the mountain or around it. A brief description of each of the supplied algorithms is listed below:

 

Breadth-First

The Breadth-First algorithm uses a graph search that explores all nodes neighboring a given root node. It then searches the neighbors of the neighbors and continues in this manner until the goal has been found or all available neighbors from the root have been searched. This algorithm is useful if you want to exhaustively search the map for every possible path, but also results in the slowest implementation.

Best-First

The Best-First algorithm searches through the node graph in an attempt to find the shortest distance to the goal. This algorithm will always find the shortest distance to the goal, but does not take the cost into account. Best-First is best used in scenarios where nodes have a uniform cost.

A*

A* pathfinding combines a Best-First search with a heuristic, or educated guess, that searches for the lowest cost route. A* will always return the route with the lowest cost to the goal. This algorithm is most useful where nodes have varying costs associated with them.

Extending the Sample