# Randomly generated track

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:

-
Welcome to GD.SE! If this is a homework assignment, you're probably better off asking a question on stackoverflow.com, tagging it with homework and directly copying or linking to the assignment. If not, please ask a (more) specific question, as it's now unclear whether you need an algorithm or just an idea. In either case, show what you have already tried: sscce.org – Eric May 27 '12 at 12:17
Can you give examples of valid tracks? Don't really understand the specifications of a "track", "Matrix", "Length" and "Corner". – Jake May 27 '12 at 15:22
@Eric actually I think it's a good path finding question, though I can't answer it myself at least right now! – Ali.S May 27 '12 at 17:28
Actually this is like the A* star algorithm except you do not find the shortest path with least cost; instead you find the path where (cost - length) < 2 (for +/- 2)... – Jake May 27 '12 at 17:47
@Gajet I'll have you know it has improved considerably since its first incarnation. :-) Nice work DominikT.! – Eric May 27 '12 at 17:56

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.

-
Thanks, I'm not good with these graph algorithms, but I have the concept how to do it with DFS. A* is also looking good for that as @Jake said. – Dominik T. May 28 '12 at 15:55
@adam, there are some limitations on your algorithm. first of all where did you put the randomness? and then think about the situation when one starts and moves directly towards the target, what should the algorithm do if it get's at the target before desired distance? – Ali.S May 29 '12 at 5:22
So what would you recommend @Gajet? – Dominik T. May 29 '12 at 17:06
@Gajet The randomness comes from the 'random square' selection. If the algorithm gets to the end square too quickly it will keep searching until it either has to backtrack or it manages to extend the route to the correct length. The algorithm is essentially trying random routes till it finds one that fits the requirements, with extra tests to cut down the search space somewhat. – Adam May 31 '12 at 23:19

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.

-
I had an idea like that before, but I prefer the way with generating paths randomly. But if I'll have problem with DFS or A*, I'll use your method. Thanks. – Dominik T. May 28 '12 at 15:56