By

文章目录
  1. 1. Preface(序言)
    1. 1.1. What is COC?
    2. 1.2. My COC Experience
  2. 2. COC Project(Unity)
    1. 2.1. Preparation
      1. 2.1.1. Unity
      2. 2.1.2. Programming Language(C#)
      3. 2.1.3. AI
      4. 2.1.4. Knowledge
        1. 2.1.4.1. Is COC a 2D game or 3D game?
        2. 2.1.4.2. Isometric Tileset Engine
          1. 2.1.4.2.1. What is Isometric Tileset Engine?
          2. 2.1.4.2.2. What does game with isometric projection look like?
          3. 2.1.4.2.3. How to make game work under isometric projection?
      5. 2.1.5. Searching
        1. 2.1.5.1. How to develope COC like game?
    2. 2.2. Project
      1. 2.2.1. Game Engine
      2. 2.2.2. Programming Language
      3. 2.2.3. Developer Tool
      4. 2.2.4. Basic Setting with Scene
      5. 2.2.5. Camera Control & Input
        1. 2.2.5.1. PC
        2. 2.2.5.2. Mobile
      6. 2.2.6. UI
      7. 2.2.7. Map
        1. 2.2.7.1. Map Type
        2. 2.2.7.2. Map Save
      8. 2.2.8. Event Manager
      9. 2.2.9. Object Pool
      10. 2.2.10. Utilities
      11. 2.2.11. AI
        1. 2.2.11.1. A Star
          1. 2.2.11.1.1. Searching
          2. 2.2.11.1.2. Create Myself A Star
            1. 2.2.11.1.2.1. A Star Preperation
            2. 2.2.11.1.2.2. PriorityQueue
            3. 2.2.11.1.2.3. A Star
      12. 2.2.12. Optimization
    3. 2.3. Sumary
    4. 2.4. Final Effect

Preface(序言)

What is COC?

COC(Clash of Clans) is a freemium mobile MMO strategy video game developed and published by Supercell.The game was released for iOS platforms on 2 August, 2012,[1] and on Google Play for Android on 7 October, 2013
(from wiki)

My COC Experience

我第一次接触COC大概是在2014年2月份，当时被朋友拉着一起玩这个游戏，三个人建立了自己的小部落，后来陆陆续续拉了不少朋友加入，口口相传，部落成长到40人的部落，从此以后就一发不可收拾。
这款游戏最吸引我的地方有以下几点：

  1. 游戏时间碎片化（采用真实时间计时），不需要玩家长时间在线。
  2. 线上进攻布局，线下防守的玩法。
  3. 不同兵种和法术的不同特性使得玩家的手法和路线规划显得尤为重要（后来出的部落战尤其体现了这一点）。
  4. 部落的概念，增强了集体的概念和玩家间的互动（分享进攻防守记录，打部落战，聊天，捐兵等）
  5. 资深COC玩家来说，游戏的种树文化也不得不说是一种游戏乐趣。

贴一张我的COC图已做留念
My COC

为了这个游戏还买过COC模型
COC Model

经历了两年多的COC洗礼，经历了部落解散，部落合并，到现在最后一起坚持到最后的7,8个小伙伴（基本都满防满王了），感慨万千（此处省略一万字）。

出于自己是做游戏开发的缘故，刚开始学习Unity（同时学习C#），所以决定以COC为模板来制作学习Unity。就这样我的Unity COC计划就这样开始了，虽然最后只实现了很小一部分东西（而且很不完美，但学到很多东西），所以写下这个篇文章来总结自己学到的一些东西。

COC Project(Unity)

Preparation

Unity

(Unity Study)

Programming Language(C#)

(C# Study)

参考书籍：
C#入门经典第五版
CLR Via C# Fourth Edition - Jeffrey Richter

AI

(Artificial-Inteligence-Study)

Knowledge

Is COC a 2D game or 3D game?

The answer is 2D game，actually we should call 2.5D.
第一眼看到COC里面的所有动画人物给人的感觉都是3D的，但后来知道了Isometric Tileset Engine的概念。

Isometric Tileset Engine

What is Isometric Tileset Engine?

(斜视角游戏的地图渲染)
(Isometric Tiles Introduction)
结合上述文章，我们可以知道，Isometric Tileset Engine主要是通过美术制作出Isometric Projection（we angle our camera along two axes (swing the camera 45 degrees to one side, then 30 degrees down)）的2D图片来实现游戏的3D效果（2.5D）。

What does game with isometric projection look like?

典型的Isometric Projection游戏有：
Age of Empires
Age of Empires
Diablo 2
Diablo2

How to make game work under isometric projection?

(参考:Creating Isometric Worlds: A Primer for Game Developers)
从标准的2D游戏到isometric projection的2.5D注意事项

  1. Coordinates Transformation – From Cartesian to isometric coordiates
  2. Creating the Art – isometric projection art
  3. Collision Detection – based on rectangle that is caculated from isometric projection

Searching

How to develope COC like game?

云风参与开发的陌陌争霸
(参考:COC Like 游戏中的寻路算法)
从上面我们可以看出通过对不同建筑队不同兵种的路径的预算，我们可以在在城墙未被破坏的前提下实现O(1)的速度查询建筑距离信息。（但这里我没明白云风大哥所说的”如果下一个行军路线是城墙就攻打城墙” – 这个前提下怎么实现远距离攻打城墙的效果，所以最终并未采取这种方式实现）。

Project

Game Engine

Unity

Programming Language

C#

Developer Tool

Unity
VS2013 / VS2010 (IDE)
ILDissembler – 反编译工具
Blender – 建模工具（本来打算学习并使用这个，但由于游戏最终并未做出来，都只是使用Unity官网的一些现有模型）
Git – 版本控制
项目地址

Basic Setting with Scene

Scene – 3D Scene(考虑2.5D素材的缘故，直接采用3D场景来学习制作2.5D游戏)
Camera – Orthographic Projection(通过采用正交投影并旋转摄像机X轴35度，Y轴45度来模拟Isometric Projection)

Camera Control & Input

PC

PC主要通过GetAxis()来针对用户的上下左右控制

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

Mobile

Mobile主要通过Input.touch来获取屏幕点击事件信息
遇到得问题：
点击到UI上的时候touch事件并未被吞噬
Solved – 通过UnityEngine.EventSystems.EventSystem.current.IsPointerOverGameObject(Input.touches[0].fingerId)来判断是否点击到UI上
e.g.

1
f (!UnityEngine.EventSystems.EventSystem.current.IsPointerOverGameObject (Input.touches[0].fingerId));
  1. 单指和多指的处理
    通过Input.touchCount分别作处理，多指的处理主要通过遍历Input.touches来判断多指的具体行为
    遇到的问题：
    单指相应速度过快
    Solved – 通过定义一个有效的单指响应时间，只有当每帧DeltaTime时间叠加超过有效响应时间的时候才响应输入
    e.g.
1
2
3
4
5
6
7
8
9
10
void Update()
{
	mInputTimer += Time.deltaTime;
	if (Input.touchCount == 1) {
		if(Input.touches[0].phase == TouchPhase.Ended && (mInputTimer > mValidInputDeltaTime))
		{
			......
		}
	}
}

两根手指如何判断是拉远还是缩近地图
Solved – 主要通过判断两根手指每一帧的距离是变大还是变小来判断
e.g.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
    }
}

UI

UI主要使用Unity自带的UI，主要以一个按钮一个方法响应的基本方式。

UI有几个重要的概念：

  1. Unity里所有的UI elements都是包含在Canvas里。
  2. UI的Render Mode主要分为三种
    2.1 Screen Space – Overlay(Rendered on top of the secene)
    2.2 Screen Space – Camera(有距离感的UI，受摄像机设置影响)
    2.3 World Space(3D UI,有深度概念，会被3D物体遮挡)

UI自适应里的重要概念：

  1. UI Scale Mode
    1.1 Constant Pixel Size
    1.2 Scale With Screen Size(自适应里比较重的一种，会根据设定分辨率比例自动扩大或缩小UI)
    1.3 Constant Physical Size
  2. Anchors – 这个我的理解是根据锚点的四个点相对父节点位置的设置，会决定子节点UI如何针对父节点的变化而变化
    比如锚点的四个点分别位于父节点的四个角落，那就表示子节点UI会根据父节点的放大缩小做出一致的变化。
    比如锚点的四个点都在父节点的四个角落中的一个角落，就表示，无论父节点如何变化，子节点UI都不会变化并且相对于父节点锚点的那个点的相对位置是不变的。

更多的UI概念参考官网学习

Map

Map Type

Tile Map
地图是基于一块一块的Tile构成，默认40 * 40

Map Save

C# System.Runtime.Serialization – 序列化来存储Map数据
Unity [System.Serializable] – 支持在编辑器可视化

遇到的问题：

  1. Unity一些自带的基础类型不支持Serializable
    e.g. UnityEngine.Vector3(is not marked as Serializable)
    Solved – 需要自定义Seralizable的Struct来封装Vector3数据
1
2
3
4
5
6
7
[Serializable]
public struct BuildingPosition
{
	public float mX;
	public float mY;
	public float mZ;
}
  1. Unity挂载和类继承问题
    Unity要挂载到GameObject上必须继承至MonoBehaviour,但C#不支持多重继承
    Solved – 定义interface，通过extends interface来实现C#中的多重继承（这一点和Java很像）
1
2
3
4
5
6
7
8
9
10
11
12
public interface GameObjectType {
	ObjectType GameType
	{
		get;
		set;
	}
}

[Serializable]
public class Building : MonoBehaviour, GameObjectType {
	.......
}

Event Manager

主要用于事件监听。（UnityAction是无参并返回void类型的的Delegate）
遇到的问题：

  1. 对于带参数的事件监听
    Solved – 通过继承UnityEvent实现带特定参数的Delegate监听
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using UnityEngine.Events;

public class MyIntEvent : UnityEvent<int>
{

}

public class EventManager : MonoBehaviour {

	private Dictionary<string, UnityEvent> mEventDictionary;

    private Dictionary<string, MyIntEvent> mIntEventDictionary;

	public static EventManager mEMInstance = null;

	void Awake()
	{
		if (mEMInstance == null) {
			mEMInstance = this;
			mEMInstance.Init();
		} else if (mEMInstance != this) {
			Destroy(gameObject);
		}
	}

	void Init()
	{
		if (mEventDictionary == null) {
			mEventDictionary = new Dictionary<string, UnityEvent>();
		}
        if (mIntEventDictionary == null)
        {
            mIntEventDictionary = new Dictionary<string, MyIntEvent>();
        }
	}

	public void StartListening(string eventname, UnityAction listener)
	{
		UnityEvent evt = null;
		if (mEMInstance.mEventDictionary.TryGetValue (eventname, out evt)) {
			evt.AddListener (listener);
		} else {
			evt = new UnityEvent();
			evt.AddListener(listener);
			mEMInstance.mEventDictionary.Add(eventname, evt);
		}
	}

	public void StopListening(string eventname, UnityAction listener)
	{
		if (mEMInstance == null) {
			return ;
		}
		UnityEvent thisevent = null;
		if (mEMInstance.mEventDictionary.TryGetValue (eventname, out thisevent)) {
			thisevent.RemoveListener(listener);
		}
	}

    public void StartListening(string eventname, UnityAction<int> listener)
    {
        MyIntEvent evt = null;
        if (mEMInstance.mIntEventDictionary.TryGetValue(eventname, out evt))
        {
            evt.AddListener(listener);
        }
        else
        {
            evt = new MyIntEvent();
            evt.AddListener(listener);
            mEMInstance.mIntEventDictionary.Add(eventname, evt);
        }
    }

    public void StopListening(string eventname, UnityAction<int> listener)
    {
        if (mEMInstance == null)
        {
            return;
        }
        MyIntEvent thisevent = null;
        if (mEMInstance.mIntEventDictionary.TryGetValue(eventname, out thisevent))
        {
            thisevent.RemoveListener(listener);
        }
    }

    public bool HasListening(string eventname)
    {
        if (mEMInstance == null)
        {
            return false;
        }
        UnityEvent thisevent = null;
        MyIntEvent intevent = null;
        if (mEMInstance.mEventDictionary.TryGetValue(eventname, out thisevent))
        {
            if(thisevent != null)
            {
                return true;
            }
        }

        if (mEMInstance.mIntEventDictionary.TryGetValue(eventname, out intevent))
        {
            if (intevent != null)
            {
                return true;
            }
        }

        return false;
    }

	public void TriggerEvent(string eventname, int p = 0)
	{
		UnityEvent thisevent = null;
		if (mEMInstance.mEventDictionary.TryGetValue (eventname, out thisevent)) {
			if(thisevent != null)
            {
                thisevent.Invoke();
            }
		}

        MyIntEvent intevent = null;
        if (mEMInstance.mIntEventDictionary.TryGetValue(eventname, out intevent))
        {
            if (intevent != null)
            {
                intevent.Invoke(p);
            }
        }
	}
}

Object Pool

主要为了重用GameObject，减少Instantiate的调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
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;
    }
}

Utilities

  1. FPS Display(用于显示FPS)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using UnityEngine;
using System.Collections;
using UnityEngine.UI;

public class FPSDisplay : MonoBehaviour
{
	public Text mFPSText;

	private float mDeltaTime = 0.0f;

	private float mFPS = 0.0f;

	void Update()
	{
		mDeltaTime += (Time.deltaTime - mDeltaTime) * 0.1f;
		float msec = mDeltaTime * 1000.0f;
		mFPS = 1.0f / mDeltaTime;
		mFPSText.text = string.Format("{0:0.0} ms ({1:0.} fps)", msec, mFPS);

	}
}
  1. Time Counter(用于计算时间消耗 – 比如A Star运算时间)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using UnityEngine;
using System.Collections;
using System.Diagnostics;

public class TimerCounter{

	private static TimerCounter TCInstance = null;

	private Stopwatch mTimer;

	private string mName;

	public float TimeSpend
	{
		get
		{
			return mTimer.ElapsedMilliseconds;
		}
	}
	private float mTimeSpend;

	public static TimerCounter CreateInstance()
	{
		if (TCInstance == null) {
			TCInstance = new TimerCounter();
		}
		return TCInstance;
	}

	public static void DestroyInstance()
	{
		if (TCInstance != null) {
			TCInstance = null;
		}
	}

