Assuming an N by N square playing space, with both towers and enemies taking up a 1x1 area, what is the optimum mazing setup to force enemies to spend the most overall distance pathing within the N by N square maze?
Asked
Active
Viewed 1.2k times
28
-
1Not sure if it makes a difference, but where are the entrance and exit in this hypothetical scenario? – Mana Apr 13 '11 at 16:24
-
I think it'd be useful to both consider entrances at the middle of the square, and at the corners, though those are, admittedly, two separate cases. – Raven Dreamer Apr 13 '11 at 16:29
-
Cool question; I wonder if a TD "solver" app would be doable? – tenfour Apr 13 '11 at 17:54
-
This question might get a better response over at http://math.stackexchange.com/ since the answer involves finding the longest path of a graph. Placing your towers removes vertices and edges, altering the current longest path. Check out http://en.wikipedia.org/wiki/Directed_acyclic_graph for more info. – Crag Apr 13 '11 at 18:13
-
@Crag - unfortunately, I lack the math vocabulary to ask the question appropriately on that site. Thanks for the link though! – Raven Dreamer Apr 13 '11 at 19:26
-
How do enemies handle corners? Do they hit the center of each block or do they cut the corner? – Arkive Apr 14 '11 at 21:43
-
@Arkive it depends on how the game is coded; it varies from Defense to Defense. – Raven Dreamer Apr 14 '11 at 21:54
-
@Arkive I was going to ask a similar question to yours yesterday, but I think it is implied that there are no corners to handle. Enemies only can travel up/down/left/right. No Diagonal movement. @Raven_Dreamer can correct me and edit the question if I'm assuming too much. – Crag Apr 14 '11 at 21:56
-
I think that most tower defense games don't have the AI programmed to go through corners, but splitters often go through them anyway, and can really mess up your designs. – Ullallulloo Apr 14 '11 at 22:26
-
1Should be posted on math or programming puzzles :) – Carra Apr 15 '11 at 23:55
-
@RavenDreamer Really... No tag? Shame on you! – Stingervz Nov 13 '12 at 12:01
-
@Josefvz It had been tagged "Tower-Defense". If questions only have a single tag, however, they lose it and the tag gets auto-deleted after 6 months. – Raven Dreamer Nov 13 '12 at 12:02
5 Answers
16
Well, assuming you start in the top left corner and end in the bottom right corner, the longest possible path will be one that zig/zags along the entire map from north to south or east to west. I wrote the following recursive program for fun to find the longest path and produce an output and it comes out with this solution no matter what size for height,weight you input:
Note though, this does not mean the longest path is actually an optimal strategy in turret defence type games, because you have to factor in things like tower costs and upgrades. More often than not, the best situation is simply to force units to congregate as much as possible in a kill zone. It gets even more convoluted when you factor in things like slowing towers. Here is some sample outputs:
# = wall
. = path
N = start
O = end
Width = 10, Height = 5
N#...#....
.#.#.#.##.
.#.#.#.#..
.#.#.#.#.#
...#...#.O
Width = 10, Height = 10
N#...#....
.#.#.#.##.
.#.#.#.#..
.#.#.#.#.#
.#.#.#.#..
.#.#.#.##.
.#.#.#.#..
.#.#.#.#.#
.#.#.#.#.#
...#...#.O
@Raven Dreamer
Yes, I realize that last edge case, I am unsure why its not doing that last optimization just yet, but I did modify my code to include a movable entrance/exit. Here is a sample generation of a middle entrance:
...#...#...#...##...
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
N#.#.#.#.#.#.#.##.#O
#..#.#.#.#.#.#.##.##
..#..#.#.#.#.#.##.## <---
.#..#..#.#.#.#.##.## <---
.#.#..#..#.#.#.##.## <---
.#.#.#..#..#.#.##.## <--- need optimization here
.#.#.#.#..#..#.##.## <---
.#.#.#.#.#..##..#.## <---
.#.#.#.#.#.####.#.## <---
...#...#...####...## <---
I removed my program since I figured out the source of error, I'll put up a working version later, but its going to take some rewriting. The answer remains unchanged though, the longest path is not that interesting, but it was a fun programming exercise.
-
Ah, this is disappointing. I had hoped the optimal maze would be a little more interesting than this. What happens when you move N into the middle of the side? – Raven Dreamer Apr 13 '11 at 19:21
-
@yx_ you might want to double-check your code; the final graph does not have the longest path; One or two length could be gained by forcing the path down to the bottom right corner instead of cutting across one row early. – Raven Dreamer Apr 13 '11 at 19:34
-
2"...this does not mean the longest path is actually an optimal strategy in turret defence type games..." - wonderful point. For example, if one tower gave AoE damage, you might instead construct a "room" with the tower centered in it to maximize damage. – Kevin Yap Apr 13 '11 at 22:50
-
@Kevin: or a maze where the enemies pass by your strongest tower(s) more than twice. Also note that this won't work in games with specialized enemies eg. Sanctum has an enemy that moves really fast on long straightaways. – BlueRaja - Danny Pflughoeft Apr 13 '11 at 23:19
-
-
@yx_ How did you calculate length? # of blocks in path? I think I have a better solution than your program yielded for the 10x10 case. I use less towers too. – Arkive Apr 14 '11 at 21:45
-
@Arkive yes, its simply by number of blocks '.' in the path, feel free to post yours :) I didn't have time to give this problem another shot today, maybe tomorrow. – l I Apr 14 '11 at 21:55
-
-
@yx_ im jsut so impressed by this, unless you have some object, may i have a look at the script you used to gen then? – TrewTzu Jul 31 '11 at 15:02
-
6
This is my favourite build. It is spiral build. it is 190x. and 156x# Main strenght of this is that creeps are circling around middle so you can invest all your money in few strong tower and put them in the middle of your maze.
..................#O
.################.#.
.#..............#.#.
.#.############.#.#.
.#.#..........#.#.#.
.#.#.########.#.#.#.
.#.#.#......#.#.#.#.
.#.#.#.####.#.#.#.#.
.#.#.#.#....#.#.#.#.
.#.#.#.#.####.#.#.#.
.#.#.#.#......#.#.#.
.#.#.#.########.#.#.
.#.#.#..........#.#.
.#.#.############.#.
.#.#..............#.
.#.################.
N#..................
KAOS
- 61
- 1
- 2
6
N = 10
Path Length = 61
Towers = 30
N#...#....
...#.#.#..
..#..#..#.
.#..#..#..
#..#..#..#
..#..#..#.
.#..#..#..
.#.#..#...
.#.#.#..#.
...#...#.O
This diagonal design, uses fewer towers than the traditional vertical design and yields a slightly longer path length for N = 10. For N = 9, I was unable to produce a longer path than the vertical approach.
I haven't tested cases other than N = 9, 10, and 12 , but I suspect that for N = 1 + 4x, where x is an integer > 0 the vertical approach will yield the maximum path length, but not necissarily the lowest tower number.
More investigation:
- Entry/exit in middle
- What values of N is this diagonal approach more effective
- Identification of combinational strategies
- The above approach uses diagonal walls with vertical segments in the NE and SW corners.
Arkive
- 11,231
- 8
- 69
- 88
1
On games like desktop tower defence where there is an entrance on the top and left, a diagonal line from top left to bottom right with a gap at bottom right, with lines on each side parallel with a gap at the top left repeated is the best, as all creeps go past every tower, and by upgrading the center few all flying creeps will go past the best towers.
Rich Bradshaw
- 111
- 3
