godosa-engine: initial public history

1 files changed, 117 insertions, 0 deletions

diff --git a/src/Godosa.Core/Runs/RouteLegs.cs b/src/Godosa.Core/Runs/RouteLegs.cs
new file mode 100644
index 0000000..e02b7c3
--- /dev/null
+++ b/src/Godosa.Core/Runs/RouteLegs.cs
@@ -0,0 +1,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;
+    }
+}