GridRouter.cs

using System.Collections.Generic;
using UnityEngine;

// Grid router for Unity: finds up to N non-crossing Manhattan paths on an XxY grid
// Uses BFS (Lee/wave) with randomized neighbor order and retries (rip-up & reroute style)
// Designed to be easy to drop into a Unity project. No scene dependencies.

public static class GridRouter
{
    public struct MultiRouteResult
    {
        public bool success;
        public List<List<Vector2Int>> paths; // all routed paths
    }

    public static MultiRouteResult RouteManyPaths(int width, int height,
                                                  List<Vector2Int> starts,
                                                  List<Vector2Int> ends,
                                                  int maxAttempts = 500, int seed = -1)
    {
        var rng = (seed < 0) ? new System.Random() : new System.Random(seed);

        if (starts.Count != ends.Count || starts.Count == 0 || starts.Count > 16)
            return new MultiRouteResult { success = false };

        int n = starts.Count;

        for (int i = 0; i < n; i++)
        {
            if (!InBounds(starts[i], width, height) || !InBounds(ends[i], width, height))
                return new MultiRouteResult { success = false };

            for (int j = i + 1; j < n; j++)
            {
                if (starts[i] == starts[j] || starts[i] == ends[j] || ends[i] == starts[j] || ends[i] == ends[j])
                    return new MultiRouteResult { success = false };
            }
        }

        for (int attempt = 0; attempt < maxAttempts; attempt++)
        {
            bool[,] blocked = new bool[width, height];
            var allPaths = new List<List<Vector2Int>>();

            var order = new List<int>();
            for (int i = 0; i < n; i++) order.Add(i);
            for (int i = n - 1; i > 0; i--)
            {
                int j = rng.Next(i + 1);
                int tmp = order[i];
                order[i] = order[j];
                order[j] = tmp;
            }

            bool failed = false;
            foreach (int idx in order)
            {
                var perm = RandomizedDirections(rng);
                var path = BFSPath(width, height, starts[idx], ends[idx], blocked, perm);
                if (path == null)
                {
                    failed = true;
                    break;
                }
                allPaths.Add(path);
                foreach (var p in path) blocked[p.x, p.y] = true;
            }

            if (!failed && allPaths.Count == n)
            {
                return new MultiRouteResult { success = true, paths = allPaths };
            }
        }

        return new MultiRouteResult { success = false };
    }

    private static List<Vector2Int> BFSPath(int width, int height, Vector2Int start, Vector2Int goal, bool[,] blocked, Vector2Int[] dirs)
    {
        if (start == goal) return new List<Vector2Int> { start };
        if (blocked[start.x, start.y] || blocked[goal.x, goal.y]) return null;

        var q = new Queue<Vector2Int>();
        q.Enqueue(start);

        var visited = new bool[width, height];
        visited[start.x, start.y] = true;

        var parent = new Vector2Int?[width * height];

        while (q.Count > 0)
        {
            var cur = q.Dequeue();
            foreach (var d in dirs)
            {
                var nb = new Vector2Int(cur.x + d.x, cur.y + d.y);
                if (!InBounds(nb, width, height)) continue;
                if (visited[nb.x, nb.y]) continue;
                if (blocked[nb.x, nb.y]) continue;

                visited[nb.x, nb.y] = true;
                parent[nb.x + nb.y * width] = cur;

                if (nb == goal)
                {
                    var path = new List<Vector2Int>();
                    var p = nb;
                    while (true)
                    {
                        path.Add(p);
                        if (p == start) break;
                        p = parent[p.x + p.y * width].Value;
                    }
                    path.Reverse();
                    return path;
                }

                q.Enqueue(nb);
            }
        }

        return null;
    }

    private static bool InBounds(Vector2Int v, int width, int height)
    {
        return v.x >= 0 && v.x < width && v.y >= 0 && v.y < height;
    }

    private static Vector2Int[] RandomizedDirections(System.Random rng)
    {
        var baseDirs = new List<Vector2Int> {
            Vector2Int.up, Vector2Int.down, Vector2Int.left, Vector2Int.right
        };
        for (int i = baseDirs.Count - 1; i > 0; i--)
        {
            int j = rng.Next(i + 1);
            var tmp = baseDirs[i];
            baseDirs[i] = baseDirs[j];
            baseDirs[j] = tmp;
        }
        return baseDirs.ToArray();
    }
}