Autoroute Express ;-)

[Count Ypsilon]

Hallo,

für die Freunde der dynamischen Programmierung - ich weiss, ihr seid hier irgendwo ;-) - hier wieder mal ein Spielzeug aus den Ypsilon Labs. Ich habe ein Freewar-Autorouting gebaut, also eine kürzeste-Wege-Suche für beliebige Start- und Zielfelder in Freewar (sofern ein deterministischer Weg existiert, d.h. Göttertempel, Keller in Buran samt Weltraum und das eigene Grab sind als Zielgebiete aussen vor, ausser, das Startfeld liegt bereits geeignet).

Entgegen meiner Gewohnheit ist es diesmal komplett in Javascript geschrieben, weil ich Angst hatte, dass mir Spielkinder sonst die ganze Rechenzeit von meinem Server wegfuttern ;-)

http://www.remote-island.org/101912/autoroute.html

Ist noch sehr unkomfortabel, man muss die Koordinaten von Hand eingeben, und die Ausgabe ist nur textuell, nicht grafisch. Ausserdem sind eventuell noch nicht alle Bewegungsmoeglichkeiten erfasst (vgl. Kantenliste im Source). Kommentare sind wie immer willkommen, insbesondere auch Ideen, was man damit cooles machen kann.

Als erste praktische Anwendung dachte ich an sowas wie einen "Leichenfledderer Companion", bei dem Leute, die am Ort des Todes in Ruward stehen, bloss noch eingeben "Serbanthi" und sofort alle Felder sehen, an denen es Serbanthi gibt, plus kürzestem Weg dahin oder so. Andererseits wissen die Profis das eh alles auswendig.

Naja, vielleicht nutzt die Sache ja auch gar nichts, aber witzig ist sie allemal. Vielleicht sollte man mal eine eingefärbte Freewar-Karte erstellen, bei der sich die Farbe nach der Weglänge von der Bank o.ä. richtet (wobei Zauberkugeln usw. als Wegstrecke 1 zählen). So könnte man die entlegensten Gebiete ermitteln...

Mein Dank gilt den Kartenarbeitern von freewartools.com, dort habe ich mir nämlich die Daten zu den Spezialkanten hergeklaut.

Viel Spass
Y.

[damh]

ich bin mal wieder am meckern *fg*

Da ist noch ein Bug drin:
Startfeld: 80|99
Zielfeld: 81|116
* reiner Fußweg
* Länge: 17
* Weg: Start->79|100->78|101->77|102->76|103->75|104->74|105->73|106->74|107->75|108->76|109->77|110->78|111->79|112->80|113->79|114->80|115->81|116

Der schickt mich durch die Mauer. Ist klar, dass ich da gerne durchlaufen würde, aber dazu fehlen mir leider die Rechte

Ich habe noch ein paar Sachen ausprobiert und er schickt mich fast immer durch Wände.
Gruß damh

[Shadow|W6]

geile idee *thumps up*

[Count Ypsilon]

Huhu,

ich bin mal wieder am meckern *fg*
[...]
Der schickt mich durch die Mauer. Ist klar, dass ich da gerne durchlaufen würde, aber dazu fehlen mir leider die Rechte

Sieht aus, als ob meine Kartendaten etwas zu grosszügig sind; die nicht begehbaren Felder sollten da eigentlich nicht drin sein, aber einige sinds wohl doch. Ich reparier's heute abend, und mache noch eine grafische Ausgabe dazu, dann sieht man auch gleich, wenn was schief geht...

Y.

[Tiramon]

Hab zwar nur nen paar Sachen getestet, ist aber sehr gut gelungen =)

[fireburn]

Kommentare sind wie immer willkommen, insbesondere auch Ideen, was man damit cooles machen kann

Super, damit kann ich mir einen prima Auftragshaus-bot bauen, danke.

Scherz beiseite, damit gibst du Leuten die evtl nichts mit Wegfindungs-Algorithmen anfangen können die Möglichkeit, bessere Bots zu schreiben. Nen praktischen legalen Nutzen seh ich da irgendwie auch nicht. Aber trotzdem: gute Arbeit.

[damh]

Ich habe mir mal die Kanten etwas genauer angesehen. Da fehlen noch ein paar auf jedenfall:
Der hohle Baum 78|98 <-> -811|-826, benötigt Arbeitshandschuhe
Liane 79|99 <-> 80|104
Ruhmeshalle -90|-90 <-> 98|98
Nomadenzelt 101|117 <-> -105|-95

Göttertempel: zweimal Hinweg(ist ausgeschlossen laut TE. Der Weg ist aber eigentlich schon deterministisch *g, nur der Zeitaufwand ist unbekannt) + viermal Rückweg

Der alte Mann fehlt für den Knast. Über den Modeingang kann ja nicht jeder laufen


Manche Wege findet er nicht, obwohl Kanten eingetragen sind:
Keller der Kathedrale

Es sind alles nur Beispiele und daher keine vollständigen Listen.
Gruß damh

[langeweile]

ich glaub, wer nen bot schreibt, der kriegt auch noch einen wegfindungs-algorithmus hin, so schwer sind die auch nicht, sondern hier, insbesondere, da die felder bekannt sind, nichts weiter als suchen in einem graph, da seh ich keine hilfe, ansonsten nettes spielzeug

[damh]

Scherz beiseite, damit gibst du Leuten die evtl nichts mit Wegfindungs-Algorithmen anfangen können die Möglichkeit, bessere Bots zu schreiben. Nen praktischen legalen Nutzen seh ich da irgendwie auch nicht.

Dachte ich auch zuerst, aber es gibt ein paar nützliche Momente.

Z.B. Gewebeamt und Du suchst eine Person auf xy. Das Auftragshaus sagt da immerhin noch den Namen des Feldes
Gruß damh

[fireburn]

ich glaub, wer nen bot schreibt, der kriegt auch noch einen wegfindungs-algorithmus hin, so schwer sind die auch nicht, sondern hier, insbesondere, da die felder bekannt sind, nichts weiter als suchen in einem graph, da seh ich keine hilfe, ansonsten nettes spielzeug

Hab mich mal damit beschäftigt, und es ist nicht so einfach wie man vielleicht denkt. Insbesondere muss man aufpassen dass man nicht in Sackgassen läuft usw. usf. In Rollercoaster Tycoon 2 war es zB so dass die KI-Männchen immer in irgendwelchen Ecken hängenblieben und den Weg nicht herausgefunden haben, das hat mich damals sehr aufgeregt, habe die Männchen dann einfach in einen Wassertümpel geworfen, wo sie dann ertranken, hrhr.

[Count Ypsilon]

ich glaub, wer nen bot schreibt, der kriegt auch noch einen wegfindungs-algorithmus hin, so schwer sind die auch nicht, sondern hier, insbesondere, da die felder bekannt sind, nichts weiter als suchen in einem graph, da seh ich keine hilfe, ansonsten nettes spielzeug

Der Nutzen liegt sicherlich vor allem in automatisierten Anwendungen. ich denke dabei weniger an Bots, sondern an Auswertungen wie z.B. das mit der Karte, was ich schon gesagt habe, oder die Berechnung einer schnellstmöglichen Route, die einen zu allen Shops und/oder Ausbaufeldern führt (travelling salesman... aber bei der kleinen Zahl der Ziele sollte das einfach durch Ausprobieren findbar sein). Den Algorithmus kann man als Basis für sowas nehmen (wenn er erstmal richtig funktioniert, ich muss damhs Anmerkungen mal noch auf den Grund gehen). Es gibt eine ganze Anzahl von unbedeutenden, aber doch alltaeglichen Problemen: Ich will irgendwohin, nehme ich die GZK nach Reikan und dann das Portal, oder nehme ich die GZK zum nächstgelegenen Kugelpunkt und laufe von dort? Entscheidungen, die jeder Spieler täglich aus dem Bauch heraus trifft, aber gerade deshalb kann man da vielleicht interessante Analysen machen. Welche zwei Felder in der Freewar-Welt sind am allerweitesten voneinander entfernt, wenn man keine Hilfsmittel einsetzen darf? Ein weiterer Plan, den ich im Hinterkopf habe, ist, für wichtige Orte im Wiki - z.B. alle Shops und Heilquellen - den jeweils nächstgelegenen Kugelpunkt zu errechnen und anzugeben. Das kann man auch alles von Hand machen, aber nicht immer ist die Lösung intuitiv klar (Zum Shop in Kerdis via Oase oder via Bank? Zum Friedhof-Shop via Wasserfall oder Terasi?).

Na toll... ich wollte doch, dass Ihr die Ideen habt, stattdessen sagt ihr "das bringt nix" und ich muss dann die Ideen liefern ;-)

Y.

[Ruler]

Finde das Proggi sehr geil, gute Idee

[langeweile]

@fireburn,
in diesem 2 dimensionalen Raum mit relativ gut abgerenzten punkten finde ich es nicht sonderlich schwer, einen algorithmus zu finden, der das kann, bzw. ihn auf fw zu übertragen

da ich im studium schon ein paar mal dieses problem hatte, kenn ich da auch mehr als nur einen weg, und diese aufgabe ist nun wirklich relativ leicht, klar abgegrenzte felder, nur 2 dimensionen, und nur exakt eine aufgabe, wohin man gehen muss, ohne wenn und aber, ist sehr schön alles beschrieben, einfach mal prof google fragen

[Count Ypsilon]

da ich im studium schon ein paar mal dieses problem hatte, kenn ich da auch mehr als nur einen weg, und diese aufgabe ist nun wirklich relativ leicht, klar abgegrenzte felder, nur 2 dimensionen, und nur exakt eine aufgabe, wohin man gehen muss

Bei mir kommt ein ganz einfacher Dijkstra-Algorithmus zur Anwendung. Viele Sonderfälle, die man normalerweise dabei beachten muss, fallen weg, weil die Kantenlänge aller Kanten im Freewar-"Graphen" 1 ist. Die einzige Optimierung, die ich gemacht habe, ist, dass ich darauf verzichtet habe, explizite Kanten zwischen nebeneinderliegenden Feldern zu definieren, um die Datenmenge nicht aufzublähen. Und dann noch das Extra, dass ich nach dem ersten Durchlauf u.U. einige Kanten entferne und erneut rechne, um einen Weg zu finden, der mit weniger Hilfsmitteln nutzbar ist.

Der Dijkstra-Algorithmus ist der klassische "least cost routing"-Algorithmus, der fast ueberall benutzt wird. Ist auch in der Wikipedia gut beschrieben.

Y.

[langeweile]

hab ich mir fast gedacht, dass du den nimmst, der zweite durchlauf find ich gut

hast du auch zwischen transfer-feldern, wie dem wasserfall kanten definiert