# I need a map generation algorithm for towerdefense

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

• Define "tower defense like style". Some images would be nice Commented Feb 2, 2017 at 20:06
• Yes, showing an example of what you've tried & marking &/or describing in more detail which parts work & don't work (and why) would help. Gemcraft & Infested Planet are both TD games, but have very different maps. Commented Feb 2, 2017 at 20:40

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:

• Generate a maze first of half the desired final size.
• Remove the exit so only the entrance remains.
• Bisect each passage with a wall.

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:

• Pad the existing maze out with a wall thick enough to contain a tunnel.
• Pick an entrance & dig a tunnel to the nearest opening.
• Pick an exit & dig a tunnel to the remaining opening.

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