Skip to content

Instantly share code, notes, and snippets.

@DanTup
Last active April 6, 2022 22:25
Show Gist options
  • Save DanTup/01d87cd599517769ebe22d60c96e1acc to your computer and use it in GitHub Desktop.
Save DanTup/01d87cd599517769ebe22d60c96e1acc to your computer and use it in GitHub Desktop.
Sudoku Killer Cage path calculations
import 'package:built_collection/built_collection.dart';
import 'package:flutter/painting.dart';
import 'package:sudoku/src/model/model.dart';
import 'package:sudoku/src/model/model_extensions.dart';
typedef CellSelector = CellCoordinate Function(CellCoordinate);
class InsetInfo {
/// The relative cell to check for selection to know if we need a line along
/// this edge.
final CellSelector edgeSelector;
/// The offset to inset the line from the edge of the cell.
final Offset offset;
final InsetPointInfo start;
final InsetPointInfo end;
const InsetInfo(this.edgeSelector, this.offset, this.start, this.end);
}
class InsetPointInfo {
/// The relative cell whose top-left corner we use as a reference point.
final CellSelector cornerSelector;
/// The cell that should be selected along with [cell2Selector] to offset in
/// the negative direction, or that should not be selected to offset in the
/// positive direction.
final CellSelector cell1Selector;
/// The cell that should be selected along with [cell1Selector] to offset in
/// the negative direction.
final CellSelector cell2Selector;
/// A multiplier to apply to both points to offset it in the correct
/// direction.
final Offset multiplier;
const InsetPointInfo(this.cornerSelector, this.cell1Selector,
this.cell2Selector, this.multiplier);
}
mixin OutlineRenderer {
static const _edgeInsetInfos = [
// If no selection to the north, render a line along the top.
InsetInfo(
_n,
Offset(0, 1),
InsetPointInfo(_c, _w, _nw, Offset(1, 0)),
InsetPointInfo(_e, _e, _ne, Offset(-1, 0)),
),
// If no selection to the east, render a line on the right side.
InsetInfo(
_e,
Offset(-1, 0),
InsetPointInfo(_e, _n, _ne, Offset(0, 1)),
InsetPointInfo(_se, _s, _se, Offset(0, -1)),
),
// If no selection to the south, render a line along the bottom.
InsetInfo(
_s,
Offset(0, -1),
InsetPointInfo(_se, _e, _se, Offset(-1, 0)),
InsetPointInfo(_s, _w, _sw, Offset(1, 0)),
),
// If no selection to the west, render a line on the left side.
InsetInfo(
_w,
Offset(1, 0),
InsetPointInfo(_s, _s, _sw, Offset(0, -1)),
InsetPointInfo(_c, _n, _nw, Offset(0, 1)),
),
];
/// Gets a set of [Path]s to draw outlines around [cells].
///
/// If all [cells] are connected, only a single [Path] will be returned. If
/// [cells] contains multiple disconnected sets of cells, multiple [Path]s
/// will be returned.
Iterable<Path> getPaths(
BuiltSet<CellCoordinate> cells,
double size, {
double? insetDistance,
}) sync* {
// Build a `Map<CellCoordinate, List<CellCoordinate>>` where the key is a
// coordinate and the value is a list of any points it should be joined to.
//
// `CellCoordinate`s are used to indicate the top-left corner of that cell
// so a line from `cell` -> `cell.east` is a line along the top of `cell`
// (a segment from the top-left of `cell` to the top-left of `cell.east`).
final lineSegments = <Offset, List<Offset>>{};
for (var i = 0; i < cells.length; i++) {
final cell = cells.elementAt(i);
for (final info in _edgeInsetInfos) {
if (!cells.contains(info.edgeSelector(cell))) {
final startOffset = _computeInsetOffset(
cells,
cell,
insetDistance,
info,
info.start,
);
final endOffset = _computeInsetOffset(
cells,
cell,
insetDistance,
info,
info.end,
);
final startCorner = info.start.cornerSelector(cell);
final endCorner = info.end.cornerSelector(cell);
lineSegments
.putIfAbsent(startCorner.offset * size + startOffset, () => [])
.add(endCorner.offset * size + endOffset);
}
}
}
// Now, pick any starting point and follow the points until we run out.
// Remove each segment as it's processed and keep going until all gone.
// It's possible there are multiple unconnected paths, so pick a new
// starting point whenever we reach the end of an existing path.
while (lineSegments.isNotEmpty) {
// Pick a starting point for the path.
var point = lineSegments.keys.first;
final path = Path()..moveTo(point.dx, point.dy);
do {
// Select any of the points joined to from here.
final targets = lineSegments[point]!;
final nextPoint = targets.removeLast();
// If this was the last point from here, remove this from the list.
if (targets.isEmpty) lineSegments.remove(point);
point = nextPoint;
// Add this line segment to the path.
path.lineTo(point.dx, point.dy);
} while (lineSegments.containsKey(point));
// Yield the path and loop around if there are still other selections.
yield path;
}
}
/// Computes the offset for a point to inset the outline by [inset].
Offset _computeInsetOffset(
BuiltSet<CellCoordinate> cells,
CellCoordinate cell,
double? inset,
InsetInfo info,
InsetPointInfo pointInfo,
) {
if (inset == null) return Offset.zero;
final cell1 = pointInfo.cell1Selector(cell);
final cell2 = pointInfo.cell2Selector(cell);
final containsCell1 = cells.contains(cell1);
final containsCell2 = cells.contains(cell2);
// If cell1 + cell2 are selected, we need to decrease the offset by `inset`.
// If cell2 is not selected, we need to increase by `inset`.
// Otherwise, we don't move the offset and go to the edge of the cell (to
// meet up with the adjacent cells line segment).
final offset = containsCell1 && containsCell2
? -inset
: !containsCell1
? inset
: 0.0;
return pointInfo.multiplier * offset + info.offset * inset;
}
static CellCoordinate _c(CellCoordinate cell) => cell;
static CellCoordinate _e(CellCoordinate cell) => cell.east;
static CellCoordinate _n(CellCoordinate cell) => cell.north;
static CellCoordinate _ne(CellCoordinate cell) => cell.northEast;
static CellCoordinate _nw(CellCoordinate cell) => cell.northWest;
static CellCoordinate _s(CellCoordinate cell) => cell.south;
static CellCoordinate _se(CellCoordinate cell) => cell.southEast;
static CellCoordinate _sw(CellCoordinate cell) => cell.southWest;
static CellCoordinate _w(CellCoordinate cell) => cell.west;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment