float moveHorizontal = Input.GetAxis ("Horizontal") * mMoveSpeed * Time.deltaTime;
float moveVertical = Input.GetAxis ("Vertical") * mMoveSpeed * Time.deltaTime;

f (!UnityEngine.EventSystems.EventSystem.current.IsPointerOverGameObject (Input.touches[0].fingerId));

for(int i = 0; i < 2; i++)
{
    if (Input.touches[i].phase == TouchPhase.Began)
    {
        mCurrentTouchFingerPos[i] = Input.touches[0].position;
        mPreTouchFingerPos[i] = Input.touches[0].position;
        mTouchFingerDeltaPos[i] = Vector2.zero;
        if (i == 1)
        {
            mPreTwoFingersDistance = mCurrentTwoFingersDistance;
            mCurrentTwoFingersDistance = Vector2.Distance(mCurrentTouchFingerPos[0], mCurrentTouchFingerPos[1]);
        }
    }
    else if (Input.touches[i].phase == TouchPhase.Moved)
    {
        mPreTouchFingerPos[i] = mCurrentTouchFingerPos[i];
        mCurrentTouchFingerPos[i] = Input.touches[i].position;
        mTouchFingerDeltaPos[i] = Input.touches[i].deltaPosition;
        if (i == 1)
        {
            mPreTwoFingersDistance = mCurrentTwoFingersDistance;
            mCurrentTwoFingersDistance = Vector2.Distance(mCurrentTouchFingerPos[0], mCurrentTouchFingerPos[1]);
        }
    }
    else if (Input.touches[i].phase == TouchPhase.Ended)
    {
        mCurrentTouchFingerPos[i] = Vector2.zero;
        mPreTouchFingerPos[i] = Vector2.zero;
        mTouchFingerDeltaPos[i] = Vector2.zero;
        mCurrentTwoFingersDistance = 0.0f;
        mPreTwoFingersDistance = 0.0f;
        return;
    }
}

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class ObjectPoolManager : MonoBehaviour{

    public static ObjectPoolManager mObjectPoolManagerInstance = null;

    public GameObject mBuildingBullet;

    public int mBBulletPoolAmount = 20;

    private List<GameObject> mBBulletsList;

    public GameObject mSoldierBullet;

    public int mSBulletPoolAmount = 50;

    private List<GameObject> mSBulletsList;

    public bool mWillGrow = true;

    void Awake()
    {
        if (mObjectPoolManagerInstance == null)
        {
            mObjectPoolManagerInstance = this;
        }
        else if (mObjectPoolManagerInstance != this)
        {
            Destroy(gameObject);
        }
    }

    void Start()
    {
        mBBulletsList = new List<GameObject>();
        mSBulletsList = new List<GameObject>();

        for (int i = 0; i < mBBulletPoolAmount; i++)
        {
            GameObject bbulletobj = Instantiate(mBuildingBullet) as GameObject;
            bbulletobj.SetActive(false);
            mBBulletsList.Add(bbulletobj);
        }

        for (int j = 0; j < mSBulletPoolAmount; j++)
        {
            GameObject sbulletobj = Instantiate(mSoldierBullet) as GameObject;
            sbulletobj.SetActive(false);
            mSBulletsList.Add(sbulletobj);
        }
    }

    public GameObject GetBuildingBulletObject()
    {
        for (int i = 0; i < mBBulletsList.Count; i++)
        {
            if (!mBBulletsList[i].activeInHierarchy)
            {
                mBBulletsList[i].SetActive(true);
                return mBBulletsList[i];
            }
        }

        if (mWillGrow)
        {
            GameObject bbulletobj = Instantiate(mBuildingBullet) as GameObject;
            mBBulletsList.Add(bbulletobj);
            return bbulletobj;
        }

        return null;
    }

    public GameObject GetSoldierBulletObject()
    {
        for (int i = 0; i < mSBulletsList.Count; i++)
        {
            if (!mSBulletsList[i].activeInHierarchy)
            {
                mSBulletsList[i].SetActive(true);
                return mSBulletsList[i];
            }
        }

        if (mWillGrow)
        {
            GameObject sbulletobj = Instantiate(mSoldierBullet) as GameObject;
            mSBulletsList.Add(sbulletobj);
            return sbulletobj;
        }

        return null;
    }
}

