Wie kann man einen Algorithmus entwickeln, um ein zufälliges, aber gültiges Gleislayout zu generieren?

https://cs.stackexchange.com/questions/117972

28-09-2020
|

Frage

Ich frage mich, ob ich eine Menge C an gebogenen Gleisen und eine Menge S an geraden Gleisen habe, wie ich einen Algorithmus (computergestützt oder nicht) entwickeln könnte, um ein „zufälliges“ Layout unter Verwendung all dieser Gleise zu entwerfen, sodass die folgenden Regeln gelten sind zufrieden:

1) Wenn alle Gleise miteinander verbunden sind, bilden sie eine geschlossene (kontinuierliche) Schleife, um die der Zug herumfahren kann.

2) Rampen, das Biegen von Gleisen, das Anstoßen von Gleisen und das Überqueren von Gleisen sind nicht gestattet.

3) C und S sind beide gerade Zahlen.Ein Beispiel wäre C=20 und S=10.Beachten Sie, dass 12 Kurven in derselben Ausrichtung erforderlich sind, um einen vollständigen Kreis von 360 Grad zu erstellen. Daher müssen mindestens 12 dieser Kurven in die gleiche Richtung ausgerichtet sein, um die 360 Grad zu vervollständigen.Die anderen können „im Zickzack“ fahren, solange das Nettoergebnis 360 Grad beträgt, sodass der Zug eine vollständige Schleife bildet.

Gerade Gleise sind etwa 10 Zoll (25,4 cm) lang und gebogene Gleise sind etwa 12,4 Zoll (31,6 cm) lang (in der Mitte entlang der Kurve) und weisen einen Winkel von 30 Grad auf.Die „Schwellen“ an den Gleisen haben eine maximale Breite von 3 5/8 Zoll (9,2 cm).Ich habe ein gerades und ein gebogenes Gleis übereinander gelegt und gemessen, dass die 12,4" (31,6 cm) lange Kurve eine lineare Länge von 12" (30,5 cm) (in der gleichen Richtung wie die gerade) und 3" (7,6 cm) hat. der Biegung (in der senkrechten Richtung der Geraden).Ein 12C-Kreis hat einen Durchmesser von 47,5 Zoll (120,6 cm) von Mitte zu Mitte der Schienen auf gegenüberliegenden Seiten.

Alle Maße sind ungefähre Angaben.

AKTUALISIEREN

Ich habe die Gleise mit vielen weiteren Gleisen neu vermessen, um Fehler auszuschließen, und zu meiner Überraschung beträgt die Länge der Geraden NICHT 10 Zoll, sie scheinen etwa 9,78 Zoll zu betragen.Dies hat erhebliche Auswirkungen auf die Anpassung von Zickzackkurven an Geraden.Ursprünglich dachte ich, 4 Zickzackkurven = 5 Geraden, aber das ist nicht ganz richtig.4 Kurven haben eine lineare Entfernung von etwa 47 Zoll, sodass 5 Geraden mit jeweils 9,78 Zoll 48,9 Zoll, fast 2 Zoll länger wären.Der Trick besteht also darin, das LCM (kleinstes gemeinsames Vielfaches) von 47 und 9,78 zu ermitteln.Es stellt sich heraus, dass es 235 sind.235 = 47*5 und 235/9,78 = 24,028...(nah genug).Das bedeutet, dass 20 Zickzackkurven praktisch 24 Geraden in linearer Länge entsprechen.Zum Glück habe ich 26 Geraden, also habe ich es gerade noch geschafft.Die beiden verbleibenden können problemlos an anderer Stelle im Layout positioniert werden.

Eine andere Sache, die ich herausgefunden habe, ist, dass, wenn ich die Kurven in jeweils zwei Richtungen im Zickzack verlaufe (OOCCCCOO), 8 davon einen linearen Abstand von nur 83 Zoll haben, nicht 94 Zoll, wie wenn ich Kurven abwechsele (OCCOOCCO).Der LCM von 83 und 9,78 beträgt etwa 166.16 dieser Kurven haben also die gleiche lineare Länge wie 17 Geraden.Das ist nützlich zu wissen, weil ich 44 Kurven und nur 26 Geraden habe, aber wenn ich diesen Ersatz mache, kann ich helfen, das auszugleichen.

Wenn ich die Kurven 3 auf einmal im Zickzack verlege (OOOCCCCCCOOO) und sie nur leicht biege, erhalte ich die exakte lineare Länge von 10 Geraden (ungefähr 97,8 Zoll).

ENDE DES UPDATES

Müsste das Computerprogramm also ein geometrisches Modell erstellen und sich die genauen Positionen jeder Spur merken, oder gibt es eine einfachere Möglichkeit, dies zu codieren?Ich möchte in der Lage sein, „einen Knopf zu drücken“ und der Computer „ausspuckt“ ein gültiges „neues“ Layout für mich.

