Expand description
§Mode Maze
Our high level approach is an A* search. This fantastic blog is a great introduction to this algorithm. The heuristic is the Manhattan distance to the target. This will never overestimate the actual distance which is an essential characteristic in the heuristic. Interestingly benchmarking showed that adding the time to switch tools if we don’t have the torch to the heuristic slowed things down.
Using A* instead of Dijkstra results
in a 6x speedup. This is because Dijkstra explores the grid evenly in both axes, so if the
target is 700 deep, then we will explore an area roughly 700 x 700 in size. In contrast A*
prefers reducing the distance to the target, exploring a more narrow area
approximately 130 x 700 in size. The state is a tuple of (location, tool) in order to track
the time per tool separately.
To speed things up even further we use a trick. Classic A* uses a generic priority queue that
can be implemented in Rust using a BinaryHeap. However the total cost follows a strictly
increasing order in a constrained range of values, so we can use a much faster
bucket queue. The range of the increase is from
0 (moving towards the target and not changing tools) to 7 (staying put and changing tools)
requiring 8 buckets total.
Structs§
- Region 🔒
Constants§
- BUCKETS 🔒
- TORCH 🔒The index of each tool is that tool that cannot be used in that region, for example Rocky => 0 => Neither, Wet => 1 => Torch and Narrow => 2 => Climbing Gear.
Functions§
- Build the minimum grid to the target then calculate the risk level.
- A* search for the shortest path to the target.
- Calculate the erosion level for each region. We swap width and height for a small speed boost without affecting the outcome of the shortest path.
Type Aliases§
- Input 🔒