Prozedural… Haus mit Raumgenerator

74

Ich habe mir einige Algorithmen und Artikel zum prozeduralen Generieren eines Dungeons angesehen. Das Problem ist, dass ich versuche, ein Haus mit Zimmern zu bauen, die meinen Anforderungen nicht entsprechen.

Zum einen haben Dungeons Korridore, in denen Häuser Hallen haben. Und während sie anfangs vielleicht gleich aussehen, ist eine Halle nichts anderes als der Bereich, der kein Raum ist, während ein Korridor speziell dafür ausgelegt ist, einen Bereich mit einem anderen zu verbinden.

Ein weiterer wichtiger Unterschied zu einem Haus besteht darin, dass Sie eine bestimmte Breite und Höhe haben und das Ganze mit Räumen und Hallen füllen müssen, während bei einem Verlies der Raum leer ist.

Ich denke, Hallen in einem Haus sind etwas zwischen einem Dungeon-Korridor (der Sie zu anderen Räumen führt) und einem leeren Raum im Dungeon (der nicht explizit im Code definiert ist).

Insbesondere sind die Anforderungen:

  • Es gibt eine Reihe vordefinierter Räume, in denen
    ich keine Wände und Türen im laufenden Betrieb erstellen kann.
  • Räume können gedreht, aber nicht in der Größe verändert
    werden. Da ich über einen vordefinierten Satz von Räumen verfüge, kann ich sie nur drehen, nicht aber in der Größe verändern.
  • Die
    Hausmaße sind festgelegt und müssen vollständig mit Räumen (oder Hallen) gefüllt sein. Das heißt, ich möchte ein 14x20-Haus mit den verfügbaren Räumen füllen, um sicherzustellen, dass es keinen leeren Raum gibt.

Hier sind einige Bilder, um dies etwas klarer zu machen:

Typischer Dungeon Generator Dungeon ohne Korridore Hausgenerator Ergebnis

Wie Sie sehen können, ist der "leere Raum" im Haus noch begehbar und bringt Sie von einem Raum zum anderen.

Nach alledem ist ein Haus vielleicht nur ein wirklich sehr dicht gedrängter Kerker mit Korridoren. Oder es ist einfacher als ein Dungeon. Vielleicht gibt es da draußen etwas, und ich habe es nicht gefunden, weil ich nicht wirklich weiß, wonach ich suchen soll.

Hier möchte ich Sie um Ihre Hilfe bitten: Können Sie mir Hinweise zum Entwurf dieses Algorithmus geben? Irgendwelche Gedanken darüber, welche Schritte es unternehmen wird? Wenn Sie einen Dungeon-Generator erstellt haben, wie würden Sie ihn an meine Anforderungen anpassen? Sie können so spezifisch oder allgemein sein, wie Sie möchten. Ich bin wirklich auf der Suche nach deinem Verstand.

