Labyrinth mittel FloodFill

[Lukases2]

Hallo zusammen,

ich möchte ein Labyrinth mittels des FloodFill - Algorithmus implementieren (siehe Anhang). Dazu habe ich diese Klasse gegeben:

[JAVA]import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.awt.Point;

public class Labyrinth {
// Größe der Karte. Die Karte ist quadratisch
private int size;
// Karte. true = Feld begehbar, false = Feld blockiert
private boolean[][] map;
// initiale Position der Prinzessin
private Point startingPoint;
// Position des Prinzen
private Point destinationPoint;
// aktuelle Position der Prinzessin
private Point currentPosition;

// Richtungen, als int kodiert
private static final int kDirUp = 0;
private static final int kDirDown = 1;
private static final int kDirRight = 2;
private static final int kDirLeft = 3;
// erste und letzte Richtung (um Richtungen in Schleifen zu durchlaufen
// etc.)
private static final int kDirFirst = 0;
private static final int kDirLast = 3;

// Interface um die GUI über Updates zu informieren
public interface Listener {
// aktuelle des Position der Prinzessin (= die Position, die von
// getCurrentPosition() zurückgegeben wird) hat sich geändert
void princessUpdated();
};

private List<Listener> listeners = new ArrayList<Listener>();

Labyrinth(int size) {
this.size = size;

Random random = new Random();

map = new boolean[size][size];
floodFill(new Point(size / 2, size / 2), random);

// finde freie Start- und Zielkoordinaten
List<Point> free = new ArrayList<Point>();
for (int x = 0; x < size; x++)
for (int y = 0; y < size; y++)
if (map[x][y])
free.add(new Point(x, y));

if (free.size() == 0)
throw new RuntimeException(
"There are not free fields in the labyrinth");

startingPoint = free.get(random.nextInt(free.size()));
destinationPoint = free.get(random.nextInt(free.size()));
currentPosition = startingPoint;
}

// wird vom GUI Code benutzt, um einen Listener zu installieren
public void addListener(Listener listener) {
listeners.add(listener);
}

public int getMapSize() {
return size;
}

public Point getStartingPoint() {
return startingPoint;
}

public Point getDestinationPoint() {
return destinationPoint;
}

public Point getCurrentPosition() {
return currentPosition;
}

public boolean tileIsBlocked(int x, int y) {
return !map[x][y];
}

// ruft alle Listener auf. Sollte nach jedem Update von
// currentPosition aufgerufen werden.
private void princessUpdated() {
for (Listener listener : listeners)
listener.princessUpdated();
}

// berechnet zu einem gegebenen Punkt den nächsten Punkt in
// einer bestimmten Richtung. Überprüft NICHT, ob der
// Ergebnispunkt auch wirklich auf der Karte liegt!
private Point addDir(Point p, int direction) {
switch (direction) {
case kDirUp:
return new Point(p.x, p.y - 1);
case kDirDown:
return new Point(p.x, p.y + 1);
case kDirRight:
return new Point(p.x + 1, p.y);
case kDirLeft:
return new Point(p.x - 1, p.y);
default:
throw new IllegalArgumentException("Illegal direction");
}
}

// testet, ob der gegebene Punkt auf der Karte liegt
// (testet NICHT dessen Begehbarkeit!)
private boolean onMap(Point p) {
return p.x >= 0 && p.x < size && p.y >= 0 && p.y < size;
}

private void floodFill(Point point, Random random) {

}

public void searchForKnight() {

}
}[/code]

Die searchForKnight-Methode kann erstmal weggelassen werden.
Bis jetzt habe ich leider nur Methode à la
[JAVA]private void floodFill(Point point, Random random) {
for(int i = 0; i < 50; i++){
map[random.nextInt(14)][random.nextInt(14)] = true;
}
}[/code]
oder ähnliches geschafft. "map[x][y] = true" bedeutet hier immer, dass hier ein freies Feld ist, false bedeutet, dass hier nicht gegangen werde kann. Auch schon aufwendigere Methoden, die ein Labyrinth mit verbunden Gängen erzeugt hat, sind mit gelungen. Aber nichts davon hatte was mit FloodFill oder einem vernünftigen Labyrinth zu tun.

Gegen ist zudem noch eine GUI:
[JAVA]package b5P;


