如何将Quoridor游戏的N*N网格转换为邻接图以支撑BFS自动寻路

1. 现有代码问题修正 #

你当前的Graph和Node类存在职责混淆问题：Node仅需要存储自身坐标、四个方向的可通行状态，无需内置邻接表；Graph负责管理全量节点、处理网格到图的映射。
修正后的基础类参考实现：

// 方向枚举，对应南北东西四个方向，索引0-3
public enum Direction : int
{
    North = 0,
    South = 1,
    East = 2,
    West = 3
}

public class GridNode
{
    public int X { get; }
    public int Y { get; }
    // 长度为4的bool数组，对应四个方向是否可通行
    public bool[] Passable { get; } = new bool[4];

    public GridNode(int x, int y)
    {
        X = x;
        Y = y;
    }
}

public class GridGraph
{
    // 网格尺寸N*N
    public int N { get; }
    // 所有节点存储，按ID索引
    public GridNode[] Nodes { get; }
    // 坐标与ID的双向转换逻辑
    public int GetNodeId(int x, int y) => y * N + x;
    public (int x, int y) GetCoords(int id) => (id % N, id / N);

    public GridGraph(int n)
    {
        N = n;
        Nodes = new GridNode[n * n];
        // 初始化全量网格节点
        for (int y = 0; y < n; y++)
        {
            for (int x = 0; x < n; x++)
            {
                Nodes[GetNodeId(x, y)] = new GridNode(x, y);
            }
        }
    }
}

2. 邻接图刷新逻辑 #

每次棋盘状态更新（玩家放置/移除墙）后，调用以下方法刷新所有节点的可通行状态：

public void RefreshGraph(Board board, GridGraph graph)
{
    int N = graph.N;
    // 第一步：初始化默认可通行状态，排除网格边界
    for (int y = 0; y < N; y++)
    {
        for (int x = 0; x < N; x++)
        {
            var node = graph.Nodes[graph.GetNodeId(x, y)];
            node.Passable[(int)Direction.North] = y > 0;
            node.Passable[(int)Direction.South] = y < N - 1;
            node.Passable[(int)Direction.East] = x < N - 1;
            node.Passable[(int)Direction.West] = x > 0;
        }
    }

    // 第二步：处理横向墙
    // horizontal[y,x]为true代表y行x列位置有横向墙，阻断(x,y)和(x,y-1)的南北通行
    for (int y = 1; y < N; y++)
    {
        for (int x = 0; x < N; x++)
        {
            if (board.horizontal[y, x])
            {
                var upperNode = graph.Nodes[graph.GetNodeId(x, y-1)];
                var lowerNode = graph.Nodes[graph.GetNodeId(x, y)];
                upperNode.Passable[(int)Direction.South] = false;
                lowerNode.Passable[(int)Direction.North] = false;
            }
        }
    }

    // 第三步：处理纵向墙
    // vertical[y,x]为true代表y行x列位置有纵向墙，阻断(x,y)和(x-1,y)的东西通行
    for (int y = 0; y < N; y++)
    {
        for (int x = 1; x < N; x++)
        {
            if (board.vertical[y, x])
            {
                var leftNode = graph.Nodes[graph.GetNodeId(x-1, y)];
                var rightNode = graph.Nodes[graph.GetNodeId(x, y)];
                leftNode.Passable[(int)Direction.East] = false;
                rightNode.Passable[(int)Direction.West] = false;
            }
        }
    }
}

3. BFS对接方法 #

运行BFS时，获取某个节点的所有邻接可通行节点直接按以下逻辑实现即可：

public List<GridNode> GetNeighbors(GridGraph graph, GridNode node)
{
    var neighbors = new List<GridNode>();
    int x = node.X;
    int y = node.Y;
    if (node.Passable[(int)Direction.North])
        neighbors.Add(graph.Nodes[graph.GetNodeId(x, y-1)]);
    if (node.Passable[(int)Direction.South])
        neighbors.Add(graph.Nodes[graph.GetNodeId(x, y+1)]);
    if (node.Passable[(int)Direction.East])
        neighbors.Add(graph.Nodes[graph.GetNodeId(x+1, y)]);
    if (node.Passable[(int)Direction.West])
        neighbors.Add(graph.Nodes[graph.GetNodeId(x-1, y)]);
    return neighbors;
}

内容的提问来源于stack exchange，提问作者John Smith