spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Die Kosten kannst du prinzipiell modellieren wie du möchtest, hauptsache sie passen zu deiner Heuristik. Damit meine ich, dass es keinen Sinn macht zu sagen die Kosten von einem Tile zu einem Nachbarn betragen immer 20, aber die Heuristik berechnet die euklidische Distanz anhand der X und Y Koordinaten und liefert entsprechend einen verhältnismäßig zu geringen Schätzwert.

Um mal auf die eingeworfenen "Dynamischen Hindernissen" einzugehen, da gibt es eine modifizierte Variante des A*-Algorithmus, der häufig D* genannt wird.

Dein Problem ist immer noch dass du deinen Graphen bei jedem Aufruf vom A* neu berechnest. Das ist natürlich Mist und sollte einfach vorher nur ein mal passieren. Das kann jetzt in irgendeinem Konstruktor sein, oder aber auch irgendwo anders. Wichtig ist dass der Graph ein mal erstellt wird und nicht jedes mal aufs neue. Ich hab dir ja erklärt wie du dir deine Klasse dafür komplett sparen könntest. Wenn du das nicht benutzen willst dann zieh den nötigen Code zumindest aus dem A* raus. Wenn du dabei Probleme bekommst musst du den Debugger benutzen. Wir kennen zu wenig von deinem Code um das Problem aktuell zu erkennen. So wie du es beschreibst dürfte das Problem nicht auftauchen. Also schnapp dir den Debugger und guck wo und warum das Problem auftritt.

Er muss schon in irgendeiner Form die gesamte Welt bekommen. Ansonsten kann er sie ja nicht suchen.

Zitat von »Javaist«

Falls du Skype hast findest du mich als "Thomas Jagust" Garfield Symbol. R uf einfachan bin heute ganzen tag on.

Da hab ich keine Zeit für und an sich haben wir ja extra das Forum. Ich hab ja an sich schon erklärt worum es geht. Du machst deine TielMap Klasse um den Graphen darzustellen. Anstatt das alles zu machen kannst du den impliziten Graphen benutzen den du schon hast. Soll heißen du hast deine Map Daten, du weißt welche Nachbarfelder es zu einem Feld gibt und du weißt ob so ein Feld begehbar ist oder eben nicht. Das ist alles was du im A* an Wissen brauchst. Ließ dir meine vorherigen Antworten noch mal durch.
Wenn du unbedingt bei deiner extra Klasse bleiben willst und alle Daten doppelt haben möchtest dann machst du das nicht in A* sondern ein einziges mal im gesamten Programm, speicherst diese ganzen Daten ab und benutzt sie im Algorithmus einfach nur noch. Nicht mehr und nicht weniger. Dabei sollst du nicht nur ein einzelnes Feld erzeugen sondern eben alle. Ansonsten kann es ja nicht funktionieren. Da liegt ja dein aktuelles Problem und das hast du ja schon selbst so beschrieben. Vielleicht hast du einfach grad ein Brett vorm Kopf und eine Pause in der du den Kopf frei kriegst hilft weiter.

Jein. A* ist ein Algorithmus auf einem Graphen. Ein Graph besteht normalerweise aus einer Menge von Knoten und einer Menge von Kanten zwischen diesen Knoten. Bei deiner Karte entspricht jetzt jede Begehbare Zelle einem Knoten in diesem Graphen. Sind zwei dieser begehbaren Zellen direkt nebeneinander so gibt es eine Kante zwischen diesen beiden Knoten im Graphen. Mit implizit meine ich jetzt dass du deine Map an sich schon besitzt. sagen wir du möchtest einen Knoten expandieren. Dein knoten ist irgendeine Zelle auf deiner Karte. Du weißt welche Nachbarzellen es zu dieser Zelle gibt. Jetzt betrachtest du von diesen Nachbarzellen nur diejenigen die begehbar sind. Das sind deine von deinem aktuellen Knoten aus erreichbaren Knoten.
Das hat nichts damit zutun ob dein Algorithmus jetzt in einer statischen Klasse ist oder nicht. Das macht überhaupt keinen Unterschied. Dein Problem ist dass du aktuell beim Aufruf vom A* für jedes Feld auf deiner Karte ein neues Objekt erstellst. Nehmen wir mal an deine Karte bestünde aus 500 Zellen. Dann würde ein Aufruf von A* 500 Objekte erstellen die dir überhaupt keine neue Information liefern. Am Ende werden diese alle wieder verworfen. Überlegen wir mal was passiert wenn du 30 Einheiten hast die gleichzeitig den Weg berechnen, dann hättest du 30 * 500 Objekte die erstellt und wieder gelöscht werden. löschen ist in diesem Fall allerdings relativ. Der Garbage Collector erledigt das für dich und so weißt du nicht mal ob diese direkt am Ende oder irgendwann später gelöscht werden. Du pumpst deinen Speicher unglaublich voll.
Zusätzlich weiß ich nicht in wie fern du den Algorithmus aktuell eingebaut hast. Ob du den Weg ein mal berechnest und dann von der Einheit ablaufen lässt bis es einen neuen Weg gibt oder aber den Weg jeden Frame neu berechnen lässt. Du sagst dein Spiel wird langsam weshalb ich vermute dass du letzteres tust. Dadurch erzeugst du am laufenden Band unglaublich viele Objekte die sofort wieder zerstört werden was am Ende unglaublich viel unnötige Arbeit ist. Um solche Probleme zu lösen gibt es Ansätze, in deinem Fall heißt der Ansatz aber eigentlich dass du den ganzen Kram raus wirfst.

Also noch mal kurz. Du hast eine einzelne Karte. Bei dieser musst du die Nachbarn von Zellen bestimmen können. Außerdem musst du prüfen können ob eine Zelle begehbar ist. Wenn eine Einheit von A nach B wandern soll dann ruft sie ein einziges mal den Algorithmus auf welcher ihr einen Pfad zurück gibt. Ab jetzt läuft sie einfach diesen Pfad ab bis sie ein neues Ziel bekommt, dann wird A* eben neu aufgerufen. Ob A* jetzt eine Methode, in einer Klasse oder in einer statischen Klasse steckt macht erst mal keinen Unterschied.