Optimal Tower Defense Grid Layout?

[The Grim Squeaker]

Assuming a rectangular grid, let's say 7x5 or 9x12, what type of layout would be optimal for tower defense type games?
(Obviously the specifics vary between games of the genre, but what interested me is the geometrically optimal layout).

[Starglider]

This is a hopelessly generic question. Towers with fixed range have circular coverage, suggesting a hexagonal grid for achieving minimal total coverage of an area. However the optimal amount and pattern of overlap varies wildly between games, terrain/tower types within a specific game and specific tactical situation.

[The Grim Squeaker]

There should be a certain basic pattern providing optimal fire-arc coverage.
Rather like a sphere being the optimum of surface area-volume ratio, or the folds of internal gut cillia..?

(Bah, where's a graphic input interface when you need one?)

[Hawkwings]

Are you assuming all towers are the same? Are you assuming creeps going from one side to another? Or along a path? Or along the path of least resistance? Are there fast/slow/special ones? Are there any special effects? Do they respond to being killed?

The optimal tower defense layout is an impenetrable wall of course.

[D.Turtle]

A spiral should be the best you can do. It was the only way I found to make the pathfinding in Starcraft 1 tower defense games give up in frustration.

[Sarevok]

^^
Thats because starcraft most likely uses waypoint based pathfinding using A*.

Navmesh based pathfinding would probably laugh at your spiral powers...

[Simon_Jester]

There should be a certain basic pattern providing optimal fire-arc coverage.

Not if you don't state your assumptions there isn't.

I mean, think about how complicated the problem of "where do I site my weapons to defend an area against attackers" can get in real life. It is not simple; there are countless ways to fuck it up. See here for an extended story of how it can be fucked up- and how it can be done well.

There is no one Optimum Defensive Strategy- just a set of rules that work as rules of thumb... and which change entirely when the nature of the weapons change.

Tower defense games are greatly simplified compared to that, but they are still quite complicated depending on the details of how weapons work, what they're capable of, where the enemy is going to go, and so on.

Rather like a sphere being the optimum of surface area-volume ratio, or the folds of internal gut cillia..?

In both those cases, you at least know what you're optimizing for. "Area to volume ratio" is a number, you can calculate it. You can't calculate the many many variables in the problem you've set for us, at least not in a way that gives you one answer.

The best you can get is general rules, for example:
-Try to block off straight-line paths.
-If the enemy follows a fixed curved path, and your assets are limited, site them in places where they can hit more than one stretch of the path.
-Long range weapons are particularly good at this; short range weapons will typically be placed to defend a specific objective.
-If you have ways of making the enemy slow down, use them right where the enemy enters your field of fire.

Stuff like that. Which is nothing like what you're looking for... but then, what you're looking for can't exist.

[defanatic]

It really does depend on the rules of the tower defence in question. Some versions don't allow you to block up the creep path, so with those it's just where you can maximise enemy unit time inside your fire range. Some do, and then it depends on where the creeps are trying to get to.

It also depends on time constraints as well.

[Sarevok]

Simon Jester speaks the truth. There is no one true solution to this problem. Only some general guidelines that produce better than average results.

I once faced a similar problem when designing a FPS game AI. When implementing soldier AI in my FPS game I hardwired some basic rules into them, such as take cover, retreat etc. It's a FSM based AI that does not always make the most correct choice. Yet the challenge felt by the player is quite good enough and it creates the illusion of fighting a living enemy that makes mistakes.

To me a perfect rigorous solution belongs to realms of games like chess. In general you would want winning strategies as opposed to the most efficient algorithm.

[D.Turtle]

Man, most of you guys are totally overthinking this problem. Have you played any amount of Tower defense games at all?

They come in pretty much exactly two variants: Fixed paths with the ability to place your towers on the side of those paths. Obviously, the defense layout in this case does not give too much opportunity for variation - more important there is what type of tower you build.

The other variant is one where they enter on one side of an open space and take the shortest path to the other side of that open space. This is where the layout is extremely important.

Now, obviously the question is about the second type of tower defense.

And in that case, AFAIK spirals are the best strategy.

Of course, if you go with a shorter path - by for example just going straight up/down in columns, then you can actually fit in more towers on the field, but usually the trade-off isn't worth it and just going for the longest path is the best strategy.

[Crossroads Inc.]

SPIRAL POWER!!! Has always been one of the best ways to go in TD games. Not just because it maximizes the trip needed for mobs, but also using the SPIRAL it maximizies the effectivness of towers so that virtually all times all towers are attacking. In a well done maze, the SPIRAL POWER!!! will have all towers being used at the same time.

[Sarevok]

By the way does anyone with think we have hit "Peak Tower Games" yet ? Tower defense seems to be the second most thing Indies are over producing after side scrollers.