Gamegrid

Weg im Labyrinth suchen: Backtracking als Lösungsstrategie

Backtracking bezeichnet eine Problemlösungsmethode, die versucht mit dem Prinzip "trial and error" eine erreichte Teillösung schrittweise zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zur Lösung führen kann, wird der letzte Schritt beziehungsweise die letzten Schritte rückgängig gemacht und alternative Wege probiert.

Genau diese Strategie verwendet auch unser Käfer beim Wegsuchen im Labyrinth. Er startet oben links. In jedem Schritt prüft er, in welcher Richtung (up, left, down, right) man weitergehen kann. Dann nimmt er die erste mögliche Richtung, verschiebt sich um eine Zelle weiter und markiert die Zelle mit einer Zahl. Trifft der Käfer auf eine Sackgasse, so dreht er um, kehrt zur letzten Wegkreuzung zurück und markiert unterwegs diese Felder mit einem roten Kreuz. Dann wiederholt er das Vorgehen von Neuem (Rekursion), wobei die rot markierten Zellen nicht mehr erlaubt sind.

Das Prinzip nennt sich Tiefensuche: Wir gehen möglichst tief in das Labyrinth hinein, erst wenn wir dabei auf eine Sackgasse stossen, gehen wir zurück und versuchen es von dort aus erneut.

Programmcode downloaden (GGLabyrinth.zip)

Programmcode

// 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));
  }
}

Erklärungen zum Programmcode:

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);	Versucht in allen Richtungen weiter zu kommen
if (visitedLocations.contains(exitLocation) \|\| visitedLocations.contains(loc)) return;	Falls eine Zelle bereits besucht wurde kehrt er zurück
Monitor.putSleep()	Der Käfer muss nach jedem Schritt warten, bis er durch die Methode act() geweckt wird