function that returns the cost to move onto a tile. To represent an 'impassable' tile, cost should return a large value. Do NOT let cost return a value large enough to overflow when added to another. For example, if cost returns an int, the return value should be less than int.max / 2.
type of the grid
grid of tiles to find path on
tile to start pathfinding from
the 'goal' the pathfinder should reach
the shortest path as a range of tiles, including end but not including start. returns an empty range if no path could be found or if start == end.
import std.algorithm : equal; // let the 'X's represent 'walls', we want a path from a to b auto grid = rectGrid([ // 0 1 2 3 4 5 <-col| row [ 'X', 'X', 'X', 'X', 'X', 'X' ], // 0 [ 'X', ' ', 'b', 'X', 'b', 'X' ], // 1 [ 'X', ' ', 'b', 'X', ' ', 'X' ], // 2 [ 'X', ' ', 'X', 'X', ' ', ' ' ], // 3 [ ' ', 'a', ' ', ' ', ' ', 'X' ], // 4 [ ' ', ' ', ' ', 'X', 'X', 'X' ], // 5 ]); // our cost function returns 1 for an empty tile and 99 for a wall (an 'X') auto path = shortestPath!(x => x == 'X' ? 99 : 1)(grid, RowCol(4,1), RowCol(1,4)); assert(!path.empty, "failed to find path when one existed"); // path should include the end but not the start assert(path[].equal([RowCol(4,2), RowCol(4,3), RowCol(4,4), RowCol(3,4), RowCol(2,4), RowCol(1,4)]));
Get the shortest path between two coordinates.