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?

Answer

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.

Attribution
Source : Link , Question Author : Raven Dreamer , Answer Author : Crag

Leave a Comment