c# - 递归蛇寻路算法方法

Question

我目前正在尝试实现递归蛇形寻路算法。我试图做点什么，但出现了一个我发现很难解决的问题。问题是我的程序只搜索一次路径，并且由于未知原因它没有违背目的地，而是像这样提前一个位置:

*紫色是食物，绿色是蛇。之后它继续向右并刚好从控制台中出来。

“Grid”是一个二维 bool 数组，与控制台一样大，如果控制台上有类似蛇的一部分，则值为 true。

Direction 是一个包含 Up、Down、Left、Right 值的枚举。 Position 是一个包含两个称为 X 和 Y 的整数的结构。

ScheduledDirections 是一个包含方向的列表，将来会用于在控制台上绘制蛇。

我想做的是快速向该列表添加一条可用路径。我知道像 A* 这样的寻路算法，但我发现它太复杂且难以实现。

源代码:

private static void FindAvailablePath(Position currentPosition, Stack<Position> previousPositions, Direction currentDirection, Stack<Direction> previousDirections)
{
    // break if the snake's path search has ended or it went out of the console
    if (currentPosition.X < 0 || currentPosition.X >= Console.WindowWidth ||
        currentPosition.Y < 0 || currentPosition.Y >= Console.WindowHeight ||
        AIController.isReady)
    {
        return;
    }

    // break if there is something that is blocking the snake's path
    if (Snake.Grid[currentPosition.X, currentPosition.Y])
    {
        return;
    }

    // break if the snake has reached its destination
    if (currentPosition.Equals(AIController.Destination))
    {
        if (AIController.scheduledDirections == null || AIController.scheduledDirections.Count > previousDirections.Count + 1)
        {
            AIController.scheduledDirections = previousDirections.ToList();
            AIController.scheduledDirections.Add(currentDirection);
        }
        return;
    }

    // Break if previously visited
    if (previousPositions.Contains(currentPosition))
    {
        return;
    }


    // if the current path is available, adds it to the collection and checks for the next one
    if (!Snake.Grid[currentPosition.X, currentPosition.Y])
    {
        AIController.scheduledDirections.Add(currentDirection);

        previousPositions.Push(currentPosition);
        previousDirections.Push(currentDirection);

        if (AIController.Destination.X > currentPosition.X && !Snake.Grid[currentPosition.X + 1, currentPosition.Y])
        {
            FindAvailablePath(new Position(currentPosition.X + 1, currentPosition.Y), previousPositions, Direction.Right, previousDirections); // right
        }
        else if (AIController.Destination.Y < currentPosition.Y && !Snake.Grid[currentPosition.X, currentPosition.Y - 1])
        {
            FindAvailablePath(new Position(currentPosition.X, currentPosition.Y - 1), previousPositions, Direction.Up, previousDirections);    // up
        }
        else if (AIController.Destination.X < currentPosition.X && !Snake.Grid[currentPosition.X - 1, currentPosition.Y])
        {
            FindAvailablePath(new Position(currentPosition.X - 1, currentPosition.Y), previousPositions, Direction.Left, previousDirections);  // left
        }
        else if (AIController.Destination.Y > currentPosition.Y + 1 && !Snake.Grid[currentPosition.X, currentPosition.Y + 1])
        {
            FindAvailablePath(new Position(currentPosition.X, currentPosition.Y + 1), previousPositions, Direction.Down, previousDirections);  // down
        }

        previousPositions.Pop();
        previousDirections.Pop();
    }
}

谢谢!如果有人有任何更好的建议，我很乐意听取他们的意见!

Answer 1

如果我没理解错的话，你需要在迷宫中为蛇找到一条路径。

让我们假设它有无限长。然后，任务是在图中找到一条从蛇的初始位置到最终位置的路径

用 dfs 做它是个坏主意，因为它有 O(N!) 复杂度。 dfs 只是按字典顺序遍历所有路径。在许多情况下，它可以通过启发式方法得到改进，例如前往离目的地最近的点，但无论如何这对于此任务来说都是耗时的。

另一方面，bfs 使用 O(N)。

在c++中有一段代码，实现了递归算法和bfs。 c# 和 c++ 具有相似的语法。

    //<Just a code template>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stdlib.h>
#include<set>
#include<map>
#include<utility>
#include<time.h>
#include<queue>
#include<limits.h>
#include<bitset>
#include<deque>
using namespace std;
typedef vector<int>::iterator vit;
typedef string::iterator sit;
typedef vector<int>::reverse_iterator rvit;
typedef long long ll;
typedef long double ld;
//</Just a code template>

const int N=100;
bool Grid[N][N];

