Wavefront Algorithm Simulator

  Uncategorized

Introduction

Introduction

Pathfinding algorithms find a path from point S (start) to point G (goal). The performance of such algorithms depend on the number of iterations in their core loop until a path is found. There are two popular pathfinding algorithms out there, the „Wavefront“ and the „A*“ (A Star) algorithm. It is my impression that the wavefront algorithm is a bit simpler to understand, whereas the A* algorithm potentially requires fewer iterations. Comparisons between both algorithm can be found in the internet.

This article is about the Wavefront algorithm. It not only describes its principles but also provides a Java Swing demo application which visualizes the progress of a running Wavefront implementation. Lets start with a simple grid. As you can see, we’ve four different markers:

S = Start
G = Goal
0 = free
1 = wall/obstacle

In order to limit the algorithm to the boundary of the grid we put a wall around the grid:

1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 S 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 G 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1

The outer iteration loop of the algorith runs until a path from S to G has been found or no new progression has been made, which means there is no path possible between S and G. The middle iteration loops through the grid either horizontally (row) or vertically (column), and the inner loop will scan through the cells in either the current row or column respectively.

The algorithm is based on the neighborhood connectivity (adjacency) of cells. See the explanation from http://www.cs.tufts.edu/comp/150IR/labs/wavefront.html:

Neighborhood connectivity

There are two ways to connect the cells in a square grid like the one above.
The von Neumann neighborhood of a cell C consists of its 4 neighbors adjacent to the sides of the cell square:

   1
4 C 2
   3
There are therefore 4 possible moves out of C, and C has 4 children in the graph induced by the von Neumann connectivity.

The Moore neighborhood of a cell C consists of its 8 neighbors adjacent to both the faces and the corners of the cell square:

8 1 2
7 C 3
6 5 4
There are therefore 8 possible moves out of C (including 4 diagnoal moves) and C has 8 children in the graph induced by the Moore connectivity.

LEAVE A COMMENT