Optimum Mazing Path (by Length)
Solution 1:
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.
Solution 2:
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.