c# - c# 广度优先搜索在迷宫中查找项目

Question

我要做一个游戏，机器人必须自动拾取物品。如果没有更多物品，游戏将结束。机器人应该使用广度优先搜索脚本搜索并转到项目。我试图用递归来做，但我的递归并没有结束。

class ComputerPlayer
{
    char[,] charMap;
    int rows, cols;
    Hashtable collectedItems = new Hashtable();
    Queue<Point> queue = new Queue<Point>();
    Stack<Point> wayback = new Stack<Point>();
    Form1 world;

    public ComputerPlayer(Form1 world, char[,] charMap, int rows, int cols)
    {
        this.rows = rows;
        this.cols = cols;
        this.charMap = charMap;
        this.world = world;
    }

    public void StartBFS()
    {
        if(SearchItem(new Point(GetPlayerPosCol(), GetPlayerPosRow()), new Point(GetPlayerPosCol(), GetPlayerPosRow())).X != -1)
        {
            while(wayback.Count > 0)
            {
                Point way = wayback.Pop();
                if(way.X > GetPlayerPosCol())
                {
                    world.MovePlayer(Form1.Direction.RIGHT);
                }
                if (way.X < GetPlayerPosCol())
                {
                    world.MovePlayer(Form1.Direction.LEFT);
                }
                if (way.Y > GetPlayerPosRow())
                {
                    world.MovePlayer(Form1.Direction.DOWN);
                }
                if (way.Y > GetPlayerPosRow())
                {
                    world.MovePlayer(Form1.Direction.UP);
                }
            }

        }
        else
        {
            Console.WriteLine("Finished");
        }
    }

    private Point SearchItem(Point coor, Point coorFrom)
    {

        try
        {
            if(charMap[coor.X, coor.Y] == '.')
            {
                Console.WriteLine("found one");
                collectedItems.Add(coor, coorFrom);
                wayback.Push(coor);
                do
                {
                    wayback.Push((Point)collectedItems[coor]);
                    coor = (Point)collectedItems[coor];
                }
                while (!collectedItems[coor].Equals(coor));

                return coor;

            }
            if(charMap[coor.X, coor.Y] == '@')
            {
                Console.WriteLine("player");
                if (charMap[coor.X + 1, coor.Y] != '#')
                {
                    return SearchItem(new Point(coor.X + 1, coor.Y), coor);
                }
                if (charMap[coor.X - 1, coor.Y] != '#')
                {
                    return SearchItem(new Point(coor.X - 1, coor.Y), coor);
                }
                if (charMap[coor.X, coor.Y + 1] != '#')
                {
                    return SearchItem(new Point(coor.X, coor.Y + 1), coor);
                }
                if (charMap[coor.X, coor.Y - 1] != '#')
                {
                    return SearchItem(new Point(coor.X, coor.Y - 1), coor);
                }
            }
        }
        catch
        {
            Console.WriteLine("catching");
            if(charMap[coor.X + 1, coor.Y] != '#')
            {
                return SearchItem(new Point(coor.X + 1, coor.Y), coor);
            }
            if (charMap[coor.X - 1, coor.Y] != '#')
            {
                return SearchItem(new Point(coor.X - 1, coor.Y), coor);
            }
            if (charMap[coor.X, coor.Y + 1] != '#')
            {
                return SearchItem(new Point(coor.X, coor.Y + 1), coor);
            }
            if (charMap[coor.X, coor.Y - 1] != '#')
            {
                return SearchItem(new Point(coor.X, coor.Y - 1), coor);
            }
        }
        return new Point(-1, -1);
    }



    private int GetPlayerPosCol()
    {
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                switch (charMap[j, i])
                {
                    case '@':
                        return j;
                        break;
                    default:
                        break;
                }
            }
        }
        return 0;
    }

    private int GetPlayerPosRow()
    {
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                switch (charMap[j, i])
                {
                    case '@':
                        return i;
                        break;
                    default:
                        break;
                }
            }
        }
        return 0;
    }
}

