Longest path strategies

[amarvin]

Let's just share ideas about longest path strategies that may inspire algorithms, as the gradient-free methods (e.g. genetic algorithm) doesn't seem promising for this type of problem.

[amarvin]

I had a thought today to split the rally points (start, waypoint0, waypoint1, ..., waypoint5, end) into two groups (call them A and B), and make a maze that separates the two groups.

The smartest way to separate the rally points then is a max cut of the sequence graph (start -> 0 -> 1 -> 2 -> 3 -> 4 - > 5 -> end). In this case, the optimal max cut is obvious -- group A is (start, 1, 3, 5) and group B is (0, 2, 4, end).

So my proposed maze forces creeps to walk through it to get to waypoint0, then back out of it to get to waypoint1, then through it again to get to waypoint2, etc.

The first step then is to make all group B rally points connected:

path length 679

Then I just tried to add as much length to the maze separating the two groups.

path length 3361
where the remaining unbuilt green squares are unbuildable, and I don't know why.

[amarvin]

Found a few strategies in https://www.reddit.com/r/DotA2/comments/3n7m1f/a_short_kappa_guide_to_gem_td/, and they all use the two-group approach I tried to force the creeps to walk through the entire maze 5 or 6 times.