Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

TreeSet statt ArrayList + compareTo überschreiben für A* Algorithmus

Werbeanzeige

equinox

Frischling

Beiträge: 56

Beruf: Student

  • Private Nachricht senden

21

09.06.2017, 11:23

C#-Quelltext

 
1
2
3
4
5
6
7

public static List<Tile> findPath(int startx,int starty,int endx,int endy){
        
        for(int i = 0; i < width; i++){
            for(int j = 0;j < height;j++){
                tiles[i][j] = new Tile(i,j,size,size,obstacles[i][j],false);
            }
        }


Hast du denn auch diesen Teil entfernt? Denn das ist eine der teuresten und zugleich unnötigsten Codestelle, die du präsentiert hast. Diese Tiles musst du nicht bei jeder Pfadsuche erstellen, da sich deine Tiles ja nicht mehr ändern.

Dazu kommt noch, dass du den Pfad für eine Einheit nicht jedes Frame berechnen musst, sondern nur einmal und dieser Pfad kann dann abgelaufen werden. Wenn natürlich jetzt vom Spieler ein neuer Befehl kommt und damit ein neuer Pfad, musst du diesen auch berechnen.
Ich gehe davon aus, dass du eine Methode/Funktion/Codestelle hast in der Benutzereingaben entgegengenommen und verarbeitet werden, in der du das machen kannst.

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

22

09.06.2017, 13:57

Zitat von »equinox«

Hast du denn auch diesen Teil entfernt? Denn das ist eine der teuresten und zugleich unnötigsten Codestelle, die du präsentiert hast. Diese Tiles musst du nicht bei jeder Pfadsuche erstellen, da sich deine Tiles ja nicht mehr ändern.

Das hast du hoffentlich mittlerweile verstanden und umgesetzt.

Zitat von »equinox«

Ich gehe davon aus, dass du eine Methode/Funktion/Codestelle hast in der Benutzereingaben entgegengenommen und verarbeitet werden, in der du das machen kannst.

Genau das ist der Punkt. Du sollst den Pfad nicht beim Spielstart berechnen, da weißt du ja auch noch gar nicht welche Punkte er verbinden soll. Sobald eine Eingabe gemacht wird wird eben ein neuer Pfad berechnet. Aufgrund der Probleme die du hier hast wirkt es so als würdest du dich hier böse überfordern. Es wäre vielleicht keine schlechte Idee erst mal ein simpleres Spiel anzugehen als direkt mit einem RTS zu starten.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Javaist

Frischling

  • »Javaist« ist der Autor dieses Themas

Beiträge: 48

  • Private Nachricht senden

23

09.06.2017, 16:15

Hallo,

ich habe es jetzt. War arbeiten und völlig abgelenkt. Danach war der Kopf wieder frei. Jetzt geht's.
Also ich berechne jetzt die findPath - Methode in der Hauptupdate und übergebe den Pfad dann der Unit-update und verändere die Parameter der findPath - Methode in der Hauptupdate so, dass diese auf die Maus reagieren kann. Und es funzt perfekt.

Das einzige ist jetzt noch die Initialisierung von startx bzw. starty, damit die Einheit interaktiv reagieren kann.

Aber es bleibt trotzdem die Anfangsfrage übrig.


Wie ordne ich das TreeSet anhand der f-Kosten durch Überschreiben der compareTo - Methode?

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

24

09.06.2017, 17:23

Zitat von »Javaist«

Also ich berechne jetzt die findPath - Methode in der Hauptupdate und übergebe den Pfad dann der Unit-update und verändere die Parameter der findPath - Methode in der Hauptupdate so, dass diese auf die Maus reagieren kann. Und es funzt perfekt.

Das heißt? Wird findPath immer noch jeden Frame aufgerufen? Und was ist mit deiner Node Klasse? Erstellst du beim Aufruf von findPath immer noch zig Instanzen davon?
Die zwei Stellen sind deine wirklichen Performance Killer.

Zitat von »Javaist«

Das einzige ist jetzt noch die Initialisierung von startx bzw. starty, damit die Einheit interaktiv reagieren kann.

Dein Pfad soll vermutlich von Spielfigur zu Mausposition gehen. Wird der Pfad beim Mausklick berechnest so solltest du an dieser Stelle die Koordinaten der Maus kennen. Diese rechnest du von Bildschirmkoordinaten in Weltkoordinaten um und hast dein Ziel. Dieser Teil läuft ja vermutlich. Weiterhin musst du an irgendeiner Stelle wissen welche Einheiten aktuell ausgewählt sind. Deren Positionen kannst du abfragen. Ich würde es vermutlich so lösen dass eine Einheit den Input bekommt dass sie sich von ihrem aktuellen Standort zu einem Ziel (X,Y) bewegen soll. Um das zu lösen würde sie bei einem Modul für die Pfadberechnung (möglicherweise über weitere Schichten gekapselt) einen möglichen Pfad anfragen. Hier würde dann Start und Ziel rein gegeben, der Pfad berechnet und zurück gegeben.

Zitat von »Javaist«

Wie ordne ich das TreeSet anhand der f-Kosten durch Überschreiben der compareTo - Methode?

Wenn du hier guckst siehst du dass ein Treeset im Konstruktor einen Comparator mitbekommen kann.

Quellcode

 
1
2
3
4
5
6
7

class NodeComparator implements Comparator<Node>{
 
    @Override
    public int compare(Node n1, Node n2) {
        return n1.f - n2.f;
    }
}

Dies wäre eine mögliche Implementierung von so einem Comparator. Dabei wäre Node die Klasse eines Knotens in deinem Graphen welcher ein Attribut f hat nachdem sortiert wird.

edit: Ich habe grad gesehen im ersten Post schreibst du dass du das unter Umständen schon probiert hast, dass es aber nicht klappt. Falls das mit dem Comparator so nicht klappt dann zeig mal den jeweiligen Code und sag was du mit "nicht funktioniert" meinst. Gibt es zum Beispiel eine Fehlermeldung, ist das Verhalten nicht wie gewünscht oder was genau meinst du.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Javaist

Frischling

  • »Javaist« ist der Autor dieses Themas

Beiträge: 48

  • Private Nachricht senden

25

09.06.2017, 19:13

Also, ich lade das gesamte grid nur noch EINMAL im Konstruktor und der Pfad wird momentan NUR berechnet, wenn ich klicke, was noch nicht so gut ist. Außerdem habe ich die tatsächliche Bewegung der einheiten verbessert.

Das mit dem TreeSet hat sich fast erledigt, denn, das mit dem Comparator bzw compareTo habe ich gecheckt ( ich wusste bereits, dass Treeset im Konstruktor nen comparator zulässt), nur kommt es visuell bei der Pfaderzeugung zu zuckern, das liegt wiederum an der Heuristik ( kann nicht anders sein, denn die Sortierung ist korrekt), die bei mir die Manhatten- Distanz ist (was aber auch reicht, denke ich), bei der direkten ( Pythagoras ) zuckelt es gleich noch mehr.

Das mit der Heuristik ist höhere Mathematik, da reicht mein Gymnasial-Wissen leider nicht ganz, aber ich tue mein bestes, wobei ich die Manhatten-Distanz mit Diagonalen schon Nachvollziehen kann(deswegen nehme ich sie ja auch).

Falls du eine bessere Heuristik kennen solltest, sag mir einfach die Formel, ansonsten weiß ich jetzt auch nicht, was ich machen kann... .

Quellcode

 
1
2
3
4
5

public int heuristic(Node A,Node B) {
        int dx = Math.abs(A.x - B.x);
        int dy = Math.abs(A.y - B.y);
        return dx + dy;
    }


Das mit den startx bzw.stary krieg ich noch hin, aber du glaubst gar nicht wie erleichtert ich war, als die Einheit endlich gelaufen ist.

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

26

09.06.2017, 19:32

Wenn ich das richtig im Kopf habe darf die Heuristik den tatsächlichen Wert nicht überschätzen. Manhatten Distance ist ja jetzt einfach der Abstand auf den einzelnen Achsen addiert. Wenn deine Welt jetzt wie ein Schachfeld aufgebaut ist und du nur vertikal oder horizontal gehen kannst ist das ok, sobald du aber auch diagonal gehen kannst geht das mit MD nicht mehr.
Stell dir vor du hast folgende Welt:
1 2
3 4
Wobei jedes Feld von jedem zugänglich ist. Abstand vertikal und horizontal ist 1, diagonal eben per Pythagoras ausrechenbar. Willst du von Feld 1 zu Feld 4 gibt dir Manhatten Distance den Wert 2. Damit hat sie den tatsächlichen Wert überschätzt. Nimm einfach den euklidschen Abstand. Damit machst du nichts verkehrt.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Javaist

Frischling

  • »Javaist« ist der Autor dieses Themas

Beiträge: 48

  • Private Nachricht senden

27

09.06.2017, 19:33

Nachtrag: Hat sich grad ausgeruckelt ^^.

Javaist

Frischling

  • »Javaist« ist der Autor dieses Themas

Beiträge: 48

  • Private Nachricht senden

28

11.06.2017, 18:53

Hallo nochmal,

also das ding läuft jetzt mit dem immer gleichen startx bzw starty, aber verschiedenen endx bzw. endy werten tadellos.
Das Problem ist nun das Startx. Wenn ich dem den letzten x bzw y wert des Spielers gebe, kommt der heap space fehler, denn er hängt bei der Erzeugung des nächsten pfades, also konkret der Rekonstruktion des pfades. Hab das ganze abgeändert und getestet ( alles was mir einfiel) aber immer der heapspace fehler. Woran kann das denn noch liegen?????? Das letzte x bzw. y nehm ich praktisch wieder als startx bzw starty für den A* her. Aber ohne erfolg... .

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

29

11.06.2017, 19:14

Stichwort Debugger.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Javaist

Frischling

  • »Javaist« ist der Autor dieses Themas

Beiträge: 48

  • Private Nachricht senden

30

13.06.2017, 07:47

Ich finde den Fehler nicht. Er zeigt mir nur an, dass er immer wieder find path aufruft, aber nix findet. Ich vermute, das ist ein ganz simples Problem. Selbst, wenn ich path auf null setzte passiert nix. Wenn man das Programm startet hat man immer das Gefühl der alte Pfad würde immer noch mitberechnet, aber der Debugger ergibt nix. Kein Plan mehr warum?

Werbeanzeige

Ähnliche Themen