# Spielfeld für RPG



## pengwolf (9. Jun 2012)

Hallo,

ich habe noch kein Problem mit Quellcode etc. Ich hänge noch in der Designphase fest.

Es geht darum, dass ich ein Rundenbasiertes RPG machen möchte. Dafür brauche ich ein Spielfeld (Dungeon) der von einem Spieler zur Laufzeit erstellt werden kann. Es soll später in die Richtung gehen, dass sich der Spieler aus einer Palette an "Bodenplatten" Elemente herausnehmen kann und damit den Dungeon erweitern kann. ( Server / Client )

Nun bin ich in der Situation, das ich noch keine Erfahrung damit habe und wollte mir mal Ansätze von euch holen, wie Ihr das machen würdet. Um das ganze verständlicher zu machen:






Man soll auf den freien Feldern laufen können ( Jeder Charakter hat später eine gewisse Anzahl an Schritten ). 
Es gibt Objekte auf den Feldern. Items, Truhen, Steine, Fallen
Es soll verschiedene Untergründe geben. Grube, Wasser und Stein soll später vielleicht erweitert werden.
Charaktere nehmen immer ein Feld ein und pro Feld kann nur ein Charakter stehen.
Es muss die Reichweite von einem Feld bis zum nächsten ermittelt werden können. ( Bewegungsweite / Angriffsreichweite )

Ich habe mir schon Gedanken in Richtung Arrays gemacht. Wüsste aber nicht, wie ich das Dynamisch halten soll. Auch wenn ich ein Feld als Klasse und dann die verschiedenen Felder (Stein, Wasser, Fallgrube) davon erben lasse. Ich hatte auch an ein Int-Arrray gedacht, wo ich dann abhängig von dem Zustand des Feldes die Werte im Array ändere. 100 = Stein && 101 = Stein + Kiste oder so ähnlich. Das nächste was mir eingefallen ist wäre eine Klasse für die einzelnen Segmente und dann die nächsten Elemente als Nachbarn speichern ( Richtung Baumstruktur ). Da wüsste ich dann aber nicht, wie ich die Sichtweite / Bewegungsweite etc. realisieren soll

Ich hoffe, das sind erst mal genug Informationen.

Sollten noch fragen sein, einfach schreiben.

Schonmal vielen Dank!


----------



## Network (9. Jun 2012)

pengwolf hat gesagt.:


> Man soll auf den freien Feldern laufen können ( Jeder Charakter hat später eine gewisse Anzahl an Schritten ).
> Es gibt Objekte auf den Feldern. Items, Truhen, Steine, Fallen
> Es soll verschiedene Untergründe geben. Grube, Wasser und Stein soll später vielleicht erweitert werden.
> Charaktere nehmen immer ein Feld ein und pro Feld kann nur ein Charakter stehen.
> Es muss die Reichweite von einem Feld bis zum nächsten ermittelt werden können. ( Bewegungsweite / Angriffsreichweite )




Das mit dem Laufen ist so eine Sache... möchtest du die möglichen Positionen auf dem Spielfeld anzeigen lassen beim Klick auf eine Figur, dann musst du bei jeder neuen Position eine Baumstruktur berechnen wohin man sich bewegen kann. Wenn nicht bietet sich der A*-Alghorithmus an, dort kann man auch ganz leicht mit einbauen, dass eine Figur auf bestimmtem Untergrund mehr "Bewegungsreichweite" verbraucht. Der Rest ist dann ganz einfach indem du die einzelnen Bodenplatten in eine Liste packst und bei jedem Schleifendurchlauf berechnest ob sich die nächste Platte von den X- oder Y-Werten kleiner, größer oder gleich groß ist zur eigenen XY-Position ist und dich dementsprechend bewegst bzw. bei gleicher Größe das nächste Tile anvisierst.
Hier wäre eine Überlegung sinnvoll inwiefern sich die Objekte auf das Spiel auswirken und was du noch so einbauen willst. Evt. verschiedene Boolean-Werte, die angeben, was sich auf dem Feld befindet im sinne von "boolean stein = true, begehbar = false". Hier würde ich zu einer bitweisen Differenzierung raten bei der jedes bit eines bytes ein boolean Wert ist. So kannst du einem TileCreator die Zahl bzw. den entstandenen Wert übergeben und der werkelt einem das anzuzeigende Bild heraus. Objekte die den Spieler beeinflussen, wie Items, Truhen oder Fallen würde ich jetzt jedem Tile übergeben, dass diese Objekte abspeichert und fals eine Figur das Tile betritt dem Objekt die Figur übergeben wird, dieses führt dann jeweiligen Code zu der Figur aus.
Siehe Nummer 1
Der Bodenplatte auf dem die Figur steht die Figur übergeben. Sobald der Wegfindungsprozess eingeleitet wird, wird überprüft ob die variable die die Figur enthält = null ist und damit begehbar oder nicht. (Zusätzlich zu der boolean-Überprüfung begehrbar)
Die Richweite sollte kein Problem darstellen. Die kriegst du unter Punkt 1 genannte Möglichkeiten. Die Angriffsreichweite ist mir ein Rätsel was das umfasst. Meistens ja die maximale Bewegung + 1.

Gruß
Net


----------



## pengwolf (9. Jun 2012)

Network hat gesagt.:


> Das mit dem Laufen ist so eine Sache... möchtest du die möglichen Positionen auf dem Spielfeld anzeigen lassen beim Klick auf eine Figur, dann musst du bei jeder neuen Position eine Baumstruktur berechnen wohin man sich bewegen kann. Wenn nicht bietet sich der A*-Alghorithmus an, dort kann man auch ganz leicht mit einbauen, dass eine Figur auf bestimmtem Untergrund mehr "Bewegungsreichweite" verbraucht. Der Rest ist dann ganz einfach indem du die einzelnen Bodenplatten in eine Liste packst und bei jedem Schleifendurchlauf berechnest ob sich die nächste Platte von den X- oder Y-Werten kleiner, größer oder gleich groß ist zur eigenen XY-Position ist und dich dementsprechend bewegst bzw. bei gleicher Größe das nächste Tile anvisierst.
> Hier wäre eine Überlegung sinnvoll inwiefern sich die Objekte auf das Spiel auswirken und was du noch so einbauen willst. Evt. verschiedene Boolean-Werte, die angeben, was sich auf dem Feld befindet im sinne von "boolean stein = true, begehbar = false". Hier würde ich zu einer bitweisen Differenzierung raten bei der jedes bit eines bytes ein boolean Wert ist. So kannst du einem TileCreator die Zahl bzw. den entstandenen Wert übergeben und der werkelt einem das anzuzeigende Bild heraus. Objekte die den Spieler beeinflussen, wie Items, Truhen oder Fallen würde ich jetzt jedem Tile übergeben, dass diese Objekte abspeichert und fals eine Figur das Tile betritt dem Objekt die Figur übergeben wird, dieses führt dann jeweiligen Code zu der Figur aus.
> Siehe Nummer 1
> Der Bodenplatte auf dem die Figur steht die Figur übergeben. Sobald der Wegfindungsprozess eingeleitet wird, wird überprüft ob die variable die die Figur enthält = null ist und damit begehbar oder nicht. (Zusätzlich zu der boolean-Überprüfung begehrbar)
> ...



Danke für die schnelle Antwort.

Ich hatte eig. schon später vorgehabt die Felder, die der Spieler gehen kann, anzeigen zu lassen. Bin mir aber im Allgemeinen noch nicht sicher, wie das alles später aussehen soll. Und wie es aussehen kann. Da ich die Funktionen und den Umfang von der GUI noch nicht kenne. Habe bis jetzt in Java noch nichts mit Grafik gemacht.

Zu deinen Vorschlägen: Der A*-Algorithmus sieht schon mal sehr nach dem aus, was ich benötige. Ich habe nur nicht so ganz den Übergang zwischen den einzelnen Elementen verstanden. 
So stelle ich mir das ganze im Moment vor: 



( hoffe sehr, das das UML verständlich ist  )

