Module path 

Paths over a square grid: where a walker can go on a budget and the cheapest path there (reachable), and how far every tile is from a set of goals (flow_field). The game says what a tile costs with a cost function; the rules of who may stand where stay the game’s.

Rules

• Steps. Only the four grid directions (Dir) are steps. A step pays the cost of the tile it enters: the cost function’s answer for that tile, or no step at all when it answers None. The start costs nothing. The cost function is only asked about tiles inside the grid.
• Budget. reachable keeps the tiles whose cheapest cost is at most the budget.
• Determinism. Both searches are one Dijkstra. Its queue is ordered by (cost, y, x), neighbours are visited in Dir::ALL order, and a tile’s recorded predecessor only changes for a strictly cheaper cost. So among equally cheap paths to a tile, the one through the neighbour expanded first wins, every time. When every step costs at least 1, tiles are expanded in (cost, y, x) order, so that neighbour is the one with the smallest (cost, y, x) among those on a cheapest path. Steps that cost 0 can reach a tile at the cost being expanded but with a smaller (y, x) than tiles already expanded at that cost, so then the order is only cheapest first.
• A cost that would pass u32::MAX is no step.

Structs

Reach

Where a walker can go from one tile on a budget, with the cheapest path to each tile. Built by reachable.

Functions

flow_field

How far every tile of a width × height grid is from the nearest of goals: the cost of the cheapest walk from the tile onto a goal, where entering a tile costs cost(tile), as in reachable, and there is no budget. A goal is 0 from itself. A tile that can’t be entered has no distance (unless it is a goal), and neither has a tile with no walk to a goal: a goal that can’t be entered is never walked onto. Goals outside the grid are left out.

reachable

Where a walker on start can go with budget to spend on a width × height grid, where entering a tile costs cost(tile) (None: it can’t be entered). A start outside the grid reaches nothing.