Ich möchte diesen funktionierenden Algorithmus den Kindern geben, die die Züge benutzen, damit sie nicht frustriert werden, wenn sie eine Anlage ausprobieren, die nicht funktioniert, und dann versuchen, die Gleise zu biegen, damit sie funktioniert, oder ein paar Gleisstücke weglassen müssen Weil sie nicht passen.Ein Computer kann aus allen Gleisen ein gültiges Layout erstellen, und wenn der Algorithmus gut ist, vielleicht in wenigen Sekunden.Dies soll dazu beitragen, Frustrationen bei ihnen vorzubeugen.

Ich habe einige Programmierkenntnisse, aber ich muss zuerst einen Algorithmus kennen, bevor ich etwas Sinnvolles programmieren kann (außer nur ein paar Teile eines Kandidatenalgorithmus zu testen).

Ich denke, ich könnte den Computer die Spuren anhand einer kleineren (verkleinerten) Darstellung modellieren lassen.Ich denke, es könnte dann einfach die Gleise im Kandidatenlayout „platzieren“ und auf Kollisionen mit anderen bereits vorhandenen Gleisen prüfen.

Ich denke jedoch, dass es wahrscheinlich bessere Möglichkeiten gibt, dies zu tun, deshalb bitte ich hier um Hilfe/Ideen.Ich möchte das wirklich zum Laufen bringen und habe die Tracks hier, damit ich sie verwenden kann, um zu überprüfen, ob der Algorithmus funktioniert.

Wir können C=20 und S=10 als Parameter verwenden, um zu versuchen, dieses Problem zu lösen, da es sich um eine relativ kleine Anzahl von Spuren handelt (insgesamt 30).Ich gehe davon aus, dass, wenn der Algorithmus robust genug ist, die C- und S-Werte nach Belieben geändert werden können und er trotzdem funktioniert.Zum Beispiel möchte ich irgendwann C=44 und S=26 ausprobieren.

Letztes Wort

Vielen Dank an alle für Ihre Kommentare und Vorschläge zu dieser Frage.Ich habe auch viel gelernt.Als Kind habe ich nie wirklich viel über Bahngleise und deren Zusammengehörigkeit nachgedacht, aber als Erwachsener kann ich sehen, dass es ein faszinierendes geometrisches Problem und ein sehr schwieriges mathematisches Rechenproblem ist, wie viele verschiedene (einzigartige) Gleisanordnungen zu generieren bzw. herauszufinden es gibt.Ich hoffe, Ihnen hat diese Übung genauso viel Spaß gemacht wie mir.Auch die Kinder wissen es zu schätzen.

Ende Letztes Wort

Lösung

Ich dachte, ich würde die Brute-Force-Lösung anbieten.

Die Idee besteht darin, nacheinander jedes einzelne Gleislayout auszuprobieren.Beim Erstellen eines Layouts müssen nur drei Aspekte berücksichtigt werden:eine Linkskurve, eine Rechtskurve und eine Gerade.

Sie können das Gleislayout als Basis-3-Zahl mit einer Breite kodieren, die der Anzahl der Teile im Layout entspricht.Um alle Gleislayouts aufzuzählen, zählen Sie einfach in Basis 3, wobei die Kodierung 0=gerade, 1=links und 2=rechts lautet.

Im nächsten Schritt wird überprüft, ob das Layout an beiden Enden zusammenpasst.Die erste Prüfung besteht darin, sicherzustellen, dass genügend Kurven vorhanden sind, um eine komplette Runde zu fahren.Wählt man für eine Strecke eine Linksdrehung, so sind 12 Linkskurven nötig.Für jede zusätzliche rechte Kurve müssen wir eine zusätzliche linke Kurve hinzufügen.Um zu überprüfen, ob das jeweilige Layout funktioniert, addieren Sie einfach die Anzahl der linken Kurven und subtrahieren die Anzahl der rechten Kurven – dies muss 12 ergeben.

Abschließend müssen wir überprüfen, ob die Ziele tatsächlich erreicht werden.Wir zeichnen die Strecke einfach auf einem kartesischen Gitter auf.Wir beginnen den Ursprung bei [0,0] und wenn er bei [0,0] endet, wird er verbunden.

Der einfachste Weg, die Strecke zu zeichnen, ist LOGO Stil.Mit anderen Worten pflegen wir einen Richtungsvektor, der in die Richtung des zuletzt verlegten Gleisstücks zeigt.Wenn wir auf eine Linkskurve stoßen, drehen Sie die Richtung um 30 Grad und für eine Rechtskurve um -30 Grad – eine Gerade hat keinen Einfluss auf die Richtung.

Um die Kurven und Geraden tatsächlich darzustellen, skalieren wir den Richtungsvektor um die Größe des Stücks, d. h.10 Einheiten für eine Gerade und 12,4 x 12 / 2 x pi (Radius der vollständigen kreisförmigen Strecke) Einheiten für eine Kurve.