Ich würde jetzt eine Art Faktor in den Bodenplatten speichern. Also die Bodenplatte oben links ( die erste ) hätte dann xFaktor = 0, yFaktor = 0. Wird dann eine Bodenplatte unter diese gesetzt so bekommt diese einen yFaktor, der um die y-Länge der ersten Platte höher ist. Um so die Koordinaten zu errechnen.
Hoffe das war verständlich 

Bin mir aber nicht ganz sicher, worauf du hinaus wolltest.


----------



## Apo (9. Jun 2012)

Ich habe mal ein kleines Tutorial für den A* geschrieben.

Vielleicht hilft er dir ja weiter. =)


----------



## pengwolf (9. Jun 2012)

Apo hat gesagt.:


> Ich habe mal ein kleines Tutorial für den A* geschrieben.
> 
> Vielleicht hilft er dir ja weiter. =)



Das wird mir auf jeden Fall weiterhelfen! Ich hätte mich jetzt durch Wiki gebissen und versucht das zu verstehen und umzusetzen und wäre dann denke ich wieder bei Google gelandet  
Sieht auf den ersten Blick verständlich aus. Erinnert mich etwas an den RPG-Maker  Gleich mal dran setzten.


----------



## Network (9. Jun 2012)

@TO ich nehme an du sprichst den Punkt Nummer 1 an.
Also die UML zeigt sehr ähnlich das worauf ich hinaus wollte wie so eine BodePlatte aussehen könnte 

Bei Nummer 1 mit den X und Y-Werten: Jede Bodenplatte muss ja ganz genau "wissen" wo sie sich von den X und Y Werten befindet wenn sie auf das Spielfeld gezeichnet werden soll. Also so wie ich das verstanden habe entspricht dass deinem xFaktor/yFaktor.

Was ich meinte ist, wenn der A*-Alghorithmus seinen Weg gefunden hast gibt es verschiedene Möglichkeiten deiner Figur den Weg bereitzustellen.
Eine naheliegende Möglichkeit wäre, dass du der Figur eine Liste übergibst die alle Bodenplatten enthält vom Startpunkt bis zum Ziel.
Jedesmal wenn du berechnest ob sich die Einheit bewegen soll, errechnest du ob entweder die X Koordinate größer/kleiner oder die Y-Koordinate größer/kleiner als die der Position deiner Figur um dich dann entsprechend auf das Feld zuzubewegen.
Wenn sowohl X als auch Y Koordinaten die selben sind, bedeutet das, dass die Figur einen der Wegpunkte erreicht hat und sofern in der Liste noch weitere Wegpunkte zur Verfügung stehen du weiterläufst, ansonsten stehenbleibst.



Apo hat gesagt.:


> Ich habe mal ein kleines Tutorial für den A* geschrieben.
> 
> Vielleicht hilft er dir ja weiter. =)



Irgendwie kommt mir das Tutorial sehr bekannt vor. Kann es sein dass du das irgendwoher kopiert oder übersetzt hast? (Bis auf die Bilder)  Vieleicht wars ja auch anderst herum


----------



## pengwolf (9. Jun 2012)

Network hat gesagt.:


> Was ich meinte ist, wenn der A*-Alghorithmus seinen Weg gefunden hast gibt es verschiedene Möglichkeiten deiner Figur den Weg bereitzustellen.



Ja, ging um die Nummer 1.

Ich bin noch am Grübeln, wie ich die einzelnen Bodenelemente in den A*-A einbringe. Aber das ist denke ich einfach eine "Formsache" da ich ja die Übergänge und die nächsten Bodenplatten in den Klassen als Nachbarn angegeben habe. Ich werde mich erst einmal mit einem freien Feld belustigen und dann nach und nach den Schwierigkeitsgrad anziehen. Sollte ich merkliche Fortschritte machen, werde ich mich nochmal melden.

Vielen Dank an euch beide.


----------



## pengwolf (9. Jun 2012)

So, mein A*-Algo funktioniert soweit. Die Implementierung der Bodenplatten kommt jetzt die nächsten Tage.

Wer möchte kann sich den Code gerne kopieren. Ich hoffe, die Kommentare helfen Anderen Leuten weiter.

Mit der Erklärung von Apo sollte es aber kein Problem mehr geben  Danke nochmal dafür.

AsternAlgo.java

