jcminqueue.cs

两种AstarPathFinder 一种DijkstraPathfinder BFS

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

namespace PathFinder
{
        class JCMinQueue
        {
            public JCMinQueue(Map myMap)
            {
                InQueue = new int[myMap.Width,myMap.Height];
            }

            public int[,] InQueue; 
            private List<JCAstarNode> FList = new List<JCAstarNode>();

            public int Count
            {
                get { return FList.Count; }
            }

            public JCAstarNode this[int Index]
            {
                get
                {
                    if (Index >= FList.Count || Index < 0)
                        throw new ArgumentOutOfRangeException("Index is less than zero or Index is greater than Count.");
                    return FList[Index];
                }
                set
                {
                    FList[Index] = value;
                }
            }

            #region  最小优先队列的相关操作
            public void Min_Heapify(int i)
            {
                //int l = Left(i), r = Right(i), smallest = i;
                int l = 2 * i, r = 2 * i + 1, smallest = i;
                if (l < FList.Count && FList[l].FTotalCost < FList[smallest].FTotalCost)
                    smallest = l;
                if (r < FList.Count && FList[r].FTotalCost < FList[smallest].FTotalCost)
                    smallest = r;
                if (smallest != i)
                {
                    Swap(i, smallest);
                    Min_Heapify(smallest);  //递归调用从上至下修复最大堆
                }

            }

            public JCAstarNode HeapExtractMin()//弹出最小的元素,并且立即可以保持更新
            {
                int lastindex = FList.Count - 1;
                JCAstarNode min = FList[0];
                InQueue[FList[lastindex].NodeLoction.X, FList[lastindex].NodeLoction.Y] = 1;
                FList[0] = FList[lastindex];//于最后一个交换,将最后一个移到最前面,重新整理
                FList.RemoveAt(lastindex);
                Min_Heapify(0);
                return min;

            }

            public void MinHeapInsert(int index, JCAstarNode Node)
            {

                if (index > FList.Count - 1)
                {
                    FList.Add(Node);

                }
                else
                {
                    FList[index] = Node;
                }
                while (index > 0)
                {
                    int p = (index - 1) / 2;
                    if (FList[p].FTotalCost > FList[index].FTotalCost)
                    {
                        Swap(index, p);
                        index = (index - 1) / 2;
                    }
                    else
                        return;
                }

            }

            public void Add(JCAstarNode Node)
            {
                FList.Add(Node);
                InQueue[Node.NodeLoction.X, Node.NodeLoction.Y] = FList.Count;
            }

            public void Remove(int index, Point to)
            {
                InQueue[FList[index].NodeLoction.X, FList[index].NodeLoction.Y] = 0;
                FList[index] = new JCAstarNode(to);
            }

            public bool Contains(Point p)
            {
                return (InQueue[p.X, p.Y] == 0) ? false : true;
            }
            #endregion

            public void Swap(int c, int d)
            {
                JCAstarNode t = FList[c];
                FList[c] = FList[d];
                FList[d] = t;
                InQueue[FList[c].NodeLoction.X, FList[c].NodeLoction.Y] = c + 1;
                InQueue[FList[d].NodeLoction.X, FList[d].NodeLoction.Y] = d + 1;
            }

        }
 

}