spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hallo,

in meinen vorherigen Beiträgen bin ich etwas zu weit vorgeprescht, was so grundsätzliche Sachen betrifft. Deshalb kann es sein, dass ich jetzt eine Frage erneut stelle. Aber das nur so am Rande.

Das mit der Isometrie funktioniert zwar, zumindest teilweise, aber ich möchte doch erst nochmal orthogonal weitermachen.

Mittlerweile ist es mir gelungen, die Knoten für den A* auf die Größe 1x1 zu schrumpfen, was meiner Kenntnis nach der Größe eines Pixels entspricht und für die Bewegung wird der Einheitenposition einfach direkt die Pfadposition zugewiesen. Das läuft auch bei sehr vielen Einheiten, die sich unabhängig voneinander bewegen(jede in eine andere Richtung) ziemlich flüssig (bin stolz auf mich ).

Nun ist das ja alles schön und gut, ABER wie sieht das dann mit der Kollision bzw. nicht begehbaren Hindernissen aus, denn die Klasse Node mit ihren zwei Parametern ist eine Klasse, während ein Pixel ein Pixel ist?

Das Problem ist, dass ich nur zwei Möglichkeiten kenne eine sehr genaue Kollision zu erzielen.

1. Ich erzeuge auf einer Canvas ein BufferedImage, lese von diesem alle Pixel aus, und weise denen dann die jeweiligen Pixel aus den einzelnen Kachelbildern zu, um die Karte zu erzeugen. Das Problem hierbei ist, dass ich nicht nur jede Kachel auslesen müsste, sondern auch irgendwie meine Nodes zu Pixeln, die ja in einem int-Array vorliegen, caste, um dann sagen zu können: Dieses Pixel ist begehbar und ein anderes nicht.

2. Ich erzeuge auf einem JPanel ein Spielfeld aus einzelnen Nodes und erweitere diese zu einer eigenen Pixelklasse usw. .Aber das scheint mir zu aufwendig zu sein, je mehr man darüber nachdenkt.

Der Grund für mein Anliegen ist, dass ich wie in meinen früheren Beiträgen hier im Forum, zwar eine Kollisionsabfrage erfolgreich implementiert habe, aber diese war dann meist ungenau. Entweder blieb irgendwo die Einheit hängen, oder es gab seltsame Überschneidungen bis hin zu unerklärlichen Neupositionierungen der Einheiten, also alles in allem sehr ungenau.

Ich brauch im Prinzip nur eine Art Konzept, wie man A*, Kollisionsabfrage und Welt in Einklang bringt.

Falls mich jemand versteht, bin ich für Vorschläge offen.

MfG

Javaist

Um es nochmal konkret zu sagen:

Meine Frage war doof... .

Es macht ja keinen Sinn das gesamte Knotenspielfeld zur Laufzeit zu malen, auch wenn es ginge die Knoten als Pixel zu definieren,denn dann ruckelt alles ja wie verrückt.

Andererseits habe ich allerdings immer noch keine praktikable Lösung zu meinem Problem gefunden.

Melde mich aber hier wieder wenn ich was habe.

Bis dann.

Ok, ich habe ein aus 1x1 großen Knoten bestehendes grid-Array, das allerdings nicht gemalt werden soll, während Sprites bzw. Tiles aus Pixeln bestehen. Mittlerweile habe ich folgendes geschafft: Ich bin einfach davon ausgegangen, dass jeder Pixel aus meinen Sprite und Tile Bildern genauso groß ist wie meine eigens erzeugten Knoten für den A*. So. Nun habe ich einfach die nichtbegehbaren Kacheln mit TILED komplett als Bild gespeichert und anschließend die nichttransparenten Pixel der gesamten obstacle Map EINMAL mittels getRGB() in einer boolschen Methode, die true zurückgibt, wenn das Pixel nichttransparent ist,eingelesen. Und siehe da das funktionierte. Somit kann man behaupten, das ich sowas ähnliches wie Pixelgenaue Kollision erzielthabe, denn der A* nimmt jedes Pixel der nichtbegehbaren Elemente des Spiels als obstacle und umgeht diese dann dementsprechend. Also das war eig. von Anfang an der Plan, ich habs eig nicht so mit Perfektionismus, aber ich mags halt möglichst exakt.

Also noch zu deiner Antwort nochmal.

