Рандомизированный путь на графике - установить длину, без пересечения, без тупиков

Question

Я работаю над игрой с сеткой 8 х 5. У меня есть функция «змея», которая должна войти в сетку и «ходить» вокруг на заданное расстояние (например, 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, удаляющего узлы из пути при возврате (обратите внимание на комментарии. Запустите его онлайн здесь ):

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, которые являются тупиковыми, тестируются, но не включаются в окончательный путь.