Wertepaar in LinkedList/PriorityQueue speichern

[Sophia1]

Hallo!

Ich muss für die Uni ein Spiel programmieren. Ich bin zuständig für die künstliche Intelligenz und brauche dafür den A*-Algorithmus.

Ich habe also ein Spielfeld, das auf einem Array basiert. Der A*-Algorithmus soll dafür sorgen, dass die Monster automatisch den kürzesten Weg zum Spieler laufen.

Überall im Internet steht, dass man die markierten Knoten im A*-Algo in einer "openlist" Speichern soll. Diese kann als priority Queue oder LinkedList implementiert werden. Der Knoten (bzw das Array Feld) mit dem geringsten f-Wert in der openlist soll dann ausgegeben werden.
Hier liegt mein Problem: Wie kann ich ein Wertepaar (Koordinaten des Arrayfeldes, auf dem mein Monster steht + zugehöriger Wert der f-Funktion des Feldes) in einer LinkedList bzw Priority Queue speichern?

Meines Wissens nach können in einer LinkedList nur einzelne Werte gespeichert werden. Ein Kommilitone von mir hat mir eine Integer PriorityQueue als Heap programmiert, jedoch weiß ich hier auch nicht, wie ich das Wertepaar dort speichern soll, da auch hier nur einzelne int Werte benutzt werden können.

Kennt sich jemand mit dem A* Algorithmus aus und kann mir helfen? Ich weiß echt nicht weiter!

 

[SilverClaw]

Also ich weiß nicht, ob du das hier schon gelsen hast, aber ich and das recht gut erklärt: A* Pathfinding for Beginners

Wenn dein einziges Problem darin besteht, zwei Koordinaten zu speichern, dann mach doch einfach eine LinkedList von Point - Objekten. Ein Point besteht schließlich aus einer x und einer y - Koordinate, also genau das, was du brauchst. Ansonsten benutzt du einfach zwei Listen und läufst sie parallel durch.
Das wären so spontan die einfachsten Ideen. Ob die von der Geschwindgkeit optimal sind, kann ich nicht garantieren, aber für ein Schul- (und auch die meisten Uni-) Projekt wird es darauf ja nicht unbedingt ankommen oder? 😀

 

[Sophia1]

Also es geht darum, dass ich in einer Liste immer das Feld + den dazugehörigen Wert speichern will.
Ich will dann später immer auf das Feld mit dem kleinsten Wert zugreifen können.
Ich muss also x-Koordinate, y-Koordinate und den Funktionswert zusammen speichern und will nach dem Funktionswert sortieren.
Wie mache ich das?

 

[SilverClaw]

Am besten machst du dir da eine Klasse, die comparable implementiert.
Sowas wie
class Field implements Comprable {
int x, y, value;
// und so weiter
}

und die Klasse speichert dann die Koordinaten und den Wert und lässt sich auch effizient sortieren.
Wie man compareTo() am besten überschreibt kannst du notfalls kurz googeln, ich will es nicht unbedingt nochmal erklären, falls du es schon kennst. 😉
(wobei es nicht zwangsläufig nötig wäre, man kann auch direkt nach getValue() sortieren).