	private TimerCounter()
	{
		mTimer = new Stopwatch ();
		mName = "Default";
	}

	public void Start(string name)
	{
		mName = name;
		mTimer.Start ();
	}

	public void Restart(string name)
	{
		mTimer.Reset ();
		mTimer.Start ();
		mName = name;
	}

	public void End()
	{
		mTimer.Stop ();

		mTimeSpend = mTimer.ElapsedMilliseconds;
	}
}

AI

  1. FSM(Finite State Machine – 有限状态机)
    通过把行为体的行为细分到几种状态来抽象行为体行为，不同状态的AI逻辑在对应的状态去编写。
    下图来源：《Artificial Intelligence for Game》 – Ian Millington
    FSM
    游戏里把士兵的状态分为三种，MoveState, AttackState, IdleState。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class SoldierAttackState : SoldierState {

	private Soldier mSoldier; 

	......
}

public class SoldierAttackState : SoldierState {

	private Soldier mSoldier; 

	......
}

public class SoldierAttackState : SoldierState {

	private Soldier mSoldier; 

	......
}

[Serializable]
public class Soldier : MonoBehaviour, GameObjectType
{
    public SoldierState SCurrentState
    {
        set
        {
            if (mSCurrentState != null)
            {
                mSCurrentState.ExitState();
            }
            mSCurrentState = value;
            mSCurrentState.EnterState();
        }
    }
    [HideInInspector]
    private SoldierState mSCurrentState;