//伪代码如下
//添加源节点开始Dijstra算法搜索
mPQ.Clear();
mPQ.Push(mFCosts[mISource]);
//Pop出所有搜索过的节点到目标节点FCost最小的节点
while (!mPQ.Empty())
{
    int nextclosestnode = mPQ.Pop().Key;

    //添加当前搜索节点里FCost最小的行进边作为最短路径的边之一
    if (mSearchFrontier[nextclosestnode] != null && mSearchFrontier[nextclosestnode].IsValidEdge())
    {
        mShortestPathTree[nextclosestnode] = mSearchFrontier[nextclosestnode];
    }
    //直到找到目标节点为止
    if (nextclosestnode == mITarget)
    {
        return;
    }

    //以当前搜索节点里到目标节点最近的点为基准进行边扩展搜索
    List<GraphEdge> edgelist = mGraph.EdgesList[nextclosestnode];
    GraphEdge edge;
    for (int i = 0; i < edgelist.Count; i++)
    {
        edge = edgelist[i];
        //计算该节点到目标节点的H值，用于控制搜索行进方向(A*对Dijstra算法的改进)
        float hcost = Heuristic_Euclid.Calculate(mGraph, mITarget, edge.To) * mHCostPercentage;

        //算出到该节点的路径GCost
        //GCost是源节点到特定节点的实际距离(用于判断是否是源节点到特定节点更近的路线)
        //G+H是源节点通过特定节点到目标节点的预估距离(用于控制行进方向)
        float gcost = mGCosts[nextclosestnode] + edge.Cost;

        //判断搜索行进的节点是否已经有任何搜索边抵达过
        //如果没有抵达过，添加该边到搜索列表里(mSearchFrontier)，并添加更新到该新节点的最短距离GCost和预估距离FCost(GCost+H)
        //同时把该FCost作为该节点通过特定节点到目标节点的估算距离添加到队列里进行排序，
        //用于得出搜索节点里下一个离目标节点最近的节点index
        if (mSearchFrontier[edge.To] != null && !mSearchFrontier[edge.To].IsValidEdge())
        {
            mFCosts[edge.To].Value = gcost + hcost;
            mGCosts[edge.To] = gcost;
            //添加的是特定节点到目标节点的估算距离G+H来作为排序的依据
            mPQ.Push(mFCosts[edge.To]);

            mSearchFrontier[edge.To] = edge;

            mAStarPathInfo.EdgesSearched++;

            if (mBDrawExplorePath)
            {
                Debug.DrawLine(mGraph.Nodes[edge.From].Position, mGraph.Nodes[edge.To].Position, Color.yellow, mExplorePathRemainTime);
            }
        }
        //如果抵达过，那么就去判断当前路线(通过当前边到该节点的路线)的GCost是否比之前记录在GCost里到达该节点的GCost更小
        //如果更小就说明有新的更短的路径可以抵达该节点
        //更新到该节点的GCost，FCost用于下一次Pop当前搜索节点里里目标节点最近(FCost)的节点
        //同时更新到该节点的最短路径边
        else if (gcost < mGCosts[edge.To])
        {
            mFCosts[edge.To].Value = gcost + hcost;
            mGCosts[edge.To] = gcost;

            mPQ.ChangePriority(edge.To);

            mSearchFrontier[edge.To] = edge;
        }
    }
}

public class GraphEdge
{
    public GraphEdge()
    {
        mFrom = (int)E_NODE_INDEX.INVALID_NODE;
        mTo = (int)E_NODE_INDEX.INVALID_NODE;
        mCost = 0.0f;
    }

    public int From
    {
        get
        {
            return mFrom;
        }
        set
        {
            Debug.Assert(value >= 0, "mFrom must great or equal to 0");
            mFrom = value;
        }
    }
    private int mFrom;

    public int To
    {
        get
        {
            return mTo;
        }
        set
        {
            Debug.Assert(value >= 0, "mTo must great or equal to 0");
            mTo = value;
        }
    }
    private int mTo;

    public float Cost
    {
        get
        {
            return mCost;
        }
        set
        {
            Debug.Assert(value >= 0, "mCost must great or equal to 0");
            mCost = value;
        }
    }
    private float mCost;
}

public class NavGraphNode : GraphNode {

	private NavGraphNode()
	{

	}

	public NavGraphNode(int index,Vector3 pos, float weight, bool iswall)
	{
		Index = index;
		mPosition = pos;
		mWeight = weight;
		mIsWall = iswall;
		mIsJumpable = false;
	}
	
	public int Index
	{
		get
		{
			return mIndex;
		}
		set
		{
			mIndex = value;
		}
	}
	private int mIndex;

	public Vector3 Position
	{
		get
		{
			return mPosition;
		}
		set
		{
			mPosition = value;
		}
	}
	private Vector3 mPosition;

	public float Weight
	{
		get
		{
			return mWeight;
		}
		set
		{
			mWeight = value;
		}
	}
	private float mWeight;

	public bool IsWall
	{
		get
		{
			return mIsWall;
		}
		set
		{
			mIsWall = value;
		}
	}
	private bool mIsWall;

	public bool IsJumpable
	{
		get
		{
			return mIsJumpable;
		}
		set
		{
			mIsJumpable = value;
		}
	}
	private bool mIsJumpable;
}

public void CreateGraph()
{
	mNavGraph = new SparseGraph<NavGraphNode, GraphEdge> (mRow * mColumn);
	
	mNavGraph.BDrawMap = mBDrawMap;

	Vector3 nodeposition = new Vector3 ();
	int nextindex = 0;
	//SparseGraph nodes data
	for (int rw = 0; rw < mRow; rw++) {
		for (int col = 0; col < mColumn; col++) {
			nodeposition = new Vector3 (rw, 0.0f, col);
			nextindex = mNavGraph.NextFreeNodeIndex;
			mNavGraph.AddNode (new NavGraphNode (nextindex, nodeposition, 0.0f, false));
		}
	}

	//SparseGraph edges data
	for (int rw = 0; rw < mRow; rw++) 
	{
		for (int col = 0; col < mColumn; col++) 
		{
			CreateAllNeighboursToGridNode(rw, col, mRow, mColumn);
		}
	}

	mTotalNodes = mNavGraph.NumNodes();
	mTotalEdges = mNavGraph.NumEdges ();
}

using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System;
using UnityEngine.Assertions;

public class SearchAStar
{
    public struct PathInfo
    {

        public List<int> PathToTarget
        {
            get
            {
                return mPathToTarget;
            }
            set
            {
                mPathToTarget = value;
            }
        }
        private List<int> mPathToTarget;

        public List<Vector3> MovementPathToTarget
        {
            get
            {
                return mMovementPathToTarget;
            }
            set
            {
                mMovementPathToTarget = value;
            }
        }
        private List<Vector3> mMovementPathToTarget;

        public bool IsWallInPathToTarget
        {
            get
            {
                return mIsWallInPathToTarget;
            }
            set
            {
                mIsWallInPathToTarget = value;
            }
        }
        private bool mIsWallInPathToTarget;

        public int WallInPathToTargetIndex
        {
            get
            {
                return mWallInPathToTargetIndex;
            }
            set
            {
                mWallInPathToTargetIndex = value;
            }
        }
        private int mWallInPathToTargetIndex;

        public float CostToTarget
        {
            get
            {
                return mCostToTarget;
            }
            set
            {
                mCostToTarget = value;
            }
        }
        private float mCostToTarget;

        public int ITarget
        {
            set
            {
                mITarget = value;
            }
            get
            {
                return mITarget;
            }
        }
        private int mITarget;

        public int OriginalTarget
        {
            get
            {
                return mOriginalTarget;
            }
            set
            {
                mOriginalTarget = value;
            }
        }
        private int mOriginalTarget;

        public int NodesSearched
        {
            get
            {
                return mNodesSearched;
            }
            set
            {
                mNodesSearched = value;
            }
        }
        private int mNodesSearched;

        public int EdgesSearched
        {
            get
            {
                return mEdgesSearched;
            }
            set
            {
                mEdgesSearched = value;
            }
        }
        private int mEdgesSearched;

        //this list of edges is used to store any subtree returned from any of the graph algorithms
        /*
        public List<GraphEdge> SubTree
        {
            get
            {
                return mSubTree;
            }
            set
            {
                mSubTree = value;
            }
        }
        private List<GraphEdge> mSubTree;
        */
        /*
        public PathInfo()
        {
            ResetPathInfo();
        }
        */

        public PathInfo DeepCopy()
        {
            PathInfo pi = (PathInfo)this.MemberwiseClone();
            pi.PathToTarget = new List<int>(mPathToTarget);
            pi.MovementPathToTarget = new List<Vector3>(mMovementPathToTarget);

            return pi;
        }

