In the latest expansion of Path of Exile you can create your own areas to play in. An example of this can be seen below:
The area is constructed by placing tiles on a board. You enter the area from one of the land tiles.
Moving away from the starting tile causes the difficulty to increase. Further away = more difficult areas, but also more rewards. In the example the highest difficulty is 10.
The trailer for the expansion shows different boards of different sizes. So what is the highest difficulty (and reward) you could achieve on any board size?
What we are looking for is the longest path from the starting location to any other tile on the board. See the algorithm I used to solve this problem.
The first one are quite obvious:
The 3x4 board continues with the “U” shape, but introduces a new kink.
In the 3x5 board the pattern continues, but this time a “2” pattern is introduced.
Variations of the “2” are the most optimal for the 3x6 and 3x7 boards.
More chaotic patterns for 4x7 boards.
Some different patterns for the 5x4 boards.
Quite a lot more patterns for the 5x5 board.
Only one optimal pattern for the 5x6 board.
And then again quite a few patterns for the 6x6 board.
The 7x6 board is the biggest board I was able to check with my algorithm:
Some 10x2 patterns.
The source code used to generate these images is open source. I am not claiming that the source code represents the most optimal way to generate these paths.
First I generate a graph representing the board:
In this graph I generate all paths between any two nodes. From these paths I ignore paths here two nodes “meet” without a edge connecting them, as this would create shortcuts:
Finally I just take the longest path from all the remaining paths.
While not exactly a efficient solution, it works.
And what else can you hope for, for a (maybe?) NP-Hard problem: longest path problem.