// Autoren: Ulrich, Zur, van der Grinten, Lückerath

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.FlowLayout;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.Point;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class GUI {
private Labyrinth labyrinth;

private JFrame frame = new JFrame();
private JPanel panelMain = new JPanel();
private JPanel panelNorth = new JPanel();
private JButton btnStart = new JButton();
private Display display = new Display();

private Image imgPrince;
private Image imgPrincess;
private Image imgCensored;
private BufferedImage imgGrass;
private BufferedImage imgRock;

public GUI() {
labyrinth = new Labyrinth(15);
labyrinth.addListener(new Labyrinth.Listener() {
@Override public void princessUpdated() {
frame.repaint();

// damit man die Bewegung sehen kann
try{
Thread.sleep(500);
} catch(InterruptedException e) { }
}
});

// initialisiere alle Swing-Komponenten
btnStart.setText("Lösen!");
btnStart.addActionListener(new ActionListener() {
@Override public void actionPerformed(ActionEvent e) {
// müssen das Labyrinth in einem anderen Thread lösen,
// damit die GUI Anwendung reaktionsfähig bleibt.
Runnable runnable = new Runnable() {
@Override public void run() {
labyrinth.searchForKnight();
btnStart.setEnabled(true);
}
};

btnStart.setEnabled(false);
new Thread(runnable).start();
}
});

panelNorth.setLayout(new FlowLayout(FlowLayout.CENTER));
panelNorth.add(btnStart);

panelMain.setLayout(new BorderLayout());
panelMain.add(panelNorth, BorderLayout.NORTH);
panelMain.add(display, BorderLayout.CENTER);

// lade Bilder und skaliere auf richtige Größe
try{
imgGrass = ImageIO.read(new File("./res/grass.jpg"));
imgRock = ImageIO.read(new File("./res/rock.jpg"));

imgPrince = ImageIO.read(new File("./res/prince.png"))
.getScaledInstance(60, 60, Image.SCALE_FAST);
imgPrincess = ImageIO.read(new File("./res/princess.png"))
.getScaledInstance(60, 60, Image.SCALE_FAST);

imgCensored = ImageIO.read(new File("./res/censored.png"))
.getScaledInstance(80, 60, Image.SCALE_FAST);
}catch(IOException e){
throw new RuntimeException("Could not load image", e);
};

// zeige das Fenster an
frame.setSize(600, 665);
frame.setResizable(false);
frame.setTitle("Save the prince!");
frame.setContentPane(panelMain);
frame.setVisible(true);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}

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

// unser Zeichenbereich
class Display extends JPanel {
@Override public void paintComponent(Graphics g) {
super.paintComponent(g);

int height = this.getHeight();
int width = this.getWidth();

// fülle Hintergrund
g.setColor(Color.white);
g.fillRect(0, 0, width, height);

for(int y = 0; y < labyrinth.getMapSize(); y++){
for(int x = 0; x < labyrinth.getMapSize(); x++){
// zeichne Feld
if(labyrinth.tileIsBlocked(x, y)) {
g.drawImage(imgRock, x * 40, y * 40, null);
}else{
g.drawImage(imgGrass, x * 40, y * 40, null);
}

// zeichne Rahmen um die Grafik
g.setColor(Color.BLACK);
g.drawRect(x * 40, y * 40, 40, 40);
}

// zeichne Prinz und Prinzessin
g.drawImage(imgPrince, labyrinth.getDestinationPoint().x * 40 - 13,
labyrinth.getDestinationPoint().y * 40 - 10, null);
g.drawImage(imgPrincess, labyrinth.getCurrentPosition().x * 40 - 8,
labyrinth.getCurrentPosition().y * 40 - 8, null);
}

// wird eine Lösung gefunden ... naja
if(labyrinth.getCurrentPosition().x == labyrinth.getDestinationPoint().x
&& labyrinth.getCurrentPosition().y == labyrinth.getDestinationPoint().y)
g.drawImage(imgCensored, labyrinth.getCurrentPosition().x * 40 - 20,
labyrinth.getCurrentPosition().y * 40 - 10, null);
}
}
}

[/code]

Wie kann ich den FloodFill Algorithmus zur Labyrintherzeugzung implementieren?

 

[TheWhiteShadow]

ich denke, die Kommentare im Code sind Selbsterklärend. Ansonten einfach nochmal nachfragen.

public class Labyrinth
{
	public static final int SOLID = 0;
	public static final int EMPTY = 1;
	
	private int width;
	private int height;
	private int[][] map;

	public Labyrinth(int width, int height)
	{
		// Das Labyrinth muss eine ungrade Anzahl an Feldern besitzen
		this.width = (width % 2 == 1) ? width : width+1;
		this.height = (height % 2 == 1) ? height : height+1;
		this.map = new int[this.width][this.height];
		
		floodFill();
	}
	
	private void floodFill()
	{
		Random rnd = new Random();
		List<Integer> dirList = new ArrayList<Integer>();
		// Fülle Richtungen nach Schema der Zehnertasten.
		dirList.add(2); // Unten
		dirList.add(4); // Links
		dirList.add(6); // Rechts
		dirList.add(8); // Oben
		// Beginne irgendwo im Labyrinth mit einem Vielfachen von 2 Feldern zu jeder Seite.
		fillTile(rnd.nextInt(width/2)*2+1, rnd.nextInt(height/2)*2+1, dirList);
	}
	
	private void fillTile(int x, int y, List<Integer> dirList)
	{
		// zufällige Reihenfolge der zu suchenden Richtungen
		Collections.shuffle(dirList);
		// Richtungsvariablen.
		int dx, dy;
		for(Integer i : dirList)
		{
			switch(i)
			{
				// Zerlege die Richtung in X/Y-Richtungs-Vektoren.
				case 2: dx = -1; dy =  0; break;
				case 4: dx = +1; dy =  0; break;
				case 6: dx =  0; dy = -1; break;
				case 8: dx =  0; dy = +1; break;
				default: throw new IllegalArgumentException("Unbekannte Richtung!");
			}
			
			// Prüfe immer zwei Felder weit
			if (isSolid(x+2*dx, y+2*dy))
			{
				// Öffne beide Felder.
				set(x+dx, y+dy, EMPTY);
				set(x+2*dx, y+2*dy, EMPTY);
				// Rekursion
				fillTile(x+2*dx, y+2*dy, dirList);
				// Weiter machen, falls wir irgendwann auf eine Sackgasse stoßen.
				continue;
			}
		}
	}
	
	private void set(int x, int y, int state)
	{
		this.map[x][y] = state;
	}
	
	public int get(int x, int y)
	{
		return this.map[x][y];
	}
	
	public boolean isSolid(int x, int y)
	{
		if (x < 0 || x >= width || y < 0 || y >= height) return false;
		return map[x][y] == SOLID;
	}
	
	public boolean isPassable(int x, int y)
	{
		if (x < 0 || x >= width || y < 0 || y >= height) return false;
		return map[x][y] == EMPTY;
	}

	public int getWidth()
	{
		return width;
	}

	public int getHeight()
	{
		return height;
	}
}