        public void ResetPathInfo()
        {
            mIsWallInPathToTarget = false;

            mWallInPathToTargetIndex = -1;

            if (mPathToTarget != null)
            {
                mPathToTarget.Clear();
            }
            else
            {
                mPathToTarget = new List<int>();
            }

            if (mMovementPathToTarget != null)
            {
                mMovementPathToTarget.Clear();
            }
            else
            {
                mMovementPathToTarget = new List<Vector3>();
            }

            mNodesSearched = 0;

            mEdgesSearched = 0;

            mCostToTarget = 0.0f;
        }
    }

    private SearchAStar()
    {

    }

    public SearchAStar(SparseGraph<NavGraphNode, GraphEdge> graph
                       , int source
                       , int target
                       , bool isignorewall
                       , float strickdistance
                       , float hcostpercentage
                       , bool drawexplorepath
                       , float explorepathremaintime)
    {
        mGraph = graph;
        mPQ = new PriorityQueue<int, float>((int)Mathf.Sqrt(mGraph.NumNodes()));
        mGCosts = new List<float>(graph.NumNodes());
        mFCosts = new List<Pair<int, float>>(graph.NumNodes());
        mShortestPathTree = new List<GraphEdge>(graph.NumNodes());
        mSearchFrontier = new List<GraphEdge>(graph.NumNodes());
        //Init G cost and F cost and Cost value
        for (int i = 0; i < graph.NumNodes(); i++)
        {
            mGCosts.Add(0.0f);
            mFCosts.Add(new Pair<int, float>(i, 0.0f));
            mShortestPathTree.Add(new GraphEdge());
            mSearchFrontier.Add(new GraphEdge());
        }
        mISource = source;
        mITarget = target;
        mOriginalTarget = target;

        Assert.IsTrue(hcostpercentage >= 0);
        mHCostPercentage = hcostpercentage;

        mBDrawExplorePath = drawexplorepath;

        mExplorePathRemainTime = explorepathremaintime;

        mAStarPathInfo = new PathInfo();

        mIsIgnoreWall = isignorewall;

        mStrickDistance = strickdistance;

        //Search(mStrickDistance, mIsIgnoreWall);

        //GeneratePathToTargetInfo();
    }

    public void UpdateSearch(int sourceindex, int targetindex, float strickdistance)
    {
        Assert.IsTrue(mISource >= 0 && mISource < mGraph.NumNodes());
        Assert.IsTrue(mITarget >= 0 && mITarget < mGraph.NumNodes());

        AstarReset(sourceindex, targetindex, strickdistance);

        Search(mStrickDistance, mIsIgnoreWall);

        GeneratePathToTargetInfo();
    }

    private void AstarReset(int sourceindex, int targetindex, float strickdistance)
    {
        mISource = sourceindex;

        mITarget = targetindex;

        mOriginalTarget = targetindex;

        mStrickDistance = strickdistance;

        for (int i = 0; i < mGraph.NumNodes(); i++)
        {
            mGCosts[i] = 0.0f;
            mFCosts[i].Value = 0.0f;
            mShortestPathTree[i].Reset();
            mSearchFrontier[i].Reset();
        }

        mAStarPathInfo.ResetPathInfo();
    }

    private bool mIsIgnoreWall;

    public float StrickDistance
    {
        set
        {
            mStrickDistance = value;
        }
    }
    private float mStrickDistance;

    public PathInfo AStarPathInfo
    {
        get
        {
            return mAStarPathInfo;
        }
        set
        {
            mAStarPathInfo = value;
        }
    }
    private PathInfo mAStarPathInfo;

    private void GeneratePathToTargetInfo()
    {
        mAStarPathInfo.PathToTarget.Clear();
        mAStarPathInfo.MovementPathToTarget.Clear();

        if (mITarget < 0)
        {
            return;
        }

        int nd = mITarget;

        mAStarPathInfo.PathToTarget.Add(nd);

        mAStarPathInfo.MovementPathToTarget.Add(mGraph.Nodes[nd].Position);

        while ((nd != mISource) && (mShortestPathTree[nd] != null) && mShortestPathTree[nd].IsValidEdge())
        {
            //Debug.DrawLine(mGraph.Nodes[mShortestPathTree[nd].From].Position,mGraph.Nodes[nd].Position,Color.green, Mathf.Infinity);

            if (!mIsIgnoreWall)
            {
                //No matter the wall in path is jumpable or not, we should record it as useful information
                if (mGraph.Nodes[nd].IsWall /*&& !mGraph.Nodes[nd].IsJumpable*/)
                {
                    mAStarPathInfo.IsWallInPathToTarget = true;
                    mAStarPathInfo.WallInPathToTargetIndex = nd;
                }
            }

            nd = mShortestPathTree[nd].From;

            mAStarPathInfo.PathToTarget.Add(nd);

            mAStarPathInfo.MovementPathToTarget.Add(mGraph.Nodes[nd].Position);
        }

        mAStarPathInfo.CostToTarget = GetCostToTarget();

        mAStarPathInfo.ITarget = mITarget;

        mAStarPathInfo.OriginalTarget = mOriginalTarget;
    }

    public List<GraphEdge> GetSPT()
    {
        return mShortestPathTree;
    }

    private float GetCostToTarget()
    {
        return mGCosts[mITarget];
    }

    private SparseGraph<NavGraphNode, GraphEdge> mGraph;

    private PriorityQueue<int, float> mPQ;

    private List<float> mGCosts;

    private List<Pair<int, float>> mFCosts;

    public List<GraphEdge> SPT
    {
        get
        {
            return mShortestPathTree;
        }
    }
    private List<GraphEdge> mShortestPathTree;

    /*
	public List<float> CostToTargetNode 
	{
		get {
			return mCostToTargetNode;
		}
		set
		{
			mCostToTargetNode = value;
		}
	}
	private List<float> mCostToTargetNode;
    */
    private List<GraphEdge> mSearchFrontier;

    public int ISource
    {
        set
        {
            mISource = value;
        }
    }
    private int mISource;

    public int ITarget
    {
        set
        {
            mITarget = value;
        }
        get
        {
            return mITarget;
        }
    }
    private int mITarget;

    public int OriginalTarget
    {
        get
        {
            return mOriginalTarget;
        }
        set
        {
            mOriginalTarget = value;
        }
    }
    private int mOriginalTarget;

    private float mHCostPercentage;

    private bool mBDrawExplorePath;

    private float mExplorePathRemainTime;

    //The A* search algorithm
    private void Search()
    {
        mPQ.Clear();

        mPQ.Push(mFCosts[mISource]);

        //mSearchFrontier [mISource] = new GraphEdge (mISource, mISource, 0.0f);
        mSearchFrontier[mISource].From = mISource;
        mSearchFrontier[mISource].To = mISource;
        mSearchFrontier[mISource].Cost = 0.0f;

        while (!mPQ.Empty())
        {
            //Get lowest cost node from the queue
            int nextclosestnode = mPQ.Pop().Key;

            mAStarPathInfo.NodesSearched++;

            //move this node from the frontier to the spanning tree
            if (mSearchFrontier[nextclosestnode] != null && mSearchFrontier[nextclosestnode].IsValidEdge())
            {
                mShortestPathTree[nextclosestnode] = mSearchFrontier[nextclosestnode];
            }
            //If the target has been found exit
            if (nextclosestnode == mITarget)
            {
                return;
            }

            //Now to test all the edges attached to this node
            List<GraphEdge> edgelist = mGraph.EdgesList[nextclosestnode];
            GraphEdge edge;
            for (int i = 0; i < edgelist.Count; i++)
            {
                edge = edgelist[i];
                //calculate the heuristic cost from this node to the target (H)
                float hcost = Heuristic_Euclid.Calculate(mGraph, mITarget, edge.To) * mHCostPercentage;

                //calculate the 'real' cost to this node from the source (G)
                float gcost = mGCosts[nextclosestnode] + edge.Cost;

                //if the node has not been added to the frontier, add it and update the G and F costs
                if (mSearchFrontier[edge.To] != null && !mSearchFrontier[edge.To].IsValidEdge())
                {
                    mFCosts[edge.To].Value = gcost + hcost;
                    mGCosts[edge.To] = gcost;

                    mPQ.Push(mFCosts[edge.To]);

                    mSearchFrontier[edge.To] = edge;

                    mAStarPathInfo.EdgesSearched++;

                    if (mBDrawExplorePath)
                    {
                        Debug.DrawLine(mGraph.Nodes[edge.From].Position, mGraph.Nodes[edge.To].Position, Color.yellow, mExplorePathRemainTime);
                    }
                }

                //if this node is already on the frontier but the cost to get here
                //is cheaper than has been found previously, update the node
                //cost and frontier accordingly
                else if (gcost < mGCosts[edge.To])
                {
                    mFCosts[edge.To].Value = gcost + hcost;
                    mGCosts[edge.To] = gcost;

                    //Due to some node's f cost has been changed
                    //we should reoder the priority queue to make sure we pop up the lowest fcost node first
                    //compare the fcost will make sure we search the path in the right direction
                    //h cost is the key to search in the right direction
                    mPQ.ChangePriority(edge.To);

                    mSearchFrontier[edge.To] = edge;

                    mAStarPathInfo.EdgesSearched++;
                }
            }
        }
    }

