Pathfinding 3D - benötige ein Grid

Übersicht

BlitzBasic

Blitz3D

	mpreu Betreff: Pathfinding 3D - benötige ein Grid	Do, Jul 25, 2013 11:12 Antworten mit Zitat
Wie macht man dieses Grid, also berechenbare Feld fürs Pathfinding wenn ich einen 3D Level habe. Müsste das ja irgendwie idealerweise in quadrate bzw. felder einteilen.

mpreu

Betreff: Pathfinding 3D - benötige ein Grid

Do, Jul 25, 2013 11:12
Antworten mit Zitat

Wie macht man dieses Grid, also berechenbare Feld fürs Pathfinding wenn ich einen 3D Level habe.
Müsste das ja irgendwie idealerweise in quadrate bzw. felder einteilen.

	Xeres Moderator	Do, Jul 25, 2013 11:17 Antworten mit Zitat
Da musst du genauer werden, wie dein Level momentan aufgebaut ist. Normalerweise startet man mit Feldern, wenn man weiß, dass man später Pathfinding implementieren will. Es gibt aber natürlich auch Möglichkeiten, Wegpunkte/Bereiche ohne Gitter zu definieren.
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Do, Jul 25, 2013 11:17
Antworten mit Zitat

Da musst du genauer werden, wie dein Level momentan aufgebaut ist. Normalerweise startet man mit Feldern, wenn man weiß, dass man später Pathfinding implementieren will. Es gibt aber natürlich auch Möglichkeiten, Wegpunkte/Bereiche ohne Gitter zu definieren.

Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

	mpreu	Do, Jul 25, 2013 11:20 Antworten mit Zitat
Eine planer Level mit Gebäuden drauf. Bäume etc. kann man dafür denke ich ja weglassen. Das Prinzip vom Pathfinding hab ich soweit verstanden, aber ich müsste das ja nun auch irgendwie auf die map umsetzen. Bzw. wie ich diese Wegepunkte setze und dann für die Berechnung nehme.

mpreu

Do, Jul 25, 2013 11:20
Antworten mit Zitat

Eine planer Level mit Gebäuden drauf.
Bäume etc. kann man dafür denke ich ja weglassen.

Das Prinzip vom Pathfinding hab ich soweit verstanden, aber ich müsste das ja nun auch irgendwie auf die map umsetzen.

Bzw. wie ich diese Wegepunkte setze und dann für die Berechnung nehme.

	feider ehemals "Decelion"	Do, Jul 25, 2013 15:28 Antworten mit Zitat
Du kannst z.B. ein gleichmäßges Gitter aus Wegpunkten über deine Map legen und dann die nicht begehbaren entfernen. Andere Ansätze oder Vertiefung hierzu: http://en.wikipedia.org/wiki/Navigation_mesh http://aigamedev.com/open/revi...ode-graph/ Wegfindung/KI allgemein: http://digestingduck.blogspot.de/

feider

ehemals "Decelion"

Do, Jul 25, 2013 15:28
Antworten mit Zitat

Du kannst z.B. ein gleichmäßges Gitter aus Wegpunkten über deine Map legen und dann die nicht begehbaren entfernen.

Andere Ansätze oder Vertiefung hierzu:

http://en.wikipedia.org/wiki/Navigation_mesh
http://aigamedev.com/open/revi...ode-graph/

Wegfindung/KI allgemein:

http://digestingduck.blogspot.de/

	mpreu	Fr, Jul 26, 2013 11:42 Antworten mit Zitat
in form eines meshes oder wie? oder soll ich die einzelnen punkte einfach speichern mit den koordinaten. das prinzip im großen ganzen hab ich ja verstanden, nur an der praktischen anwendung hapert es.

mpreu

Fr, Jul 26, 2013 11:42
Antworten mit Zitat

in form eines meshes oder wie?
oder soll ich die einzelnen punkte einfach speichern mit den koordinaten.
das prinzip im großen ganzen hab ich ja verstanden, nur an der praktischen anwendung hapert es.

	Xeres Moderator	Fr, Jul 26, 2013 12:30 Antworten mit Zitat
Für das Pathfinding muss man keine Geometrie erstellen, nur die Welt über Koordinaten einteilen. Deine Levelbeschreibung ist aber auch nicht so genau, wie man sie sich wünschen würde - warum zum Beispiel willst du Bäume auslassen? Stehen die Gebäude frei herum, oder orientieren die sich schon an einem Gitter? Gibt es bewegliche Hindernisse? Gibt es nur eine Oberfläche mit verschiedenen Höhen, oder mehrere Ebenen z.B. in Gebäuden?
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Fr, Jul 26, 2013 12:30
Antworten mit Zitat

