dfspathfinder.cs

两种AstarPathFinder 一种DijkstraPathfinder BFS

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

namespace PathFinder
{
    class DFSPathFinder : 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 byte[,] ispassed;
        private int bestcost = 0x7fffffff;
        private double deep;

        public DFSPathFinder(Map myMap)
        {
            currentMap = myMap;
            this.costs = new int[currentMap.Width, currentMap.Height];
            this.predecessor = new byte[currentMap.Width, currentMap.Height];
            ispassed = new byte[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 void DFSVisit(Point point1,Point destination)
        {
            ispassed[point1.X, point1.Y] = 1;
            if (destination == point1)
            {
                if (bestcost > costs[destination.X, destination.Y])
                {
                    bestcost = costs[destination.X, destination.Y];
                }
                return;
            }
            deep += 1;
            if(deep>=40000) 
            {
                Console.Write("nothing");
            }
            for (byte num = 0; num < moves.Length;num++ )
            {
                Point point2 = new Point(point1.X + moves[num].X, point1.Y + moves[num].Y);
                if (currentMap.isIn(point2)&&ispassed[point2.X, point2.Y]==0)
                {
                    predecessor[point2.X, point2.Y] = num;
                    costs[point2.X, point2.Y] = costs[point1.X, point1.Y] + currentMap.map[point1.X, point1.Y];
                    DFSVisit(point2,destination);
                }
            }
            deep -= 1;
            ispassed[point1.X, point1.Y] = 2;
            return;

        }

        public override Stack<Point> FindWay(Point source, Point destination)
        {
            costs[source.X, source.Y] = 0;
            Point point;
            Stack<Point> spreadPoints = new Stack<Point>();
            spreadPoints.Push(source);
            Stack<Point> stack = new Stack<Point>();
           // DFSVisit(source,destination);

            #region  非递归
            while (spreadPoints.Count > 0)
            {
                point = spreadPoints.Pop();
                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]==0)
                        {
                            spreadPoints.Push(point2);
                            predecessor[point2.X, point2.Y] = num;
                        }
                    }
                }
                ispassed[point.X, point.Y] = 1;
            }
            #endregion
            return stack;
        }
    }
}