```
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 < 10; 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[3][5].setFrei(false);
        this.field[4][4].setFrei(false);
        this.field[5][4].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(3, 2, 4, 5);
    }

    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.
            // ACHTUNG! ES MUSS EINEN WEG GEBEN! SONST ENDLOSSCHLEIFE!
        } while (aktuellerPunkt.getKoordinaten()[0] != xEnde
                || aktuellerPunkt.getKoordinaten()[1] != yEnde);

        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 i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                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;
    }
}
```

Feld.java

```
package astern.algo;

public class Feld {

    /*
     * Diese Klasse ist nichts anderes als ein großer Speicher mit getter und
     * setter
     */
    private boolean isFrei;
    private Feld vorgaenger;
    private int xKoordinate;
    private int yKoordinate;
    private int gWert;
    private int fWert;
    private int hWert;

    public Feld() {
        this.gWert = 1;
    }

    public void setVorgaenger(Feld vorgaenger) {
        this.vorgaenger = vorgaenger;
    }

    public Feld getVorgaenger() {
        return this.vorgaenger;
    }

    public void setFrei(boolean frei) {
        this.isFrei = frei;
    }

    public void setKoordinaten(int x, int y) {
        this.xKoordinate = x;
        this.yKoordinate = y;
    }

    public int[] getKoordinaten() {
        // Gibt die Koordinaten als Array zurück
        int[] erg = {xKoordinate, yKoordinate};
        return erg;
    }

    public boolean isFrei() {
        return isFrei;
    }

    public int getGWert() {
        return this.gWert;
    }

    public void setHWert(int hWert) {
        // F-Wert = H-Wert + G-Wert
        // G-Wert ist ja bekannt
        // H-Wert wird auch gesetzt
        this.fWert = hWert + this.gWert;
        this.hWert = hWert;
    }

    public int getFWert() {
        return this.fWert;
    }

    public int getHWert() {
        return this.hWert;
    }
}
```

So sieht die Ausgabe bei mir aus. Mit den Werten aus dem Programm oben:

```
XXXXXXXXXX
X        X
X        X
X    X   X
X   X    X
X   X    X
X        X
X        X
X        X
XXXXXXXXXX
Ende gefunden: 4 - 5
3 - 3
3 - 4
2 - 4
2 - 5
2 - 6
3 - 6
4 - 6
4 - 5
```


----------



## pengwolf (9. Jun 2012)

Habe gerade ein Paar Sachen geändert und wollte mal ein Labyrinth machen. Das Problem dabei war, mir ist aufgefallen, das der A*-Algo nicht den kürzesten Weg nimmt. Kann sich jemand vorstellen, woran das liegt?

AsternAlgo.java
	
	
	
	





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

Feld.java ist gleich geblieben

Die Ausgabe:

```
XXXXXXXXXX
X  X     X
XX X X   X
XX   X   X
XXXXXXX  X
X        X
X   XXXXXX
X   X    X
X     X  X
XXXXXXXXXX
Ende gefunden: 8 - 8
2 - 1
2 - 2
2 - 3
3 - 3
4 - 3
4 - 2
4 - 1
5 - 1
6 - 1
7 - 1
8 - 1
8 - 2
8 - 3
8 - 4
8 - 5
7 - 5
6 - 5
5 - 5
4 - 5
3 - 5
3 - 6
3 - 7
3 - 8
4 - 8
5 - 8
5 - 7
6 - 7
7 - 7
8 - 7
8 - 8
```

Da ich mir das auf dem Block aufgemalt habe und euch das nicht zumuten will hier die Ausgabe in Schritten:




Die Schritte(x,y) 6,1 -> 6,2 -> 6,3 -> 7,3 -> 7,4 -> 7,5 sind aber um 2 kürzer.

Ich habe den Punkt 

```
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.
```
weggelassen, da ich immer G = 1 habe. Aber es kann ja damit nichts zu tun haben.

Oder bringe ich da grad was durcheinander?


----------



## vanny (9. Jun 2012)

Ich lese mir das hier gerade mal so durch und denke, dass du auch mit einem Bewegungsfaktor auf einem eigenen Texturwrapper arbeiten kannst.
nichtBegehbar = 0; normal = 1 und schnell halt 2 etc. ...

