Algorithmus zum Erzeugen eines Netzwerks, das ein 10x10-Gitter mit einer Quelle, horizontalen Linien, rechten Winkeln, T-Verzweigungen und Knoten füllt?

Question

Nur zum Spaß Ich versuche, eine Nicht-Flash-Version von http://www.jurjans.lv/stuff/net/FreeNet.htm zu erstellen. Es ist alles ziemlich geradlinig, aber ich bin mental daran fest, wie man das anfängliche Netzwerk generiert.

Ich könnte es Quadrat für Quadrat mit vielen If/Else-Logik machen, die benachbarte Quadrate überprüft, aber offen gesagt scheint es sehr arbeitsam und ich frage mich, wenn es viel viel viel klügere Weise gibt. Erzeugen Sie eine mathematische Grafik oder etwas ähnliches und übersetzen Sie diese dann in das Gitter?

Ich frage nicht nach jemandem, der alles für mich programmiert - zeigen Sie mir einfach in die richtige Richtung!

Answer 1

Die fertige Schaltung scheint ein spannender Baum zu sein.

Es ist eine einfache Möglichkeit zur Erzeugung von random minimum spanning trees:

Zuordnen Zufallsgewichte von einiger Verteilung an die Kanten eines ungerichteten Graphen, und dann den minimalen Spanning-Tree des Diagramms zu konstruieren.

1. Bauen in der Mitte jedes Quadrates

2. Kanten hinzufügen zwischen jedem Scheitelpunkt und seinen Nachbarn oben/unten/links/rechts

   mit einem Scheitelpunkt ein Graph:

So zusammenzufassen

Weisen Sie jeder Kante zufällige Gewichte zu (z. B. uniform real von 0 bis 1)

Konstruieren minimum spanning tree z.B. mit Prim oder Kruskal

Convert Graph in Kacheln

Wenn es bestimmte Formen, die Sie (zB über eine voll angeschlossen Vertex) Sie möchten eine zusätzliche Iteration zu erhöhen, das Gewicht für Kanten verwendet verbieten wollen in alle Kacheln, die illegal sind, und regenerieren Sie dann den Spanning-Tree, bis Sie mit einem gültigen Diagramm enden.