Labyrinth mittel FloodFill ~ Silberblatt

vendredi 22 mai 2015

Labyrinth mittel FloodFill

Posted on 06:49 by verona

Hallo zusammen,

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

Java Code:

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() {
}
}

Die searchForKnight-Methode kann erstmal weggelassen werden.
Bis jetzt habe ich leider nur Methode à la

Java Code:

private void floodFill(Point point, Random random) {
for(int i = 0; i < 50; i++){
map[random.nextInt(14)][random.nextInt(14)] = true;
}
}

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 Code:

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

Wie kann ich den FloodFill Algorithmus zur Labyrintherzeugzung implementieren?

Angehängte Dateien

Labyrinth-Erzeugung mittels FloodFill.pdf (514,0 KB)

Labyrinth mittel FloodFill

Categories: Labyrinth mittel FloodFill

Silberblatt

vendredi 22 mai 2015

Labyrinth mittel FloodFill

0 commentaires:

Enregistrer un commentaire

Popular Posts

Blogger templates

Blog Archive

Blogger news

Categories

Blogroll

About