A-Stern Algorithmus Problem und Implementierung einer Map

[Eichelhäer]

Hallo,

gleich zur Sache:

zurzeit implementiere ich einen A* für eine Art RPG-Game zumindest versuch ich es.

Ich habe nur ein Problem mit der Ermittlung der Nachbarzellen bzw. Nachbartiles.
Folgende Methode gibt mir ein Array aus Knoten zurück:

public Node[] getNeighbours(Node current){

Node[] neighbors = new Node[4];

//hier nur mal eine Evaluierungsrichtung
//left

int x = current.x;
int y = current.y;

int neighborx;
int neighbory;

neighborx = x - 32 // 32 ist die Tilebreite bzw.Laenge
neighbory = y;

if(neighborx >= 0){
neighbor[0] = new Node(neighborx,neighbory);
}
return neighbors;
}

Nach Überprüfung der Funktion durch Ausgabe der erzeugten Nachbarn ist mir aufgefallen, dass ständig neue Nachbarn erzeugt werden und zwar wild durcheinander.

Das Problem, das sich daraus für meine Abbruchbedingung des A*-Algorithmus ergibt ist, dass der current-Knoten nie gleich dem goal-Knoten wird und die Schleife nie abgebrochen wird geschweige denn der kürzeste Weg ausgegeben werden kann.

Nun hab ich überlegt.

Ich möchte ja letztendlich den A* auf einer Map anwenden.
Ich habe bereits eine Map und deren Daten in einem int-Array gespeichert:

levelMap[height][width];

Deshalb dachte ich, die neighbors irgendwie mit dem levelMap-Array in Verbindung zu bringen, bisher ohne Ergebnis.

Fragen: Wie kombiniert man den A* mit einer Map als int-Array?
Wie ermittelt man dann die entsprechenden Nachbarn?

Wäre für Hilfe dankbar


Gruß Eichelhaer

 

[Baldur]

Rechnest du bei deinem Koordinatensystem in Pixeln? (Weil du in deiner Rechnung die Kachelbreite subtrahierst)
Man tut sich leichter, wenn man für die Algorithmen ein einfaches Raster als Koordinatensystem benutzt, also jedes Feld genau "1" breit und hoch ist. Beim Zeichnen dann rechnet man von Kachelkoordinaten in Pixelkoordinaten um.

Die Nachbarn bekommt man dann recht einfach:

neighbour[0] = new Node(current.x - 1, current.y);
neighbour[1] = new Node(current.x + 1, current.y);
neighbour[2] = new Node(current.x,     current.y - 1);
neighbour[3] = new Node(current.x,     current.y + 1);

(dabei aber auch nicht vergessen zu überprüfen, ob die Nachbarn noch innerhalb der Karte liegen 😉)

Wenn du deine Map als zweidimensionales Array implementierst, dann ist das durchaus der übliche Ansatz, wie es die meisten 2D-Spiele machen. Ggf wirst du später kein int-Array nutzen wollen, sondern eine eigene Klasse machen wollen, um mehr Informationen pro Kachel zu speichern.

Daß pro Nachbarfeld jeweils eine neue "Node" erzeugt wird ist auch richtig. Die Node soll ja auch die jeweils aktuellen Kosten und den jeweiligen Vorgänger abspeichern, um am Ende den Pfad erzeugen zu können.
Am Ende darfst du halt keinen Vergleich wie z.B. if (current_node == target_node) machen, sondern musst halt die Koordinate deiner Node mit dem gesuchten Ziel vergleichen.

 

[Eichelhäer]

Hallo,

Danke für deine Antwort.

Letzte Nacht war sehr lang aber sehr erfolgreich. Ich habe es endlich nach 2 Wochen geschafft den A* - Algrithmus erst in der Konsole dann Grafisch in Swing mit einer sehr primitiven Map zu implementieren.

Es funktioniert alles tadellos, also die sehr schnelle Ermittlung des kürzesten Pfades sowie die Berücksichtigung der Kollisionsblöcke.

Jetzt möchte ich weitermachen und mein startRechteck entlang des ermittelten Pfades zum Ziel bewegen.
Das werde ich schaffen denke ich, wenn nicht melde ich mich nochmal.

Aber ich hab noch eine Frage zu TileMaps und zwar:

Es ist leicht eine TileMap aus 2 bis 10 Kachel die jeweils ein eigenes Bild sind darzustellen und ich hab damit auch keine Probleme.

Wie ist das jetzt aber speziell in JAVA, wenn man beispielsweise 100 verschiedene Tiles als SpriteSheet vorliegen hat hinsichtlich der Geschwindigkeit und letztendlich der Performance?

Ich lese immer wieder in der Insel und bin auf Clipping gestoßen. Also die Methode setClip(x,y,w,h), um aus einem Bild Teilbilder zu Clippen.

Daraufhin hab ich mir eine Zeichenmethode mit Clipping geschrieben und siehe da die TileMap wurde richtig angezeigt.

