package astern.algo;
import java.util.ArrayList;
public class AsternAlgo {
private final int MAX_X = 9;
private final int MAX_Y = 9;
private Feld[][] field;
ArrayList<Feld> openList = new ArrayList<Feld>();
ArrayList<Feld> closedList = new ArrayList<Feld>();
public AsternAlgo() {
this.field = new Feld[MAX_X + 1][MAX_Y + 1];
init();
}
private void init() {
// Felder initialisieren
for (int i = 0; i <= MAX_X; i++) {
for (int j = 0; j <= MAX_Y; j++) {
field[i][j] = new Feld();
}
}
// Außenseiten des Feldes nicht passierbar machen
for (int i = 0; i <= MAX_Y; i++) {
this.field[0][i].setFrei(false);
this.field[9][i].setFrei(false);
this.field[i][0].setFrei(false);
this.field[i][9].setFrei(false);
}
// Inneren Felder passierbar machen
for (int i = 1; i < MAX_X; i++) {
for (int j = 1; j < MAX_Y; j++) {
field[i][j].setFrei(true);
}
}
// Mauern in das Feld setzten
this.field[1][2].setFrei(false);
this.field[1][3].setFrei(false);
this.field[1][4].setFrei(false);
this.field[2][4].setFrei(false);
this.field[3][1].setFrei(false);
this.field[3][2].setFrei(false);
this.field[3][4].setFrei(false);
this.field[4][4].setFrei(false);
this.field[4][6].setFrei(false);
this.field[4][7].setFrei(false);
this.field[5][2].setFrei(false);
this.field[5][3].setFrei(false);
this.field[5][4].setFrei(false);
this.field[5][6].setFrei(false);
this.field[6][4].setFrei(false);
this.field[6][6].setFrei(false);
this.field[6][8].setFrei(false);
this.field[7][6].setFrei(false);
this.field[8][6].setFrei(false);
}
public static void main(String[] args) {
// Neues Objekt erzeugen
AsternAlgo stern = new AsternAlgo();
// Zeichnen des Feldes, damit man sich ein Bild von dem Bild machen kann
stern.draw();
// Algo aufrufen um den Weg zu finden.
stern.algo(1, 1, 8, 8);
}
private void algo(int xStart, int yStart, int xEnde, int yEnde) {
Feld aktuellerPunkt, min;
int xSpeicher, ySpeicher;
/*
* 1) Füge den Startpunkt der offenen Liste hinzu.
*/
this.field[xStart][yStart].setKoordinaten(xStart, yStart);
openList.add(this.field[xStart][yStart]);
/*
* 2) Wiederhole das Folgende: a) Suche in der offenen Liste nach dem
* Punkt mit dem niedrigsten F-Wert (falls gleicher F-Wert, niedrigster
* H-Wert). Wir bezeichnen diesen Punkt im Folgenden als das aktueller
* Punkt.
*/
do {
min = openList.get(0);
for (int i = 1; i < openList.size(); i++) {
if (min.getFWert() > openList.get(i).getFWert()) {
min = openList.get(i);
}
if (min.getFWert() == openList.get(i).getFWert()) {
if (min.getHWert() > openList.get(i).getHWert()) {
min = openList.get(i);
}
}
}
aktuellerPunkt = min;
/*
* b) Speicher dir den Punkt und verschiebe ihn in die geschlossene
* Liste.
*/
closedList.add(aktuellerPunkt);
openList.remove(aktuellerPunkt);
nachbarnBearbeiten(aktuellerPunkt.getKoordinaten()[0],
aktuellerPunkt.getKoordinaten()[1], aktuellerPunkt, xEnde, yEnde);
/*
* Den aktuellen Punkt ausgeben, damit man den "verlauf" verfolgen
* kann System.out.println("OpenList is empty: " +
* openList.isEmpty()); System.out.println("x: " +
* aktuellerPunkt.getKoordinaten()[0]); System.out.println("y: " +
* aktuellerPunkt.getKoordinaten()[1]);
*/
// Solange wiederholen wie der aktuellePunkt nicht der Endpunkt ist.
// DURCH !openList.isEmpty() bricht er ab, wenn alle Felder getestest wurden
} while (aktuellerPunkt.getKoordinaten()[0] != xEnde
|| aktuellerPunkt.getKoordinaten()[1] != yEnde
&& !openList.isEmpty());
System.out.println("Ende gefunden: " + aktuellerPunkt.getKoordinaten()[0]
+ " - " + aktuellerPunkt.getKoordinaten()[1]);
// Ausgabe des Pfades als Strings:
Feld speicher = aktuellerPunkt;
ArrayList<String> erg = new ArrayList<String>();
// In den Vorgängern steht der Knoten der vor dem aktuellen kommt.
// der Startpunkt hat keinen, deswegen nimmt man diesen als abbruch.
while (speicher.getVorgaenger() != null) {
erg.add(speicher.getKoordinaten()[0] + " - "
+ speicher.getKoordinaten()[1]);
speicher = speicher.getVorgaenger();
}
// ArrayList muss rückwärts ausgegeben werden.
for (int i = erg.size() - 1; i >= 0; i--) {
System.out.println(erg.get(i));
} // ENDE DER AUSGABE
}
private void draw() {
// Zeichnet das Feld in die Konsole
for (int j = 0; j < 10; j++) {
for (int i = 0; i < 10; i++) {
if (!field[i][j].isFrei()) {
System.out.print("X");
} else {
System.out.print(" ");
}
}
// Nach jeder Zeile einen Absatz
System.out.println();
}
}
private void nachbarnBearbeiten(int xSpeicher, int ySpeicher,
Feld vorgaenger, int xEnde, int yEnde) {
Feld speicher;
xSpeicher = vorgaenger.getKoordinaten()[0];
ySpeicher = vorgaenger.getKoordinaten()[1];
/*
* Für jeden der 4 an den aktuellen Punkt angrenzenden Punkte tue: Wenn
* der Punkt nicht begehbar ist, ignoriere ihn; andernfalls mach das
* Folgende: Wenn er nicht in der offenen oder geschlossenen Liste ist,
* füge ihn der offenen Liste hinzu. Trage den aktuellen Punkt als
* Vorgängerpunkt dieses Punktes ein, um die Richtung zu haben. Trage
* zusätzlich die Werte für die F-, G- und H-Kosten dieses Punktes ein.
* Falls der Punkt bereits in der offenen oder geschlossenen Liste ist,
* prüfe, ob der Pfad vom aktuellen Punkt zu ihm - gemessen am G-Wert -,
* besser ist, als der Pfad von seinem eingetragenen Vorgängerpunkt (ein
* geringerer G-Wert bedeutet einen besseren Pfad). Falls dem so ist,
* ändere sein Vorgängerpunkt auf den aktuellen Punkt und berechne seine
* Werte für G und F neu. Sofern Deine offene Liste nach dem F-Wert
* sortiert ist, ist möglicherweise eine Neusortierung dieser Liste
* erforderlich, um dieser Veränderung Rechnung zu tragen.
*/
// Da ich bei meinem Spiel ALLE Felder G = 1 haben
// NordPunkt betrachten
if (ySpeicher - 1 >= 0) {
speicher = this.field[xSpeicher][ySpeicher - 1];
if (speicher.isFrei()) {
if (!openList.contains(speicher) && !closedList.contains(speicher)) {
// Vorgänger speichern
speicher.setVorgaenger(vorgaenger);
// Koordinaten speichern
speicher.setKoordinaten(xSpeicher, ySpeicher - 1);
// Kosten speichern
speicher.setHWert(berechneHWert(xSpeicher, ySpeicher - 1,
xEnde, yEnde));
openList.add(speicher);
}
}
}
// OstPunkt betrachten
if (xSpeicher + 1 <= MAX_X) {
speicher = this.field[xSpeicher + 1][ySpeicher];
if (speicher.isFrei()) {
if (!openList.contains(speicher) && !closedList.contains(speicher)) {
// Vorgänger speichern
speicher.setVorgaenger(vorgaenger);
// Koordinaten speichern
speicher.setKoordinaten(xSpeicher + 1, ySpeicher);
// Kosten speichern
speicher.setHWert(berechneHWert(xSpeicher + 1, ySpeicher,
xEnde, yEnde));
openList.add(speicher);
}
}
}
// SuedPunkt betrachten
if (ySpeicher + 1 <= MAX_Y) {
speicher = this.field[xSpeicher][ySpeicher + 1];
if (speicher.isFrei()) {
if (!openList.contains(speicher) && !closedList.contains(speicher)) {
// Vorgänger speichern
speicher.setVorgaenger(vorgaenger);
// Koordinaten speichern
speicher.setKoordinaten(xSpeicher, ySpeicher + 1);
// Kosten speichern
speicher.setHWert(berechneHWert(xSpeicher, ySpeicher + 1,
xEnde, yEnde));
openList.add(speicher);
}
}
}
// WestPunkt betrachten
if (xSpeicher - 1 >= 0) {
speicher = this.field[xSpeicher - 1][ySpeicher];
if (speicher.isFrei()) {
if (!openList.contains(speicher) && !closedList.contains(speicher)) {
// Vorgänger speichern
speicher.setVorgaenger(vorgaenger);
// Koordinaten speichern
speicher.setKoordinaten(xSpeicher - 1, ySpeicher);
// Kosten speichern
speicher.setHWert(berechneHWert(xSpeicher - 1, ySpeicher,
xEnde, yEnde));
openList.add(speicher);
}
}
}
}
private int berechneHWert(int xAktuell, int yAktuell, int xEnde, int yEnde) {
/*
* Gibt die Differenz zwischen den X,Y Koordinaten zurück. Start 3,5 --
* Ende 6,7 => xDiff = 6 - 3 + 7 - 5, da immer der größere - kleinere
* Wert gerechnet wird
*/
int yDiff = yAktuell > yEnde ? yAktuell - yEnde : yEnde - yAktuell;
int xDiff = xAktuell > xEnde ? xAktuell - xEnde : xEnde - xAktuell;
return xDiff + yDiff;
}
}
)
