Wegfindung: Verschiedene Einheiten-Größen

Wie kann man effektiv mit verschiedenen Einheiten-Größen umgehen, wenn man vorberechnete Graphen hat? Bisher hab es so gehandhabt, dass ich für jede Größe einen eigenen Graph erstelle (also eigene Knoten und Kanten) und versuche, nicht so viele verschiedene Größen zu haben. Gibt es da vielleicht bessere Wege?

finix

Keine Ahnung wie's wirklich geht, aber spontaner Ansatz wäre vielleicht: den Knoten ihre "Größe" mitgeben, dann in der Gewichtsfunktion infinity zurückgeben falls die Einheit zu klein ist.

Du meinst also vermutlich, für die Kanten die maximal erlaubte Größe merken? Ich habe aber noch das zusätzliche Problem, das Knoten für verschiedene Einheiten-Größen wahrscheinlich unterschiedliche Koordinaten auf der Karte repräsentieren müssen. Zum Beispiel muss eine große Einheit einen weiteren Bogen um das Hinderniss machen.

TGGC

Optimizer schrieb:

Du meinst also vermutlich, für die Kanten die maximal erlaubte Größe merken? Ich habe aber noch das zusätzliche Problem, das Knoten für verschiedene Einheiten-Größen wahrscheinlich unterschiedliche Koordinaten auf der Karte repräsentieren müssen. Zum Beispiel muss eine große Einheit einen weiteren Bogen um das Hinderniss machen.

Irgendwo muessen die Daten ja gespeichert werden, ist ja nun egal, ob in einen 2 Graphen oder in lauter "Super"Nodes, die fuer alle Groesse die Passierbarkeit und Koordinaten haben. Wenn du keine Redundanz hast, gibts ja auch nichts zu sparen. f'`8k

Gruß, TGGC (making great games since 1992)

Tjo schade. Dann halt wieder mehrere Graphen. Thx

muli

Ich hab mal ne wegplanung mit hilfe von Quadtrees gemacht und die groesse der Minimal zu zerlegenden bereiche abhaengig von der groesse des agenten gemacht.
so ist gewaehrleistet dass er um die ecke kommt ohne anzuecken!
bei interesse such ich dir das paper dazu mal raus.

ps. hab die rechte hand gebrochen -> etwas schreibfaul

besser spät als nie!

muli

Ich kann mir vorstellen wie du es meinst, glaube aber das ist nicht ganz mein Anwendungsfall. Ich verstehe dich so, als würden praktisch die Mitten von Knoten im Quadtree die Knoten im Graphen sein, so dass sich auf allen Ebenen ein regelmäßiges Grid herausbildet. So etwas mache ich nicht, sondern ich möchte die Knoten am Rand von Hindernissen oder an Sichtbarkeitspunkten erstellen. Einen Quadtree werde ich höchstens zum Gruppieren solcher Knoten benutzen oder um die Wegfindung hierarchisch zu machen. Aber trotzdem danke.

LinkeT

ich würde das mit der einheiten-gröse so machen: waypoints die mehr verbindungen haben haben automatisch eine höhere wertigkeit und werden eher gesucht. Problematisch wird das auf einen offenen feld, da alle gleich viele haben, an dieser stelle würde ich in bestimmten abständen hoch wertige waypoints bestimmen.

in jeden fall würde ich aber 2-3 max 4 "matritzen"(also waypointlists) nutzen.
hier eine varainte:
waypointID: xxyyyyyyyyyyyyyy als unsigned short, die höchsten 3 bits geben an in welcher ebene dieser waypoint exitiert je höher der ist desto grösser ist der abstand
ein waypoint hat eine koordinate und eine liste von nachbarn, max 4-6 (6 zb für spiele mit einer tiefe)

hoffe das ich nen ansatzt gegeben hab vllt ist sie speicher intensiv aber beides dürfte nicht realisirbar sein-.-