Der Vorteil ist, dass du im Nachhinein einfach neue Texturen erstellst, diese dann deinem Feld übergibst und damit schon Auswirkungen auf das Spielverhalten erzielst.
Auch Hügel und ähnliche lassen sich so recht leicht realisieren, genauso wie verschiedene Sounds in der Animation. Lässt sich alles wunderbar in so einem Texturobjekt einbinden.

Gruß Vanny


----------



## pengwolf (9. Jun 2012)

Soweit habe ich ehrlich noch nicht gedacht. Muss auch gestehen, habe noch keine Ahnung, was ein TextureWrapper ist  . Werde es aber im Hinterkopf behalten und sobald ich in die Richtung GUI etc komme dran denken :toll:


----------



## Apo (9. Jun 2012)

Das Problem ist der F-Wert. Der wird nie richtig initialisiert bzw irgendwie gesetzt ... das fehlt komplett.
Du musst dem Punkt auch sagen, wieviel er bis jetzt dahin benötigt hat. Bei dir ist er immer 0.


----------



## pengwolf (9. Jun 2012)

Apo hat gesagt.:


> Das Problem ist der F-Wert. Der wird nie richtig initialisiert bzw irgendwie gesetzt ... das fehlt komplett.
> Du musst dem Punkt auch sagen, wieviel er bis jetzt dahin benötigt hat. Bei dir ist er immer 0.



Stimmt. Hatte ich vergessen. Habe es ergänzt, nun stimmt es.


```
XXXXXXXXXX
X  X     X
XX X X   X
XX   X   X
XXXXXXX  X
X        X
X   XXXXXX
X   X    X
X     X  X
XXXXXXXXXX
Ende gefunden: 8 - 8
2 - 1
2 - 2
2 - 3
3 - 3
4 - 3
4 - 2
4 - 1
5 - 1
6 - 1
7 - 1
7 - 2
7 - 3
7 - 4
7 - 5
6 - 5
5 - 5
4 - 5
3 - 5
3 - 6
3 - 7
3 - 8
4 - 8
5 - 8
5 - 7
6 - 7
7 - 7
8 - 7
8 - 8
```

Feld.java
	
	
	
	





```
public void setHWert(int hWert) {
        this.hWert = hWert;
    }
    
    public void setFWert(int fWert) {
        this.fWert = fWert;
    }

    public int getFWert() {
        return this.fWert;
    }
```

und AsternAlgo.java
	
	
	
	





```
// Kosten speichern
speicher.setHWert(berechneHWert(xSpeicher, ySpeicher + 1,
        xEnde, yEnde));
// Setzen des neuen F-Wertes für diesen Knoten
speicher.setFWert(speicher.getVorgaenger().getFWert() 
        + speicher.getHWert() + speicher.getGWert());
```

Vielen Dank.


----------



## Network (10. Jun 2012)

Kleiner Tipp am Rande: Dein A*-Alghorithmus kann noch weit besser optimiert werden, sodass er vom Code her weniger wird sowie im Nanosekundenbereich Ergebnisse findet.
Der Grund ist der Code (Verwendung der Container), sowie der Alghorithmus an sich selbst - es gibt leistungsfähigere A*-Alghorithmen die selbstverständlich vom Prinzip her alle gleich sind.

Soll nur ein kleiner Denkanstoss sein, also ein kleiner Tipp für später einmal.
1.) Vieleicht ist es dir hier im Moment völlig unwichtig, insbesondere da es rundenbasiert abläuft und Geschwindigkeit somit eher Vernachlässigbar ist und besonderst es sich nur um ein kleines Spiel handelt.
2.) Ich äußere mich dazu jetzt auch nicht mehr. Denn selber entdecken hat so seine Vorteile und Erfolgsmomente und die will ich dir nicht ohne meine Erlaubnis nehmen.


----------



## pengwolf (10. Jun 2012)

Network hat gesagt.:


> Kleiner Tipp am Rande: Dein A*-Alghorithmus kann noch weit besser optimiert werden, sodass er vom Code her weniger wird sowie im Nanosekundenbereich Ergebnisse findet.
> Der Grund ist der Code (Verwendung der Container), sowie der Alghorithmus an sich selbst - es gibt leistungsfähigere A*-Alghorithmen die selbstverständlich vom Prinzip her alle gleich sind.
> 
> Soll nur ein kleiner Denkanstoss sein, also ein kleiner Tipp für später einmal.
> ...



Ja, hatte ich auch schon überlegt. Aber das Programm war nur für mich um zu verstehen, wie der Alghorithmus läuft. Ich wollte jetzt kein riesen großes Feld machen, da ich dort ja jedem Feld die Nachbarn als ref übergeben muss. Deswegen die Umstände mit den Koordinaten. So fand ich es einfacher für mich.

Aber vielen Dank, für die Denkanstöße


----------



## pengwolf (10. Jun 2012)

Ich mal wieder.

Ich bin schon etwas weiter. Mache mir aber gerade Gedanken, wie ich das alles Darstellen will/kann um dann die Klassen dementsprechend anzupassen

Geplant war grob erstmal etwas in der Richtung:




Ich habe als Grundlage das Heli-Spiel von Quaxli nachprogrammiert und kam daher auf die GameLoop (Sinnvoll, da ich ja später Server-Client-Verbindungen haben will). Meine Frage ist jetzt, da ich von GUI-Programmierung in Java noch nicht sonderlich viel Erfahrung habe, ob der Ansatz stimmt. Macht es Sinn, die beiden Klassen so anzulegen? Oder sollte ich von Anfang an in eine andere Richtung gehen? Und vorallem stimmen die Aufrufe so... nehme ich die richtigen Funktionen?

Ich möchte später...

... das der User peer Mouseover bei seiner Einheit die Bewegungsreichweite sehen kann (Felder färben?)
... das der User peer Mouseover bei anderen Einheiten Informationen erhalten kann in einem kleinen Info-Fenster
... mit Mausklick Einheiten bewegt werden können (x,y-Koordinaten abfragen und dann dementsprechend setzen)
Das Spielfeld soll/muss scrollbar sein. Da das Feld größer wird als die 800*600 des Fensters.

Vielen Dank.


GUI.java
	
	
	
	





```
import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;

public class GUI extends JFrame implements ActionListener, Runnable{
    
    Pitch pitch;
    JPanel pnlButton;
    JButton btnDice;
    JScrollPane spSpielfeld;
    
    public GUI(int w, int h) {
        
        btnDice     = new JButton("Würfeln");
        pitch       = new Pitch(1200,900,12,9);
        pnlButton   = new JPanel();
        spSpielfeld = new JScrollPane(pitch);
        
        
        this.setSize(new Dimension(w, h));
        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        btnDice.addActionListener(this);
        pnlButton.add(btnDice);
        
        this.add(BorderLayout.CENTER,spSpielfeld);
        this.add(BorderLayout.EAST,pnlButton);
        
        this.setVisible(true);
        
        Thread th = new Thread(this);
        th.run();
    }

    @Override
    public void actionPerformed(ActionEvent e) {
        
        //AL für Buttons
        if(e.getSource().equals(this.btnDice)) {
            System.out.println("Wuerfeln usw.");
        }
    }

    @Override
    public void run() {
        
        // GameLoop
        while(this.isVisible()) {
            this.pitch.paintComponents(this.getGraphics());
        }
    }
    
    
    
}[/Java]

Pitch.java[code=Java]
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import javax.swing.JPanel;

public class Pitch extends JPanel {

    Feld[][] field;
    int wArray;
    int hArray;

    public Pitch(int wWindow, int hWindow, int wArray, int hArray) {
        super();
        this.setSize(new Dimension(wWindow, hWindow));
        this.field = new Feld[wArray][hArray];
        this.wArray = wArray;
        this.hArray = hArray;
    }

    @Override
    public void paintComponents(Graphics g) {
        int widhtField = this.getWidth() / this.wArray;
        int heightField = this.getHeight() / this.hArray;

        /*
         * Hier würde ich jetzt beginnen mein Spielfeld zu zeichen. Erstmal nur
         * ein reines Raster.
         */

    }
}
```


----------

