Pathfinding für mehrere Figuren

Übersicht

BlitzBasic

Allgemein

	Smokie Betreff: Pathfinding für mehrere Figuren	Di, Aug 22, 2006 13:58 Antworten mit Zitat
Hi, ich arbeitet z.Z. an einem Spiel bei dem ich mehrere Figuren bewegen möchte. Das Prinzip von Pathfinding habe ich verstanden, und es funktioniert auch schon bei einer Figur, aber ich möchte eben mehrere Figuren bewegen. Meine Funktion zum Pathfinden ist eine abgewandelte Version, von blitzbase. Ich habe mir überlegt, dass ich ein dim mache in dem ich den Path zur Einheit speichere: Code: [AUSKLAPPEN] [EINKLAPPEN] Dim Pfad.path(number_of_max_nodes,number_of_max_figures) Nun wäre aber das dim sehr groß, wenn ich ne große Map habe, oder wenn ich auf diese weiße auch Tiere oder ähnliches steuern will. Bitte sagt mir wenn dies die einzige Lösung ist, oder ob es noch eine andere gibt und wenn ja, dann sagt sie mir bitte Danke! Grüße Smokie
M-Soft Studios Mit selbst gemachtem Forum!!! Unbequem lebt's sich schwer. Musik macht erst Spaß, wenn man sie mit 2,8 facher Geschwindigkeit hört Zuletzt bearbeitet von Smokie am Fr Jan 01, 1888 51:58 PM, insgesamt 1000-mal bearbeitet

Smokie

Betreff: Pathfinding für mehrere Figuren

Di, Aug 22, 2006 13:58
Antworten mit Zitat

Hi,

ich arbeitet z.Z. an einem Spiel bei dem ich mehrere Figuren bewegen möchte. Das Prinzip von Pathfinding habe ich verstanden, und es funktioniert auch schon bei einer Figur, aber ich möchte eben mehrere Figuren bewegen.

Meine Funktion zum Pathfinden ist eine abgewandelte Version, von blitzbase.
Ich habe mir überlegt, dass ich ein dim mache in dem ich den Path zur Einheit speichere:
Code: [AUSKLAPPEN]

Dim Pfad.path(number_of_max_nodes,number_of_max_figures)

Nun wäre aber das dim sehr groß, wenn ich ne große Map habe, oder wenn ich auf diese weiße auch Tiere oder ähnliches steuern will.

Bitte sagt mir wenn dies die einzige Lösung ist, oder ob es noch eine andere gibt und wenn ja, dann sagt sie mir bitte Smile

Danke!

Grüße
Smokie

M-Soft Studios Mit selbst gemachtem Forum!!!
Unbequem lebt's sich schwer.
Musik macht erst Spaß, wenn man sie mit 2,8 facher Geschwindigkeit hört
Zuletzt bearbeitet von Smokie am Fr Jan 01, 1888 51:58 PM, insgesamt 1000-mal bearbeitet

	Dreamora	Di, Aug 22, 2006 14:09 Antworten mit Zitat
Was verstehst du unter sehr gross? Tiere die du nicht siehst brauchen in dem moment eigentlich keine Bewegung. Denn wenn du mehrere hundert Objekte gleichzeit von AI rumbewegen lassen wolltest, würde das sowieso zusammenbrechen. Der DIM wird also so ziemlich das kleinste Problem
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Di, Aug 22, 2006 14:09
Antworten mit Zitat

Was verstehst du unter sehr gross?

Tiere die du nicht siehst brauchen in dem moment eigentlich keine Bewegung.

Denn wenn du mehrere hundert Objekte gleichzeit von AI rumbewegen lassen wolltest, würde das sowieso zusammenbrechen.

Der DIM wird also so ziemlich das kleinste Problem Smile

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Smokie	Di, Aug 22, 2006 14:12 Antworten mit Zitat
Aber ich muss doch die Position berechnen, da es wichtig ist wo die Figuren stehen, sollte ich dazu eine andere Methode verwenden? Unter sehr groß verstehe ich ca 10.000 * 10.000px große Map, aber das ist schon größer als eine Durschnitts map sein. Grüße[/b]
M-Soft Studios Mit selbst gemachtem Forum!!! Unbequem lebt's sich schwer. Musik macht erst Spaß, wenn man sie mit 2,8 facher Geschwindigkeit hört Zuletzt bearbeitet von Smokie am Fr Jan 01, 1888 51:58 PM, insgesamt 1000-mal bearbeitet

