CODEWITHSUNDEEP
algorithm
Codemonkey
Codemonkey

Reputation: 4809

Algorithm to generate a network that fills a 10x10 grid with a source, horizontal lines, right angles, t-junctions and nodes?

Just for fun I'm trying to create a non-flash version of http://www.jurjans.lv/stuff/net/FreeNet.htm. It's all pretty straightforward stuff, but I'm mentally stuck on how to generate the initial network.

I could do it square by square with lots of if/else logic checking neighboring squares, but frankly it seems very laborious and I wonder if there's a much much MUCH smarter way. Generate a mathematical graph or something similar and then translate that into the grid?

I'm not asking for someone to code it all for me - just point me in the right direction!

Upvotes: 1

Views: 139

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

The completed circuit appears to be a spanning tree.

There is an easy way to generate random minimum spanning trees by:

assigning random weights from some distribution to the edges of an undirected graph, and then constructing the minimum spanning tree of the graph.

So to summarise:

  1. Build a graph with a vertex at the centre of each square

  2. Add edges between each vertex and its neighbours above/down/left/right

  3. Assign random weights (e.g. uniform real from 0 to 1) to each edge

  4. Construct minimum spanning tree e.g. with Prim or Kruskal

  5. Convert graph into tiles

If there are certain shapes you want to forbid (e.g. a fully connected vertex) you may want an extra iteration to increase the weight for edges used in any tiles that are illegal, and then regenerate the spanning tree until you end up with a legal graph.

Upvotes: 2

Related Questions