Made with Java
One project in my computer science class was called "Battle Royale". It was originally straightforward but I had a lot of spare time back then, so I made a very optimized solution.
The problem is very similar to the video game genre it is named after.
You are given a player which you can place at any position on an n by m rectangular grid. You may move in the four cardinal directions (up, down, left, right). Every time you move, the grid shrinks in all four directions. For example, a 5x5 grid becomes a 3x3 grid after one move. There is also loot scattered throughout the grid, each with value 1.
Your task is to find a route that maximizes the value of your loot and which reaches the center of the grid without dying. Remember that the grid shrinks every move, if you are at one of the grid cells that is removed then you will die.
Below is an example of a 14x20 grid
. . . 1 1 . . 1 . 1 . 1 . . 1 . . . . .
1 . . . . . 1 1 . 1 . . . . . . . . . .
1 . . 1 . . . . 1 . . . . 1 . 1 . 1 . 1
. . 1 . . 1 . . . . . . . . . . . . . .
. 1 1 1 1 . . . . . 1 . . . . . 1 . . 1
. . . . . 1 . . . . 1 . . 1 . 1 . . . .
. . 1 1 . . 1 . . . 1 1 1 1 . . . 1 . 1
. . . . 1 . . . . . 1 1 . . . . . . . .
. . 1 1 . . . . . 1 . . . . 1 1 . . . .
. . . 1 . . . . . . . . . . . . 1 . . 1
. . . 1 . . . . . . 1 1 . . 1 . . 1 . 1
. . . . . . 1 1 . . . . . . . . . 1 1 .
. . . . . . . . . . . . . . . . . . 1 1
1 1 . . . . . 1 . . . . 1 . . . . . . .. represents an empty cell. We can move into it but there's nothing there.1s represent loot. The total loot of a path is the sum of all 1s the path passes over.P represents the player's starting position. We have to decide where to place it for optimal results.The solution is
. . . 1 1 . . 1 . 1 . 1 . . 1 . . . . .
1 . . . . . 1 1 . 1 . . . . . . . . . .
1 . . 1 . . . . 1 . . . . 1 . 1 . 1 . 1
. . 1 . . 1 . . . . P . . . . . . . . .
. 1 1 1 1 . . . . . v . . . . . 1 . . 1
. . . . . 1 . . . . v . . 1 . 1 . . . .
. . 1 1 . . 1 . . . v v 1 1 . . . 1 . 1
. . . . 1 . . . . . f v . . . . . . . .
. . 1 1 . . . . . 1 . . . . 1 1 . . . .
. . . 1 . . . . . . . . . . . . 1 . . 1
. . . 1 . . . . . . 1 1 . . 1 . . 1 . 1
. . . . . . 1 1 . . . . . . . . . 1 1 .
. . . . . . . . . . . . . . . . . . 1 1
1 1 . . . . . 1 . . . . 1 . . . . . . .where v represents the path taken and f represents the final position (the center of the grid).
The maximum loot is 6.
The naive solution (which is the intended one for the class) is to run a graph traversal algorithm such as Depth-First Search (DFS) on the grid. The shrinking of the grid must be simulated at every "step" of the traversal. If the player goes out of bounds due to the shrinking grid, we terminate that particular traversal and return up the call stack to the last valid state of our DFS. We don't have to keep track of which cells we visited since the shrinking grid will ensure our DFS won't recurse infinitely.
Whenever we pass over a cell with loot (AKA a 1), we add it to the count of currently obtained loot.
If the DFS reaches the center cell, we terminate the search and update the maximum loot obtained.
The thing is, we need to run this DFS on every position in the grid to find the optimal position for the player to start at.
Of course, we can do many optimizations for a brute force algorithm like this:
1s as we pass over them and then add them back to the grid after the recursive call (backtracking). This saves us an entire 2D array.Every position gives us four more recursive calls. The time complexity of this algorithm is exponential: O(n*m * 4^(n*m)).
A common pathfinding algorithm in many games is A*, which finds optimal routes relatively quickly. Like DFS, it explores cells recursively. The difference is that it uses a heuristic: the estimated distance from the current position to the target position. It puts all cells to be explored next into a priority queue where the estimated distance from the target cell is the cell's priority. This means that it always first explores cells that it thinks are closer to the target. If it hits a dead end (player died), then it backtracks and tries the next closest cell.
The thing is, A is a pathfinding algorithm, so it needs a target. Well, we can loop over the entire grid and record the position of every cell with loot. Then we can treat these as targets for A.
So we will still use DFS but instead of our graph consisting of every cell in the grid, we only consider cells with loot. We can then use A* to construct our optimal path between these cells. We are trying all permutations of cells with loot. This is much faster for maps with less loot but potentially much worse for maps with a lot of loot. In practice, it is orders of magnitude faster than the brute force algorithm.
The algorithm's running time is O(n*m * L!) where L is the number of cells with loot.
Let A, B, C, D be cells with loot where B and C are equally distant from A and D. Then the paths (A, B, D) and (A, C, D) have the same length, same loot, and same final cell. Thus we can optimize by saying that they both have the same solution.
This is usually done using Bitmask Dynamic Programming (DP) but since there are only 64 bits in the largest integer, we have to find some other way to store the states.
I took inspiration from chess engine (chess AI) programming. There has been a lot of work towards optimizing chess engines, and one such optimization is Zobrist Hashing.
Initialize a 2D array zob, of random 64-bit integers with the same dimensions as the grid.
Take all the loot cells and put them in a list.
state is an integer list where state[0] is the current depth and state[i] = 1 if lootCells[i - 1] is in the path and 0 if not.
Whenever we reach a loot cell, we create a hash representing the current state using Zobrist hashing. Essentially we XOR all the random numbers for each loot cell:
zob[(cell i).row][(cell i).col] ^ zob[(cell i+1).row][(cell i+1).col] ^...
This gives a unique hash representing a certain state. We memoize the recursive DFS and store the maximum loot possible for a path starting at the current position in a dictionary, using the state's Zobrist hash as its key.
This results in around a 2 to 3 times speed up.