I'm making a simple JavaScript tower defense game, I've experimented on some map generation my self, i seem to get one that works properly.
What I want is for you to provide a start point (possibly an end point) and an algorithm to generate a random path between them in a tower defense like style.
Examples
You essential want a maze with no dead ends, sometimes also known as a unicursal maze or a labyrinth.
Jamis Buck describes a way to build rectangular unicursal maze as follows:
This makes dead-ends into u-turns, and will give you a unicursal labyrinth that is twice the size of the original maze. Here's an illustration of his process using a very small maze:
One drawback to this approach is that the resulting entrance & the exit are right next to each other. Here is a simple modification that will allow for an arbitrary entrance & exit:
Here's an illustration that applies the modification to the previous example:
This isn't the only adaptation to fix the entrance & exit. Another somewhat more complex modification involves combining mulitple labyrinths. A more complex solution would be to partition & reconnect portions of the labyrinth.
Finally, note that while the illustrations I've used have varying wall thickness to illustrate the steps of the algorithm, all mazes are essentially (mathematical) graphs & you can adjust the representation (visual output) of the graph according to the needs of your game.
Recently I worked on the map generation algorithm for a tower defense game. The approach I took was to take a maze generation algorithm and use the solution path as the path that creeps follow.
This worked well because maze algorithms are so well-studied, there are plenty of features already there for you to adapt to the tower defense genre. For example, one major determinant of difficulty is the length of the path; for maze algorithms the relevant metric is river:
River, from high to low
You can read more about maze algorithm here: http://www.astrolog.org/labyrnth/algrithm.htm
Of course, you'll want to make some adaptations to suit your particular tower defense game. You may want enough space around corners to place towers there, or ways to control whether the path has lots of small turns or large turns that double back on itself.
Most AI I behavior I know of is meant to get the shortest path first type thing...aka traveling salesman problem.
I would say use the symmetry theory like in this example ... but with one caveat, you have the logic setup in order to keep the symmetry equal as long as possible. In order to induce curves and such you half the value and select a random direction, then maintain the symmetry after the turn & a few extra.
Then there's "noise theory", where you generate a map, randomly select a starting point & then the pattern is that you test for the highest or lowest value of noise for each adjacent space moving across the map.
I haven't read this one in awhile, but remember thinking it was decent