“#”表示墙，“.” 表示物品，“@”表示玩家。为什么它不起作用？某人可以帮助我吗？先感谢您！

lg bttl

标签： c#breadth-first-search

Answer 1

我做了一些不同的事情，但现在 ComputerPlayer 拿起第一个项目然后卡住了。它只找到 2 个字段，其中什么都没有，但通常它应该找到更多。怎么了？

class ComputerPlayer
{
    char[,] charMap;
    int rows, cols;
    Hashtable visitedFields = new Hashtable();
    Queue<Point> queue = new Queue<Point>();
    Stack<Point> wayback = new Stack<Point>();
    Form1 world;

    public ComputerPlayer(Form1 world, char[,] charMap, int rows, int cols)
    {
        this.rows = rows;
        this.cols = cols;
        this.charMap = charMap;
        this.world = world;
    }

    public void StartBFS()
    {
        Timer t1 = new Timer();
            t1.Interval = 1000;
            t1.Tick += new EventHandler(T1_Tick);
        t1.Start();
        Console.WriteLine("started");
    }

    private void T1_Tick(object sender, EventArgs e)
    {
        Console.WriteLine("tick");
        SearchItem(new Point(GetPlayerPosCol(), GetPlayerPosRow()), new Point(GetPlayerPosCol(), GetPlayerPosRow()));
        Console.WriteLine(queue.Count);
        while(queue.Count > 0)
        {
            Point pointer = queue.Dequeue();
            if(charMap[pointer.X,pointer.Y] == '.')
            {
                Point coor = pointer;
                do
                {
                    wayback.Push(coor);
                    coor = (Point)visitedFields[coor];
                }
                while (!visitedFields[coor].Equals(coor));

                while(wayback.Count > 0)
                {
                    Point way = wayback.Pop();
                    if(way.X > GetPlayerPosCol())
                    {
                        world.MovePlayer(Form1.Direction.RIGHT);
                    }
                    if (way.X < GetPlayerPosCol())
                    {
                        world.MovePlayer(Form1.Direction.LEFT);
                    }
                    if (way.Y > GetPlayerPosRow())
                    {
                        world.MovePlayer(Form1.Direction.DOWN);
                    }
                    if (way.Y > GetPlayerPosRow())
                    {
                        world.MovePlayer(Form1.Direction.UP);
                    }
                }
                world.UptdateMap();
            }
        }
        visitedFields.Clear();
        queue.Clear();
        wayback.Clear();
    }

    private Point SearchItem(Point coor, Point coorFrom)
    {

        try
        {
            visitedFields.Add(coor, coorFrom);
            Console.WriteLine("found field");
            queue.Enqueue(coor);
            if (charMap[coor.X + 1, coor.Y] != '#')
            {
                return SearchItem(new Point(coor.X + 1, coor.Y), coor);
            }
            if (charMap[coor.X - 1, coor.Y] != '#')
            {
                return SearchItem(new Point(coor.X - 1, coor.Y), coor);
            }
            if (charMap[coor.X, coor.Y + 1] != '#')
            {
                return SearchItem(new Point(coor.X, coor.Y + 1), coor);
            }
            if (charMap[coor.X, coor.Y - 1] != '#')
            {
                return SearchItem(new Point(coor.X, coor.Y - 1), coor);
            }
        }
        catch
        {

        }
        return new Point(-1, -1);
    }



    private int GetPlayerPosCol()
    {
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                switch (charMap[j, i])
                {
                    case '@':
                        return j;
                        break;
                    default:
                        break;
                }
            }
        }
        return 0;
    }

    private int GetPlayerPosRow()
    {
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                switch (charMap[j, i])
                {
                    case '@':
                        return i;
                        break;
                    default:
                        break;
                }
            }
        }
        return 0;
    }

    public void SetCharMap(char[,] charMap)
    {
        this.charMap = charMap;
    }
}