Nodebasierende Wegfindung

[[RK]]

Ich bin mir nicht sicher ob ich hier richtig bin, jedenfalls würde ich halt genere meine Wegfindung ausstellen und von euch testen lassen. Wie dem auch sei hier ist sie jedenfalls, meine ...


Nodebasierende Wegfindung:

Erstellt werden die Nodes so indem man einfach eingibt wieviele Nodes man haben will und dann geht man auf "createNode". Jetzt klickt man wild auf der Bühne herrum und erstellt sie, bis alle ertellt wurden. Danach drückt man auf ein Node und DragDropped auf einen anderen, so das ein Weg zwischen ihnen erstellt wird. Ist der Weg falsch gemacht worden, einfach auf den Weg selbst klicken und er verschwindet.

calcAll berechnet alle möglichen Wege von Node zu Node und speichert diese ab. Das dauert zwar eine Weile, allerdings sind darauffolgende Wegfindungen irre schnell, da er dann eben auf diese vorberechneten zugreift und nicht selbst mühsam abcheckt welcher Weg nun der kürzeste ist. Ich hab schon eine Möglichkeit entwickelt das dieses calculieren aller Wege doppelt so schnell verläuft, kam aber noch nicht dazu diese auch einzubauen.

.] gelbe Nodes sind Nodes die per Vorberechneter-Wegfindung genommen wurden.
.] blaue Nodes sind die Nodes die per Echtzeit-Wegfindung genommen wurden.



Node Wegfindung incl. Editor:
http://img69.imageshack.us/my.php?im...findungns0.swf

[shorty]

Toll, hast fein gemacht, und nun?

[anihulli]

lustig, zufällig bin ich über die Suche in diesen Thread gekommen, obwohl ich sonst nie hier unterwegs bin und auch nicht nach diesem Problem auf der Suche war.

Du hast dich wahrscheinlich unbewusst mit dem Problem des Handelsreisenden (Traveling Salesperson/man Problem) beschäftigt. Wenn du alle Wege berechnest, geht das dramatisch auf die Performance. Das liegt daran, dass dieses Problem NP-Vollständig ist bzw. du bei n untereinander verbundenen Nodes (n−1)!/2-verschiedene Wege durchrechnen musst. Einen herkömlichen PC kannst du mit eher kleinen Zahlen für Jahre auf 100% Prozessorauslastung bringen.

Um relativ gute Ergebnisse in einer akzeptablen Zeit zu bekommen kommt man beim Traveling Salesman Problem (TSP) nicht um Heuristiken herum, also Abschätzungen und Abwägungen. Ansätze, bei denen du z.B. sagst wenn du 3mal in die falsche Richtung gehst ist der Weg sinnlos.

In der Informatik wurden zur "Lösung" dieses Problems verschiedene Algorithmen entwickelt, wie z.B. der A*- oder der Dijkstra-Algorithmus.

Links zur Wikipedia:
TSP: http://de.wikipedia.org/wiki/Problem...sungsverfahren
A*: http://de.wikipedia.org/wiki/A%2A
Dijkstra: http://de.wikipedia.org/wiki/Algorithmus_von_Dijkstra

Ich finde es cool, dass du dich mit dem Thema auseinander gesetzt hast, vielleicht hast du jetzt noch einen Anreiz weiter zu machen. In der Spieleprogrammierung gehört dies übrigens zu den elementaren Problemen bei der Entwicklung intelligenter Computergegner. Schwieriger wird es noch, wenn die Pfade gewichtet sind, z.B. eine Figur langsamer "Berg auf" als "Berg ab" gehen kann etc.

Adriaan

[Omega Psi]

Ich bin gespannt was er sagen wird... ich habe mich um Graphen-Theorie erfolgreich gedrückt

[[RK]]

Hallo anihulli und danke für dein Kommentar und die Hilfestellungen

Ingame wird nicht wirklich eine Wegfindung im eigentlichen Sinn genutzt. Die Zeitaufwendige Wegberechnung findet bei der Erstellung der Map statt - betrifft also nur die Entwickler des Spieles und nicht die Spieler x) Im Spiel selbst wird nur berechnet welche Start- und Endnode sind und dann wird auf ein Array zugegriffen wo der vorberechnete Weg gespeichert ist. Und soweit ich das testen konnte ist das schneller als jede Heuristik die ich hatte.

Ich hatte es eben auch schon mit Heuristik (und ingame), allerdings schlichen sich da bei meinen üblen Programmierkenntnissen viel zu oft Fehler ein. Das war es mir dann einfach nicht wert und ich hab es bei der Wegberechnung vor dem Spiel belassen.

Diese Wegfindung soll ja auch nur dazu dienen statische Levelobjekten wie Tischen, Wänden etc. auszuweichen. Für das ausweichen von Charakteren, bzw. generell sich bewegenden Objekten muss ich mir erst was überlegen :P

Ist denn meine Wegfindung zu langsam bei euch?
Ich hatte eig. immer ganz gute Werte. :/

[Janoscharlipp]

Wie viele Knoten wird es denn mit wievielen Verbindungen im Schnitt geben?

[Omega Psi]

Schneller als vorberechnen geht nicht. Aber irgendwann macht das keinen Sinn mehr, nämlich dann, wenn du sehr viele Wege hast und auch Zwischenstationen miteinbeziehst. Das ist ja mit das Kernproblem von "Travelling salesman". Der "Travelling salesman" will Staubsauger verkaufen und kennt die Strassen und Gassen der Stadt sowie seine einzelnen Stationen. Ziel ist es den günstigsten Weg zu finden, um alle Haushalte auf einmal herauszufinden. Routenberechnungen mit Zwischenstationen müssenbeispielsweise auf solche Heuritiken und Algorithmen zugreifen, da das Abspeichern aller möglichen Wege von A nach B über C (wobei C auch eine leere Menge sein kann) sehr viel Speicherplatz verbrauchen kann.

Wenn du alles vorher einmal durchratterst, ist das bei so kleinen Apps durchaus legitem, wie ich finde.

[[RK]]

Es sind im Schnitt wohl ca. 5-10 Nodes ...
Aber ich denke mir, wenn schon - dann gleich richtig! x)

@ Travelling salesman ...
Zwischenstationen wie C bei A -> C -> B ... ist ja nichts anderes als der Weg von A zu C und von C zu B. Also das Vorrausberechnen würde dadurch nicht länger dauern. Einzige Vorraussetzung ist das er (ingame) die vorberechneten Wege aus dem Array pickt und dann zusammensetzt. Oder habe ich was falsch verstanden?

€: Achja!
lol - Ich hab gerade gesehn das ich sehr wohl eine Heuristic verwende. Ist mir jetzt gerade erst aufgefallen als ich den TSP Artikel auf Wikipedia gelesen habe. Und zwar wäre das die Nearest-Neighbor-Heuristik
Irgendwie war das so trivial das ich nun vergessen hatte das das ja eigentlich auch schon eine Heurisitk ist.