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

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

31

13.06.2017, 09:21

Dann steppe doch mal langsam durch und schau, warum findPath immer wieder aufgerufen wird.
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]

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

32

13.06.2017, 11:33

Zitat von »Javaist«

aber der Debugger ergibt nix.

In irgendeiner Form muss der Debugger ja helfen. Du kannst dein Programm ja Schritt für Schritt durchlaufen und dabei muss ja dann auch auffallen wo das Problem liegt. Wie BlueCobold schon sagt, guck erst mal ob und warum findPath immer wieder aufgerufen wird. Mit deinen Informationen können wir ansonsten relativ wenig anfangen.

Zitat von »Javaist«

Selbst, wenn ich path auf null setzte passiert nix.

Was das heißen soll kann uns ja gar nicht klar sein. Wir kennen weder deinen Code, noch das was er in so einem Fall tun soll, noch was er aktuell tut. "Nix" ist ja keine Beschreibung ;) An sich können wir uns aber auch nicht hinsetzen und dein komplettes Programm debuggen. Deshalb musst du das tun. Aber am Ende hast du dann eben nicht nur dein Problem gelöst sondern kannst vernünftig debuggen.
„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.“

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

33

13.06.2017, 11:42

Der Debugger findet nicht auf magische Weise Bugs und entfernt sie (wie der Name es nahelegen könnte), sondern bietet dir eine Palette von Werkzeugen (Programm Schritt für Schritt ausführen, das Programm mit Breakpoints an bestimmten Stellen anhalten, Werte von Variablen inspizieren und verändern, ...), mit denen du selbst effektiv auf Fehlersuche gehen kannst.
David Scherfgens Website | Konzentrationstest Polizei

Javaist

Frischling

  • »Javaist« ist der Autor dieses Themas

Beiträge: 48

  • Private Nachricht senden

34

17.06.2017, 12:55

Hallo,
uff habs Endlich geschafft, allerdings war ein Haufen Glück dabei, denn ich hab nen Gedankengang verfolgt und sofort danach gehandelt (im Code), kurz bevor ich ferig war dachte ich ne das kanns doch nicht sein. Doch ich habs trotzdem ausgeführt und siehe da jetzt passt es.

Also, um es nochmal zusammenzufassen,

1. Grid komplett einmal in den Konstruktor packen geht.
2. Überprüfung ob begehbar oder nicht geht auch.
3. Einheiten zur Laufzeit steuern (wie in den Spielen üblich geht auch)

Jetzt ruckelt es erst ab ca 120 Einheiten ein wenig ab ca. 190 geht nichts mehr.

Aber wie ich eingangs schon erwähnt hatte, ging es ja eig. um das TreeSet usw. ich hatte kurzzeitig den A* mit dem TreeSet am Laufen, doch wenn ich das jetzt implementiere rührt sich gar nichts mehr. Momentan nehm ich für die openList eine ArrayList. Nach zahlreichen gescheiterten Versuchen , melde ich mich hier nochmal.

Als das mit dem TreeSet funktionierte, habe ich einzelne x bzw y Werte als Parameter für den A* entgegengenommen und mit diesen dann abhängig vom Grid den start bzw end Knoten durch den Algorithmus gejagt, außerdem habe ich als Bedingung für das Ende den direkten Vergleich also current == end verwendet. Damit ging das mit dem TreeSet.

Jetzt nehme übergebe ich einzelne Knoten an die findPath, prüfe aber current.x == end.x &&... ,sobald ich jetzt aber ein TreeSet verwende klappt das ganze nicht mehr und ich weiss halt nicht warum das so ist.

So wie ich dabei meinen Debugger verstanden habe, wird das f mit dem compareTo nicht richtig oder gar nicht berechnet. Jetzt habe ich ein bisschen rumexperimentiert mit dem compareTo aber ohne Erfolg.

Was genau ist beim TreeSet im Gegensatz zu einer ArrayList eigentlich anders?

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

35

17.06.2017, 13:20

Bevor du versuchst zu optimieren wäre es sinnvoll zu gucken was du warum machen möchtest. In einer Baumstruktur lässt sich effizienter suchen als in einer Liste. Bei A* hast du Knoten in einer OpenList und wählst den Knoten mit den günstigsten Kosten als nächsten Knoten für die Untersuchung aus. Das heißt diese OpenList sollte sich einigermaßen günstig befüllen bzw Elemente aus ihr löschen lassen. Wenn die Elemente sortiert wären wäre das zum Beispiel extrem hilfreich. Anstatt das jetzt hier alles selbst auszuführen möchte ich einfach auf Wikipedia verweisen. Das sollte für den Anfang schon weiter helfen.
„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.“

TypeOverride

Treue Seele

Beiträge: 268

  • Private Nachricht senden

36

18.06.2017, 03:51

Zitat von »Javaist«


Was genau ist beim TreeSet im Gegensatz zu einer ArrayList eigentlich anders?


Container Klassen haben allgemein unterschiedle Performance, wenn es um das Einfügen von Elementen, vom Löschen von Elementen, oder dem Zugriff von Elemente geht. Wenn du viele Sachen einfügst dann wählt man eine Container-Klasse die das effizient macht. Will man schnelleres Löschen, dann eine andere zb. Und etc. Die Datenstruktur hinter den Operationen ist unterschiedlich. Über Iteratoren lässt sich die Datenstruktur iterieren und man kann ohne den Code zu verändern die Container-Klasse im Nachhein besser wechseln.

Es gibt verschiedene Typen von Container-Klassen. Set, Map, Stack, Queue, List. (Das sollten die abstrakten sein) Konkrete sind dann ArrayList, HashMap ...

Eine Set bedeutet eine Menge (auf Deutsch). Und nach der Mengenlehre, sind alle Elemente in dem Container gleichberechtigt. Die Reihenfolge der Elemente hat somit keine Bedeutung und es kann auch sein, dass man sie nicht in der Reihenfolge rausbekommt, wie man sie reingetan hat. Zudem können Elemente nicht doppelt drin sein. Zb "a", "b", "c", und nochmal "b" rein würde bedeuten er überschreibt den alten "b".

Die Liste ist dort ein wenig zugänglicher für die Meisten. Ich denke du arbeitest erstmal allgemein mit ArrayList. Da kannst du mehrere Elemente drin abspeichern die die selbe Reference haben. Sie ist sehr einfach zu bedienen. Und später guckst du wie du es optimierst mit Container-Klassen die besser geeignet sind.

Werbeanzeige

Ähnliche Themen