Plumbing Random Paths 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:
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#&amp;1{{MQMQ=PE2D#+tt:M;}:G~7,1&gt;[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