VORBEHALTE

Aufgrund von Rundungsfehlern beim Addieren von Gleitkommazahlen ist die Darstellung nicht exakt.Und im wirklichen Leben können wir etwas Spielraum lassen, damit die Ziele erreicht werden, also muss dafür gesorgt werden.

Viele Layouts werden gleich sein, jedoch um eine Position verschoben.Ich sehe keine andere Möglichkeit, doppelt verschobene Layouts auszuschließen, als die vorherigen beizubehalten und mit ihnen zu vergleichen.

Der Algorithmus schließt Layouts nicht aus, bei denen sich Teile kreuzen.Dazu müssten Sie sicherstellen, dass nicht jedes Teil in einem Layout ein anderes Teil im Layout kreuzt (das ist O(n^2)).Und es müsste Kontrollen für Kurve-Kurve-, Kurve-Gerade- und Gerade-Gerade-Kreuzungen geben, und das wird sehr komplex.

Die Laufzeit des Algorithmus beträgt offensichtlich O(3^N), was exponentiell ist – und für sehr große Layouts wahrscheinlich unpraktisch ist.

Nachfolgend finden Sie einen VBA-Code, den Sie in Excel einfügen können, um einen Machbarkeitsnachweis zu erhalten.Ich habe bewusst versucht, den Code so einfach wie möglich zu halten, um die Konvertierung in Ihre Lieblingssprache zu erleichtern.Bei Fragen stehen wir Ihnen gerne zur Verfügung.

Option Explicit

Type Vector
    X As Double
    Y As Double
End Type

Sub GenerateTrackLayout()
    Dim lCounts(40) As Long
    Dim lColumn As Long
    Dim lTrackLength As Long
    Dim lCurveSum As Long
    Dim lIndex As Long
    Dim lIndex2 As Long
    Dim vDirection As Vector
    Dim vBase As Vector
    Dim vTrackPosition As Vector
    Dim fPI As Double
    Dim fCurveRadius As Double
    Dim fStraightLength As Double
    Dim sPath As String
    Dim lOutputRow As Long
    Const TOLERANCE = 0.5 'inch

    lOutputRow = 1

    vBase.X = Sqr(3) / 2 ' 30 degrees
    vBase.Y = 1 / 2 ' 30 degrees

    fPI = 4 * Atn(1)
    fCurveRadius = 12.4 * 12 / (2 * fPI)
    fStraightLength = 10

    lTrackLength = 12 ' initial track length

    Application.ScreenUpdating = False

    Do
        ' Check for closed track
        lCurveSum = 0

        For lIndex = 0 To lTrackLength - 1
            If lCounts(lIndex) = 1 Then
                lCurveSum = lCurveSum + 1
            ElseIf lCounts(lIndex) = 2 Then
                lCurveSum = lCurveSum - 1
            End If
        Next

        If lCurveSum = 12 Then ' one 360 degree rotation anti-clockwise
            vDirection.X = 0
            vDirection.Y = 1
            vTrackPosition.X = 0
            vTrackPosition.Y = 0

            ' Plot the track and ensure that ends meet
            For lIndex = 0 To lTrackLength - 1
                Select Case lCounts(lIndex)
                    Case 0 ' straight
                        vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fStraightLength))
                    Case 1 ' left curve
                        vDirection = MultiplyVectors(vDirection, vBase, 1)
                        vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fCurveRadius))
                    Case 2 ' right curve
                        vDirection = MultiplyVectors(vDirection, vBase, -1)
                        vTrackPosition = AddVectors(vTrackPosition, ScaleVector(vDirection, fCurveRadius))
                End Select

                ' If ends meet within tolerance then output the track
                If Abs(vTrackPosition.X) < TOLERANCE Then
                    If Abs(vTrackPosition.Y) < TOLERANCE Then
                        If lIndex = (lTrackLength - 1) Then
                            sPath = ""
                            For lIndex2 = 0 To lIndex
                                Select Case lCounts(lIndex2)
                                    Case 0 ' straight
                                        sPath = sPath & "S"
                                    Case 1 ' left
                                        sPath = sPath & "L"
                                    Case 2 ' right
                                        sPath = sPath & "R"
                                End Select
                            Next
                            Application.ScreenUpdating = True
                            Cells(lOutputRow, 1).Value = sPath
                            Application.ScreenUpdating = False
                            lOutputRow = lOutputRow + 1
                        End If
                    End If
                End If
            Next
        End If

        ' Count in base 3 where number width is Track Length
        lColumn = 0
        Do
            lCounts(lColumn) = lCounts(lColumn) + 1
            If lCounts(lColumn) = 3 Then
                lCounts(lColumn) = 0
                lColumn = lColumn + 1
            Else
                Exit Do
            End If
        Loop Until lColumn = lTrackLength

        ' We've tried all tracks of this length, next one up...
        If lColumn = lTrackLength Then
            Erase lCounts ' reset all columns to zero
            lTrackLength = lTrackLength + 1
        End If
        DoEvents
    Loop
End Sub

' Vector maths

Function MultiplyVectors(vVectorA As Vector, vVectorB As Vector, ByVal fConjugate As Double) As Vector
    MultiplyVectors.X = vVectorA.X * vVectorB.X - fConjugate * vVectorA.Y * vVectorB.Y
    MultiplyVectors.Y = vVectorA.Y * vVectorB.X + fConjugate * vVectorA.X * vVectorB.Y
End Function

Function AddVectors(vVectorA As Vector, vVectorB As Vector) As Vector
    AddVectors.X = vVectorA.X + vVectorB.X
    AddVectors.Y = vVectorA.Y + vVectorB.Y
End Function

Function ScaleVector(vVector As Vector, ByVal fScale As Double) As Vector
    ScaleVector.X = vVector.X * fScale
    ScaleVector.Y = vVector.Y * fScale
End Function

Andere Tipps

Zunächst eine Rahmenherausforderung:

Ein Computer kann aus allen Gleisen ein gültiges Layout erstellen, und wenn der Algorithmus gut ist, vielleicht in wenigen Sekunden

Der Algorithmus muss nicht in wenigen Sekunden ausgeführt werden.Sie benötigen eine Ausgabe in wenigen Sekunden.Ich sehe nicht, dass irgendetwas Sie davon abhält, einen Brute-Force-Layout-Cruncher einzurichten, der auf einem Computer in der Ecke läuft und Lösungen in einer Datenbank speichert, aus der die Benutzeroberfläche dann zufällige Layouts auswählen kann.

Hinsichtlich der Generierung gibt es eine Reihe halbstandardisierter Ansätze.Der Zustandsraum ist ziemlich groß, sodass eine umfassende Suche möglicherweise nicht möglich ist.Aber eines der folgenden Dinge könnte einen Versuch wert sein:

Rein zufälliges Mischen einer Liste von Geraden und der gleichen Anzahl von Links- und Rechtskurven, gefolgt von einem „Gütetest“.
Berg steigen:Beginnen Sie mit einer zufälligen Permutation und testen Sie dann einfache Austausche, um zu sehen, ob sie die „Güte“ verbessern.Wenn dies der Fall ist, führen Sie den Austausch durch und wiederholen Sie den Vorgang.
Simuliertes Glühen:ähnlich, erlaubt aber manchmal Änderungen, die die „Güte“ verringern, in der Hoffnung, zu einer besseren Schanze zu gelangen.
Genetischen Algorithmus:Generieren Sie viele zufällige Permutationen und mischen Sie sie wiederholt, um die besten Ergebnisse zu erzielen.Es ist jedoch nicht ganz klar, wie man sie mischt.
Die letzten drei könnten mit „bekanntermaßen guten“ Kurven beginnen, die durch Einfügungen in einen Kreis erzeugt werden.
Entdecken Sie Möglichkeiten für Meet-in-the-Middle.Z.B.Generieren Sie alle Kurven mit einem Gesamtwinkel von +90 Grad, indizieren Sie sie anhand des 2D-Vektors zwischen den Endpunkten. Wenn es viel weniger Vektoren als Kurven gibt, können Sie möglicherweise Vierlinge davon ausführlich betrachten, um diejenigen zu finden, die ein geschlossenes Viereck bilden .

Für „Güte“-Tests muss es offensichtlich eine große Strafe geben, wenn die Kurve nicht geschlossen ist.Es muss auch eine hohe Strafe für Selbstüberschneidungen geben.Ich würde diese gerne mit einem Quad-Tree testen, um Segmente zu finden, die nicht aufeinanderfolgend, aber nahe beieinander liegen, und dann Bogen-Bogen-, Bogen-Linien- und Linie-Linien-Schnitttests durchführen, um zu sehen, ob es eine Kante gibt, die ein Segment begrenzt überlappt eine Kante, die eine andere begrenzt.

Eine andere Strategie, die in der Lage sein könnte, den kleineren Fall völlig brutal zu erzwingen, den größeren jedoch nicht, wäre die Verwendung eines algebraischen Ansatzes für den Gesamtvektor.Sei die Länge des geraden Stücks $2\ell$ und der Radius des gebogenen Stücks sei 2r$.Da die Ausrichtungen alle Vielfache von 30 Grad sind, ist der Vektor zwischen den Enden eines geraden Stücks in $$(0, \pm 2\ell), (\pm 2\ell, 0), (\pm \ell, \pm \sqrt3 \ell), (\pm \sqrt3 \ell, \pm \ell)$ $ und ähnlich ist der Vektor zwischen den Enden eines gebogenen Stücks in $$(\pm r, \pm \sqrt3 r), (\pm \sqrt3 r, \pm r), (\pm (\sqrt3 - 1)r, \pm (\sqrt3 - 1)r))$$

