N*M矩阵指定长度随机路径生成算法优化问询

需求明确 #

现有NM规模矩阵，需从随机起点生成长度固定（小于NM）的随机路径，终点无要求。已实现函数getRandomNeighbor(Point x)，返回当前节点的随机可用邻居；若周围无可用邻居，则返回空值（陷入停滞）。

当前实现的问题 #

现有代码采用盲目随机重试逻辑：一旦路径生成中途陷入停滞，就直接清空所有进度、重新选起点从头再来。这种方式存在明显缺陷：

• 路径越长、矩阵越复杂，失败概率越高，反复重试会浪费大量计算资源
• 完全没有回溯机制，只要某一步走死就前功尽弃，效率极低

优化方案 #

方案1：回溯式随机路径生成

核心思路是走不通就往回退，回到上一个节点尝试其他未走过的邻居，而非直接放弃整个路径。

实现步骤：

• 用栈存储路径节点，方便回溯操作
• 每次从当前节点获取随机邻居时，排除已在路径中的节点
• 找到有效邻居就继续前进，没找到就回溯到上一个节点
• 直到路径长度达标，或确认当前起点无法生成目标长度路径时，再换起点重新尝试

示例代码：

private HashSet<Vector2> GeneratePath()
{
    // 先算出需要的路径总长度：起点1个节点 + 所有单词的非空格字符数
    int targetLength = 1;
    foreach (Word word in RingsGameManager.Instance.wordsToUse)
    {
        targetLength += word.word.Replace(" ", "").Length;
    }

    while (!stopGenerating)
    {
        // 随机挑选起点
        int randXIndex = Random.Range(0, board.Count);
        int randYIndex = Random.Range(0, board[randXIndex].Count);
        Vector2 start = new Vector2(randXIndex, randYIndex);
        
        Stack<Vector2> pathStack = new Stack<Vector2>();
        HashSet<Vector2> visited = new HashSet<Vector2>();
        pathStack.Push(start);
        visited.Add(start);
        
        bool pathCompleted = false;
        while (pathStack.Count < targetLength && !stopGenerating)
        {
            Vector2 current = pathStack.Peek();
            Vector2 next = GetValidUnvisitedNeighbor(current, visited);
            
            if (next != null)
            {
                pathStack.Push(next);
                visited.Add(next);
            }
            else
            {
                // 当前节点无路可走，回溯一步
                if (pathStack.Count <= 1)
                {
                    // 起点也没其他路了，直接换起点
                    break;
                }
                visited.Remove(pathStack.Pop());
            }
        }
        
        if (pathStack.Count == targetLength)
        {
            return new HashSet<Vector2>(pathStack);
        }
    }
    return null;
}

// 封装：获取未被访问过的随机邻居
private Vector2 GetValidUnvisitedNeighbor(Vector2 current, HashSet<Vector2> visited)
{
    Vector2 neighbor = getRandomNeighbor(current);
    int maxAttempts = 4; // 最多尝试4次（对应上下左右四个方向）
    int attempts = 0;
    
    // 循环找未访问的邻居，直到找到或确认没有
    while (neighbor != null && visited.Contains(neighbor) && attempts < maxAttempts)
    {
        neighbor = getRandomNeighbor(current);
        attempts++;
    }
    
    return visited.Contains(neighbor) ? null : neighbor;
}

方案2：提前筛选合格起点

在选起点前，先判断该起点所在的连通分量大小是否≥目标路径长度：

• 用BFS/DFS快速统计起点能到达的所有节点总数
• 如果连通分量不足目标长度，直接跳过这个起点，不用浪费时间尝试

这一步能提前排除不可能生成有效路径的起点，进一步减少无效尝试。

方案3：减少重复初始化开销

现有代码每次失败都完全清空路径、重新创建集合。可以改为：

• 复用已有的集合对象，失败时仅清除内容而非重新实例化
• 用字典记录每个节点已经尝试过的邻居，回溯时跳过这些已尝试的选项，避免重复走同一条死路

优化后优势 #

• 回溯机制大幅降低无效重试次数，路径越长优化效果越明显
• 提前筛选起点进一步提升生成效率
• 减少不必要的对象创建和销毁，降低资源消耗

内容的提问来源于stack exchange，提问作者Khalil Al-abadlih