H.urna - Use senses to learn sciences

H.urna is currently under reconstruction. Thank you for your patience.

  1. Academy
  2. Computer Science
  3. Algorithms
  4. Pathfinders

Quick Access

Breadth First Search - BFS Maze Pathfinder Breadth First Search (BFS)

Depth First Search - DFS Maze Pathfinder Depth First Search (DFS)

Dijkstra - Maze Pathfinder Dijkstra

A* (A-Star) - Maze Pathfinder A* (A-Star)

Introduction

What’s the shortest drive from our place to the nearest park?
How do we find a way through a maze?
Can we program a game character to find the exit avoiding enemies?

Pathfinding algorithms address the problem of finding a path from a source to a destination avoiding obstacles and minimizing the costs (time, distance, risks, fuel, price, etc.). This is a common programming challenge. Mainly known from navigation and games, we will find that the core algorithms apply to a huge range of problems.

For a brief introduction about mazes and why we enjoy them so much, please refer to 'Introduction to Maze Generators'.

Objectives

We will first study Breadth First Search and Depth First Search because they are fundamental for traversing a graph (or a tree) and are often a required first step for many other types of analysis. We will then cover more advanced algorithms such as Dijkstra or A* (A-Star).


What is next?

At the end, most developers doing any serious data/graph manipulation end up writing their own custom algorithms, although highly based on those known solutions. We may, then, write our own pathfinders using for instance H.urna Core C++ as a start ready project.

Understanding the data

The first thing to do when studying an algorithm is to understand the data.
What is the input? What is the output?
Here is the kind of board we will play with.
Maze board 20x10 - Kruskal Generator

How is the data structured?
Here is a labyrinth with a few more details.
Labyrinth 5x5 - Grid and node informations

In this grid, each box represents a node. A connection between two nodes is represented by a path between two boxes. This information is also displayed textually (top left box in the image). Here, our mouse is on the first node (0,0) and displays connections with the nodes (0,1) and (1,0).

We choose to describe our grid (or graph) using an adjacency lists data structure. The idea is pretty simple : an array of nodes with node storing the list of their neighbors. Easy to create, easy to manipulate, here is how the data could be represented in JSON : 

[
  {
    "x":0, "y":0,
    "neighbors":[1,5]
  }, {
    "x":0, "y":1,
    "neighbors":[0,2]
  }, {
    "x":0, "y":2,
    "neighbors":[1,3,7]
  }
  ...
]

The node id is given by its array index, this id is used to refer to the neighbors.
Yes, it’s that simple! It includes all the information we need to go through and to visualize the maze.

What is the output?

The most basic output that could be expected is the path found between two nodes. To represent this, an ordered (by step order) array is quite sufficient: 

[0, 3, 19, 9, ...]

Starting from the node 0, we go to node 3, then to node 19 etc. until the goal.

Perfect, we know everything to build our pathfinders!
Note: A grid can use a non-grid pathfinding graph, or vice versa.
Here, grids are used for explanations as it is easier to understand, work and visualize.

Overview

Provides a pretty good summary of the basic pathfinding algorithms.

Breadth First Search

Breadth First Search explores equally in all directions.

This is an incredibly useful algorithm, not only for regular traversal, but also for procedural map generation, flow field pathfinding, distance maps, and other types of map analysis.

This may be the algorithm of choice to identify nearby places of interest in GPS.

BFS guarantees the shortest path.

Depth First Search

Traverses by exploring as far as possible down each path before backtracking.

As useful as the BFS: DFS can be used to generate a topological ordering, to generate mazes, to traverse trees, to build decision trees, to discover a solution path with hierarchical choices...

DFS does not guarantee the shortest path.

Dijkstra

Dijkstra’s Algorithm lets us prioritize which paths to explore. Instead of exploring all possible paths equally, it favors lower cost paths.

We can assign lower cost to encourage moving on roads while assigning high cost on highway to avoid them.

It is the algorithm of choice for finding the shortest path paths with multiple destinations.

A* (A-Star)

A* is a modification of Dijkstra’s Algorithm that is optimized for a single destination.

Dijkstra’s Algorithm can find paths to all locations; A* finds paths to one location. It prioritizes paths that seem to be leading closer to a goal.

In a game, we could set costs to be attracted or discouraged in going near some objects : how useful it is for an AI.

It is more or less the golden ticket or industry standard algorithm for all applications finding directions between two locations.
To better understand the differences between these algorithms and their operations, use H.urna Explorer : our interactive platform, which will allow you to manipulate and compare them.

References