bfspathfinder.cs

两种AstarPathFinder 一种DijkstraPathfinder BFS

using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;

namespace PathFinder
{
    class BFSPathFinder:PathFinder
    {
        private Map currentMap;
        private int[,] costs;
        private Point[] moves = new Point[] { new Point(0, 1), new Point(1, 0), new Point(0, -1), new Point(-1, 0) };
        private byte[,] predecessor;
        private bool[,] ispassed;

        public BFSPathFinder(Map myMap)
        {
            currentMap = myMap;
            this.costs = new int[currentMap.Width, currentMap.Height];
            this.predecessor = new byte[currentMap.Width, currentMap.Height];
            ispassed = new bool[currentMap.Width, currentMap.Height];
            for (int i = 0; i < currentMap.Width; i++)
            {
                for (int j = 0; j < currentMap.Height; j++)
                {
                    predecessor[i, j] = 5;
                    costs[i, j] = 0x7fffffff;
                }
            }
            
        }

        public override Stack<Point> FindWay(Point source, Point destination)
        {
            costs[source.X, source.Y] = 0;
            Point point;
            Queue<Point> spreadPoints = new Queue<Point>();
            spreadPoints.Enqueue(source);
            ispassed[source.X, source.Y] = true;
            Stack<Point> stack = new Stack<Point>();

            while(spreadPoints.Count>0)
            {
                point = spreadPoints.Dequeue();
                if (point == destination)
                {

                    Point item = destination;
                    byte num8;
                    while ((num8 = this.predecessor[item.X, item.Y]) < 4)
                    {
                        stack.Push(item);
                        item.X -= moves[num8].X;
                        item.Y -= moves[num8].Y;
                        if (item == source)
                        {
                            Console.Write("Reached");
                        }

                    }
                    break;
                }

                for (byte num = 0; num < moves.Length; num++)
                {
                    Point point2 = new Point(point.X + moves[num].X, point.Y + moves[num].Y);
                    if (currentMap.isIn(point2))
                    {

                        if (!ispassed[point2.X, point2.Y])
                        {
                            spreadPoints.Enqueue(point2);
                            costs[point2.X, point2.Y] = costs[point.X, point.Y] + currentMap.map[point.X, point.Y];
                            predecessor[point2.X, point2.Y] = num;
                            ispassed[point2.X, point2.Y] = true;
                        }
                     
                    }
                 
                }
            }
            return stack;
        }
    }
}