图上的随机路径 - 设置长度，无交叉，无死角

Question

我正在开发一个 8 宽 5 高网格的游戏。我有一个 'snake' 功能，需要进入网格并 "walk" 周围设定距离（例如 20）。蛇的移动有一定的限制：

需要遍历预定的块数(20)
它不能越过自己或双回（无死角）

目前我正在使用随机深度优先搜索，但是我发现它偶尔会返回到自身（穿过它自己的路径）并且我不确定这是否是最好的方法。

考虑的选项：我已经考虑过使用 A*，但我正在努力寻找一种没有预定目标和上述条件的好方法。我还考虑过添加一个启发式方法来支持不在网格外部的块 - 但我不确定这些中的任何一个都可以解决手头的问题。

感谢任何帮助，如有必要，我可以添加更多详细信息或代码：

public List<GridNode> RandomizedDepthFirst(int distance, GridNode startNode)
{
    Stack<GridNode> frontier = new Stack<GridNode>();
    frontier.Push(startNode);
    List<GridNode> visited = new List<GridNode>();
    visited.Add(startNode);
    while (frontier.Count > 0 && visited.Count < distance)
    {
        GridNode current = frontier.Pop();

        if (current.nodeState != GridNode.NodeState.VISITED)
        {
            current.nodeState = GridNode.NodeState.VISITED;

            GridNode[] vals = current.FindNeighbours().ToArray();
            List<GridNode> neighbours = new List<GridNode>();
            foreach (GridNode g in vals.OrderBy(x => XMLReader.NextInt(0,0)))
            {
                neighbours.Add(g);
            }
            foreach (GridNode g in neighbours)
            {
                frontier.Push(g);
            }

            if (!visited.Contains(current))
            {
                visited.Add(current);
            }
        }

    }
    return visited;
}

Answer 1

考虑回溯的一种简单方法是使用递归 dfs 搜索。
考虑下图：

和java dfs 搜索的实现，在回溯时从路径中删除节点（注意评论。运行在线here）：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class Graph {

    //all graph nodes 
    private Node[] nodes;

    public Graph(int numberOfNodes) {

        nodes = new Node[numberOfNodes];
        //construct nodes
        for (int i = 0; i < numberOfNodes; i++) {
            nodes[i] = new Node(i);
        }
    }

    // add edge from a to b
    public Graph addEdge(int from, int to) {
        nodes[from].addNeighbor(nodes[to]);
        //unless unidirectional: //if a is connected to b
        //than b should be connected to a
        nodes[to].addNeighbor(nodes[from]);
        return this; //makes it convenient to add multiple edges
    }

    //returns a list of path size of pathLength.
    //if path not found : returns an empty list 
    public List<Node> dfs(int pathLength, int startNode) {

        List<Node> path = new ArrayList<>(); //a list to hold all nodes in path 
        Stack<Node> frontier = new Stack<>();
        frontier.push(nodes[startNode]);
        dfs(pathLength, frontier, path);
        return path;
    }

    private boolean dfs(int pathLength, Stack<Node> frontier, List<Node> path) {

        if(frontier.size() < 1) { 
            return false; //stack is empty, no path found 
        }

        Node current = frontier.pop();
        current.setVisited(true);
        path.add(current);

        if(path.size() == pathLength) {
            return true;  //path size of pathLength found 
        }

        System.out.println("testing node "+ current); //for testing 
        Collections.shuffle(current.getNeighbors());  //shuffle list of neighbours 
        for(Node node : current.getNeighbors()) {
            if(! node.isVisited()) {
                frontier.push(node);
                if(dfs(pathLength, frontier, path)) { //if solution found 
                    return true; //return true. continue otherwise  
                }
            }
        }
        //if all neighbours tested and no solution found, current node 
        //is not part of the path
        path.remove(current);      // remove it 
        current.setVisited(false); //this accounts for loops: you may get to this node 
                                   //from another edge
        return false;
    }

    public static void main(String[] args){

        Graph graph = new Graph(9); //make graph
        graph.addEdge(0, 4)  //add edges 
        .addEdge(0, 1)
        .addEdge(1, 2)
        .addEdge(1, 4)
        .addEdge(4, 3)
        .addEdge(2, 3)
        .addEdge(2, 5)
        .addEdge(3, 5)
        .addEdge(1, 6)
        .addEdge(6, 7)
        .addEdge(7, 8);

        //print path with length of 6, starting with node 1 
        System.out.println( graph.dfs(6,1));
    }
}

class Node {

    private int id;
    private boolean isVisited;
    private List<Node>neighbors;

    Node(int id){
        this.id = id;
        isVisited = false;
        neighbors = new ArrayList<>();
    }

    List<Node> getNeighbors(){
        return neighbors;
    }

    void addNeighbor(Node node) {
        neighbors.add(node);
    }

    boolean isVisited() {
        return isVisited;
    }

    void setVisited(boolean isVisited) {
        this.isVisited = isVisited;
    }

    @Override
    public String toString() {return String.valueOf(id);} //convenience 
}

输出：

testing node 1
testing node 6
testing node 7
testing node 8
testing node 2
testing node 5
testing node 3
testing node 4
[1, 2, 5, 3, 4, 0]

请注意，节点 6、7、8 是死胡同，已被测试，但未包含在最终路径中。

图上的随机路径 - 设置长度，无交叉，无死角

Randomised Path on graph - set length, no crossing, no dead ends

algorithm

graph

depth-first-search

path-finding