//Emulating your classes
struct TConsole
{
    int WindowWidth,WindowHeight;
    TConsole()
    {
        WindowWidth=WindowHeight=N;
    }
};
TConsole console;
struct Position
{
    int X,Y;
    bool Equals(Position other)
    {
        return X==other.X&&Y==other.Y;
    }
    Position(int _X=0, int _Y=0)
    {
        X=_X;
        Y=_Y;
    }
};

const int UP=0,DOWN=1,LEFT=2,RIGHT=3;
struct Direction 
{
    int cnt;
    Direction(int _cnt=0)
    {
        cnt=_cnt;
    }
    bool operator==(Direction other)
    {
        return cnt==other.cnt;
    }
    bool operator==(int other)
    {
        return cnt==other;
    }
};
Direction R=Direction(RIGHT);
Direction L=Direction(LEFT);
Direction U=Direction(UP);
Direction D=Direction(DOWN);
struct AI
{
    bool isReady;//What is it for?
    Position Destination;
    vector<Direction> scheduledDirections;
    AI()
    {
        isReady=false;
    }
};
AI AIController;

Direction prevdir[N][N];//Bfs stores for each cell destination with which it is entered
bool was[N][N];//if was[i][j] is 1, then the snake has visited position (i,j) in this branch of recursion in dfs case or just visited (bfs)
vector<Direction> path; // inversed path from start position to finish 

//function prototypes. To explain the compiler that their definition is somwhere below
bool dfs(Position pos, Direction dir);
void bfs(Position pos, Direction dir);

void calculate_schedules()
{
    //Restore the path from reversed and write it down
    reverse(path.begin(),path.end());
    for(vector<Direction>::iterator i=path.begin();i!=path.end();++i)
    {
        AIController.scheduledDirections.push_back(*i);
        printf("%d\n",*i);
    }
}
Position position_by_destination(Position initial, Direction d)//Returns a position to which snake comes, if it goes from position 'initial' in direction d
{
    if(d==U)
    {
        return Position(initial.X-1,initial.Y);
    }
    else if(d==D)
    {
        return Position(initial.X+1,initial.Y);
    }
    else if(d==R)
    {
        return Position(initial.X,initial.Y+1);
    }
    return Position(initial.X,initial.Y-1);
}
//Returns opposite to d direction
Direction get_inverse(Direction d)
{
    if(d==D)
        return U;
    else if(d==U)
        return D;
    else if(d==R)
        return L;
    return R;
}
//It starts from destination point and in each iteration 1)pushes the direction with which a current state was reached. 2)Goes to previous state
void bfs_path_restore(Position target,Position player)
{
    Position cpos=target;
    while(!(cpos.X==player.X&&cpos.Y==player.Y))
    {
        path.push_back(prevdir[cpos.X][cpos.Y]);
        cpos=position_by_destination(cpos,get_inverse(*(path.end()-1)));
    }
}
void FindAvailablePathBFS(Position currentPosition, Direction currentDirection)
{
    //The snake hasn't been anywhere
    memset(was,0,sizeof(was));
    path.clear();

    //Find path. 
    bfs(currentPosition,currentDirection);
    bfs_path_restore(AIController.Destination,currentPosition);

    printf("By BFS:\n");
    calculate_schedules();
}
void FindAvailablePathDFS(Position currentPosition, Direction currentDirection)
{
    //The snake doesn't know anything about the path, and hasn't visited anything but the starting point
    memset(was,0,sizeof(was));
    was[currentPosition.X][currentPosition.Y]=1;
    path.clear();

    //Find path. 
    dfs(currentPosition,currentDirection);

    printf("By DFS:\n");
    calculate_schedules();
}
int mabs(int x)// Abs function. The standard one tends to return double in some cases
{
    return x<0?-x:x;
}

//Positions' evaluation and comparsion function for their sorting based on it
int appraise_position(Position p)
{
    return mabs(p.X-AIController.Destination.X)+mabs(p.Y-AIController.Destination.Y);
}
bool heuristic_smaller(Position f, Position s)
{
    return appraise_position(f)<appraise_position(s);
}

//Returns direction of a snake when it goes from 'from' to 'to'.
Direction get_dir(Position from, Position to)
{
    if(to.X>from.X)
        return D;
    if(to.X<from.X)
        return U;
    if(to.Y>from.Y)
        return R;
    if(to.Y<from.Y)
        return L;
}

