Plumbing Random Paths

Question

Write a program or function that takes in three integers, a width w, a height h, and a step count s. You will be drawing a non-self-intersecting random walk s steps long on a 5*w by 5*h pixel image where every 5 by 5 pixel cell is either empty (pure beige) or one of these twelve simple "pipes":

The image above is enlarged to show detail. Here are the pipes at actual size:

^{(The gray lines are just to separate the pipe types.)}

The random walk will be a single continuous pipe path that starts at one pipe endpoint (one of the bottom four pipe types) and ends at another pipe endpoint.

Start with an empty w by h grid and randomly choose one cell to be the starting point. Then randomly choose one of the four directions to start in and draw the corresponding pipe endpoint. This starting cell marks the first step in your walk and every time you draw a new cell or overwrite an existing one it counts as another step taken.

Now, repeatedly, randomly choose to go right, left, or straight, drawing the appropriate pipe cell if the direction chosen is valid. Backtrack and re-choose if a direction is not valid until the complete s step path is formed. The path should end with a pipe endpoint, which might be anywhere on the grid, depending on the course the path took.

It is very important to note that only the two straight pipe cells can be overwritten, and only by the straight pipe cell of the opposite orientation, the result being an intersection cell. Otherwise, all pipes must be placed in empty cells.

When an intersection is drawn, the part of the path that is further along from the starting cell should be drawn on top.

It is up to you whether or not the grid has periodic boundary conditions (PBC), i.e. whether a pipe exiting one side of the grid will come out on the other side. Without PBC the grid boundary counts as a barrier that you can run into just like other pipes.

Special Cases

• When s is 0 no pipes should be drawn and the output should be a blank 5*w by 5*h image (i.e. all beige).

• When s is 1 a single pipe stub

  (Actual size: )

  should be drawn at the randomly chosen starting cell.

Other Details

• You may assume that s is at most w*h so a path will always be possible. (Though longer paths are possible due to intersections.)
• w and h will always be positive.
• All random choices must be uniformly random. e.g. you shouldn't avoid making intersections when they are possible even if it makes the problem easier. Pseudo-random number generators are allowed.
• Any three visually distinct colors may be used in place of the black, blue, and beige.
• Your output images may be enlarged so that they are really 5*w*k by 5*h*k pixels where k is a positive integer. (Enlarging any examples you post is advised even if your k is 1.)
• Any common lossless image file format may be used and the image may be saved to a file, displayed, or spewed raw to stdout.

The shortest code in bytes wins.

Examples

^{(All enlarged by 500%.)}

If the input is w=2, h=1, s=0 then the output will always be:

If the input is w=2, h=1, s=1 then the output will be one of these images with equal chance:

If the input is w=2, h=1, s=2 then the output will be

or possibly

if the grid is assumed to have PBC.

(Note that starting the path like would make a second step impossible.)

---

Here are some possible outputs for w=3, h=2, s=6, assuming PBC:

---

Here is a possible output for w=3, h=3, s=9, assuming PBC:

Notice that the path didn't need to cover all the cells due to the intersection counting as two steps. Also, we can deduce that the corner endpoint was the starting cell since the intersection overpass must have been drawn afterwards. Thus we can infer the sequence of random choices that were made:

start at top left, facing east
go straight
go right
go right
go right
go straight
go left
go right
end

---

Finally, here are examples of w=4, h=5, s=20 and w=4, h=5, s=16:

Answer 1

CJam, 274

q~:K;:B;:A;{0aA*aB*:M5*5f*:I;K{[Bmr:QAmr:P]5f*:R;3Ym*{R.+:)2{1$0=I=2$W=@tI@0=@t:I;}:F~}/R2f+1FK({MQ=P=:EY4mr:D#&1{{MQMQ=PE2D#+tt:M;}:G~7,1>[W0_1_0_W]2/D=:Off*{[QP]5f*2f+.+_:H1F_OW%.+2FOW%.m2F}/H2FO~P+:P;Q+:Q;MQ=P=:E_5YD2%-*=!JK2-=+*1{D2+4%:D;G}?}?}fJ]}0?}g'P2NA5*SI,N2NI:+N*

Try it online

Uses PBC, outputs in PGM format. You can remove the :+ near the end to get a nicer visual output in the browser.

It's very slow for larger input, especially if the step count is close to the area.

Example result for input 4 3 10 (scaled 500%):

Brief explanation:

The general approach is:

• repeat all the following steps until successful:
• initialize 2 matrices: one recording which sides are being used in each cell, and one for the image
• if s=0, we're done, else:
• pick a random cell and draw a square, then do the following s-1 times:
• pick a random direction; if that side is already used, fail and start over
• mark the side as used and draw the actual pipe in the image (drawing 3 adjacent lines of length 6, starting right "after" the center pixel of the current cell, then adding a dot to cap the end of the pipe)
• update the current position (moving to the next cell)
• check if the cell is empty or it's a valid crossing; if not, fail and start over
• mark the side in the opposite direction as used in this cell, then continue the loop

Answer 2

QBasic, 517 516 bytes

RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
1CLS
IF s=0GOTO 9
x=5*INT(RND*w)
y=5*INT(RND*h)
GOSUB 7
FOR k=1TO s-1
r=INT(RND*4)+1
a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)=0GOTO 1
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
9IF c GOTO 1
END
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN

• Takes w, h, and s from user input, comma-separated.
• Output is drawn on the screen. While the program is searching for a solution, you may see partial solutions flickering past.
• Does not use periodic boundary conditions. I found it easier to draw and test for connecting pipes without having to worry about half of the pipe being on one side of the grid and half on the other.

The approach here is to try a random direction at each step and start over from the beginning if it results in an invalid move. We draw the pipes as the directions are decided, and use POINT to test points on the screen for our validity conditions. A move is valid if it doesn't go outside the boundaries of the grid and:

1. The moved-to cell is empty; or
2. Both
   1. The moved-to cell contains a pipe going straight through, either horizontally or vertically, and
   2. The new pipe section does not double up an existing pipe section

Like aditsu's CJam answer, this code is very slow, and can be mind-numbingly slow if s is a significant fraction of w*h. On my QB64 setup, it comes up with an answer for 5,5,19 fairly promptly, but takes longer than I was willing to wait on 5,5,20.

If you want to run larger/more densely packed examples, here's my original approach using a depth-first search. It's much more efficient, at the cost of a whopping 300 extra bytes.

RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
DIM t(s),m(s)
0
FOR z=1TO s
t(z)=-1
NEXT
i=5*INT(RND*w)
j=5*INT(RND*h)
k=1
1CLS
IF s=0GOTO 9
x=i
y=j
GOSUB 7
FOR z=1TO k-1
r=m(z)
GOSUB 6
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
IF c*(k=s)THEN k=k-1:GOTO 1 ELSE IF k=s GOTO 9
IF k<1GOTO 0
IF t(k)>=0GOTO 4
t(k)=0
f=30
WHILE f
r=INT(RND*4)+1
IF f AND 2^r THEN t(k)=t(k)*5+r:f=f-2^r
WEND
4r=t(k)MOD 5
m(k)=r
t(k)=t(k)\5
GOSUB 6
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)THEN k=k+1 ELSE IF t(k)>0GOTO 4 ELSE t(k)=-1:k=k-1
GOTO 1
6a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
RETURN
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN
9

Example output for inputs 10, 10, 100, actual size:

A still fancier version can be found in this gist. Besides being ungolfed and thoroughly commented, it scales up the output by a constant factor and allows for a set delay between steps, enabling you to watch the DFS algorithm at work. Here's an example run: