Pathfindung - Ideen und Alternativen

Übersicht

Sonstiges

Gamedesign

	feider ehemals "Decelion" Betreff: Pathfindung - Ideen und Alternativen	So, Jul 28, 2013 15:50 Antworten mit Zitat
Moin Nachdem wir ja jetzt dieses schöne Unterforum zum Thema Gamedesign haben und ich erst kürzlich einen passenden Thread sah, möchte ich eine Ideensammlung zum Thema Pathfinding ins Leben rufen. Die meisten Nutzer dieses Forums sind wahrscheinlich damit vertraut, ein A* auf ein zweidimensionales, gekacheltes Feld anzuwenden. Im 3D-Bereich nutzt man dann einfach ein Gitter aus Wegpunkten. Gerade im dreidimensionalen Bereich und im nicht-tilemap-basierten Bereich ist dies allerdings nicht zwangsläufig das Beste: http://www.ai-blog.net/archives/000152.html <- Dieser Artikel ist es meiner Meinung nach definitiv wert, gelesen zu werden. Die hier vorgestellte Methode Verwendet kein Gitter aus Wegpunkten, sondern einige wenige sehr vereinfachte Wegpunkte zusammen mit Flächen. Dies sorgt für weitaus natürlichere Bewegungen, schnellere Berechnungen und weniger Speicherbedarf. Welche Ansätze verwendet ihr normalerweise, auf welche Probleme stoßt ihr dabei? Gruß feider

feider

ehemals "Decelion"

Betreff: Pathfindung - Ideen und Alternativen

So, Jul 28, 2013 15:50
Antworten mit Zitat

Moin

Nachdem wir ja jetzt dieses schöne Unterforum zum Thema Gamedesign haben und ich erst kürzlich einen passenden Thread sah, möchte ich eine Ideensammlung zum Thema Pathfinding ins Leben rufen.

Die meisten Nutzer dieses Forums sind wahrscheinlich damit vertraut, ein A* auf ein zweidimensionales, gekacheltes Feld anzuwenden. Im 3D-Bereich nutzt man dann einfach ein Gitter aus Wegpunkten.

Gerade im dreidimensionalen Bereich und im nicht-tilemap-basierten Bereich ist dies allerdings nicht zwangsläufig das Beste: http://www.ai-blog.net/archives/000152.html <- Dieser Artikel ist es meiner Meinung nach definitiv wert, gelesen zu werden.
Die hier vorgestellte Methode Verwendet kein Gitter aus Wegpunkten, sondern einige wenige sehr vereinfachte Wegpunkte zusammen mit Flächen. Dies sorgt für weitaus natürlichere Bewegungen, schnellere Berechnungen und weniger Speicherbedarf.

Welche Ansätze verwendet ihr normalerweise, auf welche Probleme stoßt ihr dabei?

Gruß
feider

	DAK	So, Jul 28, 2013 18:26 Antworten mit Zitat
Handgesetzte Wegpunkte mit Radien. Die Einheit sucht sich auf dem Weg zum nächsten Wegpunkt einen beliebigen Punkt im Radius (mit leicht höherer Wahrscheinlichkeit zum Mittelpunkt hin) aus, und bewegt sich dort hin. Wenn der Punkt erreicht wird, dann zählt das als Wegpunkt erreicht. Dazu wird die momentane Bewegungsrichtung graduell zur Zielrichtung umgelenkt: Code: [AUSKLAPPEN] [EINKLAPPEN] tatsächlicherBewegungsvektor = letzterBewegungsvektorSkalar + EinheitsvektorRichtungZielGeschwindigkeit*(1-Skalar) Für Skalar gilt dabei: 0<Skalar<1, meist liegt Skalar bei 0.99 oder so. Das sorgt für flüssigere Bewegungen. Ist sicher nicht die beste Lösung, aber das Beste, was ich bis jetzt gemacht habe.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

So, Jul 28, 2013 18:26
Antworten mit Zitat

Handgesetzte Wegpunkte mit Radien. Die Einheit sucht sich auf dem Weg zum nächsten Wegpunkt einen beliebigen Punkt im Radius (mit leicht höherer Wahrscheinlichkeit zum Mittelpunkt hin) aus, und bewegt sich dort hin. Wenn der Punkt erreicht wird, dann zählt das als Wegpunkt erreicht.

Dazu wird die momentane Bewegungsrichtung graduell zur Zielrichtung umgelenkt:

Code: [AUSKLAPPEN]

tatsächlicherBewegungsvektor = letzterBewegungsvektor*Skalar + EinheitsvektorRichtungZiel*Geschwindigkeit*(1-Skalar)

Für Skalar gilt dabei: 0<Skalar<1, meist liegt Skalar bei 0.99 oder so.

Das sorgt für flüssigere Bewegungen.

Ist sicher nicht die beste Lösung, aber das Beste, was ich bis jetzt gemacht habe.

Gewinner der 6. und der 68. BlitzCodeCompo

	Kruemelator	So, Jul 28, 2013 22:01 Antworten mit Zitat
Ich habe mal eine Variante genutzt bei der die Welt aus Hindernissen besteht die ihrerseits aus Vielecken bestehen. Es wird eine Linie von der aktuellen Position der Figur zur gewünschten gezogen. Wenn die Linie die Seite eines der Vierecke schneidet, wird einmal links herum und einmal rechtsherum gegangen (auf den Seiten des Vielecks entlang, solange bis sich das Lösen vom Vieleck schneller zum Ziel führt). Jenachdem welcher Weg kürzer ist wird sich bewegt. Ich hoffe es war verständlich sonst würde ich ein Bild zum verdeutlichen malen.

Kruemelator

So, Jul 28, 2013 22:01
Antworten mit Zitat

Ich habe mal eine Variante genutzt bei der die Welt aus Hindernissen besteht die ihrerseits aus Vielecken bestehen. Es wird eine Linie von der aktuellen Position der Figur zur gewünschten gezogen. Wenn die Linie die Seite eines der Vierecke schneidet, wird einmal links herum und einmal rechtsherum gegangen (auf den Seiten des Vielecks entlang, solange bis sich das Lösen vom Vieleck schneller zum Ziel führt). Jenachdem welcher Weg kürzer ist wird sich bewegt. Ich hoffe es war verständlich sonst würde ich ein Bild zum verdeutlichen malen.