Für das Pathfinding muss man keine Geometrie erstellen, nur die Welt über Koordinaten einteilen.
Deine Levelbeschreibung ist aber auch nicht so genau, wie man sie sich wünschen würde - warum zum Beispiel willst du Bäume auslassen? Stehen die Gebäude frei herum, oder orientieren die sich schon an einem Gitter? Gibt es bewegliche Hindernisse? Gibt es nur eine Oberfläche mit verschiedenen Höhen, oder mehrere Ebenen z.B. in Gebäuden?

	mpreu	Fr, Jul 26, 2013 12:46 Antworten mit Zitat
Ich würde für den Anfang nur eine Höhe nehmen und die Gebäude werden über Koordinaten plaziert. Aber es gibt eben noch keinen Koordinatensystem welches man fürs Pathfinding nehmen könnte. Wie erstellt man ein solches in Abhängigkeit der "Begehbarkeit"? Ich könnte natürlich auch einfach solche Wegpunkte von Hand speichern und diese dann für die Berechnung nehmen.

mpreu

Fr, Jul 26, 2013 12:46
Antworten mit Zitat

Ich würde für den Anfang nur eine Höhe nehmen und die Gebäude werden über Koordinaten plaziert.
Aber es gibt eben noch keinen Koordinatensystem welches man fürs Pathfinding nehmen könnte.
Wie erstellt man ein solches in Abhängigkeit der "Begehbarkeit"?
Ich könnte natürlich auch einfach solche Wegpunkte von Hand speichern und diese dann für die Berechnung nehmen.

	DAK	Fr, Jul 26, 2013 18:09 Antworten mit Zitat
Also per Hand geht eh klar. Automatisch könntest du es so regeln: Du setzt zuerst ein Raster an Wegpunkten durch die Welt. Dann überprüfst du im ersten Schritt ob Wegpunkte in z.B. nicht begehbaren Häusern oder Wänden sind. Die lässt du dann wegfallen. Ist dir das zu komplex zu überprüfen, dann kannst du das auch mit dem nächsten Schritt vereinen. Als Nächstes musst du überprüfen, von welchem Wegpunkt du zu welchem anderen Wegpunkt kommst. Dazu machst du einen LinePick von jedem Wegpunkt zu jedem Nachbaren und speicherst dir welche Wegpunkte man von dort erreichen kann. Hast du den Schritt mit dem Überprüfen ob der Wegpunkt an einem gültigen Ort ist ausgelassen, dann muss der LinePick in beide Richtungen erfolgen. Folgendes Beispiel zum Erläutern: Code: [AUSKLAPPEN] [EINKLAPPEN] W \| P W und P sind Wegpunkte. Dieser Strich dazwischen ist ein Face von z.B. der Außenwand eines Hauses. W befindet sich innerhalb des Hauses, P nicht. Das Face zwischen W und P ist nur von einer Richtung aus sichtbar, nämlich von P nach W. Schaut man von W aus nach draußen, dann ist es unsichtbar (Backface Culling). Deswegen den Doppelpick, und wenn einer der beiden Picks nicht durchgeht, dann gibt es keine Verbindung. Als Nächstes kann man alle Wegpunkte entfernen, die keine Verbindungen haben. Jetzt bleiben nur noch Wegpunkte übrig, die gemeinsam innerhalb eines unbegehbaren Gebiets sind, also z.B. alle in einem großen unbegehbaren Haus sind. Dazu startest du bei einem Wegpunkt, von dem du weißt, dass er begehbar ist (z.B. der Spawnpunkt), und rennst Floodfill-artig über alle anderen Wegpunkte. Alle Wegpunkte, die von diesem Floodfill nicht erreicht werden, werden auch entfernt. Übrig bleiben alle gültigen, erreichbaren Waypoints sowie ihre Verbindungen. Diese Verbindungen müssen dann noch gewichtet werden, je nach ihrer Länge und schon bist du fertig für den Wegfindungsalgo. Eventuell könntest du noch vor dem Gewichten durch alle Wegpunkte durchlaufen und überprüfen, ob sie sich eventuell sehr nahe an einer Wand befinden, und sie passend verschieben. Dazu noch mal etwas ASCII-Art um das zu verdeutlichen: Code: [AUSKLAPPEN] [EINKLAPPEN] \|P \| Die Striche sind Wände, P ist der Wegpunkt. Dieser Wegpunkt ist durch das reine Rastern ziemlich nahe an die linke Wand gekommen, während nach rechts noch viel Platz ist. Das sorgt dafür, dass NPCs sich beim Vorbeilaufen immer an die linke Wand drücken. Ist das nicht gewollt, muss man hald schauen, wie weit die nächsten Wände (und Wegpunkte) von dem Wegpunkt sind, und den Wegpunkt so verschieben, dass er möglichst ähnlich weit von allen Wänden (und anderen Wegpunkten) weg ist. Code: [AUSKLAPPEN] [EINKLAPPEN] \| P \|
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Fr, Jul 26, 2013 18:09
Antworten mit Zitat