Das was du mir empfiehlst ist mir alles schon bekannt und habe es auch implementiert. Also BoundingBoxen und irgendwelche Kreisshapes, die dann (mir leider zu unpräzise) die obstacles darstellen und für die Kollisionen verwendet werden. Das ist ja auch richtig so. Aber deswegen stelle ich ja meine Frage auch so komisch mit ein Punkt ist kein Pixel. Ich versuche eben auch ein bißchen unkonventionellere Herangehensweisen auszuprobieren.

ABER: Was ich eingangs ganz vergessen habe zu erwähnen ist, das ich versuche eine Art Strategiespiel in 2D-Grafik zu entwickeln. HHHH.
Man sollte hier natürlich schon sagen was man überhaupt machen will.

Das Thema hätte sich damit eigentlich erledigt. Das einzige, was halt nicht erledigt ist, ist meine Annahme, das ein Pixel genau 1x1 groß ist.

Nun habe ich aber noch eine Frage:

Wie wird in Spielen wie Starcraft 2 o.ä. die Ziellinien vom Startknoten der Einheit zum Zielknoten ermittelt?

Das ist keine triviale Frage Vorsicht hier. Mir ist durchaus klar, dass ich von der x-bzw. y-Position eine simple Linie Zeichnen kann. Das Problem, dass ich aber damit habe ist, dass der berechnete Weg des A* ungleich zur dieser Ideallinie ist.

Und hier meine eigentliche neue Frage: Wie berechne ich diese eben beschriebene Ideallinie nur durch den A*? Denn das wäre optimal für mich. Nur komme ich da nicht wirklich weiter. Ich werde mir nun die Algorithmen zum Lininzeichnen anschauen (Bresenham Line usw.), aber vielleicht hat hier jemand ne bessere Idee?

Meine Vorstellung ist es dabei, wenn ich eine Einheit anklicke und diese dann irgendwo auf der Karte hinschicke, wird mittels A* der direkte Weg zum Ziel(Luftlinie) angezeigt und eben dank des A* , jedes obstacle auf der Ideallinie umgangen. Ich hoffe soweit klar.

Bisher erzeuge ich mit meinem A* eine Linie mit einem leichten Knick und ich weiss leider nicht wie man den rausbekommt. Zum einen kann das am f-Wert liegen zum anderen an der Sortierung der openList oder ich muss noch was am Algorithmus selbst ergänzen. Bin leider etwas faul zurzeit und möchte eig keinen Wertetabelleabend machen.

Wäre für Hilfe dankbar.

Gruß Javaist

Nachtrag: Sorry ich habe deinen Vorschlag nicht ganz verstanden gehabt. Ich habe gerade geschaut was Navigations Meshes sind und wie das funktioniert. Sehr interessant wirklich. Es ging mir nur um die Kollision beweglicher Einheiten mit der Umwelt nichts mehr. Und das habe ich jetzt für mich somit erledigt. Trotzdem danke.

Meine neue Frage ist aber noch aktuell.

Gruß Javaist

Ok sehr gut du hast mich verstanden. Also zu Deiner ersten Frage:
Ich mache das so, dass wenn man auf ein Obstacle der Umwelt klickt, wird in meinem A* trotzdem der bestmögliche weg dorthin berechnet, sodass die Einheit praktisch dort zum stehen kommt, wo sie am bestmöglichen hinkommt um das Ziel zu erreichen, also das habe ich schon implementiert.

Und ja, prinzipiell hast du mit deiner letzten Vermutung in deiner Antwort Recht, denn mein A* berechnet den richtigen Weg(ich habe mich sehr lange damit beschäftigt) und eigentlich könnte ich das so lassen und einfach eine einfache Linie als Zielindikator zeichnen und mit der Abweichung von ca 30 Grad leben. ABER exakt isses natürlich dann doch nicht. Als Heuristik nehme ich einfach die euklidsche Distanz. Im Prinzip möchte ich halt einfach nur erreichen, das die euklidsche Distanz zwischen start und Ziel unter Berücksichtigung der obstacles als Linie gezeichnet wird(also den Zielindikator). Ich hatte ähnliche Gedanken wie du was du als "smoothen" bezeichnest. Aber nimms nicht persönlich ich halte nicht so viel von mathematischem "herumgedoktore". Außerdem wäre das Ergebnis dann zwar etwas besser aber halt nicht wirklich exakt. Vielleicht könnte ich so bis zu 15 Grad gutmachen aber wahrscheinlich nicht mehr.

Screenshot: