Labyrinthe in Shadowrun

Zitat

nichtrekursive ungerichtete planare Graphen

Ich schlüssel Warentesters Nerdkauderwelsch im Zusammenhang mit der Rechts-/Linkslaufregel in Labyrinthen mal soweit wie möglich auf.

Bei diesem Bild wird man, außen startend, niemals in die Mitte geraten(rekursiv):
[IMG:http://de.academic.ru/pictures/dewiki/75/K4_planar.png]

Ausgehend von einer Linkslaufregel würde man in diesem gerichteten Labyrint niemals bei d ankommen(gerichtet):
[IMG:http://de.academic.ru/pictures/dewiki/50/260px-nicht_topologisch_sortierbarer_graph.svg.png]

Für nichtplanar habe ich kein Beispiel. Planar bedeutet, dass das Labyrint nur eine Ebene haben darf. Generell gibt es nicht planare Labyrinte die mit der Rechtslaufregel lösbar sind, aber nur dann wenn die unterschiedlichen Ebenen durch Schrägen verbunden sind. Senkrecht nach oben/unten wird man mit der Rechtslaufregel halt nie gehen. Stellt euch ein Mietshaus vor und das Ziel ist das Badezimmer in der Wohnung unter/über euch, ihr werdet mit der Rechtslaufregel irgendwann dort landen. Entfernt man nun die Treppe und ersetzt sie durch eine Feuerwehrstange, werdet ihr das Ziel niemals erreichen.

Hinzufügen möchte ich noch zeitinvariant, also die Tatsache, dass sich das Labyrinth, in dem Zeitraum in dem man es löst, nicht verändern darf.

...nichtrekursive ungerichtete zeitinvariante planare Graphen

PS: Graphen sind flapsig gesagt "Linien/Pfeile" zwischen zwei Knotenpunkten, nur falls irgendwer über das Wort stolpert.

*lol*
Ich kann meinen beiden Vorrednern nur auf voller Ebene zustimmen (ist es jetzt gut oder schlecht, dass ich jedes detail genau verstanden habe? ;)), möchte es aber noch um ein paar "Faustregeln" ergänzen.

Zuerst mal ist das zweite Beispiel von Splinter insofern nicht gut, weil es davon ausgeht, dass man bei einer Sackgasse (Knoten F) stehen bleibt und weint, während die Links-/Rechtslaufregel in diesem Fall ja automatisch "wendet" und so auch zu D kommt. Aber generell gilt, dass du deinen Irrgarten gegen diese Strategie "absichern" kannst auf 2 Arten (die sich problemlos kombinieren lassen): 1) veränderbare Wände und 2) Ringe und innere Bereiche, die nicht mit der Außenwand verbunden sind (eben Beispiel 1 von Splinter).
Letztlich braucht es das aber in meinen Augen nicht mal. Denn das die Links-/Rechtslaufen in einem "nichtrekursiven ungerichteten zeitinvarianten planaren Graphen" (also einem konventionellen Irrgarten) funktioniert steht außer Frage, aber diese Strategie ist höchst ineffizient, weil du im schlimmsten Fall durch das ganze Labyrinth läufst, bevor du an deinem Ziel ankommst. Also einfach viele Sackgassen hinzufügen, dann sind deine Spieler lange beschäftigt, auch wenn sie irgendwann garantiert ankommen werden (was ja aus Sicht des Meisters eine optimale Situation ist ^^).

Damn... Raffo war schneller

War nämlich auch meine überlegung

Langjährige Erfahrung mit D&D sagt:
"Linke Hand an Linke Wand" funktioniert
(und im Falle der Pyramide würde Ich.Wenn Ich oben wieder angekommen bin dann" Rechte Hand an Rechte Wand " befolgen und wäre schnell in der Mitte )

Hough !
Medizinmann

Gerichtet meint in dem zweiten Beispiel, dass man nur in Pfeilrichtung laufen kann. Hätte ich dazu schreiben sollen sry.

"Medizinmann" schrieb:

Langjährige Erfahrung mit D&D sagt:
"Linke Hand an Linke Wand" funktioniert
(und im Falle der Pyramide würde Ich.Wenn Ich oben wieder angekommen bin dann" Rechte Hand an Rechte Wand " befolgen und wäre schnell in der Mitte )

Hough !
Medizinmann

Dafür bräuchtest du aber eine Strategie die Gedächtnis vorraussetzt, um oben wiederzuerkennen. Das ist somit keine lokal anwendbare Strategie wie linke Wand/rechte Wand mehr. Die Handwechselstrategie ist aber auch das ist durch ineinander verschachtelte Ringe leicht verhinderbar. Oder durch Knotenkopien, die identisch aussehen, aber an verschiedenen Stellen sind und somit das Opfer zu einem Wechsel der Strategie verführen, obwohl der Wechsel nicht angebracht ist.

Wenn man Gedächtnis zuläßt wäre die optimale Stategie wie üblich A* (also Breitensuche kombiniert mit Greedy-Search, wobei Greedy Search allerdings die Distanz immer unterschätzen muss), aber dafür müsste man natürlich eine zulässige Heuristik für die Distanz zum Ausgang haben.

@Gerichtete Graphen: Dann verbinde einfach F mit A, gerichtet von F-->N und schon rennst du weiter herum und wirst nie bei D ankommen.

Ich hab vor Jahren (noch SR3 Zeiten) mal einen Drachenhort in einen Berg gesetzt, der nur durch ein Höhlen-Labyrinth zu erreichen war. Die SC sollten da was von dem Drachen (kleine gefiederte Schlange, kein großer westlicher Drache falls ihr das jetzt denkt) klauen. Ich hatte das Labyrinth ohne fallen ausgearbeitet, dafür aber in 3D, mit Gängen die nach unten oder oben abknicken und lustigen Schleifen. Eigentlich wollte ich meinen Spielern damit nur das Gefühl vermitteln, dass sie umöglich den kürzesten Weg ans Ziel gelaufen sein können und der Drache deshalb bei einer Flucht garantiert schneller als sie am Ausgang ist.

Das Problem war nur, dass meine Spieler durch (mehr oder weniger) zufälliges links- und rechts abbiegen tatsächlich auf Anhieb den kürzesten Weg zum Ziel gefunden haben.

Um zum Thema zurückzukommen. Drachen, freie Geister oder andere magische Phänomene sind auf jeden Fall eine gute Erklärung für ein Labyrinth. Und spätestens seit der tiefen Lacuna in L.A. kann man jedes verzweigte Höhlensystem in SR mit Magie erklären und quasi beliebig Monster reinpacken.

ich stelle mir gerade in einem Fantasy-System Gullbrakk den Barbar vor, wie er vor einem Labyrinth steht und Überlegungen zu

"Warentester" schrieb:

guter Heuristik für die Distanz zum Ausgang

und

"Splinter" schrieb:

nichtrekursive ungerichtete zeitinvariante planare Graphen

anstellt.

Wenn er ein Troll ist und es sehr kalt im Labyrinth ist, könnte das hinhauen (nach Pratchett).

Die Szene im Schlachthaus... groß, einfach nur groß! Schade um dieses Genie.

A* (Warentester) oder ein Strategiewechsel (Medizinmann) funktioniert aber nur zufällig (mein Beileid, Trichter ;)) oder wenn man einen Plan hat, da man sonst nicht weiß, wann man den Strategiewechsel durchführen muss, oder die Heuristik für A* zwangsweise so stark unterschätzt, dass man effektiv mit einer nackten Breitensuche rumläuft, die wieder die erwähnte Ineffizienz hat. Und wenn man einen Plan hat, ist die ganze Diskussion eher langweilig, weil man dann sogar Routenplaner dafür einsetzen kann, einem den kürzesten Weg inkl. Donut-Stop zu berechnen...

"Raffo" schrieb:

Und wenn man einen Plan hat, ist die ganze Diskussion eher langweilig, weil man dann sogar Routenplaner dafür einsetzen kann, einem den kürzesten Weg inkl. Donut-Stop zu berechnen...

Und was glaubst du, welchen Suchalgorithmus der Routenplaner verwendet

Das Hauptsproblem mit der Strategie mit Memory ist, dass man zwei neue Problemfelder eröffnet:
1. Man muss alle besuchten Knoten im Kopf/Gedächtnis behalten. Dies kann recht Memorylastig werden (spielt aber eigentlich nur bei VR oder magischen Irrgärten eine Rolle, da man sonst ausreichend viel Speicherplatz zur Verfügung hat).

2. Man muss bestimmen, ob ein Knoten mit einem bereits besuchten Knoten identisch ist. Dies ist nicht immer ganz einfach und man kann dies versuchen gezielt zu täuschen. Wenn dieser Prozess fehlerhaft ist, wird die Suche extrem erschwert, weil man widersprüchliche Informationen Einspeichert.

"Warentester" schrieb:

Und was glaubst du, welchen Suchalgorithmus der Routenplaner verwendet

Der hat ja die Karte... (Und wenn er den Donut-Stand findet, weiß er auch mehr als der Meister! ^^)

Je mehr ich hierr mit Irrgärten zu tun habe, desto mehr hab ich vor, sowas jetzt selbst mal auszuprobieren in einem Run. Aber dann natürlich nur die harte Variante, mit variablen Wänden, etlichen Schleifen, 3D... Kennt irgendjemand einen Berg, den man für diesen Zweck aushöhlen und durchlöchern könnte?
Overmind, sobald du mit deinem Run durch bist, hätte ich gerne ein paar Berichte und Ideen.

Die "Karte" ist für den Routenplaner ein Graph. Und darauf läuft ein Suchalgorithmus. Du kannst einem Computer nicht einfach eine Karte (als Bild) geben und dann "weiß" er wo der Ausgang ist.

In Shadowrun schon.

Nein. Auch dort nicht. Dort sind lediglich die imageprozessingfähigkeiten besser.

Und das ändert was genau am Ergebnis?

Das es nach wie vor eine Graphensuche ist nachdem das Bild in einen Graphen ungewandelt wurde und kein Göttlich eingegebenes Wissen.

Warentester : Ich glaube, wir reden hier ein wenig aneinander vorbei... Was ich ja meinte war, dass der Routenplaner eben seinen vollständigen (!) Graphen/seine Karte/seinn Bild schon fertig hat, und deshalb effizient die günstigste Route ausrechnen kann (einfach gesagt, "weil er's ja sieht"). Was ich meinte war, dass ein A* ein einem geschickt angelegten Irrgarten, von dem vorher nichts bekannt ist ("keine Karte"), immer noch trotz Heuristik so viele Wege durchgehen muss, dass er nah am worst case ist (was dann halt fast wieder eine "dumme" Breitensuche wäre).

"Overmind" schrieb:

Nur die astrale Bewegung des Magiers würd ich doch gern unterbinden können, wenn sich das irgendwie realistisch machen lässt. Weil das gerade in dieser Höhle überall duales Efeu von den Wänden hängt ist dann wohl doch etwas abgefahren. Hab auch schon an duale Bakterienstämme gedacht. Will aber auch nicht so ganz passen. Und warum sollte es in der Höhle so große Hintergrundstrahlung geben? Fragen über Fragen...

Gut, das Beispiel mit dem massig vorhandenen Efeu von mir war wirklich doof, weil völlig unpraktikabel in dieser Größenordnung. Aber in diesem Fall ist das Schlüsselwort "Höhle", unter der Erde ist astrale Bewegung ohnehin ziemlich erschwert (wobei ich auch erst selber die genauen Regeln nachschauen müsste), eben weil schon so viele Lebewesen (Insekten, Bakterien etc.) in natürlicher Erde leben. Und selbst relativ hohe Hintergrundstrahlung lässt sich sehr leicht erklären. Was ist das denn für ein Gelände? Wenn es der Zugang zu einem Drachenhort gewesen wäre, hätte der Drache allein schon für diese Hintergrundstrahlung gesorgt, indem er regelmäßig selbst die Gänge abgeht. Passieren da unten "komische Dinge", unnatürliches Zeug, grausames Zeug, und das in großen Dosen? Bingo...