Befunge, 344 bytes
&v>>>#p_:63p:43g`\!+v>/*53g+\01g:2%2*1-\2/!*63g+\0\:v
40$ v++!\`g14:p35:\<^2\-1*2%2p10::%4+g00:\g36\g35-1_v
#11^$_83p73v >1+:41g`!#v_$,1+:43g`!#v_@>->2>+00p+141^_
<p1^ vp< ^,g+7g36:<<<<1+55p36:<<<< ^1?0^#7g36g35*
8&p|!++!%9#2g+7g10\*!-g38g10!-g37:g00!!*<>3^
443>:!#v_>>1-::3%1-:53g+00p\3/1-:63g+01p^
^>^>>$#<"#"53g63g7+p41g53g-43g63g-+!#^_
Try it online!
As @flawr mentioned in their MATLAB answer, this may take some time if the field size is of any non-trivial size. In fact it's quite easy to get into a situation where it's really not worth trying to wait for it to finish, because you're quite likely to be waiting until the end of time.
To understand why this happens, it helpful to view the program as it's executing in one of Befunge's many "visual debuggers". Since data and code are the same thing in Befunge, you'll get to view the path as it changes over time. For example, here is a short animation showing what a part of a run on a slow path might look like.
![Animation showing the path construction getting itself stuck in a corner](../../I/static/images/1ed73541a0a89d9626f2ab93a01f08d286ad860a86c8eaca64705b41b02f60d6.gif)
Once the algorithm decides to make that fateful turn to the left at the bottom of the field boundary, it has essentially condemned itself to a lifetime of aimless wandering. From that point on it has to follow every single possible path in that fenced off area before it can back out and try the turn to the right. And the number of potential paths in these cases can easily become astronomical.
Bottom line: If it seems to be taking a long time, it's probably a good idea to just abort the execution and start again.
Explanation
This is basically a recursive algorithm, trying every possible path through the field, and then unwinding steps that have already been followed whenever it gets stuck. Since Befunge doesn't have the concept of functions, a recursive function is out of the question, but we can emulate the process by tracking the state on the stack.
This works by populating the stack with potential coordinates that we may want to follow. Then we pull one set from the stack and check whether it is suitable (i.e. in range and not overlapping with an existing path). Once we've got a good spot, we write a #
into the playfield at that location, and add those details to the stack in case we need to backtrack later.
We then push an additional four sets of coordinates onto the stack (in random order) indicating the potential paths we can take from this new location, and jump back to the start of the loop. If none of the potential paths are feasible, we'll get to the point on the stack where we saved the location of the #
we wrote out, so we'll undo that step and continue trying potential coordinates from one step prior.
This is what the code looks like with the various component parts highlighted:
![Source code with execution paths highlighted](../../I/static/images/a7ce68a1dbc15addd11fc781959aed91bd38a06ed2a32b509c2b25d524301b92.png)
Read the width and height of the field, and push the start coordinates along with a 0
type marker to indicate a potential path rather than a backtracking location.
Check for backtracking locations (indicated by a 1
type marker) which are reverted with a simple p
command, since they're stored in the exact format needed to write a space back into the playfield.
Check if the coordinates are still inside the playfield. If they're out of range, drop them from the stack and loop back to try the next potential coordinates.
If they are in range, get the next two values from the stack, which is the location of the previous step (required in the test that follows this).
Check if the coordinates are going to come into contact with an existing segment of the path. The location of the previous step is obviously ignored from this check.
If all test are successful, write a #
into the playfield, and check if we've reached the destination location.
If we have, write out the final path,
and exit.
Otherwise save the coordinates onto the stack with a 1
type marker for later backtracking.
This is interrupted with a random number calculation which we're going to need soon.
Push four potential destinations that can be reached from the current location. The random number determines the order in which they're pushed and thus the order that they will be followed.
Wrap back to the start of the main loop and process the next values on the stack.
RBX.Lua output format valid? ;) – devRicher – 2017-01-05T22:31:34.730
Is it correct that as long as every valid path has a positive probability of being chosen, the probability distribution is arbitrary? – flawr – 2017-01-05T22:45:16.567
@devRicher yeah – Rɪᴋᴇʀ – 2017-01-05T22:54:46.577
@flawr yeah, that's correct – Rɪᴋᴇʀ – 2017-01-05T22:54:54.007