Randomly generated track

Question

I would like to create randomly generated track from one point to another with specified length of that track (it can be 2 more or less as a result of that function) in matrix. I have function called buildRoad(x,y,length) where x is width of my matrix and y is the height.

I separately generate start and end point.

I have to do it as a stack by use of Vector class, so every point is connected to each other horizontally or vertically (e.g. (0,1)->(0,2)->(1,2)).

And here is the point that I really don't know how to do: I don't know how to connect start and end with such a track. Track cannot cross. It would be easy, but it needs to be random. I've already made easiest and shortest route to the end and I tried to implement some kind of probability of choosing (randomly) direction where track will go on next step.

But when track turn into corner (because it can) it's dead end and I should try to build track again. And it can fail again and again. I just need an idea how to solve it.

EDIT:

Answer 1

One way to do it is with a Depth First Search (DFS) where at each step you look to place a new node in a random square which is:

• Unoccupied.
• Adjacent to the previous square.
• Close enough to the end point so that you can reach it given the distance remaining.
• Not been rejected previously via backtracking.

If there are no valid squares you backtrack and try a different option on the previous node.

You stop searching when you've reached the destination with a route in the length range you require.

The first and last nodes can obviously be placed before you start the search as there's no option over where those should be.

Answer 2

To make things easier, I would probably cut the requirement the algorithm should be able to generate tracks of different lengths. Since you've specified a range, it will need to keep track of the length anyway. You might as well pick one before, at random if you like, keeping in mind the starting and ending locations determine whether the length will be odd or even. Imagine a checkered board to see why.

Start out by drawing any one of the shortest possible tracks. If it is too short, select a random point on the track, then a second point a few nodes (Q) beyond the first, break up the track in between, and redraw the section using the two points as start and finish, but this time with a length of (Q+2), for instance by moving up at random until the traveled distance plus the minimum distance between the current node and the finish equals (Q+2), and start moving one tile in the direction of the finish every step after that. If at any point, you get stuck, revert to the last valid track and try again.

This algorithm will probably try to draw a lot of invalid paths, but leaves a lot of room for optimization, allows you to balance efficiency against 'flatness' of the probability distribution of all theoretically possible tracks, doesn't use relatively expensive tree searches and scales well, because you can make the redrawn sections as small as you want.