2
\$\begingroup\$

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 enter image description here

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Define "tower defense like style". Some images would be nice \$\endgroup\$ – Bálint Feb 2 '17 at 20:06
  • \$\begingroup\$ 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. \$\endgroup\$ – Pikalek Feb 2 '17 at 20:40
1
\$\begingroup\$

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:

enter image description here 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: enter image description here 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.

\$\endgroup\$
5
\$\begingroup\$

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

recursive backtracker eller prim

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.