1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
namespace Godosa.Core.Runs;
/// <summary>Route planning for run scripts (docs/notes/run-scripts-routing.md): a way over a grid (8 neighbours) cut into
/// the legs the game's own router accepts, the script seals that close a way, and portal hops between walkable areas. Pure;
/// the game passes its grid, its router's acceptance test and its portals.</summary>
public static class RouteLegs
{
/// <summary>Breadth-first over <c>[0,width)×[0,height)</c>, 8 neighbours, until <paramref name="goal"/>: each reached
/// cell → the one it was reached from (start → itself).</summary>
public static Dictionary<(long X, long Y), (long X, long Y)> Reach((long X, long Y) start, (long X, long Y) goal, long width, long height,
Func<long, long, bool> blocked)
{
var from = new Dictionary<(long X, long Y), (long X, long Y)> { [start] = start };
var queue = new Queue<(long X, long Y)>([start]);
while (queue.Count > 0 && !from.ContainsKey(goal))
{
var at = queue.Dequeue();
for (var dx = -1; dx <= 1; dx++)
for (var dy = -1; dy <= 1; dy++)
{
var next = (at.X + dx, at.Y + dy);
if (from.ContainsKey(next) || next.Item1 < 0 || next.Item2 < 0 || next.Item1 >= width || next.Item2 >= height
|| blocked(next.Item1, next.Item2))
continue;
from[next] = at;
queue.Enqueue(next);
}
}
return from;
}
/// <summary>The cells from <paramref name="start"/> (excluded) to <paramref name="goal"/> (included); null when walled
/// off.</summary>
public static List<(long X, long Y)>? Path((long X, long Y) start, (long X, long Y) goal, long width, long height, Func<long, long, bool> blocked)
{
var from = Reach(start, goal, width, height, blocked);
return from.ContainsKey(goal) ? Trace(from, start, goal) : null;
}
/// <summary>Legs along <paramref name="path"/>: from each stop the farthest path cell <paramref name="accepts"/> (the
/// game's router takes the trip), until the goal; null when the router takes no further cell from a stop.</summary>
public static List<(long X, long Y)>? Legs((long X, long Y) start, IReadOnlyList<(long X, long Y)> path,
Func<(long X, long Y), (long X, long Y), bool> accepts) => Legs(start, path, accepts, out _);
/// <inheritdoc cref="Legs(ValueTuple{long, long}, IReadOnlyList{ValueTuple{long, long}}, Func{ValueTuple{long, long}, ValueTuple{long, long}, bool})"/>
/// <param name="stuck">The stop no leg leaves (refusals name it).</param>
public static List<(long X, long Y)>? Legs((long X, long Y) start, IReadOnlyList<(long X, long Y)> path,
Func<(long X, long Y), (long X, long Y), bool> accepts, out (long X, long Y) stuck)
{
var legs = new List<(long X, long Y)>();
var (stop, index) = (start, 0);
while (index < path.Count)
{
var best = path.Count - 1;
while (best >= index && !accepts(stop, path[best]))
best--;
if (best < index)
{
stuck = stop;
return null;
}
(stop, index) = (path[best], best + 1);
legs.Add(stop);
}
stuck = default;
return legs;
}
/// <summary>The <paramref name="soft"/> cells (blocked by the game's scripts, opened later) the way would cross once
/// open, start to goal, at most <paramref name="max"/>; empty when walled off anyway or open already.</summary>
public static List<(long X, long Y)> Seals((long X, long Y) start, (long X, long Y) goal, long width, long height,
Func<long, long, bool> blocked, Func<long, long, bool> soft, int max = 8)
{
if (Path(start, goal, width, height, blocked) != null)
return [];
var way = Path(start, goal, width, height, (x, y) => blocked(x, y) && !soft(x, y));
return way == null ? [] : way.Where(c => soft(c.X, c.Y)).Take(max).ToList();
}
/// <summary>Portal hops: breadth-first over portal exits from <paramref name="start"/>; the portals to take, in order, so
/// that <paramref name="reaches"/> (a walk inside one area) gets to <paramref name="goal"/>; empty when it walks there;
/// null when no chain does.</summary>
public static List<TPortal>? Hops<TPos, TPortal>(TPos start, TPos goal, IReadOnlyList<TPortal> portals, Func<TPortal, TPos> at,
Func<TPortal, TPos> exit, Func<TPos, TPos, bool> reaches) where TPos : notnull
{
var via = new Dictionary<TPos, (TPos From, TPortal? Portal)> { [start] = (start, default) };
var queue = new Queue<TPos>([start]);
while (queue.Count > 0)
{
var here = queue.Dequeue();
if (reaches(here, goal))
{
var hops = new List<TPortal>();
for (var p = here; !EqualityComparer<TPos>.Default.Equals(p, start); p = via[p].From)
hops.Add(via[p].Portal!);
hops.Reverse();
return hops;
}
foreach (var portal in portals)
if (!via.ContainsKey(exit(portal)) && reaches(here, at(portal)))
{
via[exit(portal)] = (here, portal);
queue.Enqueue(exit(portal));
}
}
return null;
}
private static List<(long X, long Y)> Trace(Dictionary<(long X, long Y), (long X, long Y)> from, (long X, long Y) start, (long X, long Y) goal)
{
var path = new List<(long X, long Y)>();
for (var c = goal; c != start; c = from[c])
path.Add(c);
path.Reverse();
return path;
}
}
|
