Optimum Mazing Path (by Length)

Assuming an N by N square playing space, with both towers and enemies taking up a 1×1 area, what is the optimum mazing setup to force enemies to spend the most overall distance pathing within the N by N square maze?

5 Solutions collect form web for “Optimum Mazing Path (by Length)”

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.

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.

We love Playing Games, especially Video Games.