Optimaler Multiplayer-Labyrinth-Generierungsalgorithmus

Question

Ich arbeite an einem einfachen Multiplayer-Spiel, in dem 2-4 Spieler an separaten Eintrittspunkten in einem Labyrinth platziert werden und einen Zielpunkt erreichen müssen. Ein Labyrinth im Allgemeinen zu erzeugen ist sehr einfach, aber in diesem Fall ist das Ziel des Spiels, das Ziel vor allen anderen zu erreichen und ich möchte nicht, dass der Generierungsalgorithmus einen Spieler drastisch vor anderen bevorzugt.

Ich bin also auf der Suche nach einem Labyrinth-Algorithmus, wo der optimale Weg für jeden Spieler vom Startpunkt bis zum Ziel nicht mehr als 10% mehr Schritte als der durchschnittliche Weg ist. Auf diese Weise haben die Spieler mehr oder weniger ein gleiches Spielfeld. Kann sich jemand einen solchen Algorithmus ausdenken?

(Ich habe eine Idee, wie es steht, aber es ist nicht gut durchdacht und scheint weit weniger als optimal -. Ich es als eine Antwort hinterlassen werden)

Answer 1

Eine Alternative zur Antwort von freespace wäre, ein zufälliges Labyrinth zu erzeugen, dann jeder Zelle einen Wert zuzuordnen, der die Anzahl der Züge zum Erreichen des Endes darstellt des Labyrinths (du kannst beides gleichzeitig tun, wenn du entscheidest, dass du am Ende anfängst). Dann wähle eine Distanz (vielleicht die höchste mit n Punkten in dieser Entfernung?) Und platziere die Spieler auf Quadrate mit diesem Wert.

Answer 2

Die einfachste Lösung, die ich oben kommen kann mit ist es, zufällig ein ganzes Labyrinth wie normal zu erzeugen, und dann zufällig den Zielpunkt und die Startpunkte des Spielers auszuwählen. Sobald dies erledigt ist, berechnen Sie den kürzesten Weg von jedem Startpunkt zum Ziel. Finden Sie den Durchschnitt und beginnen Sie mit dem "Glätten" (Entfernen/Verschieben von Barrieren - ich weiß nicht, wie das funktionieren wird) mit den Pfaden, die deutlich darüber liegen, bis alle Pfade innerhalb des richtigen Randes liegen. Zusätzlich könnte es möglich sein, diejenigen zu nehmen, die deutlich unter dem Durchschnitt liegen und zusätzliche Barrieren einfügen.

Answer 3

Wie wäre es, zuerst die Position der Spieler und des Ziels und einen Pfad gleicher Länge auszuwählen und anschließend ein Labyrinth zu bauen, das die definierten Pfade berücksichtigt? Wenn die Wege nicht schneiden, sollte dies leicht funktionieren, nehme ich an

Answer 4

Ich würde dies erreichen, indem ich das Ziel und den Eintrittspunkt jedes Spielers setze und dann Pfade ähnlicher Länge für jedes von ihnen zum Ziel erzeuge. Dann würde ich falsche Zweige entlang dieser Pfade hinzufügen, wobei ich darauf achten sollte, dass keine Verbindungen zu den Pfaden anderer Spieler hergestellt werden oder dass ein Zweig mit dem Pfad verbunden wird. Im Grunde ist jeder Zweig eine Sackgasse.

Auf diese Weise garantieren Sie, dass die Pfade in der Länge ähnlich sind. Spieler können jedoch nicht miteinander interagieren. Sie können dies jedoch tun, indem Sie Verbindungen zwischen Zweigen herstellen, so dass Zweigeinstiegspunkte auf beiden Pfaden in ähnlicher Entfernung vom Ziel liegen. Und auf diesem Zweig können Sie mehr Sackgassen für Spaß und Profit abzweigen :-)

Answer 5

Wählen Sie Ihren Ausgangspunkt irgendwo in der Mitte

Ihre N Pfade von dort zu starten, Hinzufügen von 1 zu jedem Pfad pro Schleife, , bis sie so lange, wie Sie sie haben wollen.

Es gibt Ihre N Startpunkte, und sie haben alle die gleiche Länge.

Fügen Sie weitere Zweige von den Linien hinzu, bis das Labyrinth voll ist.