pek
quelle
2
Eine seltsame Empfehlung: Ich empfehle nachdrücklich, Christopher Alexanders Bücher The Timeless Way Of Building und A Pattern Language zu lesen , die Architekturbücher, die die ursprüngliche Grundlage für den Begriff eines (Software-) Musters bildeten. Sie beschreiben im Wesentlichen eine explizite Sprache für Gebäude und Wohnräume, die in eine prozedurale Bauweise von oben nach unten umgewandelt werden kann.
Steven Stadnicki
Persönlich würde ich versuchen, einen Algorithmus wie die Antwort von egarcias zu erstellen. Beginnen Sie mit der Generierung von Raumplatzhaltern (große Bereiche, die mit einer unterschiedlichen Anzahl von Räumen gefüllt werden können. Jeder Raumplatzhalter muss eine bestimmte (oder zufällige mit einer niedrigeren Schranke) Größenlücke aufweisen Wird als Flur betrachtet, dh als Raum im Haus, aber nicht in einem Raum, und die Raumplatzhalter werden durch Räume mit zufälliger Größe gefüllt, ähnlich wie in Ihrem Beispiel "Dungeon ohne Korridore".
Benjamin Danger Johnson
@pek Bitte erstellen Sie eine Antwort für Ihre Lösung, nicht in die Frage stellen.
MichaelHouse
@ Byte56 Fertig. Um es klar zu sagen, ich habe das getan, weil ich keine Anerkennung erhalten wollte, da ich nur das getan habe, was andere Leute vorgeschlagen haben. Ich verstehe jedoch, warum dies für das Format der Site nicht ideal ist, und fügte meine Antwort hinzu.
pek
Danke @pek. Machen Sie sich keine Sorgen, ob Sie Kredite bekommen, es ist verdient und nützlich für Leute, die auf die Website kommen, um die Lösung zu sehen (und zu sehen, wo sie am besten zu erwarten ist).
MichaelHouse

Antworten:

50

Ich denke, dies ist ein guter Fall für die Verwendung von binären oder ternären Raumpartitionen.

Teilen Sie den Hausraum beim ersten Durchgang in Hallen und {Wohnblocks} auf. Holen Sie sich den nächsten großen Teil, teilen Sie ihn in {Halle und Teil} oder {2 Teile und Halle dazwischen} auf. Drehen Sie die Schnittrichtung bei jedem Schritt um 90 Grad. Stoppen Sie, wenn {keine großen Brocken mehr übrig sind} oder {die gesamte Hallenfläche das Limit erreicht hat}.

Teilen Sie beim zweiten Durchgang die verbleibenden Stücke in Räume auf. Holen Sie sich das nächste große Stück und teilen Sie es. Überspringen Sie die zufällige Aufteilung einiger weniger großer Stücke, um einige große Räume zu haben.

Wenn eine Halle einer viel älteren Halle zugewandt ist, platzieren Sie dort eine Wand (oder eine Wand mit Tür).

Verbinden Sie Räume mit Hallen direkt oder durch andere bereits verbundene Räume.

Zum Beispiel können Sie entweder mein manuell erstelltes Ergebnis oder C ++ sehen - ähnlich wie teilweise erstellten Pseudocode . Letzter Schuss:

letzter Schuss

Schatten im Regen
quelle
Das ist, wo meine Forschung ergab, in Raumaufteilung. Ihr Beispiel mit Code gab mir einen sehr sehr guten Start. Ich lese gerade über Algorithmen. Eine Frage: Eine meiner Anforderungen ist, dass Räume vordefiniert sind (dh es gibt 2x2 Räume mit einer Tür, 1x1 mit zwei Türen, aber keine 2x2 mit drei Türen), sodass ich nicht mit der Unterteilung beginnen und dann entscheiden kann, wo ich Türen platzieren werde . Ich denke, ich muss meine Einschränkungen berücksichtigen, während ich partitioniere. Haben Sie einen Vorschlag, wie ich vorgehen würde? Auf jeden Fall vielen Dank für Ihre Antwort und Mühe!
pek
@pek Ich bin mir nicht sicher, ob ein Sterblicher eine akademische Lösung für dieses Problem finden kann. Sie können versuchen, zusätzliche Bedingungen für Chunk-Splitter und Box-Splitter festzulegen und dann Ebenen zu generieren und zu löschen, bis Sie eine finden, bei der alle Bedingungen erfüllt werden können.
Schatten im Regen
Ja, ich hatte gehofft, dass mir etwas fehlt. Mein erster Ansatz war die Verwendung von A *, um herauszufinden, wie die Räume in einen bestimmten Raum passen, aber es fehlte die Logik für die Hallen. Jetzt denke ich, dass ich BSP verwenden kann, um Hallen zu platzieren, und dann A * für die Blöcke verwenden kann. Ich mache mir hauptsächlich Sorgen, dass es zu teuer sein könnte und nicht immer zu einem Ergebnis führt. Aber ich muss das erst testen. Vielleicht wird es nicht so schlimm sein?
pek
2
@pek Ich habe etwas Nützliches gefunden, wenn Sie noch interessiert sind. Schauen Sie sich diese , auch Google L-system.
Schatten im Regen
24

Sie können die Tatsache nutzen, dass Ihr gewünschtes Design die Räume in rechteckige Räume umgibt, die von Korridoren umgeben sind. In diesem Sinne würde ich Folgendes tun:

  1. Entwerfen Sie die Flure und die "großen Räume" für Räume
  2. Füllen Sie jeden "großen Raum" mit Räumen aus

2 Schritte

Das Auffüllen der großen Räume mit Räumen ist einfach, wenn Sie mit den Räumen an den Rändern beginnen - sie unterliegen bestimmten Einschränkungen, z. B. können die Räume, die einem Korridor zugewandt sind, eine Tür an dieser Wand haben, aber die Räume, die den „Außenwänden“ zugewandt sind. kann nicht (sie könnten vielleicht Fenster haben). Räume "innerhalb" der großen Blöcke der Räume benötigen mindestens einen Eingang.

egarcia
quelle
15

Also, hier ist, wie ich dieses Problem gelöst habe. Aber zuerst möchte ich mich bei @Shadows In Rain und @egarcia für ihre Antworten bedanken. Sie gaben mir eine gute Richtung, die mir half, einige Ergebnisse zu erzielen.

Ich benutzte Shadows In Rain's Raumaufteilung, um ein einfaches Haus zu erstellen und folgte dann Egarcias Rat, um den Bereich mit Räumen auszufüllen.

Die Raumaufteilung war ziemlich unkompliziert, da 90% des Codes von Shadows erstellt wurden. Der Teil "Räume ausfüllen" war etwas herausfordernder. Ich entschied mich für ein Pseudo-KI-Planungssystem, das A * verwendet, um die Räume entsprechend zu positionieren. Das Gute an der Verwendung von Planung anstelle von nur A * ist, dass die Voraussetzungen dazu beitragen, den Suchraum erheblich zu verringern.

Hier sind einige Screenshots mit den Ergebnissen:

Grundrisserstellungsphase Grundrisserstellungsphase

Raumvergabephase Raumvergabephase

Jetzt mit Verbindungstüren!
Jetzt mit Verbindungstüren!

pek
quelle
11

Dahl & Rinde haben eine Abschlussarbeit über die prozedurale Erzeugung von Innenräumen verfasst, die einen Skelett- & Regions-Ansatz verwendet, um Gebäudeinnenräume mit Räumen und Fluren zu füllen. Das Papier enthält Klassendiagramme für ihren Prototyp. Es gibt auch einige gute Referenzen in ihrer Bibliographie, einschließlich der oben erwähnten A Pattern Language .

Ihre Arbeit war auf die folgenden vereinfachenden Annahmen ausgerichtet:

  • nur mit Mehrfamilienhäusern
  • Keine aufgeteilten Ebenen
  • Die Begrenzung der Gebäudeform (Hülle) muss polygonal sein
  • Keine Löcher im Umschlag
  • ähnliche oder sich linear ändernde Hüllendicke (dh keine Sanduhrformen)
  • Nur für Gebäude, die Korridore benötigen

Hier ist ein kurzer Überblick über ihren Prozess:

  • Finden Sie das Skelett für den Umschlag. Korridore werden dann entlang des Skeletts basierend auf dem Abstand zur Hülle, der Nähe zu Türen oder Treppen und der Nähe zu zuvor platzierten Korridoren platziert.
  • Als nächstes wird der verbleibende Nichtkorridorraum in maximal verbundene Bereiche mit jeweils einer einzigen durchgehenden Grenze unterteilt. In einigen Fällen muss hierfür eine Wand eingefügt werden.
  • Diese Regionen werden dann in Wohnungen unterteilt, die versuchen, mindestens ein Fenster pro Wohnung zuzuweisen. In einigen Fällen werden kleinere Bereiche zusammengelegt, um zu kleine Wohnungen zu vermeiden. Regionen ohne Fenster werden einfach ignoriert.
  • Schließlich werden die Wohnungen anhand eines gewichteten Voronoi-ähnlichen Diagramms wie folgt in Räume unterteilt:

    • Samengewichte werden verwendet, um die Raumgröße zu beeinflussen. Samen werden an Türen und Fenstern hinzugefügt. Zusätzliche Samen werden hinzugefügt, im Allgemeinen einer pro gewünschtem Raum; Obwohl nicht explizit angegeben, sieht es so aus, als ob die Samen entlang der Außenwände der Wohnung platziert werden.
    • Beginnend mit dem am weitesten entfernten Punkt wird eine Linie zwischen dem gegebenen Startpunkt und allen anderen Punkten berechnet und dann ein Abstand relativ zu den jeweiligen Gewichten der Endpunkte halbiert (ZB wenn A & B Gewichte von 1 & 4 hätten, wäre der Halbierungspunkt 1/4 des Weges von A nach B). Die Ansammlung von Halbierungslinien bildet dann zusammen mit der Außenwand die Zelle für den Samen.
    • Anschließend wird ein S-Space-Wandskelett (nach Peponis et al. 1997) erstellt, indem der Bereich durch Linien unterteilt wird, die senkrecht von den Mittelpunkten zwischen benachbarten Paaren von Außenwandelementen (Fenstern oder Türen) ausgehen.
    • Schließlich werden Wände aus dem S-Raum-Gerüst ausgewählt, die "den Voronoi-Zellwänden so gut wie möglich entsprechen".
Pikalek
quelle
3
Können Sie Bilder einbinden? Das wäre toll. Ich habe das Papier überflogen und die Räume, die sie erzeugt haben, sahen aus einem architektonischen POV gut aus.
congusbongus
Sehr interessante Methode, ich muss sie mir genauer ansehen, um herauszufinden, welche Ideen ich daraus ableiten kann.
Draco18s
Ich bin hierher gekommen, um mich von der Arbeit zu erholen ... Überrascht, dass mein Forschungsthema herauskommt. Ich bin zu faul, um eine Antwort zu schreiben, die auf meinen eigenen Forschungen basiert (ich habe bisher nur die nackten Knochen des Algoirthms entworfen, es lohnt sich also sowieso nicht) oder Danil Nagys Herangehensweisen an das Problem zu beschreiben autodeskresearch.com/publications/…
Felipe Gutierrez