1. 什么是单例设计（Singleton Design）
在学校学习面向对象编程中的一些常用的设计模式时，我第一次系统的接触到了单例设计（Singleton Design），或者说单例设计模式。所谓设计模式（Design Pattern），指的是在软件开发中针对一些常见问题提出的可复用的解决方式；而单例设计便是针对在面向对象编程中一些只会被实例化一次、或只允许一个实例（instance）存在的类（class）而出现的设计模式。这种对象/实例通常是作为工程中一个全局管理的存在，因此他们会在整个工程的各个角落被调用。由于在面向对象编程的设计中你往往需要通过储存一个对象的地址来随时调用其中的方法和数据，这便可能会造成同一个对象的地址被储存很多次的情况。
在单例设计模式中，你可以通过将单例目标类的构造器（Constructor）设置为private类型使该类无法在外部被实例化，然后在这个类的内部实例一个自己的对象并将其储存在一个静态变量中。同时，你也可以写一个公开的静态getter方法来作为获取和调用这个单例的方式。如此这般，通过使用单例设计模式，你便可以实现一个全局有且只有一个实例的类。具体实现方式我会在下一个部分举例说明。
2. 如何使用单例设计 （Java 范例）
Java是单例设计最常被应用的语言。一个最典型的例子便是java.lang.Runtime中的Runtime class. 该类无法被实例，你可以通过其中的静态方法Runtime.getRuntime()来调用他的单例 object。
除此之外，在软件和游戏开发中还有很多的功能可以利用单例设计实现，以下便是一个用Java通过单例设计实现的可能被应用在游戏和软件中的音频管理器（AudioManager）的简单模型：
/**===========================================
这是一个在游戏中管理音频文件的类，有且只有存在一个。
因此使用单例设计模式。
*===========================================*/
class AudioManager {
// 设置为private，外部便不能再修改这个单例。
private static instance;
// 单例中实际储存的内容。这里使用的数据类型只是作为该单例的应用背景（context），仅供参考，在AudioManager中具体要用什么数据类型来储存音频资料应视情况而定
private HashMap clips;
// ... 此处略过其他AudioManager可能需要的变量 ...
// private 构造器，无法被外部调用
private AudioManager(){
clips = new HashMap();
// ... 此处略过其他可能需要初始化的东西
}
// 单例的 Getter。会且只会实例一个该类的实例。
// 如果担心第一次调用时的速度影响，可以在loading的时候统一将单例设计的类的getInstance方法调用一次
public static AudioManager getInstance(){
// 实例化如果此前没有实例
if (instance == null){
instance = new AudioManager();
}
return instance;
}
// 播放一段音频的方法
public void playAudioClip(String clipName){
clips.get(clipName).play();
}
}
以下是调用方法：
public static void main(String[] args){
AudioManager.getInstance().playAudioClip("BGM");
}
3. 游戏开发中的运用 （Unity）
在游戏开发过程中，我们常常会需要应用到一些负责全局管理的并且只会同时存在一个实例的类，例如上面提到的AudioManager，还有负责管理游戏状态或界面的StateManager和SceneManager，我自己写游戏也经常会写一个负责数据管理的类DataManager。这些类都是有且只有一个实例存在，都可以通过 Part 2 中的方法依样画葫芦实现和调用，这里就不复述了。
在使用Unity开发游戏时，我们往往会要用到一个GameController。在我接触单例设计之前，我都会选择在要用到他的地方存一个变量，然后通过在编辑器中把它拖到inspector，或者使用
gameController = GameObject.FindWithTag("GameController");
来找到它。久而久之，这样不但使代码变得混乱且重复，在速度上和内存空间上也给我一种很浪费的感觉。这个时候，我们可以利用Singleton Design思想，在GameController中加一个静态变量
public class GameController : MonoBehaviour {
private static GameController instance;
void Awake(){
// ... 省略其他初始化相关代码 ...
instance = this;
}
public static GameController GetInstance(){
return instance;
}
}
这样，虽然这个类是绑定Unity中的GameObject被实例的而并非按照此前提到的通过private constructor的方法生成的单例，我们依然可以利用单例设计中的部分思想来使他调用起来更方便。此后，当我们需要调用GameController中的方法时，只需要调用他的单例即可
GameController.GetInstance().MethodName();
4. 小段总结
在我学习OOP中常用的设计模式的过程中，我的教授表达了并不推荐学生使用单例设计的看法。他认为单例设计 “破例的使用了全局变量，破坏了模块化设计的思想 ”。但此后，我在学习过程中多次看到其他教授使用单例设计，Github上也有一些不小的项目用到过单例设计；同时，我自己在游戏开发过程中也常常感受到这种设计模式带来的便利。所以，我觉得只要合理运用，单例设计也不失为一种好的设计模式。
（二）：栈（Stack）1. 什么是栈（Stack）
通常来说，我们认为栈（Stack）是一种抽象的数据类型（Abstract Data Type)，或者说抽象的数据结构（Abstract Data Structure）。之所以说是抽象，我个人的见解是因为这种数据结构并非根据他的内部组成或者实现方式定义的，而是根据其调用方式。举一个简单的例子，链表（LinkedList）是一种由一个一个不同的节点（Node）通过指针连接而成的线性数据结构。他的使用方式和一般的ArrayList没有什么区别，但是由于他们的实现方式不同，导致我们会在不同的情况下使用它们，而他们也被视为不同的数据结构。因此，这些数据结构都是由他们的实现方式定义的。
相比上述提到的数据结构，Stack这个概念本身不会限制开发者如何实现它，而只是抽象的告诉使用者，这个结构会将数据一层一层的“堆叠”起来。你可以通过如图1所示的方法在将新的元素加入（Push）到栈的 顶端（Top），或者获取当前顶端的元素。这样每次从中获得或者移除的数据就是你最后一次加入的数据，这也就是 先进后出（First In, Last Out） 的概念。至于具体如何实现，开发者可以自行决定。很多人甚至会直接把其他的线性数据结构例如数组和链表当作Stack来使用——事实上，Stack通常也只是这两种数据结构之一的外面包一层外壳而已。
图 1：Stack中元素的加入，查看，和移除
相对于 “栈” 这个名词，我个人更喜欢港台地区对Stack的翻译 —— “堆叠”。在我学习编程之初，“堆栈”的用法对我造成了很大的困扰。因为Stack这个词本身的意思就和“堆”差不多，我在用英文学习的时候也是把它视作一种 “将东西堆起来” 的数据结构，因此我常常先入为主的把中文的“堆”（Heap）和“栈”（Stack）的含义弄反。直到很长一段时间以后才从一些中文的资料中发现我之前闹的乌龙……
在内存中，堆和栈代表着不同的意思。由于这篇文章主要讨论的是Stack作为一种抽象数据结构在游戏开发中的运用，在这里我不会讨论他们的其他含义。在之后博客中我也会谈到堆（Heap）作为一种数据结构在游戏开发中的应用，此处就不多提了。
2. 如何实现和使用 Stack （Java）
在这一部分，我将用利用Java中的数组（Array）来实现Stack。之所以使用数组而不是前面提到的链表，是因为这样可以尽量保证Stack使用的是连续的内存空间。虽说在游戏开发中用到Stack的大多数情况下这点优化都几乎可以忽略不计，但养成一个好的开发习惯总归是没错的，更何况你永远不知道什么时候这些小问题会在将来造成更大的影响。
以下便是一个利用java中的数组实现的简单的栈。要注意的是，因为使用的是最普通的数组，我们难免会要面对Stack的容量限制问题。这一点上，我们可以选择接受Stack有容量限制的事实，在超出容量时报错；也可以选择类似java中ArrayList的处理方式，在Stack满了以后扩大容量 （建一个新的数组，两倍于原来的大小，将原数组中的所有元素转移到新数组）。下面的代码选择的是第一种处理方式。
public class Stack{
private T arr[];
private int top;
// 构造器 1： 使用参数容量
public Stack(int size){
arr = new T[size];
top = -1;
}
// 构造器 2：假定默认容量为 10
public Stack(){
arr = new T[10];
top = -1;
}
// 加入新元素 element
public void push(T element){
// stack 已满的情况：
if(arr.length - 1 == top){
// 这里你可以选择扩大Stack的容量或报错
throw new Exception("push(): stack is full")
}
top++;
arr[top] = element;
}
// 移除并返回顶端元素
public T pop(){
// stack 为空的情况：
if(isEmpty()){
// 这里你可以选择报错或其他处理方式
throw new Exception("pop(): stack is empty");
}
T element = arr[top];
// 移除顶端
arr[top] = null;
top--;
return element;
}
// 查看当前顶端元素
public T peek(){
// stack 为空的情况：
if(isEmpty()){
throw new Exception("peek(): stack is empty");
}
return arr[top];
}
// 查看是否为空
public boolean isEmpty(){
return top == -1;
}
}
下面则是使用的范例
Stack intStack = new Stack(); intStack.push(3); intStack.push(2); intStack.push(1); System.out.println(intStack.isEmpty()); // false System.out.println(intStack.pop()); // 1 System.out.println(intStack.pop()); // 2 System.out.println(intStack.pop()); // 3 System.out.println(intStack.isEmpty()); // true
3. 游戏开发中的应用
在游戏开发中，Stack往往是被用来实现 “返回/撤销” 的功能。一个典型的例子就是推箱子类游戏中的撤销上一步的操作。我们可以将每一步的操作或者是坐标信息加入到Stack中，当玩家按下返回/撤销键时将上一步操作从栈中移除并根据其中的信息在游戏中反向操作，这样就可以达到想要的效果。
另一个Stack常常被用到的地方就是在游戏 “状态/窗口/场景” 管理中。在游戏中，我们往往会有多个窗口叠加在一起，或者从一个场景进入到子场景。这个时候，通过在 进入 “新场景/打开新窗口” 时将这个 “场景/窗口” 加入到Stack中，玩家选择返回时再从栈中弹出并销毁。所有的事件和操作都只对当前的顶端的窗口生效，以下是一段简单的示范代码
public class SceneManager{
private Stack scenes;
// constructor
public SceneManager(){
scenes = new Stack();
}
// 刷新当前场景
public void update(){
scenes.peek().update();
}
// 返回到上一场景
public void popScene(){
if(scenes.isEmpty()){
return;
}
scenes.pop();
}
// 进入新场景
public void pushScene(Scene scene){
scenes.push(scene);
}
}
在刚开始学习编程和制作游戏的时候，我使用的都是RPG Maker中用一个变量来指向当前场景，然后在每个场景中保存上一个场景的信息的方法。这样虽然简单，却时常造成了很多重复的信息存取和一些难以预料的bug，直到接触了Stack，我才从中解脱出来。
4. 小段总结
作为一种线性的数据结构，Stack本身并不复杂。大部分编程语言的内置包中都会有Stack, 除非有特殊需求，程序员也往往都不会需要自己编写。不过先了解Stack的原理才能更好的运用它，而且我个人觉得Stack这个数据结构是现实生活中的概念和编程的完美结合，在游戏开发的过程中，它给我带来了很多灵感; 我将来可能还会在讨论一些算法的时候再接着聊聊它的妙用。
（三）：插值（Interpolation）
什么是插值
插值（Interpolation）其实是数学中的一种常用概念，他是利用一种给定函数来连接点的方式。在数学中，插值被用于通过将离散的点数据连接成连续的曲线，来达到补全函数图像的目的。而在游戏开发中，插值则常常被运用于实现动画**（Animation）和 移动（motion）。
所谓插值，代表的是在离散点之间通过插入连续的“估值”来连接他们的概念，而不同的插值方法可以达到不同的连接效果。常用的插值有线性插值，三角函数插值，样条插值等。不同的插值类型会造成在关键点附近图像的平滑程度有所区别，但总的而言，给定的数据点都一定会在图像上，这也是插值与数学中另一个常常被拿来讨论的概念 拟合（Curve Fitting）的区别。
线性插值是直接利用直线来连接点
- 非线性插值产生的图像斜率变化得更为平滑
2. 如何实现和使用插值
插值的类型很多，但调用方式都大同小异，基本上都是给定数据点（起点和终点）以及当前自变量的值为参数，然后返回这个自变量所对应的插值。由于这篇博文主要讨论的是插值在游戏中的应用而非每个插值的实现原理，这里我只以最简单的线性插值和利用三角函数实现的非线性插值为例进行代码实现。
线性插值的实现非常简单，你可以把他想象成路程为（起点 - 终点），总时间为1的匀速直线运动。以下为范例代码：
float LinearInterpolate(float startVal, float endVal, float t){
return startVal + t * (endVal - startVal);
}
非线性插值的主要优势在于在比线性插值在数据点附近会更为平滑，实现例如在起点附近加速，终点附近减速的效果；但他同样是t从0到1，返回值从起点运动到终点。也就是说，只要对t稍加处理，只要两端的0和1不变，就可以达到这个平滑的效果。
我们都知道cos(t π \pi π)的函数图像在 t ∈ [ 0 , 1 ] t \in [0, 1] t∈[0,1]中y值是“平滑”的从1运动-1,在t = 0 附近加速变化，t=1附近减速变化。
所以我们只要稍加变化, 用 (1 - cos(t π \pi π)) / 2 就可以得到我们想要的效果，平滑的从起点运动到终点，如下图所示
以下为范例代码：
float CosInterpolate(float startVal, float endVal, float t){
float t_cos = (1 - Mathf.Cos(t * Mathf.PI)) / 2;
return startVal + t_cos * (endVal - startVal);
}
在unity以及各种有向量概念的游戏引擎中，你也可以直接将数据点参数改成向量类型。由于实现方式除了使用的数据类型以外基本相同，这里就不重复了。
Vector3 interpolate(Vector3 startpoint, Vector3 endpoint, float t);
插值函数具体的调用方法会在下面介绍。
3. 游戏开发中的应用（Unity）
在游戏开发中，插值主要被运用在下列几个方面：
- 将时间作为参数，通过插值来补充某个数据（坐标点、颜色等）来实现平滑的直线运动或者颜色渐变的效果。
以下是Unity中用线性插值实现线性移动和渐变的代码（非线性插值的使用同理，只要改变调用的函数即可；除了上一部分实现的cos插值以外，很多游戏引擎本身也有提供类似的函数，感兴趣的可以去了解一下Unity中的SmoothStep 和 SmoothDamp）。
public class Mover : MonoBehaviour
{
// 在Inspector中设置起点和终点的位置
public Vector3 startpoint, endpoint;
// 从起点运动到终点所需要的时间（周期）
public float period;
// 当前时间参数t
private float t;
private SpriteRenderer spriteRenderer;
// Start is called before the first frame update
void Start()
{
t = 1;
spriteRenderer = GetComponent();
}
// Update is called once per frame
void Update()
{
// 按下空格键开始移动
if(Input.GetKeyDown(KeyCode.Space)){
t = 0;
}
// 更新当前时间,并通过插值获取位置
if(t < period){
t += Time.deltaTime;
// 这里使用的是Unity Vector3中自带的线性插值函数，效果相同只是直接作用在Vector3上
// 以时间为参数，用插值获得起点到终点之间的位置
// 由于插值默认时间t在0..1之间（period = 1），这里需要用 t/period 来转化成动画播放的实际周期
transform.position = Vector3.Lerp(startpoint, endpoint, t / period);
// UnityEngine.Color也同样有线性插值函数Lerp，实现方法一样只是作用与Color(r,g,b,a)
//这里展示的是在移动中从白色转变为黑色的过程
spriteRenderer.color = Color.Lerp(Color.white, Color.black, t / period);
}
}
}
假设你的精灵表单（Spritesheet）中有n个精灵（Sprite）是用于某一个动画中的，那么你可以将时间作为参数，用插值的方法来获得[0, n]之间的精灵索引值（Index）来控制精灵图片的切换速率，实现精灵动画（Sprite Animation）效果。
以下为Unity中的范例代码
public class SpriteSheetAnimator : MonoBehaviour
{
// spritesheet中所有的sprites
public Sprite[] sprites;
// 动画播放一遍所需要的时间（周期）
public float period;
// 当前动画播放时间
private float t;
private SpriteRenderer spriteRenderer;
// Start is called before the first frame update
void Start()
{
t = period;
spriteRenderer = GetComponent();
}
// Update is called once per frame
void Update()
{
// 按下空格键重制时间，从头播放
if(Input.GetKeyDown(KeyCode.Space)){
t = 0;
Debug.Log("Start");
}
// 更新 当前时间t 和 当前精灵图片
if(t < period){
t += Time.deltaTime;
// 利用获得以0为起点，（sprites总数-1）为终点的插值来计算当前精灵图片的index
// 由于插值默认时间t在0..1之间（period = 1），这里需要用 t/period 来转化成动画播放的实际周期
int curIndex = Mathf.FloorToInt(interpolate(t / period, 0, sprites.Length - 1));
spriteRenderer.sprite = sprites[curIndex];
}
}
public float interpolate(float startVal, float endVal, float t){
return startVal + t * (endVal - startVal);
}
}
除了上述两个被详细介绍的方面以外，插值也可以用于碰撞检测（实际上是通过使用参数方程来计算碰撞点是否存在，以后开单章介绍）以及曲线运动（基本和连接函数图像一样，这里就不赘述了）。同时，插值在图形学中也有很多妙用。不过对于游戏开发来说，图形学涉及的部分已经非常底层，这里也同样略过了。
4. 小段总结
总体而言，插值在实现简单的动态效果上是非常实用的，更何况他的实现方式也并不复杂，而且大部分游戏开发工具都会自带插值函数。不过要学习更多有趣的插值函数和运用方法，不是短短一篇博客可以解决的，这篇文章也旨在帮助大家了解插值在游戏开发中最常用到的地方，所以如果有兴趣进一步了解的话还是需要自己去学习。
（四）：队列（Queue）1. 什么是队列
如同栈（Stack）一般，队列（Queue）也是一种抽象的数据结构（Abstract Data Structure）。所以同理的，“队列” 这个名称定义的是你如何从外部理解和使用这种数据结构，而非该数据类型的具体实现方式或者内部结构——你可以根据自己的需求选择用数组、链表等各种各样的数据结构来实现队列
相反于栈的先进后出（FILO: First in, Last out），队列是一种先进先出（FIFO） 的数据类型。就和现世生活中的排队购物一样，先进队伍的人在前面，可以比后进队伍的人先结账并脱离队伍；而新来的人则会加入到队伍的末尾。
与Stack类似，队列也有三个基本的方法：一个用于加入新的元素到尾部 （enqueue入队），一个用于获取并移除队列最前端的元素 （dequeue出队），以及一个用于查看当前队列是否为空。同时根据需要，队列也常常会有用于查看最前方元素（Front）和尾端元素（Rear）的方法，与栈的Peek/Top方法相似。
上面谈到的是最基本的线性队列的概念与结构。事实上，除了这种所谓 “传统意义上的队列” 以外，编程中也有很多功能花哨甚至可能是非线性的数据结构也号称“队列”。一个典型的特殊队列的例子就是很多算法都会运用到的优先队列(Priority Queue)，这个会在以后讲Heap或者寻路算法的时候再详细讨论。
2. 如何实现和使用队列
队列有很多实现方法，其中最简单的便是利用链表（LinkedList）。但在实际运用中，利用链表往往不是最优的队列实现方法，且大多数语言内置的Collection包里也不会用链表来实现队列。如果你对数据结构有一定的了解，就会知道相较于链表，使用数组会有明显的速度和空间使用效率上的优势（尤其是队列容量固定的时候）。但由于这篇博文重点在于介绍队列的概念和使用，为了方便理解这里会采用最直观的链表来实现队列的方法（其实在数据不多的情况下，链表的这些劣势基本可以忽略不急）。
private Node<T> front, rear;
public Queue(){
front = null;
rear = null;
}
// 入队
// add a new element to the rear of the queue
public void enqueue(T e){
// create a node, assign to both rear and front if the queue was empty
// 新建一个元素并插入到队列最前方。如果队列此前为空，那么这个元素会同时为前端和尾端。
if(front == null){
front = new Node(e);
rear = front;
}else{
rear.next = new Node(e);
rear = rear.next;
}
}
// remove and return the front element
// 出队
public T dequeue(){
// throw an error if the queue is empty
// 队列为空时抛出异常
if(front == null){
throw new Exception("dequeue(): queue is empty.");
}
// save front value, remove front node
// 获取队列最前端的值，并移除用于保存该值的Node
T e = front.value;
front = front.next;
// if the removed front is the only element in queue
// both front and null should be null
// 如果移除后最前端的值变为空，则将队尾的值也设置为空
if(front == null){
rear = null;
}
return e;
}
// return true if front is null, meaning no element in Linked List
// 查看队列是否为空
public boolean isEmpty(){
return front == null;
}
// an inner class representing a node in the linkedlist
// 一个node代表链表/队列中的包含一个元素的容器。
class Node<T>{
T value;
Node<T> next;
public Node(T e){
value = e;
next = null;
}
}
}
这里要注意的是，我在上一段代码中使用的是Java语法，但我并没有选择使用Java自带LinkedList，而是直接在队列的类中自己实现了一个简单的链表。事实上，Java的LinkedList类本身就继承了一个Queue的接口（Interface），你可以直接将它当队列来使用，用linkedList.add()来入队，linkedList.remove()来出队。因此，如果在外面再套一层Queue的话会显得有些多此一举；同时，我选择直接在Queue中实现链表的方式实际上也和Java自带的链表类里实现Queue接口中的方法的方式大同小异，这样也更方便理解。
3. 游戏开发中的应用
回合制游戏中的行动顺序队列（Turn Queue）
回合制和半回合制游戏中常常有速度、行动力的概念来决定场上所有单位的行动顺序，这个时候可以通过队列来安排。当然，很多游戏中会有提升或降低速度的技能和物品，这个时候会需要重新生成队列。
管理经营类游戏中的生产队列
很多管理经营类游戏，或者即时战略游戏中都会有生产队列的概念。通过使用队列来提前规划之后的生产顺序可以使玩家操作起来更为方便。一个典型的例子就是文明系列中在城市里的生产列队，提前安排之后需要生成的单位或设施，将后续需要制造的东西依次加入队列，当当前生产任务完成时，从队列中移除并获取下一个需要生成的单位。
行动队列
很多及时战略游戏和MOBA类游戏中都有用队列提前安排之后的行动的功能。例如DotA中可以在TP的时候按住Shift将跳刀加到行动队列中实现落地瞬间跳走，沙王施法前摇时将跳到放到队列中实现跳大等操作。
剧情对话
当剧情对话会因为玩家的选择产生分支的时候，常常需要用树结构来储存，但归根结底，这可以被当作一种非线性的队列。实际运行的时候，还是可以用Queue来储存和操作正在播放的剧情文字，分支产生并被选择以后再将该分支下的对话加入到队列中。
动画播放，多节点移动
游戏动画中，有时候会有沿着一系列节点移动的操作，这个过程可以使用队列来完成，将所有节点按照顺序加入队列，然后用dequeue获取并移除队列顶端的点来实现按照相同顺序移动。
消息、事件的传输和分发
一些网游或者多进程的单机需要用接收、处理从网络或其他进程传入的指令和消息，而当本地在处理消息的时候，其他陆续传入的消息将在队列中等待，然后当前一个任务执行完毕后从队列中获取下一个需要被执行的指令或需要处理的消息。
4. 总结
总而言之，队列是一种非常常见且实用的抽象数据结构。其重点不在实现过程，而是概念和使用方式；很多时候，初学者都会以使用队列的方式来利用数组或链表而不自知。能够熟练和合理的运用和理解这种极简却实用的抽象数据类型可以为游戏开发提供很大的便利。
图片来源：http://www.hp91.cn/ 页游