Also per Hand geht eh klar.
Automatisch könntest du es so regeln: Du setzt zuerst ein Raster an Wegpunkten durch die Welt. Dann überprüfst du im ersten Schritt ob Wegpunkte in z.B. nicht begehbaren Häusern oder Wänden sind. Die lässt du dann wegfallen. Ist dir das zu komplex zu überprüfen, dann kannst du das auch mit dem nächsten Schritt vereinen.
Als Nächstes musst du überprüfen, von welchem Wegpunkt du zu welchem anderen Wegpunkt kommst. Dazu machst du einen LinePick von jedem Wegpunkt zu jedem Nachbaren und speicherst dir welche Wegpunkte man von dort erreichen kann. Hast du den Schritt mit dem Überprüfen ob der Wegpunkt an einem gültigen Ort ist ausgelassen, dann muss der LinePick in beide Richtungen erfolgen. Folgendes Beispiel zum Erläutern:

Code: [AUSKLAPPEN]

W | P

W und P sind Wegpunkte. Dieser Strich dazwischen ist ein Face von z.B. der Außenwand eines Hauses. W befindet sich innerhalb des Hauses, P nicht. Das Face zwischen W und P ist nur von einer Richtung aus sichtbar, nämlich von P nach W. Schaut man von W aus nach draußen, dann ist es unsichtbar (Backface Culling).
Deswegen den Doppelpick, und wenn einer der beiden Picks nicht durchgeht, dann gibt es keine Verbindung.

Als Nächstes kann man alle Wegpunkte entfernen, die keine Verbindungen haben.

Jetzt bleiben nur noch Wegpunkte übrig, die gemeinsam innerhalb eines unbegehbaren Gebiets sind, also z.B. alle in einem großen unbegehbaren Haus sind.
Dazu startest du bei einem Wegpunkt, von dem du weißt, dass er begehbar ist (z.B. der Spawnpunkt), und rennst Floodfill-artig über alle anderen Wegpunkte. Alle Wegpunkte, die von diesem Floodfill nicht erreicht werden, werden auch entfernt.

Übrig bleiben alle gültigen, erreichbaren Waypoints sowie ihre Verbindungen. Diese Verbindungen müssen dann noch gewichtet werden, je nach ihrer Länge und schon bist du fertig für den Wegfindungsalgo.

Eventuell könntest du noch vor dem Gewichten durch alle Wegpunkte durchlaufen und überprüfen, ob sie sich eventuell sehr nahe an einer Wand befinden, und sie passend verschieben. Dazu noch mal etwas ASCII-Art um das zu verdeutlichen:

Code: [AUSKLAPPEN]

|P |

Die Striche sind Wände, P ist der Wegpunkt. Dieser Wegpunkt ist durch das reine Rastern ziemlich nahe an die linke Wand gekommen, während nach rechts noch viel Platz ist. Das sorgt dafür, dass NPCs sich beim Vorbeilaufen immer an die linke Wand drücken. Ist das nicht gewollt, muss man hald schauen, wie weit die nächsten Wände (und Wegpunkte) von dem Wegpunkt sind, und den Wegpunkt so verschieben, dass er möglichst ähnlich weit von allen Wänden (und anderen Wegpunkten) weg ist.

Code: [AUSKLAPPEN]

| P |

Gewinner der 6. und der 68. BlitzCodeCompo

Übersicht

BlitzBasic

Blitz3D

Nach Oben

BlitzBasic Portal

Pathfinding 3D - benötige ein Grid

Betreff: Pathfinding 3D - benötige ein Grid