Smokie

Di, Aug 22, 2006 14:12
Antworten mit Zitat

Aber ich muss doch die Position berechnen, da es wichtig ist wo die Figuren stehen, sollte ich dazu eine andere Methode verwenden?

Unter sehr groß verstehe ich ca 10.000 * 10.000px große Map, aber das ist schon größer als eine Durschnitts map sein.

Grüße[/b]

	Dreamora	Di, Aug 22, 2006 14:28 Antworten mit Zitat
Erm ja 10k x 10k pixel ist na nicht das Problem, sondern die grösse deiner Zellen (und die auf pixelgrösse zu wählen währe ehrlich gesagt schon schwachsinnig ausser du hast 1 pixel grosse figuren woran ich sehr zweifel). Und selbst dann: Was hat das mit obigem Dim zu tun? Da kommen nur 2 Dinge vor: Anzahl Figuren, Maximale Pfadlänge Nur weil die map 10k x 10k ist heisst das noch lange nicht das man mehrere tausend schritte lange pfade zulassen müsste (geschweige denn das der pfadfindealgo da wochen braucht bei sovielen einheiten). Von daher sehe ich dein Problem nicht aber scheint bis anhin als ob du dir noch nicht soviel Gedanken darüber gemacht hast in welcher Grössenordnung das ganze überhaupt notwendig ist und für wieviele Einheiten. Einige potentielle Ideen: - Wenn ein Trupp von 10 Leuten vom gleichen Ort zum gleichen Ziel will, warum 10 Pfade? Warum nicht 1 Pfad und Bewegungsoffset + "bewegungsfreiheit" um um potentielle Hindernisse herum zu kommen? - Wenn du wirklich eine so grosse Map hättest (10k x 10k zellen), dann wird dennoch niemand so weit wandern. Sprich du kannst die Map in Blöcke unterteilen in denen der Pfad gesucht wird. Dadurch reduziert sich das auf wenige Blöcke normalerweise und reduziert auch die potentiellen Möglichkeiten drastisch. - "vielgenutzte" Pfade zwischen diesen Blöcken könnten theoretisch gemerkt werden. Noch besser ist der Ansatz den einige RTS nutzen: Lass den Spieler doch einfach fixe pfade vordefinieren an die er dann seine einheiten schicken kann und dem sie folgen. Das ist so praktisch für die Spieler wie es dir Arbeit erspart ^^ - "wildtiere" bewegen sich nur in sehr begrenzten Bereichen. Die brauchen also keine langen Pfade noch werden die meisten je eine Blockgrenze überschreiten. Ein weiterer nicht zu unterschätzender Vorteil.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Di, Aug 22, 2006 14:28
Antworten mit Zitat

Erm ja
10k x 10k pixel ist na nicht das Problem, sondern die grösse deiner Zellen (und die auf pixelgrösse zu wählen währe ehrlich gesagt schon schwachsinnig ausser du hast 1 pixel grosse figuren woran ich sehr zweifel).

Und selbst dann: Was hat das mit obigem Dim zu tun?

Da kommen nur 2 Dinge vor: Anzahl Figuren, Maximale Pfadlänge
Nur weil die map 10k x 10k ist heisst das noch lange nicht das man mehrere tausend schritte lange pfade zulassen müsste (geschweige denn das der pfadfindealgo da wochen braucht bei sovielen einheiten).

Von daher sehe ich dein Problem nicht aber scheint bis anhin als ob du dir noch nicht soviel Gedanken darüber gemacht hast in welcher Grössenordnung das ganze überhaupt notwendig ist und für wieviele Einheiten.

Einige potentielle Ideen:

- Wenn ein Trupp von 10 Leuten vom gleichen Ort zum gleichen Ziel will, warum 10 Pfade? Warum nicht 1 Pfad und Bewegungsoffset + "bewegungsfreiheit" um um potentielle Hindernisse herum zu kommen?

- Wenn du wirklich eine so grosse Map hättest (10k x 10k zellen), dann wird dennoch niemand so weit wandern. Sprich du kannst die Map in Blöcke unterteilen in denen der Pfad gesucht wird. Dadurch reduziert sich das auf wenige Blöcke normalerweise und reduziert auch die potentiellen Möglichkeiten drastisch.