ABER bis die TileMap angezeigt wurde vergingen locker 10 Sekunden und das Programm stockte und ruckelte, kurz gesagt es ging gar nix mehr. Die Bilddatei mit den Tiles darauf ist auch nicht sehr groß(ist ja blos 2D Grafik) und an JAVA kann es nicht liegen, denn ich hab bereits andere grafische Sachen gemacht die mehr Performance gekostet haben.

Aber zurück zu meiner Frage:

Kann mir jemand sagen wie man große TiledMaps aus einem Spritescheet, das aus mehr als 100 verschiedenen Tiles besteht ohne große Performance Probleme zu bekommen ?

Da ich etwas faul bin, was die Eingabe von Daten betrifft, möchte ich bitte keine Vorschläge in dem Stil:

int tileNr = levelMap[x][y];
if(tileNr == 56){
mal das Tile;
}
usw. für jedes der hundert Bilder.

Für konstruktive Vorschläge bin ich offen und vielen Dank im Voraus,

Gruß Eichelhaer

 

[Baldur]

Früher unter JavaME haben wir auch Spritesheets benutzt und mittels Clipping die einzelnen Frames daraus gezeichnet. Also falsch ist der Ansatz jedenfalls nicht und sollte auch ohne Performance Probleme funktionieren.

Wie gehst du denn beim Zeichnen vor? Setzt du erst das Clipping und zeichnest dann die Graphik?
Die java.awt.Graphics Klasse hat auch Funktionen, um direkt nur einen Teilbereich einer Graphik zu zeichnen. Das sollte schneller sein. Falls deine Karte größer ist als der Bildschirm, solltest du auch selbst noch die Zeichenoperationen filtern, wenn eine Kachel außerhalb des Bildschirms liegt.

 

[Eichelhäer]

Ich habs dann doch wieder allein geschafft. Mit meiner Clipping Methode. Das Problem war nur die Grafik.
Ich hatte nämlich rund 120 Kacheln als sehr langen Streifen als Bild vorliegen und selbst wenn man diese Grafik nur als solche in einem Swing Fenster anzeigen will geht die Breite des Streifens über die Fensterbreite hinaus. Nun habe ich diesen Streifen in meiner Spielschleife immer wieder zeichnen wollen und deshalb der Absturz.

Nach kurzer Überlegung habe ich nun folgendes gemacht. Zuerst hab ich in paint.net den Streifen mühsam zum Rechteck zusammenkopiert und anschließend lass ich nun nicht mehr die ganze Map auf einmal zeichnen, sondern nur den sichtbaren Bereich und tada es läuft wie am Schnürchen.

Also das ist erledigt!!!

Ach ja, ich benutzte den renomierten Tiled-Editor. Leider kann ich noch keinen tmx-Parser coden deshalb kopiere ich mir immer die Mapdaten aus der tmx-File in eine txt File und lade die dann via FileReader einmal im Konstruktor.

Es gibt da nur ein Problem, zwar wird der Kachelindex des Spritesheets während der Bearbeitung korrekt angezeigt, ABER wenn man die Map dann speichert beginnt der Kachelindex bei 1 und nicht wie beim Spritesheet bei 0. Das heißt, das ich entweder beim zeichnen für jedes zu zeichnende Tile die tileNr um eins vermindern muss oder von Hand via ersetzten Funktion die entsprechen Zahlen in der TextFile anpassen muss und das für alle Zahlen.

Jetzt hab ich in Tiled alles durchsucht und nur die Einstellung gefunden: Kachelindex --- gerade oder ungerade. Aber dadurch ändert sich nix und in der erzeugten tmx-datei steht gidfirst = 1, also fang bei eins an und deshalb sind die Zahlen dann auch alle genau um eins größer wie gewollt.

Frage: Weiß jemand, ob man das in Tiled irgendwie ändern kann, also konkret den Kachelindex auf null zu stellen?

Gruß Eichelhaer

 

[Baldur]

Ich hab grad nochmal in meinen Parser von Tiled reingeschaut...

Irgendwo am Anfang hast du eine Liste deiner Tilesets:

 <tileset firstgid="1" name="tileset1" tilewidth="64" tileheight="32">
  <image source="tilesets/tileset1.png" width="128" height="32"/>
 </tileset>
 <tileset firstgid="148" name="tileset2" tilewidth="64" tileheight="32">
  <image source="tilesets/tileset2.png" width="320" height="32"/>
 </tileset>

Der "tileset" block wiederholt sich für jedes Tileset, das in der Karte angegeben ist. "firstgid" sagt dir, welche Nummer das erste Tile aus dem jeweiligen Tileset hat.
In dem Fall hab ich zwei Tilesets, eins geht von Index 1 bis 147, das andere von 148 bis x.

Wenn jetzt bei den Tiledaten irgendwo steht <tile gid="251"/>, dann kannst du nachschaun, zu welchem Tileset das gehört und den Wert von "firstgid" des entsprechenden Tilesets subtrahieren. Dann bekommst du den eigentlichen Tileindex raus.
<tile gid="0"/> ist bei Tiled ein leeres Tile, drum fangen die eigentlichen Tiles bei 1 an und nicht bei 0.

 

[Eichelhäer]

Ok danke.