Pathfinding im Weltraum

Übersicht

Sonstiges

Smalltalk

	FBI-blitz Betreff: Pathfinding im Weltraum	Sa, Jul 07, 2007 20:04 Antworten mit Zitat
Hi, das ist jetzt mal ne theoretische Frage, war mir nicht ganz sicher, ob das hier in den Off Topic-Bereich gehört... ich hoff mal Also, meine Frage, der Titel sagt es schon, ist, wie ihr Pathfinding in einem 3D-Space-Shooter realisieren würdet. Es gibt ja keine Wände/Straßen/Gänge oder irgendwas, an das sich der Computer halten muss. Im Prinzip kann er ja einfach geradeaus fliegen. Dennoch kann irgendetwas im Weg sein, etwa ein anderes Raumschiff, was ja auch nicht immer vorherzusehen ist. Diesen Gegenständen/Objekten, die den weg eventuell bversperren könnten, msus man ausweichen. Aber wie würdet ihr soetwas realisieren? A*-Pathfinding wäre ein wenig Overkill, schätze ich. Freue mich auf Denkanstöße und Tipps
Computer 1: AMD Athlon64 3500+ \| nVidia GF 7900GT \| 1024 MB DDR-RAM \| ASUS A8N-SLI Preimium \| 250 GB SATA 2 \|\| WindowsXP \| Blitz3D \| Blitz+ Computer 2: AMD AthlonXP 2400+ \| ATI Radeon 9500 \| 512 MB DDR-RAM \| MSI K7N2 \| 80 GB IDE \| 160 GB IDE \|\| WindowsXP \| Blitz3D \| Blitz+ Computer 3: Intel Pentium MMX \| onBoard-Grafik \| 32 MB RAM \| 1 GB IDE \|\| Windows 98 SE \| Blitz+

FBI-blitz

Betreff: Pathfinding im Weltraum

Sa, Jul 07, 2007 20:04
Antworten mit Zitat

Hi,

das ist jetzt mal ne theoretische Frage, war mir nicht ganz sicher, ob das hier in den Off Topic-Bereich gehört... ich hoff mal Smile

Also, meine Frage, der Titel sagt es schon, ist, wie ihr Pathfinding in einem 3D-Space-Shooter realisieren würdet.

Es gibt ja keine Wände/Straßen/Gänge oder irgendwas, an das sich der Computer halten muss. Im Prinzip kann er ja einfach geradeaus fliegen.

Dennoch kann irgendetwas im Weg sein, etwa ein anderes Raumschiff, was ja auch nicht immer vorherzusehen ist.
Diesen Gegenständen/Objekten, die den weg eventuell bversperren könnten, msus man ausweichen.

Aber wie würdet ihr soetwas realisieren? A*-Pathfinding wäre ein wenig Overkill, schätze ich.

Freue mich auf Denkanstöße und Tipps Smile

Computer 1: AMD Athlon64 3500+ | nVidia GF 7900GT | 1024 MB DDR-RAM | ASUS A8N-SLI Preimium | 250 GB SATA 2 || WindowsXP | Blitz3D | Blitz+
Computer 2: AMD AthlonXP 2400+ | ATI Radeon 9500 | 512 MB DDR-RAM | MSI K7N2 | 80 GB IDE | 160 GB IDE || WindowsXP | Blitz3D | Blitz+
Computer 3: Intel Pentium MMX | onBoard-Grafik | 32 MB RAM | 1 GB IDE || Windows 98 SE | Blitz+

	Blitzcoder Newsposter	Sa, Jul 07, 2007 20:18 Antworten mit Zitat
Naja, ganz einfach wäre es, einfach den direkten Weg zu nehmen, und wenn ein Hindernis auftaucht, daran vorbei zu fliegen Du könntest also den Punkt picken, in dem du in das Ding reinkrachen würdest. Dann kann man oben/unten/rechts/links prüfen, welches der kürzeste Weg vorbei ist, also, in welche Richtung vom Gepickten Punkt aus gesehen das Mesh nach außen am kürzesten ist. Dann einfach in die gewünschte Richtung drehen, wenn man dann auf der Richtigen Höhe ist, einfach wieder auf das Zeil zufliegen. MfG Blitzcoder
P4 3 Ghz@3,55Ghz\|GF 6600GT 256MB\|Samsung 80GB \| 2x Samsung 160GB\|2048MB DDR-400 RAM\|6 Mbit Flatrate \| Logitech G15 \| Samsung 225BW-TFT \| Ubuntu Gutsy Linux \| Windows Vista \| Desktop \| Blog \| CollIDE \| Worklog ________________ \|°°°°°°°°°°°°°°\|\|'""\|""\__,_ \|______________ \|\|__ \|__\|__ \|) \|(@) \|(@)"""\|(@)(@)**\|(@)

Blitzcoder

Newsposter

Sa, Jul 07, 2007 20:18
Antworten mit Zitat

Naja, ganz einfach wäre es, einfach den direkten Weg zu nehmen, und wenn ein Hindernis auftaucht, daran vorbei zu fliegen Wink

Du könntest also den Punkt picken, in dem du in das Ding reinkrachen würdest. Dann kann man oben/unten/rechts/links prüfen, welches der kürzeste Weg vorbei ist, also, in welche Richtung vom Gepickten Punkt aus gesehen das Mesh nach außen am kürzesten ist. Dann einfach in die gewünschte Richtung drehen, wenn man dann auf der Richtigen Höhe ist, einfach wieder auf das Zeil zufliegen.

MfG Blitzcoder

P4 3 Ghz@3,55Ghz|GF 6600GT 256MB|Samsung 80GB | 2x Samsung 160GB|2048MB DDR-400 RAM|6 Mbit Flatrate | Logitech G15 | Samsung 225BW-TFT | Ubuntu Gutsy Linux | Windows Vista | Desktop | Blog | CollIDE | Worklog
________________
|°°°°°°°°°°°°°°||'""|""\__,_
|______________ ||__ |__|__ |)
|(@) |(@)"""**|(@)(@)****|(@)

	TheShadow Moderator	Sa, Jul 07, 2007 20:21 Antworten mit Zitat
Idee wäre sowas wie Realtime-Pathfinding Du hat Objekte etwa Planeten mit bestimmten Größe - zusätzlich kannst du für jedes Objekt eine art Faktor bestimmen -> 1 wäre normal, 2 stößt mehr ab, -1 wäre z.B. sogar anziehend (Schwarzes Loch) mit einer Formel ähnlich http://de.wikipedia.org/wiki/Metaball könnte man die "Summe" errechnen Weiterhin musst du für alle möglichen Bewegungsrichtungen so eine Summe errechnen und einen optimalen Bewegungsvektor auswählen Problem: Ziel müsste einen hohen negativen Faktor haben, damit es auch von Weit angezogen wird... Insg. müsste man mit Werten/Größen spielen... soweit die Theorie
AMD64 3500+ \| GeForce6600GT 128MB \| 1GB DDR \| WinXPsp2

TheShadow

Moderator

Sa, Jul 07, 2007 20:21
Antworten mit Zitat

Idee wäre sowas wie Realtime-Pathfinding

Du hat Objekte etwa Planeten mit bestimmten Größe - zusätzlich kannst du für jedes Objekt eine art Faktor bestimmen -> 1 wäre normal, 2 stößt mehr ab, -1 wäre z.B. sogar anziehend (Schwarzes Loch)

mit einer Formel ähnlich

http://de.wikipedia.org/wiki/Metaball

könnte man die "Summe" errechnen

Weiterhin musst du für alle möglichen Bewegungsrichtungen so eine Summe errechnen und einen optimalen Bewegungsvektor auswählen

Problem: Ziel müsste einen hohen negativen Faktor haben, damit es auch von Weit angezogen wird... Insg. müsste man mit Werten/Größen spielen...

soweit die Theorie

AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2

	peacemaker	Sa, Jul 07, 2007 23:01 Antworten mit Zitat
Naja. Einfach halt per AligntoVector und MoveEntity. Mit EntityDistance () schauen ob was in der Nähe ist. Wenn ja halt einfach "umfliegen". Fertig. MfG
~Tehadon~ www.tehadon.de http://www.blitzforum.de/worklogs/14/

peacemaker

Sa, Jul 07, 2007 23:01
Antworten mit Zitat

Naja.

Einfach halt per AligntoVector und MoveEntity.

Mit EntityDistance () schauen ob was in der Nähe ist.

Wenn ja halt einfach "umfliegen".

Fertig.

MfG

~Tehadon~
www.tehadon.de
http://www.blitzforum.de/worklogs/14/

	KhanLeo	Mi, Jan 26, 2011 20:00 Antworten mit Zitat
Hallo Gemeinde, ich habe ein ähnliches Problem und würde gerne eure Meinung zu meinen Überlegungen bzgl. einer KI-Steuerung in einem 3D-Weltraum Action-Strategie-Spiel hören : Dieses Spiel enthält Elemente eines Weltraum Action-Spiels (schnelle, einfache Schlachten, in denen der Spieler ein eigenes Schiff steuert) gepaart mit Strategieelementen (Planeten besiedeln, KI-Schiffe produzieren). Die KI-Schiffe sollen einfache "Go-to"-Befehle bis zu etwas komplexeren Kampfmanövern (verfolgen, ausweichen) beherrschen. Ich überlege nun, wie man diese KI-Steuerung am besten umsetzen sollte : 1. Waypoint gesteuert oder 2. richtungsgesteuert Mit Waypoint-gesteuert meine ich, das KI-Schiff bekommt einen Zielpunkt, und wird solange bewegt, bis es den Zielpunkt erreicht hat. Nach dem Erreichen macht es irgendwas oder bekommt einen neuen Zielpunkt (z.B. bei einem Ausweichmanöver). Ich finde diese Methode einfach umzusetzen, aber wenn später z.B. 100 Schiffe ihre jeweiligen Waypoints anfliegen, und diese auch noch schnell wechseln, wie sieht das Performancemäßig aus ? Ich habe hierfür folgende Funktion gebaut, in der mir vor allem die dann sehr häufig benutzte Entfernungsmessung perfomancelastig erscheint ? Code: [AUSKLAPPEN] [EINKLAPPEN] ;----- Schiffe bewegen ----- Function fctMoveObjects() Local pntTicket.tTicketMove For pntTicket.tTicketMove= Each tTicketMove If EntityDistance(pntTicket\ObjEntityID, pntTicket\ObjDest[4]) > 0.2 MoveEntity pntTicket\ObjEntityID, 0, 0, pntTicket\ObjSpeed# Else FreeEntity pntMoveShip End If Next End Function Mit richtungsgesteuert meine ich, das KI-Schiff wird nur über die Winkel gesteuert. Bei Manövern wird keine Kette von Waypoints abgeflogen, sondern das Schiff fliegt für eine bestimmte Zeit einfach in die winkelmäßig bestimmte Richtung. Finde ich schwieriger umzusetzen, spart aber Performance ? Möglich wäre auch ein Mix aus beidem : Waypoint-gesteuert, wobei die Entfernung nicht dauernd gemessen wird, sondern das Schif für x Sekunden in Richtung Waypoint bewegt wird. Und wenn die Koordinaten von Waypoint / Schiff eng beieinanderliegen, dann erfolgt der nächste Schritt. Koordinaten zu vergleichen mit Subtraktion ist doch performancesparender, als die EntityDistance-Funktion oder tut sich das nichts ? Was denkt ihr dazu, ich kann das irgendwie schwer einschätzen. Danke schon mal für eure Tipps ! Lars
Blitz3D 1.94 Milkshape 1.8.5 BenQ Joybook S73G mit ATi Radeon Mobility X1600 // WinXP SP3, ATi Catalyst 9.2

KhanLeo

Mi, Jan 26, 2011 20:00
Antworten mit Zitat

Hallo Gemeinde,

ich habe ein ähnliches Problem und würde gerne eure Meinung zu meinen Überlegungen bzgl. einer KI-Steuerung in einem 3D-Weltraum Action-Strategie-Spiel hören :

Dieses Spiel enthält Elemente eines Weltraum Action-Spiels (schnelle, einfache Schlachten, in denen der Spieler ein eigenes Schiff steuert) gepaart mit Strategieelementen (Planeten besiedeln, KI-Schiffe produzieren). Die KI-Schiffe sollen einfache "Go-to"-Befehle bis zu etwas komplexeren Kampfmanövern (verfolgen, ausweichen) beherrschen.

Ich überlege nun, wie man diese KI-Steuerung am besten umsetzen sollte :

1. Waypoint gesteuert
oder
2. richtungsgesteuert

Mit Waypoint-gesteuert meine ich, das KI-Schiff bekommt einen Zielpunkt, und wird solange bewegt, bis es den Zielpunkt erreicht hat. Nach dem Erreichen macht es irgendwas oder bekommt einen neuen Zielpunkt (z.B. bei einem Ausweichmanöver). Ich finde diese Methode einfach umzusetzen, aber wenn später z.B. 100 Schiffe ihre jeweiligen Waypoints anfliegen, und diese auch noch schnell wechseln, wie sieht das
Performancemäßig aus ? Ich habe hierfür folgende Funktion gebaut, in der mir vor allem die dann sehr häufig benutzte Entfernungsmessung perfomancelastig erscheint ?

Code: [AUSKLAPPEN]

;----- Schiffe bewegen -----
Function fctMoveObjects()
Local pntTicket.tTicketMove

For pntTicket.tTicketMove= Each tTicketMove
   If EntityDistance(pntTicket\ObjEntityID, pntTicket\ObjDest[4]) > 0.2
   MoveEntity pntTicket\ObjEntityID, 0, 0, pntTicket\ObjSpeed#
   Else
   FreeEntity pntMoveShip
   End If
Next
End Function

Mit richtungsgesteuert meine ich, das KI-Schiff wird nur über die Winkel gesteuert. Bei Manövern wird keine Kette von Waypoints abgeflogen, sondern das Schiff fliegt für eine bestimmte Zeit einfach in die winkelmäßig bestimmte Richtung. Finde ich schwieriger umzusetzen, spart aber Performance ?

Möglich wäre auch ein Mix aus beidem : Waypoint-gesteuert, wobei die Entfernung nicht dauernd gemessen wird, sondern das Schif für x Sekunden in Richtung Waypoint bewegt wird. Und wenn die Koordinaten von Waypoint / Schiff eng beieinanderliegen, dann erfolgt der nächste Schritt. Koordinaten zu vergleichen mit Subtraktion ist doch performancesparender, als die EntityDistance-Funktion oder tut sich das nichts ?

Was denkt ihr dazu, ich kann das irgendwie schwer einschätzen.

Danke schon mal für eure Tipps !
Lars

Blitz3D 1.94
Milkshape 1.8.5

BenQ Joybook S73G mit ATi Radeon Mobility X1600 // WinXP SP3, ATi Catalyst 9.2

	nilfor	Mi, Jan 26, 2011 21:19 Antworten mit Zitat
Ich weiß nicht, ob sich das einfach so in 3d umsetzen lässt und es ist eigentlich für Dlephi, aber als Ansatz vielleicht hilfreich: http://wiki.delphigl.com/index...thfinding2

nilfor

Mi, Jan 26, 2011 21:19
Antworten mit Zitat

Ich weiß nicht, ob sich das einfach so in 3d umsetzen lässt und es ist eigentlich für Dlephi, aber als Ansatz vielleicht hilfreich:
http://wiki.delphigl.com/index...thfinding2

	Firstdeathmaker	Do, Jan 27, 2011 10:35 Antworten mit Zitat
Vielleicht hilft dir folgender Artikel: http://www.ai-blog.net/archives/000152.html und dann das googeln nach "navigation mesh"
www.illusion-games.de Space War 3 \| Space Race \| Galaxy on Fire \| Razoon Gewinner des BCC #57 User posted image

Firstdeathmaker

Do, Jan 27, 2011 10:35
Antworten mit Zitat

Vielleicht hilft dir folgender Artikel:

http://www.ai-blog.net/archives/000152.html

und dann das googeln nach

"navigation mesh"

www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

	Arrangemonk	Do, Jan 27, 2011 17:46 Antworten mit Zitat
nen nav mesh is aber nutzlos bei sowas ein nav mesh geht davon aus, dass es schwerkraft gibt im weltall, wäre das genaue gegenteil eher nützlich weil es gibt mehr passierbares als nicht passierbares da würd ich den objekten nen radius geben und den mechwarrior algorithmus hernehmen und nur die bedinung umdrehen
ingeneur

Arrangemonk

Do, Jan 27, 2011 17:46
Antworten mit Zitat

nen nav mesh is aber nutzlos bei sowas

ein nav mesh geht davon aus, dass es schwerkraft gibt

im weltall, wäre das genaue gegenteil eher nützlich

weil es gibt mehr passierbares als nicht passierbares

da würd ich den objekten nen radius geben
und den mechwarrior algorithmus hernehmen und nur die bedinung umdrehen

ingeneur

	KhanLeo	Mo, Jan 31, 2011 20:41 Antworten mit Zitat
Hallo, danke für die zahlreichen Anregungen ! Werde ich mir alles mal zu Gemüte führen. Ich denke allerdings auch, dass ein Nav Mesh für den freien Weltraum nicht benötigt wird. Aber den Artikel kann ich sehr gut für ein anderes Projekt gebrauchen, vielen Dank !
Blitz3D 1.94 Milkshape 1.8.5 BenQ Joybook S73G mit ATi Radeon Mobility X1600 // WinXP SP3, ATi Catalyst 9.2

KhanLeo

Mo, Jan 31, 2011 20:41
Antworten mit Zitat

Hallo,

danke für die zahlreichen Anregungen ! Werde ich mir alles mal zu Gemüte führen. Ich denke allerdings auch, dass ein Nav Mesh für den freien Weltraum nicht benötigt wird. Aber den Artikel kann ich sehr gut für ein anderes Projekt gebrauchen, vielen Dank !