    //The A* search algorithm with strickdistance
    private void Search(float strickdistance)
    {
        float currentnodetotargetdistance = Mathf.Infinity;

        mPQ.Clear();

        mPQ.Push(mFCosts[mISource]);

        //mSearchFrontier [mISource] = new GraphEdge (mISource, mISource, 0.0f);
        mSearchFrontier[mISource].From = mISource;
        mSearchFrontier[mISource].To = mISource;
        mSearchFrontier[mISource].Cost = 0.0f;

        while (!mPQ.Empty())
        {
            //Get lowest cost node from the queue
            int nextclosestnode = mPQ.Pop().Key;

            mAStarPathInfo.NodesSearched++;

            //move this node from the frontier to the spanning tree
            if (mSearchFrontier[nextclosestnode] != null && mSearchFrontier[nextclosestnode].IsValidEdge())
            {
                mShortestPathTree[nextclosestnode] = mSearchFrontier[nextclosestnode];
            }

            currentnodetotargetdistance = Heuristic_Euclid.Calculate(mGraph, mITarget, nextclosestnode);

            if (nextclosestnode == mITarget || currentnodetotargetdistance <= strickdistance)
            {
                mITarget = nextclosestnode;
                return;
            }

            //Now to test all the edges attached to this node
            List<GraphEdge> edgelist = mGraph.EdgesList[nextclosestnode];
            GraphEdge edge;
            for (int i = 0; i < edgelist.Count; i++)
            {
                edge = edgelist[i];
                //calculate the heuristic cost from this node to the target (H)
                float hcost = Heuristic_Euclid.Calculate(mGraph, mITarget, edge.To) * mHCostPercentage;

                //calculate the 'real' cost to this node from the source (G)
                float gcost = mGCosts[nextclosestnode] + edge.Cost;

                //if the node has not been added to the frontier, add it and update the G and F costs
                if (mSearchFrontier[edge.To] != null && !mSearchFrontier[edge.To].IsValidEdge())
                {
                    mFCosts[edge.To].Value = gcost + hcost;
                    mGCosts[edge.To] = gcost;

                    mPQ.Push(mFCosts[edge.To]);

                    mSearchFrontier[edge.To] = edge;

                    mAStarPathInfo.EdgesSearched++;

                    if (mBDrawExplorePath)
                    {
                        Debug.DrawLine(mGraph.Nodes[edge.From].Position, mGraph.Nodes[edge.To].Position, Color.yellow, mExplorePathRemainTime);
                    }
                }

                //if this node is already on the frontier but the cost to get here
                //is cheaper than has been found previously, update the node
                //cost and frontier accordingly
                else if (gcost < mGCosts[edge.To])
                {
                    mFCosts[edge.To].Value = gcost + hcost;
                    mGCosts[edge.To] = gcost;

                    //Due to some node's f cost has been changed
                    //we should reoder the priority queue to make sure we pop up the lowest fcost node first
                    //compare the fcost will make sure we search the path in the right direction
                    //h cost is the key to search in the right direction
                    mPQ.ChangePriority(edge.To);

                    mSearchFrontier[edge.To] = edge;

                    mAStarPathInfo.EdgesSearched++;
                }
            }
        }
    }