- "vielgenutzte" Pfade zwischen diesen Blöcken könnten theoretisch gemerkt werden. Noch besser ist der Ansatz den einige RTS nutzen: Lass den Spieler doch einfach fixe pfade vordefinieren an die er dann seine einheiten schicken kann und dem sie folgen. Das ist so praktisch für die Spieler wie es dir Arbeit erspart ^^

- "wildtiere" bewegen sich nur in sehr begrenzten Bereichen. Die brauchen also keine langen Pfade noch werden die meisten je eine Blockgrenze überschreiten. Ein weiterer nicht zu unterschätzender Vorteil.

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Smokie	Di, Aug 22, 2006 14:39 Antworten mit Zitat
Erstma danke Aber mein Hauptproblem liegt darin, dass ich net weiß (außer das dim), wie ich den einzelnen Figuren ihren Pfad zuweißen soll. Dass ich dem net den Pfad über die ganze map berechne is kla, desshalb sollte es kein Problem mit dem Speed geben. Grüße
M-Soft Studios Mit selbst gemachtem Forum!!! Unbequem lebt's sich schwer. Musik macht erst Spaß, wenn man sie mit 2,8 facher Geschwindigkeit hört Zuletzt bearbeitet von Smokie am Fr Jan 01, 1888 51:58 PM, insgesamt 1000-mal bearbeitet

Smokie

Di, Aug 22, 2006 14:39
Antworten mit Zitat

Erstma danke Smile

Aber mein Hauptproblem liegt darin, dass ich net weiß (außer das dim), wie ich den einzelnen Figuren ihren Pfad zuweißen soll. Dass ich dem net den Pfad über die ganze map berechne is kla, desshalb sollte es kein Problem mit dem Speed geben.

Grüße

	BladeRunner Moderator	Di, Aug 22, 2006 14:54 Antworten mit Zitat
Stichwort: bank Erstelle zwei banks: Eine für die Nodes, welche nacheinander abgelegt werden. Eine für eine Indexliste welche auf die Speicherzellen zeigt an denen neue Pfade beginnen. Nun kannst du per index auf die bank zugreifen und dich von dem in index zu dem in index+1 angegebenen nodes vorarbeiten. Vorteil: recht flexibel, denn du kannst die banks auch resizen. Nachteil: du musst dich selbst um "Aufräumarbeiten" kümmern, d.h. gegebebenfalls "benutzte" Pfade entfernen. Hier ist es wichtig dass zu Umräumarbeiten kein Pfadinder aktiv ist, bzw. den aktiven automatisch der neue index zugewiesen wird. Sicher nicht das leichteste - aber als Anregung okay, denke ich.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Di, Aug 22, 2006 14:54
Antworten mit Zitat

Stichwort: bank
Erstelle zwei banks:
Eine für die Nodes, welche nacheinander abgelegt werden.
Eine für eine Indexliste welche auf die Speicherzellen zeigt an denen neue Pfade beginnen.
Nun kannst du per index auf die bank zugreifen und dich von dem in index zu dem in index+1 angegebenen nodes vorarbeiten.

Vorteil: recht flexibel, denn du kannst die banks auch resizen.
Nachteil: du musst dich selbst um "Aufräumarbeiten" kümmern, d.h. gegebebenfalls "benutzte" Pfade entfernen. Hier ist es wichtig dass zu Umräumarbeiten kein Pfadinder aktiv ist, bzw. den aktiven automatisch der neue index zugewiesen wird.
Sicher nicht das leichteste - aber als Anregung okay, denke ich.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	Smokie	Di, Aug 22, 2006 15:10 Antworten mit Zitat
Okay, danke. Hab zwar noch nie was mit Bank gemacht, dafür kann ich es jetzt nachholen Grüße
M-Soft Studios Mit selbst gemachtem Forum!!! Unbequem lebt's sich schwer. Musik macht erst Spaß, wenn man sie mit 2,8 facher Geschwindigkeit hört Zuletzt bearbeitet von Smokie am Fr Jan 01, 1888 51:58 PM, insgesamt 1000-mal bearbeitet

Smokie

Di, Aug 22, 2006 15:10
Antworten mit Zitat

Okay, danke.

Hab zwar noch nie was mit Bank gemacht, dafür kann ich es jetzt nachholen Smile

Grüße

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Pathfinding für mehrere Figuren

Smokie

Betreff: Pathfinding für mehrere Figuren

Dreamora

Smokie

Dreamora

Smokie

BladeRunner

Smokie