Also habe ich darüber nachgedacht, einen einfachen zufälligen Weltgenerator zu machen. Dieser Generator würde eine Startzelle erstellen, die zwischen einem und vier zufälligen Ausgängen (in den Hauptrichtungen, so etwas wie ein Labyrinth) hätte. Nachdem ich diese Ausgänge bestimmt hatte, erzeugte ich an jedem dieser Ausgänge eine neue zufällige "Zelle" und wiederholte sie, sobald ein Spieler sich einem Teil der Welt näherte, der noch nicht erzeugt worden war. Dieses Konzept würde eine "unendliche" Welt von Arten erlauben, alle zufällig erzeugt; Ich bin mir jedoch nicht sicher, wie ich das intern am besten darstellen soll.
Ich benutze C ++ (was nicht wirklich wichtig ist, ich könnte jede Art von Datenstruktur implementieren). Zuerst dachte ich daran, eine Art gerichteter Graphik zu verwenden, in der jeder Knoten Kanten zu jeder ihn umgebenden Zelle geleitet hätte, aber das wird wahrscheinlich nicht gut funktionieren, wenn ein Benutzer einen Punkt in der Welt findet, Backtracks zurückkehrt und darauf zurückkommt Spot aus einer anderen Richtung. Die Welt könnte einige seltsame Dinge tun, zum Beispiel zwei Zellen an einem Ort erzeugen.
Irgendwelche Ideen, welche Art von Datenstruktur für eine solche Situation am effektivsten ist? Oder mache ich etwas wirklich Dummes mit meiner zufälligen Weltgeneration?
Jede Hilfe wird sehr geschätzt. Vielen Dank, Chris
A map< pair<int,int>, cell> würde wahrscheinlich gut funktionieren; das Paar würde die x, y-Koordinaten darstellen. Wenn sich an diesen Koordinaten keine Zelle in der Karte befindet, erstellen Sie eine neue Zelle. Wenn Sie es wirklich unendlich machen wollten, könnten Sie die Ints durch eine Integer-Klasse beliebiger Länge ersetzen, die Sie bereitstellen müssten (wie zum Beispiel eine Bigint)
Ich empfehle Ihnen, über Graphen zu lesen. Dies ist genau eine Anwendung der zufälligen Graphengenerierung. Statt 'Zelle' und 'Ausgang' beschreiben Sie 'Knoten' und 'Kante'.
Außerdem können Sie Dinge wie die Analyse des kürzesten Wegs, die Zykluserkennung und alle anderen nützlichen Anwendungen der Graphentheorie durchführen.
Dies hilft Ihnen, die Knoten und Kanten besser zu verstehen:
und hier ist eine fertige Anwendung dieser Konzepte. Ich implementierte dies auf eine OOP-Weise - jeder Knoten wusste von seinen Kanten zu anderen Knoten. Eine beliebte Alternative ist die Implementierung einer Adjazenzliste . Ich denke, das Konzept der Adjazenzliste ist im Grunde das, was user470379 mit seiner Antwort beschrieben hat. Seine Kartenlösung erlaubt jedoch unendliche Graphen, während eine traditionelle Adjazenzliste dies nicht tut. Ich liebe die Graphentheorie, und das ist eine perfekte Anwendung davon.
Viel Glück!
-Brian J. Stianr
Wenn die Zellen der Welt in einem Gitter angeordnet sind, können Sie ihnen leicht kartesische Koordinaten geben. Wenn Sie eine große Liste vorhandener Zellen behalten, können Sie vor dem Bestimmen von Exits aus einer bestimmten Zelle diese Liste überprüfen, um zu sehen, ob einer ihrer Nachbarn bereits existiert. Wenn sie das tun und keine 1-Wege-Türen (gerichteter Graph?) Haben wollen, dann müssen sie ihre Ausgänge berücksichtigen. Wenn es Ihnen nichts ausmacht, Rutschen in Ihrem Spiel zu haben, können Sie immer noch Exits nach dem Zufallsprinzip wählen, stellen Sie einfach sicher, dass Sie mit vorhandenen Zellen verlinken, wenn sie da sind.
Optimierungshinweis: Wenn Sie eine Hashtabelle überprüfen, um festzustellen, ob sie einen bestimmten Schlüssel enthält, ist O (1).
Konnten Sie keinen Hash (oder STL-Satz) haben, der eine Sammlung aller Gitterkoordinaten speicherte, die besetzte Zellen enthielten?
Wenn Sie dann eine neue Zelle erstellen, können Sie schnell prüfen, ob der Zellkandidaten bereits belegt ist.
(Wenn Sie endlich Platz hatten, könnten Sie ein 2D-Array verwenden - ich glaube, ich sah das in einem Artikel von Byte Magazine in ~ 1980-ish, aber wenn ich richtig verstehe, wollen Sie eine Welt, die sich unbegrenzt erweitern könnte) / p>
Tags und Links c++ data-structures