Ich habe eine einfache gitterbasierte Karte, die aus solchen Räumen besteht (A = Eingang, B = Ausgang):
0 1 2 3 ######### 0 # B # ##### ######### 1 # ### # ######### 2 # # # # # # 3 # # # ######### 4 # ### # ######### 5 ### A # ### # 6 ### # #########
Und ich bin festgefahren, einen geeigneten Algorithmus zu entwickeln, um einen Türweg zwischen den Räumen zu erstellen, so dass der Spieler den größten Teil der Karte erkunden muss, bevor er den Ausgang findet.
Mit anderen Worten, ich versuche den längsten Weg von A nach B zu finden .
(Mir ist bewusst, dass dieses Problem für azyklische Graphen gelöst werden kann. In diesem Fall kann es jedoch zu Zyklen kommen.)
BEARBEITEN: Ein weiteres Beispiel, bei dem Räume mithilfe von Floodfill verbunden werden und der Ausgang als der am weitesten vom Eingang entfernte Raum ausgewählt wird:
0 1 2 3 ######### 0 # B # # # # - ##### 1 # | # # ### # # 2 ### # # ### - # - ### 3 # | ### # - ####### 4 #A | # # # # 5 # # # # # # 6 # # # #########
Beachten Sie, dass der Pfad zum Ausgang überhaupt nicht der längste ist.
quelle
Antworten:
Ich denke, du machst das falsch. Der maximale Pfad in einem Diagramm mit Zyklen ist technisch undefiniert, da er unendlich ist, wenn der Zyklus zwischen Anfang und Ende liegt. Es gibt wahrscheinlich clevere Möglichkeiten, die Definition des maximalen Pfades zu erweitern / einzuschränken, aber ich denke nicht, dass dies hier der beste Ansatz ist.
Sie versuchen nicht, einen tatsächlichen langen Pfad zu modellieren (z. B. einen Roboter, der versucht, so viel Gebiet wie möglich auf einer Karte zu erkunden). Sie versuchen nur, den Spieler dazu zu bringen, viele Räume zu erkunden.
Also, machen Sie die Chance der Spieler findet der Ausgang proportional zum Prozentsatz der Karte so weit erforscht . Angenommen, es gibt X Räume auf einer Ebene, und der Spielercharakter hat Y erkundet. Wenn der Charakter das nächste Mal einen Raum betritt, platzieren Sie den Ausgang dort mit der Wahrscheinlichkeit f (Y, X). Ein triviales Beispiel für f könnte (Y * Y) / (X * X) sein - z. B. besteht für 10 Räume eine 100% ige Chance, dass der Ausgang im letzten Raum liegt, eine 81% ige Chance, dass er sich im vorletzten Raum befindet - und nur a 1% Chance, dass es im ersten Raum ist.
Sie können die Gleichung anpassen, wie Sie möchten, damit sich das Spiel richtig anfühlt, und dem Spieler möglicherweise sogar einige Fähigkeiten geben, um die Wahrscheinlichkeit zu erhöhen, dass es generiert wird. Der Schlüssel ist, erst den Ausgang zu generieren, wenn der Charakter tatsächlich den Raum betritt. Diese Methode ist auch immun gegen das Wissen der Spieler über den Dungeon-Generierungsalgorithmus. Selbst wenn der Spieler seltsame Bewegungsmuster wie den Sprung des Ritters in NetHack oder die Teleportation hat, muss er mehr Räume erkunden, um den Ausgang zu finden.
Wenn Sie den Exit statisch generieren müssen , können Sie dieselbe Idee mit einem virtuellen Charakter verwenden. Stellen Sie sich eine Flutfüllung vor, die von der Position des Charakters ausgeht und sich bei jeder Iteration einmal in einer Zelle bewegt. Der letzte Raum, der gefüllt wird, ist der Raum, in den der Ausgang gehört (tatsächlich ist die letzte Zelle, die gefüllt wird, die Zelle, in der sie am weitesten vom Spieler entfernt ist). In diesem Fall hat der Spieler jedoch mehr Informationen über den Ausgang - wenn er sich links befindet, ist es höchstwahrscheinlich rechts - und wenn er sich teleportieren kann, kann er möglicherweise tatsächlich schneller als ein normaler zufälliger Spaziergang dorthin gelangen.
Schließlich habe ich gerade ein Roguelike beendet, bei dem der Ausgang auf der anderen Seite der Karte vom Spielercharakter erzeugt wurde, und bin dann zufällig gewandert. Einige Gegenstände im Dungeon machten es auf der Karte sichtbar, auf Kosten des schnelleren Hungers. Ich habe keine Analyse durchgeführt, aber es fühlte sich definitiv so an, als müsste ich mehr von der Karte erkunden, um sie zu finden, und es gab den Levels ein einzigartiges Gefühl.
quelle
Eine mögliche Alternative wäre, mit Prim / Kruskal einen (maximalen?) Spanning Tree zu erstellen (um Zyklen zu eliminieren) und einen traditionellen Algorithmus für den längsten Pfad auf den Spanning Tree anzuwenden.
Ich mache mir jedoch Sorgen, dass der Spanning Tree-Algorithmus dazu neigt, Sackgassenverzweigungen zu erzeugen, die den Spieler dazu zwingen, sich ständig zurückzuziehen.
BEARBEITEN: Ergebnis der Verwendung eines Kruskal-basierten Algorithmus und Platzieren des Ausgangs am Ende des längsten Zweigs:
quelle
Hier ist etwas zum Spielen:
Ich würde zufällig Türen entlang des Pfades entfernen, sonst erhalten Sie 1 Tür am Ausgang und Tonnen von Türen am Anfang.
Ich denke, das ist
O(n^2)für große Karten nicht so toll.quelle
2 Stapelüberlaufpfosten ähnlich diesem: Diagramm längster Pfad , Referenz von demselben Beitrag .
quelle
Ich glaube, Sie haben bereits gute Antworten, aber hier ist meine theoretische Lösung für das Problem in Höhe von 0,02 USD.
Was Sie wollen, ist NICHT der längste Weg, sondern der längste kürzeste Weg. Sie möchten den Raum, der am weitesten entfernt ist, vorausgesetzt, Sie erwägen den kürzesten Weg zum Raum. Das klingt wahrscheinlich verwirrend, ist aber sehr einfach zu berechnen.
Das Berechnen eines tatsächlich längsten Pfades (dauert nicht zu lange für beispielsweise 10 Räume) funktioniert nicht, da Sie den Spieler nicht dazu bringen können, diesen längsten Pfad zu nehmen. Daher ist es am besten, den Ein- und Ausgang in zwei Räumen zu platzieren, die am weitesten voneinander entfernt sind. Um dies zu finden, berechnen Sie den am weitesten entfernten Raum aus einem zufälligen Raum. Dann finden Sie von diesem Raum aus den am weitesten entfernten Raum. Dies wird als Ermitteln des Durchmessers eines Diagramms bezeichnet. Bitte googeln Sie es.
quelle