# Optimum Mazing Path (by Length)

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?

-
Not 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 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 en.wikipedia.org/wiki/Directed_acyclic_graph for more info. – Crag Apr 13 '11 at 18:13
Should be posted on math or programming puzzles :) – Carra Apr 15 '11 at 23:55

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
"...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 Y 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
@MarkTrapp - That looks much better. – Raven Dreamer Apr 14 '11 at 4:41
``````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.
-

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#..................
``````
-

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.

-

Is there an assumption that the walls/towers/obstacles are permanently placed? If not, then you can try juggling.

-
I think "Mazing" implies permanence. – Raven Dreamer Apr 14 '11 at 21:31