Pathfinding for Tower Defense
Last week though I was reading this tutorial, Pathfinding for Tower Defense.
He explains a method for creating a single vector/flow field for game AI’s to follow. This allows a single calculation to be used by a lot of AI bots, which is great for a Tower Defense game.
A new game…
“What is the longest path possible? / What is the highest number I can reach?”
After I found out I can move the start position around, I came up with the following configuration:
The maze is 113 long… but it turns out this is far from optimal. After coding up a little solver and playing around I found the following configuration:
This is a solution that goes up to 124 (near the top left corner). I’ve also found one later with a score of 125.
It seems that diagonals are the best way to pack the longest maze into there, but the problem is, one diagonal cuts the field in two smaller parts. Zig-zagging works great, but there is no ‘easiest’ way to zig-zag.
It doesn’t seem to me that there is a trivial solution? I haven’t found one at least, is there? Are there simple optimal patterns for given boxes, NxN?
Searching for a solution seems to be NP-hard and even 20x10 is out of the question, the amount of possible configurations of walls and starting positions is huge and grows exponentially. Coding up a solver is pretty easy though, using some simple heuristics and some random searches I got my 125 solution.
Maybe this would be a fun puzzle for a future AZsPCs contest…?
Can you get a better configuration than 125? I’d love to know.
When I wrote a score checker for the puzzle above I needed a way to get the neighbors in an 2D array. I’ve gotten used to code 2D mazes/puzzles and I always use the following way to calculate all the neighbors.
I find this to be easier and more readable that the alternatives, going over all the -1/+1 combinations or having two nested loops.
How does this work?
First we list all directions with a single integer, 0 to 9, and we’ll need to skip the middle number four, this points to ourself.
From this single direction we’re able to easily calculate both the new row value (n_row) and the new col value (n_col). To do this we’ll need to divide by three and use modulo three.
Neighbor row value:
To find the new row value we start our by using modulo 3. The only thing left to do is to subtract 1 and we’ll get the new row value for each direction:
Neighbor col value:
The same thing can be done for the col value. Instead of using modulo 3, we’ll be using divide by 3. And the same as with the row value, we’ll also need to subtract 1 to get the following new column values:
And there you go, list all neighbors in a 2D array without using two nested loops and dirty checks.