dijkstrapathfinder.cs

两种AstarPathFinder 一种DijkstraPathfinder BFS

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

namespace PathFinder
{
    class DijkstraPathFinder:PathFinder
    {
        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 Map currentMap;

        public DijkstraPathFinder(Map myMap)
        {
            currentMap = myMap;
            this.costs = new int[currentMap.Width, currentMap.Height];
            this.predecessor = new byte[currentMap.Width, currentMap.Height];
        }

        public override Stack<Point>  FindWay(Point origin, Point destination)
        {
            int num;
            List<Point>[] listArray = new List<Point>[4];
            for (num = 0; num < 4; num++)
            {
                listArray[num] = new List<Point>();
            }
            num = 0;
            while (num < currentMap.Width)
            {
                for (int i = 0; i < currentMap.Height; i++)
                {
                    this.predecessor[num, i] = 5;
                    this.costs[num, i] = 0x7fffffff;
                }
                num++;
            }
            int num3 = 1;
            listArray[0].Add(origin);
            this.costs[origin.X, origin.Y] = 0;
            while (num3 > 0)
            {
                while (listArray[0].Count == 0)
                {
                    List<Point> list = listArray[0];
                    num = 0;
                    while (num < 3)
                    {
                        listArray[num] = listArray[num + 1];
                        num++;
                    }
                    listArray[3] = list;
                }
                Point point = (Point)listArray[0][listArray[0].Count - 1];
                int num4 = this.costs[point.X, point.Y];
                listArray[0].RemoveAt(listArray[0].Count - 1);
                num3--;
                if (point.Equals(destination))
                {
                    break;
                }
                for (num = 0; num < moves.Length; num++)
                {
                    Point point2 = new Point(point.X + moves[num].X, point.Y + moves[num].Y);
                    if (currentMap.isIn(point2))
                    {
                        int num5;
                        switch (currentMap.map[point2.X, point2.Y])
                        {
                            case 1:
                                num5 = 1;
                                break;

                            case 2:
                                num5 = 2;
                                break;

                            case 3:
                                num5 = 3;
                                break;

                            default:
                                num5 = 0x7fffffff;
                                break;
                        }
                        if (num5 != 0x7fffffff)
                        {
                            int num6 = this.costs[point2.X, point2.Y];
                            if (num6 > (num4 + num5))
                            {
                                if (num6 != 0x7fffffff)
                                {
                                    int index = listArray[num6 - num4].IndexOf(point2);
                                    if (index != -1)
                                    {
                                        listArray[num6 - num4].RemoveAt(index);
                                        num3--;
                                    }
                                }
                                this.costs[point2.X, point2.Y] = num4 + num5;
                                this.predecessor[point2.X, point2.Y] = (byte)num;
                                listArray[num5].Add(point2);
                                num3++;
                            }
                        }
                    }
                }
            }
            Stack<Point> stack = new Stack<Point>();
            Point item = destination;
            try
            {
                byte num8;
                while ((num8 = this.predecessor[item.X, item.Y]) <= 4)
                {
                    stack.Push(item);
                    item.X -= moves[num8].X;
                    item.Y -= moves[num8].Y;
                }
            }
            catch
            {
                stack.Clear();
            }

            //if ((origin != destination) && (predecessor[destination.X, destination.Y] < 5))
            //{
            //    byte num8;
            //    while ((num8 = this.predecessor[item.X, item.Y]) <= 4)
            //    {
            //        stack.Push(item);
            //        item.X -= moves[num8].X;
            //        item.Y -= moves[num8].Y;
            //    }
            //}

            return stack;
        }

        public Stack<Point> ListfindWay(Point origin, Point destination)
        {
            int num;
            List<Point>[] listArray = new List<Point>[4];
            for (num = 0; num < 4; num++)
            {
                listArray[num] = new List<Point>();
            }
            num = 0;
            while (num < currentMap.Width)
            {
                for (int i = 0; i < currentMap.Height; i++)
                {
                    this.predecessor[num, i] = 5;
                    this.costs[num, i] = 0x7fffffff;
                }
                num++;
            }
            int num3 = 1;
            listArray[0].Add(origin);
            this.costs[origin.X, origin.Y] = 0;
            while (num3 > 0)
            {
                while (listArray[0].Count == 0)
                {
                    List<Point> list = listArray[0];
                    num = 0;
                    while (num < 3)
                    {
                        listArray[num] = listArray[num + 1];
                        num++;
                    }
                    listArray[3] = list;
                }
                Point point = (Point)listArray[0][listArray[0].Count - 1];
                int num4 = this.costs[point.X, point.Y];
                listArray[0].RemoveAt(listArray[0].Count - 1);
                num3--;
                if (point.Equals(destination))
                {
                    break;
                }
                for (num = 0; num < moves.Length; num++)
                {
                    Point point2 = new Point(point.X + moves[num].X, point.Y + moves[num].Y);
                    if (currentMap.isIn(point2))
                    {
                        int num5;
                        switch (currentMap.map[point2.X, point2.Y])
                        {
                            case 1:
                                num5 = 1;
                                break;

                            case 2:
                                num5 = 2;
                                break;

                            case 3:
                                num5 = 3;
                                break;

                            default:
                                num5 = 0x7fffffff;
                                break;
                        }
                        if (num5 != 0x7fffffff)
                        {
                            int num6 = this.costs[point2.X, point2.Y];
                            if (num6 > (num4 + num5))
                            {
                                if (num6 != 0x7fffffff)
                                {
                                    int index = listArray[num6 - num4].IndexOf(point2);
                                    if (index != -1)
                                    {
                                        listArray[num6 - num4].RemoveAt(index);
                                        num3--;
                                    }
                                }
                                this.costs[point2.X, point2.Y] = num4 + num5;
                                this.predecessor[point2.X, point2.Y] = (byte)num;
                                listArray[num5].Add(point2);
                                num3++;
                            }
                        }
                    }
                }
            }
            Stack<Point> stack = new Stack<Point>();
            Point item = destination;
            try
            {
                byte num8;
                while ((num8 = this.predecessor[item.X, item.Y]) <= 4)
                {
                    stack.Push(item);
                    item.X -= moves[num8].X;
                    item.Y -= moves[num8].Y;
                }
            }
            catch
            {
                stack.Clear();
            }

            //if ((origin != destination) && (predecessor[destination.X, destination.Y] < 5))
            //{
            //    byte num8;
            //    while ((num8 = this.predecessor[item.X, item.Y]) <= 4)
            //    {
            //        stack.Push(item);
            //        item.X -= moves[num8].X;
            //        item.Y -= moves[num8].Y;
            //    }
            //}

            return stack;
        }
    }
}