    [HideInInspector]
    public SoldierAttackState mSAttackState;

    [HideInInspector]
    public SoldierDeadState mSDeadState;

    [HideInInspector]
    public SoldierMoveState mSMoveState;

    ......

	public virtual void Awake()
	{
	    mSAttackState = new SoldierAttackState(this);

	    mSMoveState = new SoldierMoveState(this);

	    mSDeadState = new SoldierDeadState(this);

	    ......
	}

	public virtual void Update()
    {
        if (gameObject)
        {
            mSCurrentState.UpdateState();
        }
    }

    ......
}
  1. Decision Trees(决策树 – 用于简单的AI(Decision making))
    Decision Trees主要用于AI体做决策，通过对已知数据的分析判断，根据Decision Tree抉择出最终的决定（即AI行为）。（项目里我主要使用FSM而非Decision Trees）
    下图来源：《Artificial Intelligence for Game》 – Ian Millington
    Decision Tree
  2. A Star(A Star是 Dijkstra（著名的最短路径算法）基础上通过一个启发因子来预估给定节点到目标节点的距离来使得路径节点搜索是向目标节点方向逼近不至于出现搜索大量无效节点的情况)
    (AI相关学习)

A Star

Searching

通过搜索，我发现网络上有现成的很完善的A Star的版本
A Star Pathfinding Project(Asset)
但通过使用后发现，里面所支持的Four,Six and Eight connections都不符合我的需求（每个点都和周围的八个点连通），所以最终放弃了A Star Pathfinding Project而决定自己实现自己的A Star Pathfinding

Create Myself A Star
A Star Preperation

结合Artificial-Inteligence-Study的学习，让我们了解下A Star里的一些基本概念和核心思想：
A Star属于什么图？
A Star里的图属于导航图（Navigation Graph），是基于开销的图搜索(cost-based graph searches)

导航图信息的数据存储？
邻接矩阵：
![Adjacency _Matrix](/img/AI/Adjacency _Matrix.PNG)
邻接表：
Adjacency_List
邻接表用于存储稀疏图非常有效，不会浪费空间来存储空链接。(邻接矩阵会存储大量无效数据(没有连接的边))
这里我们只需要每个点和周边的8个点相连接，所以可以定位成稀疏图。
当我们初始化地图数据的时候，会把所有的点和边以及点和周边相连接边等信息存储起来。
大部分操作都是插入和查询(一般不涉及删除，一旦地图创建好，一般只是修改节点信息而非删除节点(如果真要删除可以通过设定节点信息为INVALID_INDEX来实现而非真正删除))。
为了快速查询我们采用C#里的List < Node > 和List < List < Edge > >来存储节点信息和边连接信息。因为我们会用一个唯一的index去标识节点，所以当我们用节点index去访问节点数据的时候是O(1)的时间复杂度，添加节点到List里也是O(1)。同理，当我们用List < List < Edge > >来存储边连接信息(邻接表)的时候，我们可以通过List[index]去访问特定节点的边连接信息(O(1)，对于边连接信息的添加和删除(这里不是O(1)主要是因为添加的时候我们需要确保不会重复添加同一个边连接信息，删除的时候要去查询找到该边连接信息)
这样一来所有的节点和边链接信息就都存储起来了。