Es sei denn einer von $\frac \ell r$, $\frac {\sqrt 3 \ell} r$, oder $\frac \ell {\sqrt 3 r}$ ist ein Bruch mit einem kleinen Zähler und einem kleinen Nenner, Kurven und Geraden sind unabhängig, sodass Sie funktionierende Kurvensätze finden können (brutale Gewalt reicht für 20 Kurven, davon 16 in die eine Richtung und 4 in die andere Richtung);Für 44 Kurven mit einer Aufteilung von 28 bis 16 benötigen Sie einen besseren Ansatz.Ich habe die Auswirkungen der Anforderung noch nicht durchgearbeitet $+\sqrt 3$s, um eine passende Anzahl von zu haben $-\sqrt 3$s, aber sie ermöglichen möglicherweise eine starke Filterung) und fügen dann paarweise Straights ein.Wenn Sie dies mit roher Gewalt auf eine kleine Anzahl von Kurven anwenden, können Sie abschätzen, wie viele Layouts Sie mit dem symmetrischen Ansatz möglicherweise verlieren.

Eine mögliche Lösung Dies so einfach wie möglich zu machen, um schnell einen funktionierenden Algorithmus zu erhalten, wäre wie folgt.Das einfachste Layout ist natürlich 12C (12 gebogene Gleise, alle mit der gleichen Ausrichtung (relativ zueinander) und bilden einen einfachen Kreis.Dies wird die Basis sein, auf der wir aufbauen können.

Der grundlegende Algorithmus besteht also darin, beim Hinzufügen von Titeln bei jedem Schritt das 360-Grad-Loop-Layout beizubehalten.Wir können dies tun, indem wir prüfen, wie viele gebogene Gleise wir noch haben, und sie in Gruppen zum Layout hinzufügen, sodass die 360-Grad-Eigenschaft erhalten bleibt.Beginnen Sie beispielsweise mit unserem 12C-Layout (einem einfachen Kreis).Wir wissen, dass wir insgesamt 20 °C haben, also bleiben uns noch 8 °C.Die einfachste Ergänzung einiger dieser Elemente, die die 360-Grad-Eigenschaft beibehalten würden, wäre das Hinzufügen einer Kurve mit umgekehrter Ausrichtung und einer Kurve mit derselben Ausrichtung (wie der Hauptkreis, mit dem wir begonnen haben).Das Gleiche würden wir dann auf der gegenüberliegenden Seite des Layouts tun.In diesem einfachen Beispiel hätten wir dem Kreislayout vier weitere Kurven hinzugefügt, sodass aus 12C 16C wurden (wobei 4C übrig blieben).Wir würden so lange Kurven platzieren, bis alle 20 (in diesem Beispiel) richtig platziert sind.Beachten Sie, dass dieses aus allen Kurven bestehende Layout ein gültiges Closed-Loop-Layout ist.Der Zug kann diese Anordnung verwenden, da er jedoch ausschließlich aus gebogenen Gleisen besteht, sodass wir noch nicht fertig sind.

Die geraden Spuren würden dann auf die gleiche Weise eingefügt, mit der Ausnahme, dass diese paarweise (2 Spuren) hinzugefügt werden können, da sie die 360-Grad-Eigenschaft nicht ändern.Sie können überall eingefügt werden, daher denke ich, dass es am besten wäre, zuerst ALLE gebogenen Gleise zu platzieren und dann zurückzugehen und einen zweiten Durchgang zu machen, um die Geraden zufällig (aber symmetrisch) zu platzieren.

Dies ist der einfachste Algorithmus, der mir derzeit einfällt.Es wird garantiert eine geschlossene 360-Grad-Schleife und eine symmetrische Strecke erzeugt. Unter der Annahme, dass die Anzahl der Kurven ein Vielfaches von 4 und die Anzahl der Geraden ein Vielfaches von 2 ist, wird jede einzelne Strecke verwendet.

Eine Sache, die Sie jedoch bedenken sollten (wenn Sie diesen Algorithmus entweder auf einem Computer oder nur in Ihrem Kopf beim Erstellen des Layouts verwenden), ist, dass es in einer Richtung mehr Platzbeschränkungen geben kann als in der anderen.Zum Beispiel auf einer Terrasse, die lang, aber nicht so breit ist.Bei der Verwendung des Algorithmus sollte er stärker auf die lange Dimension ausgerichtet sein, in der das Layout zusammengestellt wird.

Wenn jemand einen Algorithmus finden könnte, um aus allen Gleisen ein asymmetrisches Layout zu erstellen, wäre das noch beeindruckender.

Der Komplexitätsunterschied zwischen der einfachsten und der kompliziertesten Lösung ist atemberaubend.Mit einem Kreis (12C) zu beginnen, ist für dieses Problem so einfach wie möglich und für Kinder sinnvoll. Es ist jedoch sehr interessant, eine generische Lösung zu analysieren, die JEDES gültige Layout (einschließlich asymmetrischer) erzeugen kann.

In Wirklichkeit würde ein nicht computergestützter Algorithmus darin bestehen, einfach ein paar „coole“ Formen zum Layout hinzuzufügen und es in die Nähe einer Verbindung zu bringen, dann zurückzugehen und es so anzupassen, dass es tatsächlich eine Verbindung herstellt (für eine geschlossene Schleife).Mit insgesamt 70 Gleisstücken (44C und 26S) ist eine riesige Anlage möglich.Ich habe insgesamt etwa 67 Fuß Gleis berechnet, also etwa 20 Meter.Der Zug sollte etwa 1 Minute brauchen, um die gesamte Anlage einmal zu umrunden.

Eine weitere mögliche Lösung würde darin bestehen, die tatsächlichen Maße jedes Gleises zu nehmen und sich den äußersten rechten Rand des Layouts zu merken.Beim Erstellen des Layouts können Sie mit einem geraden Gleis oder mit einer Linkskurve (gegen den Uhrzeigersinn) beginnen und dabei akkumulieren, wie weit das zuletzt hinzugefügte Gleis von der äußersten rechten Kante entfernt ist. Wenn Sie dann weitere Gleise hinzufügen, dürfen Sie niemals eine Kombination von Gleisen zulassen die Kante ganz rechts stoßen oder überqueren oder vielleicht nicht einmal in die Nähe kommen.Beginnen Sie also beispielsweise mit einem geraden Gleis (kein 12C-Anfangskreis bei dieser Kandidatenlösung) und wählen Sie dann zufällig ein anderes Gleisstück aus.Beachten Sie von Anfang an, dass wir KEINE Rechtskurve (im Uhrzeigersinn) zulassen würden, da dies gegen die Regel des „Überquerens“ der äußersten rechten Kante verstoßen würde.Nach der ersten Geraden bleibt uns nur noch eine weitere Gerade oder eine Linkskurve (gegen den Uhrzeigersinn).Eine weitere durchzusetzende Regel wäre, dass wir nach einer Geraden nicht mehr als 9 Kurven mit gleicher Ausrichtung hintereinander hinzufügen dürfen, da es sonst wahrscheinlich zu Überschneidungen mit anderen bereits vorhandenen Gleisen kommt.Diese Grenze könnte sogar auf 8 reduziert werden, um mehr Abstand zu haben. In diesem Fall MUSS die nächste Strecke eine Kurve mit umgekehrter Ausrichtung sein (da eine Gerade Probleme verursachen kann).

Dieser Algorithmus bräuchte etwas Hilfe, damit er zurückkommt und eine Verbindung zur anderen Seite des zuerst hinzugefügten Gleisstücks herstellt.Wir können dies erreichen, indem wir darauf bestehen, dass Kurven gegen den Uhrzeigersinn als +1 und Kurven im Uhrzeigersinn als -1 zählen und dass sich diese auf der zuletzt hinzugefügten Kurve zu 12 addieren müssen.Wir können Abhilfe schaffen, indem wir die CC-Kurven (gegen den Uhrzeigersinn) im Verhältnis 4:1 zu den Kurven im Uhrzeigersinn verzerren, sodass die Wahrscheinlichkeit groß ist, dass wir 16 CC und 4 im Uhrzeigersinn erhalten, was effektiv einen 360-Grad-Kreis ergibt.Wenn der Algorithmus versucht, eine CC-Kurve hinzuzufügen, aber auf vorhandene Gleise stößt, haben wir an diesem Punkt zwei Möglichkeiten: Versuchen Sie es mit einer Kurve mit entgegengesetzter Ausrichtung oder verlassen Sie das Layout und beginnen Sie von vorne.Ich denke, dass man auf einem schnellen Computer irgendwann ein gutes Layout bekommt.

Ich bin mir noch nicht sicher, ob diese Methode zu denselben Layouts führen würde wie die Methode, die mit 12C beginnt, aber vielleicht ist die Implementierung auf einem Computer einfacher, da nur wenige Regeln durchgesetzt werden müssen und wir das Layout auf einer Spur erstellen auf einmal.

Eigentlich habe ich gerade an a gedacht 3. mögliche Kandidatenlösung Das sollte funktionieren und ist nicht allzu schwierig umzusetzen.Es geht wie folgt.

Verwenden Sie die oben beschriebene Technik, erstellen Sie jedoch nur eine halbe Anlage (mit der Hälfte der Gleise jedes Typs, also 10 Kurven und 5 Geraden).Wir lassen den Computer zufällige Gleise auswählen, akzeptieren aber nur Layouts, die mit einem Netz von 180 Grad Linkskurve enden (da wir eine rechte Grenze erzwingen, die kein Gleis berühren oder überqueren kann).Okay, also gehen wir davon aus, dass der Computer sehr schnell ein gültiges „Halblayout“ findet.Dann machen wir einfach eine Bestandsaufnahme, wie viele Kurven im Uhrzeigersinn und gegen den Uhrzeigersinn es gibt, und duplizieren diese in der anderen Hälfte der Strecke (jedoch nicht unbedingt symmetrisch).Bei den Geraden müssen wir den Winkel aufzeichnen, in dem sie eingefügt wurden, und sie dann in der anderen Hälfte der Strecke abgleichen, allerdings wiederum nicht unbedingt symmetrisch.

Versuchen wir ein Beispiel mit S für Gerade, O für Kurve gegen den Uhrzeigersinn und C für Kurve im Uhrzeigersinn.Konzentrieren Sie sich zunächst auf das Halblayout.

Der erste gerade Weg führt von uns weg und definiert unseren äußersten rechten Rand, den wir nicht überqueren dürfen.

SOOSOCSOOSSOOOC – Dies ist ein gültiges Halblayout, da es 5 Geraden und 10 Kurven mit einem Netz von 6 Kurven gegen den Uhrzeigersinn hat (2 der 8 wurden „durch 2 Kurven im Uhrzeigersinn aufgehoben“).

Jetzt müssen wir „im Auge behalten“, in welchem Winkel die Geraden eingefügt wurden, und diese mit einer Spur mit demselben Winkel (aber entgegengesetzter Richtung) abgleichen, um sie „aufzuheben“.

1:Geraden mit einem Winkel von 0 Grad
0:Geraden im 30-Grad-Winkel
2:Geraden im 60-Grad-Winkel
0:Geraden im 90-Grad-Winkel
2:Geraden im 120-Grad-Winkel
0:Geraden im 150-Grad-Winkel
0:Geraden im 180-Grad-Winkel

Um dies also auf der anderen Hälfte des Layouts „anzupassen“ und es so zu gestalten, dass es mit der einzelnen Startgeraden-Strecke verbunden ist, müssen wir nur die gleiche Anzahl an Os und Cs, aber auch die gleiche Anzahl an Geraden am + anbringen 180-Grad-Rückkehrwinkel.Beispielsweise ist es bei einer 60-Grad-Geraden besser, irgendwo auf der anderen Seite des Layouts eine 240-Grad-Gerade zu haben, nicht unbedingt genau gegenüber.Dies liegt daran, dass die 60-Grad-Gerade hauptsächlich nach links und ein wenig nach oben führt (mit diesem Schema) und die 240-Grad-Gerade um den gleichen Betrag nach rechts und wieder nach unten führt, um die Beiträge der beiden Gleise effektiv „aufzuheben“. Abweichung von der Startspurposition.

Um die „fehlende Hälfte“ des Layouts zu erstellen, müssen wir jetzt nur noch die bekannten Gleise nehmen, die wir benötigen (und wissen, welche Winkel die Geraden haben müssen) und sie einfach in beliebiger Reihenfolge „verwürfeln“.

Möglicherweise gibt es eine Möglichkeit, NICHT genau die eine Hälfte des Layouts mit „komplementären“ Gleisen auf der anderen Seite abgleichen zu müssen, aber das würde einige komplexere Berechnungen erfordern und wahrscheinlich ist in der Zeit nicht genug Zeit, um das zu lösen Bounty ist aktiv für.Es besteht auch die Möglichkeit, dass nicht alle Gleise auf diese Weise genutzt werden und eine leichte Biegung des Gleises erforderlich wäre.Wir können diese spezielle Eigenschaft für diese Frage ignorieren.

Ich habe tatsächlich eine asymmetrische Spur erstellt, um zu sehen, ob sie funktionieren würde, und es scheint, dass sie funktioniert hat.Unter Verwendung von S für Gerade, O für Kurve gegen den Uhrzeigersinn und C für Kurve im Uhrzeigersinn plus dem Winkel (in Grad) relativ zur geraden Ausgangsspur habe ich Folgendes für die obere Hälfte erhalten:

S0, O30, O60, S60, O90, C60, S60, O90, O120, S120, S120, O150, O180, O210, C180

Für die untere Hälfte der Strecke habe ich Folgendes bekommen:

O210, O240, S240, C210, O240, S240, O270, O300, S300, S300, O330, O360, O390, C360, S360

Tatsächlich wurde das Bild von der falschen Seite aufgenommen, sodass die Ober- und Unterseite vertauscht sind.Das erste verlegte Gleis war die Gerade in der Nähe des blauen Mülleimers, die auf den Betrachter des Bildes zukommt, und das zweite Gleis ist die Kurve gegen den Uhrzeigersinn.

Es scheint, als würde diese Technik für viele gerade Kurven und Geraden funktionieren, einschließlich 44C und 26S, was mein ultimatives Ziel ist.Das ist wirklich ermutigend, da zur Lösung dieses Problems kein elektronischer Computer erforderlich ist. Ich kann die Kinder einfach jede gewünschte Halbkreisform mit der Hälfte der Gleise (22C und 13S) bauen lassen und dann ihr Design entsprechend „korrigieren“. dass es 180 Grad ist, dann „passt“ es auf die andere Seite der Strecke, nicht unbedingt symmetrisch.

Sie müssen vorsichtig sein, wenn Sie ein halbes 180-Grad-Layout erstellen, bei dem das Startgleis und das Endgleis sehr nahe beieinander liegen.Zum Beispiel die Form des oberen Teils eines Fragezeichens "?" (ohne den Punkt) Aber setzen Sie diese obere Kurve fort, so dass es mehr kommt und ein geradliniger Fall von der Straße wäre sehr nahe an der Straße, die über dem Punkt liegt, wo sich der Punkt befand.Dann könnten Sie für die untere Hälfte NICHT sofort mehr Kurven gegen den Uhrzeigersinn fahren, da es von der „oberen Hälfte“ aus noch andere Geraden gibt.Das Bild meines Closed-Loop-Layouts hat funktioniert, da ich in der „oberen“ Hälfte keine „Engpässe“ hatte, aber diese sind natürlich möglich, wie ich gerade beschrieben habe.

Bei der „problematischen“ Zugführung handelt es sich um eine etwa sanduhrförmige Gleishälfte mit einer schmalen Mitte.In diesem Fall muss man den oberen Teil fast „spiegeln“, da bestimmte Kurven aufgrund der Nähe der Gleise nicht möglich sind.Hier ist ein Beispiel...

Eine weitere interessante Beobachtung ist, dass 4 zickzackförmig gebogene Gleise fast ein exakter Ersatz für 5 Geraden sind (was die lineare Distanz betrifft).Zu viele davon führen jedoch zu einem erheblichen Längenunterschied.Wie im Abschnitt „AKTUALISIERT“ oben angegeben, entsprechen 20 Zickzackkurven (für die lineare Entfernung) fast genau den 24 Geraden.

Mit dieser Technik kann eine riesige Anlage mit allen 70 Gleisstücken erstellt werden.Es würde mit einem 12c -Kreis beginnen, dann könnte ich auf einer Seite 24 Geraden einfügen (240 Zoll lang).Auf der gegenüberliegenden langen Seite des Layouts (um fast der Länge der geraden Seite zu entsprechen) würde ich 20 Zickzackkurven verwenden (ebenfalls etwa 240 Zoll lang).Diese sollten fast auf einer Linie liegen und durch eine leichte Biegung sollte es funktionieren.Die restlichen Gleise (2 gerade und 12 gebogene) könnten problemlos platziert werden, um die Anlage „ausgeglichen“ (und verbunden) zu halten.

Gehen Sie davon aus, dass Sie am Punkt (0, 0) beginnen und direkt nach rechts gehen.Sie müssen Spuren hinzufügen, bis Sie erneut den Punkt (0, 0) erreichen, dieses Mal direkt von links.Hier gibt es zwei Probleme:Eine besteht darin, den Punkt (0, 0) von links kommend zu erreichen genau.Die andere besteht darin, keine Überschneidungen zu haben.

Um einen Kreis gegen den Uhrzeigersinn zu bilden, benötigen Sie 12 nach links gedrehte gebogene Teile.Diese bilden einen exakten Kreis.Mit 0 oder 24 oder 36 gebogenen Teilen hätte man eine Acht oder zwei oder drei Kreise, von denen keiner ohne Kreuzungen gemacht werden kann.

Und natürlich können Sie weitere Spuren hinzufügen, und diese müssen bestimmten Regeln folgen:Sie können linksgekrümmte, gerade und rechtsgekrümmte Teile paarweise hinzufügen, beginnend bei Winkeln von x Grad und x+30 Grad, sodass Sie wieder zu 0,0 zurückkehren.Und die Anzahl der linksgekrümmten Teile über die ersten 12 hinaus muss mit der Anzahl der rechtsgekrümmten Teile übereinstimmen, sodass die Teile im rechten Winkel bei 0,0 übereinstimmen.

Das sind also die Teile, die Sie verwenden können.Sie müssen sicherstellen, dass es offensichtlich keine Kreuzungen gibt.

Wenn die Längen genau stimmen, kann es beispielsweise sein, dass eine Kombination links/rechts/rechts/links genau die gleiche Distanz zurücklegt wie vier oder fünf Geraden, sodass möglicherweise andere Kombinationen zulässig sind.

Und natürlich Tracks Sind biegsam, was möglicherweise viele weitere Möglichkeiten bietet.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit cs.stackexchange