//! Pathfinder algorithms on a grid. The grid is stack-based, we only use heap allocations //! in solvers. const std = @import("std"); const Str = []const u8; /// Various predefined valid neighbour directions on a 2D grid. pub const D2 = struct { pub const horizontal = [_][2]i2{ .{ 0, -1 }, .{ 0, 1 } }; pub const vertical = [_][2]i2{ .{ -1, 0 }, .{ 1, 0 } }; pub const HV = horizontal ++ vertical; pub const diagonal = [_][2]i2{ .{ -1, -1 }, .{ -1, 1 }, .{ 1, -1 }, .{ 1, 1 } }; pub const all = HV ++ diagonal; }; /// Grid for various pathfinder algorithms. /// `T` is the type of Grid items. /// `GRID_ROWS` and `GRID_COLS` defines the Grid size. pub fn Grid(comptime T: type, comptime GRID_ROWS: usize, comptime GRID_COLS: usize) type { return struct { grid: [GRID_ROWS][GRID_COLS]T = undefined, const QueueType = struct { state: [2]usize, cost: T, }; pub fn setGrid(self: *@This(), grid: [GRID_ROWS][GRID_COLS]T) void { self.grid = grid; } /// Parses a grid-file located in `path`. The items must be separated with `sep`. pub fn parseGridFromCSV(self: *@This(), comptime path: Str, sep: Str) !void { const input = @embedFile(path); var lines = std.mem.tokenize(u8, input, "\n"); var ret: [GRID_ROWS][GRID_COLS]T = undefined; var row: usize = 0; while (lines.next()) |line| : (row += 1) { var items = std.mem.tokenize(u8, line, sep); var col: usize = 0; while (items.next()) |item| : (col += 1) { switch (@typeInfo(T)) { .Int => |item_type| { if (item_type.signedness == .unsigned) { ret[row][col] = try std.fmt.parseUnsigned(T, item, 0); } else { ret[row][col] = try std.fmt.parseInt(T, item, 0); } }, .Float => ret[row][col] = try std.fmt.parseFloat(T, item), else => @compileError("unsupported type: " ++ @typeName(T)), } } } self.setGrid(ret); } fn lessThan(context: void, a: QueueType, b: QueueType) std.math.Order { _ = context; if (a.cost == b.cost) { return .eq; } else if (a.cost < b.cost) { return .lt; } else { return .gt; } } /// Finds shortest path between `start` and `goal` using Dijkstra's algorithm. /// Returns the path length or `error.PathNotFound`. pub fn dijkstra( self: *@This(), allocator: std.mem.Allocator, start: [2]usize, goal: [2]usize, dir: anytype, ) !T { var CostGrid = switch (@typeInfo(T)) { .Int => [_][GRID_COLS]T{[_]T{std.math.maxInt(T)} ** GRID_COLS} ** GRID_ROWS, .Float => [_][GRID_COLS]T{[_]T{std.math.floatMax(T)} ** GRID_COLS} ** GRID_ROWS, else => @compileError("unsupported type: " ++ @typeName(T)), }; CostGrid[start[0]][start[1]] = 0; var queue = std.PriorityQueue(QueueType, void, comptime lessThan).init(allocator, {}); defer queue.deinit(); try queue.add(.{ .state = start, .cost = 0 }); while (queue.removeOrNull()) |curr| { if (std.meta.eql(curr.state, goal)) { return curr.cost; } for (dir) |d| { const diffrow = @as(isize, @intCast(curr.state[0])) + d[0]; if (diffrow < 0 or diffrow >= GRID_ROWS) continue; const dr = @as(usize, @intCast(diffrow)); const diffcol = @as(isize, @intCast(curr.state[1])) + d[1]; if (diffcol < 0 or diffcol >= GRID_COLS) continue; const dc = @as(usize, @intCast(diffcol)); const cost = CostGrid[curr.state[0]][curr.state[1]] + self.grid[dr][dc]; if (cost < CostGrid[dr][dc]) { CostGrid[dr][dc] = cost; try queue.add(.{ .state = .{ dr, dc }, .cost = cost }); } } } return error.PathNotFound; } pub fn astar( self: *@This(), allocator: std.mem.Allocator, start: [2]usize, goal: [2]usize, dir: anytype, heuristics: anytype, ) !T { var CostGrid = switch (@typeInfo(T)) { .Int => [_][GRID_COLS]T{[_]T{std.math.maxInt(T)} ** GRID_COLS} ** GRID_ROWS, .Float => [_][GRID_COLS]T{[_]T{std.math.floatMax(T)} ** GRID_COLS} ** GRID_ROWS, else => @compileError("unsupported type: " ++ @typeName(T)), }; CostGrid[start[0]][start[1]] = 0; var queue = std.PriorityQueue(QueueType, void, comptime lessThan).init(allocator, {}); defer queue.deinit(); try queue.add(.{ .state = start, .cost = 0 }); while (queue.removeOrNull()) |curr| { if (std.meta.eql(curr.state, goal)) { return curr.cost; } for (dir) |d| { const diffrow = @as(isize, @intCast(curr.state[0])) + d[0]; if (diffrow < 0 or diffrow >= GRID_ROWS) continue; const dr = @as(usize, @intCast(diffrow)); const diffcol = @as(isize, @intCast(curr.state[1])) + d[1]; if (diffcol < 0 or diffcol >= GRID_COLS) continue; const dc = @as(usize, @intCast(diffcol)); const cost = CostGrid[curr.state[0]][curr.state[1]] + self.grid[dr][dc]; if (cost < CostGrid[dr][dc]) { CostGrid[dr][dc] = cost; try queue.add( .{ .state = .{ dr, dc }, .cost = cost + try heuristics(.{ dr, dc }, goal) }, ); } } } return error.PathNotFound; } }; }