    //The A* search algorithm with strickdistance with wall consideration
    private void Search(float strickdistance, bool isignorewall)
    {
        float currentnodetotargetdistance = Mathf.Infinity;

        mPQ.Clear();

        mPQ.Push(mFCosts[mISource]);

        //mSearchFrontier [mISource] = new GraphEdge (mISource, mISource, 0.0f);
        mSearchFrontier[mISource].From = mISource;
        mSearchFrontier[mISource].To = mISource;
        mSearchFrontier[mISource].Cost = 0.0f;
        GraphEdge edge = new GraphEdge();
        int nextclosestnode = -1;

        while (!mPQ.Empty())
        {
            //Get lowest cost node from the queue
            nextclosestnode = mPQ.Pop().Key;

            mAStarPathInfo.NodesSearched++;

            //move this node from the frontier to the spanning tree
            if (mSearchFrontier[nextclosestnode] != null && mSearchFrontier[nextclosestnode].IsValidEdge())
            {
                mShortestPathTree[nextclosestnode] = mSearchFrontier[nextclosestnode];
            }

            currentnodetotargetdistance = Heuristic_Euclid.Calculate(mGraph, mITarget, nextclosestnode);

            if (nextclosestnode == mITarget || (currentnodetotargetdistance <= strickdistance && !mGraph.Nodes[nextclosestnode].IsWall))
            {
                mITarget = nextclosestnode;
                return;
            }

            //Now to test all the edges attached to this node
            List<GraphEdge> edgelist = mGraph.EdgesList[nextclosestnode];
            for (int i = 0; i < edgelist.Count; i++)
            {
                //Avoid pass refrence
                edge.Reset();
                edge.From = edgelist[i].From;
                edge.To = edgelist[i].To;
                edge.Cost = edgelist[i].Cost;
                //calculate the heuristic cost from this node to the target (H)
                float hcost = Heuristic_Euclid.Calculate(mGraph, mITarget, edge.To) * mHCostPercentage;

                //calculate the 'real' cost to this node from the source (G)
                float gcost = 0.0f;
                if (isignorewall)
                {
                    gcost = mGCosts[nextclosestnode] + edge.Cost;

                    if (mGraph.Nodes[edge.From].IsWall)
                    {
                        gcost -= mGraph.Nodes[edge.From].Weight;
                    }
                    if (mGraph.Nodes[edge.To].IsWall)
                    {
                        gcost -= mGraph.Nodes[edge.To].Weight;
                    }
                }
                else
                {
                    gcost = mGCosts[nextclosestnode] + edge.Cost;
                    if (mGraph.Nodes[edge.From].IsJumpable)
                    {
                        gcost -= mGraph.Nodes[edge.From].Weight;
                    }
                    if (mGraph.Nodes[edge.To].IsJumpable)
                    {
                        gcost -= mGraph.Nodes[edge.To].Weight;
                    }
                }

                //if the node has not been added to the frontier, add it and update the G and F costs
                if (mSearchFrontier[edge.To] != null && !mSearchFrontier[edge.To].IsValidEdge())
                {
                    mFCosts[edge.To].Value = gcost + hcost;
                    mGCosts[edge.To] = gcost;

                    mPQ.Push(mFCosts[edge.To]);

                    mSearchFrontier[edge.To].ValueCopy(edge);

                    mAStarPathInfo.EdgesSearched++;

                    if (mBDrawExplorePath)
                    {
                        Debug.DrawLine(mGraph.Nodes[edge.From].Position, mGraph.Nodes[edge.To].Position, Color.yellow, mExplorePathRemainTime);
                    }
                }

                //if this node is already on the frontier but the cost to get here
                //is cheaper than has been found previously, update the node
                //cost and frontier accordingly
                else if (gcost < mGCosts[edge.To])
                {
                    mFCosts[edge.To].Value = gcost + hcost;
                    mGCosts[edge.To] = gcost;

                    //Due to some node's f cost has been changed
                    //we should reoder the priority queue to make sure we pop up the lowest fcost node first
                    //compare the fcost will make sure we search the path in the right direction
                    //h cost is the key to search in the right direction
                    mPQ.ChangePriority(edge.To);

                    mSearchFrontier[edge.To].ValueCopy(edge);

                    mAStarPathInfo.EdgesSearched++;
                }
            }
        }
    }
}

class Heuristic_Euclid
{
    public static float Calculate(SparseGraph<NavGraphNode, GraphEdge> g, int nd1, int nd2)
    {
        //Manhattan distance heuritic
        //Vector2 v1 = Utility.ConvertIndexToRC (nd1);
        //Vector2 v2 = Utility.ConvertIndexToRC (nd2);
        //float dis = v1.x - v2.x + v1.y - v2.y;
        //Debug.Log("dis = " + dis);
        //return dis;
        //Caculation distance takes much time
        return Vector3.Distance(g.Nodes[nd1].Position, g.Nodes[nd2].Position);
    }
}