Finding the way through a labyrinth: backtracking as a solving strategy

Backtracking is a problem solving strategy which works with the method "trial and error". A partially detected solution is completed step by step until the final solution is found. As soon as it is clear a partial solution does not lead to the final solution we go back one or several steps and try a new or alternative way.

This strategy is used in this example by the bug to find its way through the labyrinth. Its starts in the top left corner and after each step it checks if it can advance to the left, to the right, up or down. If one of these directions is possible, the bug move accoringly and marks the cell with a number. If it reaches a dead end, it moves back to the last cross-way marking each cell with a red cross. At the cross-way the bug checks each possible direction anew (recursion) - not taking the red-crossed way into account - and starts moving again.

This method is called depth-first search: the bug moves into the labyrinth as deep as possible only turning around and trying a new way after hitting a dead end.

Run this example

Edit this example in the Online-Editor

Download the program code (GGLabyrinth.zip)

Program code

// GGLabyrinth.java

import ch.aplu.jgamegrid.*;
import java.util.*;
import java.awt.*;
import ch.aplu.util.*;

public class GGLabyrinth extends GameGrid
{
  private static final int nbHorzCells = 31; // must be odd
  private static final int nbVertCells = 31; // ditto
  private static final int cellSize = 18;

  public GGLabyrinth()
  {
    super(nbHorzCells, nbVertCells, cellSize);
    setSimulationPeriod(100);
    GGMaze maze = drawMaze(this);
    Bug sbug = new Bug(this);
    addActor(sbug, maze.getStartLocation());
    show();
    doRun();
    sbug.startSearch();
  }

  private GGMaze drawMaze(GameGrid gg)
  {
    GGBackground bg = getBg();
    GGMaze maze = new GGMaze(nbHorzCells, nbVertCells);
    for (int x = 0; x < nbHorzCells; x++)
      for (int y = 0; y < nbVertCells; y++)
      {
        Location location = new Location(x, y);
        if (maze.isWall(location))
          bg.fillCell(location, Color.black);
        else
          bg.fillCell(location, Color.white);
      }
    return maze;
  }

  public static void main(String[] args)
  {
    new GGLabyrinth();
  }
}

// ------ class Bug ---------------------

class Bug extends Actor
{
  private final Location startLocation = new Location(0, 1);
  private final Location exitLocation;
  private ArrayList<Location> visitedLocations;
  private Location previousLoc = startLocation;
  private GameGrid gg;

  public Bug(GameGrid gg)
  {
    super(true, "sprites/smallbug.gif"); // Rotatable
    exitLocation = new Location(gg.getNbHorzCells() - 1, gg.getNbVertCells() - 2);
    visitedLocations = new ArrayList<Location>();
    this.gg = gg;
  }

  public void startSearch()
  {
    TextActor distMark = new TextActor("");
    gg.addActor(distMark, new Location(0, 0));
    gg.setPaintOrder(Bug.class, TextActor.class);
    searchPath(startLocation, 0);
  }

  public void act()
  {
    Monitor.wakeUp();
  }

  private void searchPath(Location loc, int dist)
  {
    Monitor.putSleep();
    if (visitedLocations.contains(exitLocation)
      || visitedLocations.contains(loc))
      return;
    else
    {
      visitedLocations.add(loc);
      setLocationFacing(loc);
      if (loc.equals(exitLocation))
        return;
      else
      {
        // set number on current location
        TextActor distMark = new TextActor("" + dist);
        distMark.setLocationOffset(new Point(-7, 0));
        gg.addActorNoRefresh(distMark, loc);

        // find next location (rekursiv)
        if (canMove(new Location(loc.x, loc.y - 1))) // up
          searchPath(new Location(loc.x, loc.y - 1), dist + 1);
        if (canMove(new Location(loc.x - 1, loc.y))) // left
          searchPath(new Location(loc.x - 1, loc.y), dist + 1);
        if (canMove(new Location(loc.x, loc.y + 1))) // down
          searchPath(new Location(loc.x, loc.y + 1), dist + 1);
        if (canMove(new Location(loc.x + 1, loc.y))) // right
          searchPath(new Location(loc.x + 1, loc.y), dist + 1);

        // if this way not posible, set red X
        if (!visitedLocations.contains(exitLocation))
        {
          gg.removeActorsAt(loc, TextActor.class); //delete number
          TextActor wrongMark = new TextActor("x", Color.red,
            Color.white, new Font("SansSerif", Font.PLAIN, 12));
          distMark.setLocationOffset(new Point(-8, 0));
          gg.addActorNoRefresh(wrongMark, loc);
          setLocationFacing(loc);
        }
      }
    }
  }

  private void setLocationFacing(Location loc)
  {
    setDirection(previousLoc.getCompassDirectionTo(loc));
    previousLoc = loc;
    setLocation(loc);
  }

  private boolean canMove(Location location)
  {
    Color c = getBackground().getColor(location);
    return (!c.equals(Color.black));
  }
}

GameGrid: Game programming with Java	Deutsch
Research project PHBern

GameGrid: Game programming with Java

Finding the way through a labyrinth: backtracking as a solving strategy