//Position pos is not in the console
bool out_of_bounds(Position pos)
{
    return pos.X<0||pos.Y<0||pos.X>console.WindowWidth||pos.Y>console.WindowHeight;
}
bool dfs(Position pos, Direction dir)//It returns true if managed to find position to the target with a state of was created by recursion
{

    if(out_of_bounds(pos))
        return false;

    //An obstacle
    if(Grid[pos.X][pos.Y])
        return false;

    //Got it
    if (pos.Equals(AIController.Destination))
        return true;

    //v contains all possible positions for the next step.
    vector<Position> v;

    v.push_back(Position(pos.X+1,pos.Y));
    v.push_back(Position(pos.X-1,pos.Y));
    v.push_back(Position(pos.X,pos.Y+1));
    v.push_back(Position(pos.X,pos.Y-1));

    //Evaluate them and process according to a result
    sort(v.begin(),v.end(),heuristic_smaller);
    for(vector<Position>::iterator i=v.begin();i!=v.end();++i)
    {
        //The snake was there in this branch
        if(was[i->X][i->Y])
            continue;
        Direction cdir=get_dir(pos,*i);
        if(cdir==get_inverse(dir))//This prevents the snake from turning inside out
        {
            continue;
        }

        //Go to next position and tell child branches that the snake was there
        was[i->X][i->Y]=1;
        if(dfs(*i,cdir))
        {
            path.push_back(cdir);
            return true;
        }
        //Return from position
        was[i->X][i->Y]=0;
    }
    return false;
}

//Processes a cell, finds closest ones to it and ads them to queue of procession. 
void bfs(Position pos, Direction dir)
{
    //Pathfinding starts from initial snake position
    queue<Position> qp;
    queue<Direction> qd;
    qp.push(pos);
    qd.push(dir);

    while(!qp.empty())
    {
        //Get current cell
        Position curpos=qp.front();
        Direction curdir=qd.front();

        //BFS processes cells in order of increasing distance from the first. Hence, if destination cell is found, it cannot be reached with less steps
        if(curpos.Equals(AIController.Destination))
        {
            qp=queue<Position>();
            qd=queue<Direction>();
            return;
        }

        //Find all neighbours
        vector<Position> v;

        v.push_back(Position(curpos.X+1,curpos.Y));
        v.push_back(Position(curpos.X-1,curpos.Y));
        v.push_back(Position(curpos.X,curpos.Y+1));
        v.push_back(Position(curpos.X,curpos.Y-1));

        for(vector<Position>::iterator i=v.begin();i!=v.end();++i)
        {
            //Check if a neighbour is acceptable
            if(out_of_bounds(*i))
                continue;

            if(was[i->X][i->Y])
                continue;

            if(Grid[i->X][i->Y])
                continue;

            Direction cdir=get_dir(curpos,*i);

            if(cdir==get_inverse(curdir))
                continue;

            //State that the way to the neighbour cell is found. Write destination with which the snake goes there to the corresponding prevdir. Add the cell to the queue
            was[i->X][i->Y]=1;
            prevdir[i->X][i->Y]=cdir;
            qp.push(*i);
            qd.push(cdir);
        }
        qp.pop();
        qd.pop();
    }
}

int main()
{
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);

    int n,m;
    scanf("%d%d",&n,&m);
    char a[N][N];
    Position player,target;
    for(int i=0;i<N;++i)//Never do like this
    {
        for(int j=0;j<N;++j)
        {
            Grid[i][j]=1;
        }
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
        {
            scanf("%c",&a[i][j]);
            if(a[i][j]=='\n')
            {
                --j;
                continue;
            }
            if(a[i][j]=='@')
                player=Position(i,j);
            else if(a[i][j]=='x')
                target=Position(i,j);
            if(a[i][j]!='*')
                Grid[i][j]=0;   
        }
    }
    AIController.Destination=target;
    FindAvailablePathDFS(player,D);
    FindAvailablePathBFS(player,D);
    return 0;
}

请注意，这是在假设路径存在的情况下进行的。此源从 test.in 文件中获取关卡图，其中 @ 表示蛇的初始位置，x - 目标点和 * - 障碍物前两个数字应该是字段的宽度和高度。字段示例:

7 7
.......
.......
..***.*
..*@*.*
..*...*
..*****
......x

---

让我们回到有限蛇。如果它的尾部已经不在那里，有限蛇可以访问同一个地方 X 两次。

有两种情况:

a) 蛇可以在 X 的第一次访问期间朝目的地移动。那么不这样做是没有意义的。

b) 蛇做不到。然后，为了向目标点移动，它必须相对于头部速度返回。然后蛇应该尝试找到到它的尾部的最长路径(转身并从 X 开始)，如果不可能，找到它的头部(在可访问的网格的一部分转身)，即 NP-hard

已经很晚了。我可能错过了什么/