# 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, 2012 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, 2012 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! May 27, 2012 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, 2012 at 17:47
• @Gajet I'll have you know it has improved considerably since its first incarnation. :-) Nice work DominikT.!
– Eric
May 27, 2012 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. May 28, 2012 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? May 29, 2012 at 5:22
• So what would you recommend @Gajet? May 29, 2012 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.