图搜索(寻路)是怎样基于图实现的了？
首先我们要明确我们的搜索目的，为什么这样说了，只有明确了搜索目的我们才能制定合理的搜索策略。
在之前的学习Artificial-Inteligence-Study中提到了盲目搜索(基于广度(Stack来模拟FILO)或者深度的搜索策略(Queue来模拟FIFO))和基于开销的搜索(最短路径开销的策略)。
因为这里我是为了找到最短路径，所以肯定采用的是基于开销的搜索策略。
基于开销的搜索策略的一个重要思想是边放松，边放松的核心思想是通过存储源节点到其他节点的最短路径信息，一边探索新边一边更新该最短路径信息(如果新的边加入导致A节点到B节点有更优的最短路径，那么就更新该A节点到B节点的最短路径信息。直到找到从源节点到目标节点的最短路径信息为止。)

SPT(Shortest Path Tree – 最短路径树)存储的就是源节点到其他节点的最短路径信息(只存储了搜索过的)。(List的方式存储起来，比如源节点是0，目标节点是8，那么最短路径存储即为List[0] = Edge(0,x) List[x] = Edge(x,y) …. List[8] = Edge(y,8))
Edge的抽象Edge(From,To)，From表示初始点，To表示结束点。

知道了最短路径的存储，那么更重要的问题来了，这个最短路径是怎么推导出来的？
这里不得不提Dijstra算法和A Star算法。
Dijstra步骤 ：

  1. 从源节点开始搜索，利用优先队列对在搜索的节点的GCost(源节点到搜索节点的距离)进行排序
  2. Pop出到当前所有搜索过的节点里GCost最小的节点
  3. 添加到该节点的行进边作为抵达该节点的最短路径边(包含在SPT里)
  4. 基于该节点进行扩展搜索
  5. 如果在扩展搜索时有到该节点更短(GCost)的路线边出现就更新该点的GCost以及行进边信息
  6. 继续弹出搜索节点里GCost最小的节点
  7. 直到搜索到目标节点为止
  8. 最后通过最短路径树(SPT)从目标节点反推得出源节点到目标节点的最短路径行进路线

Dijstra算法的缺点：
Dijkstra算法检查了太多的边。

Dijstra算法改进：
A Star – 和Dijkstra算法的唯一区别是对搜索边界上的点的开销(GCost)的计算。因为Dijstra的搜索扩展方向是由GCost决定的，所以A Star算法通过给GCost添加一个启发因子(H)来确保搜索行进方向。
F的计算：
F = G + H
G是到达一个节点的累计开销， H是一个启发因子，它给出的是节点到目标节点的估计距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//伪代码如下
//添加源节点开始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;
        }
    }
}

上面有一个关键的点(PriorityQueue)，用于得到所有搜索节点到目标节点的FCost最小的节点。
这里对于节点的操作主要是插入和修改。
为了快速得到当前搜索节点里里目标节点的估算距离最近的节点，我们需要对当前所有的搜索节点进行排序。
而这里每一次排序的时间复杂度很大程度就决定了A Star的时间消耗。
参考排序算法概念的学习
可以知道借助堆的特性，我们可以很容易的得到最大最小值。
原本堆排序要经历下列步骤:

  1. Init heap(创建最大堆（Build_Max_Heap）：初始化堆数据)
  2. Adjust heap(最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点) – O(Log(n))
  3. Sort heap(堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算) – O(n)
    但这里我们并不需要对堆进行完整的排序，我们只需每次插入或删除或修改的时候能得到最大或最小值即可(即只需要Adjust Heap即可)
    这样一来每一次插入，删除或修改都只需O(Log(n))的时间复杂度。

了解了理论，接下来一步一步看一下如何实现A Star算法的：
首先我们需要抽象出导航图里的节点和边
NavGraphNode里的mIsWall和mIsJumpable后续会讲到为什么会有这两个成员变量
e.g.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
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;
}

抽象了节点和边后，我们就可以初始化我们的地图数据了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 ();
}

这样一来我们的地图基本数据就都创建完成了。
在实现A Star之前，我们需要一个优先队列来排序我们所搜索的所有边的优先级。

PriorityQueue

