2

I'm currently working on a tower defense game for iOS using objective-c and am running into problems as far as generating a random path for each level. After researching on google, I only found bezier path generators, which is not what I'm looking for. I basically need an algorithm that generates random waypoints which are connected to each other with straight lines.

# * * * # / / / / /   
/ / / / * / # * # /       
/ / / / * / * / * /
/ # * * # / * / * /
/ * / / / / * / * /
/ # * * * * # / * /
/ / / / / / / / # #

The above is a perfect example of what I would need, where all the waypoints(#) connect either vertically or horizontally with each other so the resulting grid has straight, connecting lines. Any help would be great. Thanks.

jscs
  • 63,694
  • 13
  • 151
  • 195
TheFatNarwhal
  • 89
  • 7
  • Why do you want it to be random? Then you have no control over how easy/hard it is. – Wain Jul 11 '13 at 18:13
  • Look into Maze generation algorithms: http://en.wikipedia.org/wiki/Maze_generation_algorithm http://stackoverflow.com/questions/38502/whats-a-good-algorithm-to-generate-a-maze http://flashgamedojo.com/wiki/index.php?title=Fathom's_Labyrinth_Algorithm – CodeSmile Jul 11 '13 at 18:14
  • Can a line that connects two waypoints cross another line? – Ramy Al Zuhouri Jul 11 '13 at 18:38
  • @RamyAlZuhouri preferably not, but it's not essential that they don't. – TheFatNarwhal Jul 11 '13 at 19:00

3 Answers3

3

This is just a very basic idea to start you off:

  • Generate random points.

  • Repeatedly connect two random points by moving only vertically from the one point and horizontally from the other (there are two ways to do this). See example for more details.

    Assuming you want a non-splitting path, these chosen points should not both already be connected to any other points (but one already having been connected is fine).

  • Backtrack if you get stuck (if you can't connect a point to anything or you've made a path from start to finish and there are points outstanding) and/or restrict how you pick points in such a way to prevent / reduce the probability of getting stuck. Connecting the start and end points to start, for example, won't get you anywhere.

For example, to get to your maze:

The randomly generated points will look like this: (note that the start and end-points could be fixed here, or at least be constrained to (certain?) sides)

1 / / / / / / / / /   
/ / / / / / 4 / / /       
/ / / / / / / / / /
/ / / / 3 / / / / /
/ / / / / / / / / /
/ 2 / / / / / / / /
/ / / / / / / / 5 6

Then you connect 1 and 3 by moving horizontally from 1 and vertically from 3. An alternative would've been moving vertically from 1 and horizontally from 3.

1 * * * # / / / / /   
/ / / / * / 4 / / /       
/ / / / * / / / / /
/ / / / 3 / / / / /
/ / / / / / / / / /
/ 2 / / / / / / / /
/ / / / / / / / 5 6

Then you connect 3 and 2, 2 and 4, 4 and 5 and 5 and 6 in the same way.

Note that when connecting 5 and 6, they can only be directly connected with no intersection point since they lie on the same horizontal line. Or you can think of it as either 5 or 6 moving vertically by 0 units.

Community
  • 1
  • 1
Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
0

I believe you are looking for A-Star algorithm which is very well explained on many sites. Please refer to tutorials which describe how navigate through maze/map.

The Tosters
  • 417
  • 3
  • 15
0

What you want is related to maze generation.

Basically, you're generate a maze with some sort of bias for long straight hallways and then discarding everything except the single path from the start to the end.

I can't really give much in terms of specifics, because the sorts of paths you want and the theme of your game will heavily impact what results you want.

Perhaps a good place to start is some sort of fractal process.

Craig Gidney
  • 17,763
  • 5
  • 68
  • 136