通过Search我发现C#没有自带的优先队列，所以需要自己实现
这里的优先队列主要要实现排第一位的永远是cost最低的（其他并不需要有序，因为A Star里面是通过pop出cost最低的边来进行搜索行进的）
这里我用到了堆排序(Heap Sort)：
平均时间复杂度：O(n log(n))
最坏时间复杂度：O(n log(n))
最优时间复杂度：O(n log(n)) (时间复杂度都跟堆的深度和数据长度相关，无可避免的需要去做堆调整和堆排序
所以最坏时间复杂度和最优时间复杂度都是O(nlog(n)
因为我们只需要确保第一个是cost最低的，所以我们并不需要每一次都完整的排序整个堆（完整排序的时间复杂度是n * Log(n)），我们只需要在每一次insert和pop的时候重新掉整一下堆即可（这样一来就可以在Log(n)的时间内保证第一个是cost最低的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
using UnityEngine;
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine.Assertions;

public class PriorityQueue<T1, T2>
{
	public PriorityQueue()
	{
		mHeap = new Heap<T1, T2>();
	}

	public PriorityQueue(int size)
	{
		mHeap = new Heap<T1, T2> (size);
	}

	public PriorityQueue(Heap<T1, T2> heap)
	{
		mHeap = heap;
	}

	public PriorityQueue(List<Pair<T1,T2>> key)
	{
		mHeap = new Heap<T1, T2> (key);
	}
	
	public bool Empty()
	{
		return (mHeap.Size() == 0);
	}

    public void Clear()
    {
        mHeap.Clear();
    }
	
	public void Push(Pair<T1, T2> kvp)
	{
		mHeap.Insert(kvp);
	}
	
	public Pair<T1, T2> Pop()
	{
		Pair<T1,T2> result = mHeap.Top();
		mHeap.RemoveTop();
		return result;
	}
	
	public int Size()
	{
		return mHeap.Size();
	}
	
	public Pair<T1, T2> Top()
	{
		return mHeap.Top(); ;
	}

	public void ChangePriority(T1 index)
	{
		//Assert.IsTrue (index >= 0 && index < mHeap.Size ());
		int i = 0;
		i  = mHeap.FindSpecificKeyIndex(index);
		mHeap.HeapifyFromEndToBeginning (i);
	}
	
	public void PrintOutAllMember()
	{
		mHeap.PrintOutAllMember();
	}
	
	private Heap<T1, T2> mHeap;
}

public class Heap<T1, T2>
{
	private List<Pair<T1, T2>> mList;
	private IComparer<T2> mComparer;
	private IComparer<T1> mCompareKey;
	private int mCount;
	
	public Heap()
	{
		mList = new List<Pair<T1, T2>>();
		mComparer = Comparer<T2>.Default;
		mCompareKey = Comparer<T1>.Default;
		mCount = 0;
	}

	public Heap(int size)
	{
		mList = new List<Pair<T1, T2>>(size);
		mComparer = Comparer<T2>.Default;
		mCompareKey = Comparer<T1>.Default;
		mCount = 0;
	}
	
	public Heap(List<Pair<T1, T2>> list)
	{
		mList = list;
		mCount = list.Count;
		mComparer = Comparer<T2>.Default;
		mCompareKey = Comparer<T1>.Default;
		BuildingHeap();
	}

    public void Clear()
    {
        mList.Clear();
        mCount = 0;
    }
	
	public int Size()
	{
		if (mList != null)
		{
			return mCount;
		}
		else
		{
			return 0;
		}
	}
	
	//O(Log(N))
	public void RemoveTop()
	{
		if (mList != null)
		{
			mList[0] = mList[mCount - 1];
			mList.RemoveAt(mCount-1);
			mCount--;
			HeapifyFromBeginningToEnd(0,mCount - 1);
		}
	}
	
	public Pair<T1, T2> Top()
	{
		if (mList != null)
		{
			return mList[0];
		}
		else
		{
			//No more member
			throw new InvalidOperationException("Empty heap.");
		}
	}

	public int FindSpecificKeyIndex(T1 key)
	{
		return mList.FindIndex (x => mCompareKey.Compare (x.Key, key) == 0);
	}
	
	public void PrintOutAllMember()
	{
        Pair<T1, T2> valuepair;
		for (int i = 0; i < mList.Count; i++)
		{
            valuepair = mList[i];
			Debug.Log(valuepair.ToString());
		}
	}
	
	//O(Log(N))
	public void Insert(Pair<T1, T2> valuepair)
	{
		mList.Add(valuepair);
		mCount++;
		HeapifyFromEndToBeginning(mCount - 1);
	}
	
	//调整堆确保堆是最大堆，这里花O(log(n))，跟堆的深度有关
	public void HeapifyFromBeginningToEnd(int parentindex, int length)
	{
		int max_index = parentindex;
		int left_child_index = parentindex * 2 + 1;
		int right_child_index = parentindex * 2 + 2;
		
		//Chose biggest one between parent and left&right child
		if (left_child_index < length && mComparer.Compare(mList[left_child_index].Value, mList[max_index].Value) < 0)
		{
			max_index = left_child_index;
		}
		
		if (right_child_index < length && mComparer.Compare(mList[right_child_index].Value, mList[max_index].Value) < 0)
		{
			max_index = right_child_index;
		}
		
		//If any child is bigger than parent, 
		//then we swap it and do adjust for child again to make sure meet max heap definition
		if (max_index != parentindex)
		{
			Swap(max_index, parentindex);
			HeapifyFromBeginningToEnd(max_index, length);
		}
	}
	
	//O(log(N))
	public void HeapifyFromEndToBeginning(int index)
	{
		if(index >= mCount)
		{
			return;
		}
		while (index > 0)
		{
			int parentindex = (index - 1) / 2;
			if(mComparer.Compare(mList[parentindex].Value,mList[index].Value) > 0)
			{
				Swap(parentindex, index);
				index = parentindex;
			}
			else
			{
				break;
			}
		}
	}
	
	//通过初试数据构建最大堆
	////O(N*Log(N))
	private void BuildingHeap()
	{
		if (mList != null)
		{
			for (int i = mList.Count / 2 - 1; i >= 0; i--)
			{
				//1.2 Adjust heap
				//Make sure meet max heap definition
				//Max Heap definition:
				// (k(i) >= k(2i) && k(i) >= k(2i+1))   (1 <= i <= n/2)
				HeapifyFromBeginningToEnd(i, mList.Count);
			}
		}
	}
	
	////O(N*log(N))
	private void HeapSort()
	{
		if (mList != null)
		{
			//Steps:
			// 1. Build heap
			// 1.1 Init heap
			// 1.2 Adjust heap
			// 2. Sort heap
			
			//1. Build max heap
			// 1.1 Init heap
			//Assume we construct max heap
			BuildingHeap();
			//2. Sort heap
			//这里花O(n)，跟数据数量有关
			for (int i = mList.Count - 1; i > 0; i--)
			{
				//swap first element and last element
				//do adjust heap process again to make sure the new array are still max heap
				Swap(i, 0);
				//Due to we already building max heap before,
				//so  we just need to adjust for index 0 after we swap first and last element
				HeapifyFromBeginningToEnd(0, i);
			}            
		}
		else
		{
			Debug.Log("mList == null");
		}
	}
	
	private void Swap(int id1, int id2)
	{
		Pair<T1, T2> temp;
		temp = mList[id1];
		mList[id1] = mList[id2];
		mList[id2] = temp;
	}
}

public class Pair<T1, T2>
{
	public Pair()
	{
		
	}
	
	public Pair(T1 k, T2 v)
	{
		Key = k;
		Value = v;
	}
	
	public override string ToString()
	{
		return String.Format("[{0},{1}]",Key,Value);
	}
	
	public T1 Key
	{
		get;
		set;
	}
	
	public T2 Value
	{
		get;
		set;
	}
}

这样一来我们所需要的优先队列就完成了。

A Star
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
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);
    }
}

从上面可以看出我写了三个Search的版本：
第一个没有参数是最初的A Star Search，用于普通的寻路。
第二个带有float strickdistance的参数，是由于后来为了实现兵种间不同攻击距离下的寻路，只要达到攻击范围就算寻路完成。
第三个参数带了float strickdistance和bool isignorewall两个参数，还记得之前在GraphNode里写到的由于游戏里有城墙的概念，所以我在NavGraphNode里加入的mIsWall和mIsJumpable变量，用于判断节点是否是城墙并且是否可以直接越过。而这里的第二个参数isignorewall主要是用于判断当前兵种是否支持跳跃城墙（比如COC里的野猪），如果可以忽略城墙，那么寻路的时候就不会加入城墙的考虑。
后续我都会一一展示。

注意： A算法和Dijkstra算法的唯一区别是对搜索边界上的点的开销的计算。被修正的到节点的开销F用来决定节点在优先队列中的位置。
F的计算：
F = G + H
G是到达一个节点的累计开销， H是一个启发因子，它给出的是节点到目标节点的估计距离。

1
float hcost = Heuristic_Euclid.Calculate(mGraph, mITarget, edge.To) * mHCostPercentage;

这里算的是两点之间的实际距离，通过设定一个mHCostPercentage来实现对启发因子数值的控制。

让我们看看mHCostPercentage不同值时的效果：
黄色为寻路过程中探测的路线，绿色是最终路线。
mHCostPercentage = 1，即以两点之间的实际距离为H值的寻路的效果：
mHCostPercentage1

mHCostPercentage = 1.5,即以两点之前的实际距离的1.5倍为H值得寻路效果：
mHCostPercentage1point5

从上图可以看出H的值会使得A Star的搜索方向尽可能的往正确的方向搜索，从而避免不必要的边搜索。
上图由于绘制了搜索路径，所以实际上的Search Time没有那么高，如果mHCostPercentage设置成1.5一般都在2ms以内。

让我们看看加入城墙以后的效果：
注意，这里城墙的权值是设的4，即经过城墙相当于多走4的距离
mHCostPercentage = 1
mHCostPercentage1withWall

mHCostPercentage = 1.5
mHCostPercentage1point5withWall

从上图可以看出通过探索，士兵选择了最近的路线是绕过城墙，同时mHCostPercentage越大使得搜索的边减少了。

接下来看看当建筑被城墙大量包围时的寻路效果：
mHCostPercentage = 1
mHCostPercentage1withMoreWall

mHCostPercentage = 1.5
mHCostPercentage1point5withMoreWall

通过上面可以看出，由于建筑被城墙幅度包围，士兵的最终路线选择是经过城墙。
让我们来看一张有城墙的和无城墙的权值图：
有城墙：
WithWallWeightValue

无城墙：
WithoutWallWeightValue

NavGraphNode里加入的mIsJumpable变量将用于对城墙是否可跳跃的状态进行了抽象（实现COC里的弹跳法术）。

最终这个游戏实现了如下功能：

  1. 地图的存储
  2. 地图的编辑（建造和删除）
  3. 游戏进攻AI（包括对特有类型建筑有限攻击（好比COC里胖子优先攻击防御建筑））
  4. 存档清除
  5. PC和Mobile控制
  6. A Star调试信息面板
  7. 调整兵种信息调整（对优先攻击进行设定，行进速度设定，攻击距离设定，攻击伤害，血量是否可跳墙等属性设定等）
  8. 对建筑物信息调整（所占格子22 or 33等设定（暂时只支持11,22,3*3），攻击距离，攻击伤害，血量等信息）
  9. 法术信息调整（法术范围，法术持续时间等信息）

兵种支持：

  1. 近战型优先攻击防御建筑 – 好比COC的胖子
  2. 远程，无特定攻击对象 – 好比COC的弓箭手

建筑支持：

  1. 攻击建筑 – 好比COC里的箭塔
  2. 不可攻击建筑 – 好比COC里的兵营
  3. 城墙 – 好比COC里的城墙

法术支持：
弹跳法术

所有功能都会在最后的视频一一展示。

Optimization

  1. Rendering
    最初是绘制了40*40，1600个带Sprite图案的Tile，后来改为用一张整的Ground和只带Collider的1600个Tile。

  2. GC
    A Star最初写的时候是每一次运算都申请新的内存(每一次都New上百k的内存)，后来改为通用数据保留下来，每次只重新申请需要返回的A Star Path的数据(大概几K)

  3. Physics
    最初是打开了所有Layer之间的碰撞检测，后来改为只打开需要碰撞检测的Layer之间的碰撞检测(Edit -> Project Settings -> Physics)

  4. Memory
    避免不必要的内存开销(比如box会在堆上申请额外的内存)
    项目里用Dictionary而不要用Hashtable，因为Dictionary是基于模板的，在针对ValueType的时候不会触发box和unbox。
    Unity里foreach会触发box，所以在Unity里尽量避免使用foreach，用while or for代替。

Sumary

在这次尝试制作和学习的过程中，学习了解了Unity和C#的一些基本概念。
巩固学习了AI寻路方面的知识。
对于炸弹人的AI，虽然云风大哥说大概是“寻找附近封闭空间中最近目标”，对于如何实现这一点没有头绪。(未来AI学习书籍 – 《Artificial Intelligence for Game》 — Ian Millington)
通过这一次的实践学习，我明白了，好的数据结构设计才是性能的关键所在。我的实现依赖于A Star的实时运算，即使每次运算时1ms级别，但数量一旦达到成百上千，A Star是无法保证帧率的。尽量做到预算和O(1)时间的查找或者运用更好的数据结构解决问题才是提升性能的关键。
最后再贴一个没有解决的真机bug（相对严重的，PC上没有），暂时未能解决的。
Unity 的提问

Final Effect

视频

文章目录
  1. 1. Preface(序言)
    1. 1.1. What is COC?
    2. 1.2. My COC Experience
  2. 2. COC Project(Unity)
    1. 2.1. Preparation
      1. 2.1.1. Unity
      2. 2.1.2. Programming Language(C#)
      3. 2.1.3. AI
      4. 2.1.4. Knowledge
        1. 2.1.4.1. Is COC a 2D game or 3D game?
        2. 2.1.4.2. Isometric Tileset Engine
          1. 2.1.4.2.1. What is Isometric Tileset Engine?
          2. 2.1.4.2.2. What does game with isometric projection look like?
          3. 2.1.4.2.3. How to make game work under isometric projection?
      5. 2.1.5. Searching
        1. 2.1.5.1. How to develope COC like game?
    2. 2.2. Project
      1. 2.2.1. Game Engine
      2. 2.2.2. Programming Language
      3. 2.2.3. Developer Tool
      4. 2.2.4. Basic Setting with Scene
      5. 2.2.5. Camera Control & Input
        1. 2.2.5.1. PC
        2. 2.2.5.2. Mobile
      6. 2.2.6. UI
      7. 2.2.7. Map
        1. 2.2.7.1. Map Type
        2. 2.2.7.2. Map Save
      8. 2.2.8. Event Manager
      9. 2.2.9. Object Pool
      10. 2.2.10. Utilities
      11. 2.2.11. AI
        1. 2.2.11.1. A Star
          1. 2.2.11.1.1. Searching
          2. 2.2.11.1.2. Create Myself A Star
            1. 2.2.11.1.2.1. A Star Preperation
            2. 2.2.11.1.2.2. PriorityQueue
            3. 2.2.11.1.2.3. A Star
      12. 2.2.12. Optimization
    3. 2.3. Sumary
    4. 2.4. Final Effect