Tire 树又称单词查找树、前缀树，是一种哈希树变种的树形结构。核心思想是空间换时间，利用字符串的公共前缀来提高查询效率，常常被应用字符统计、检索等场景，比如搜索引擎的词频统计和提示等

原理

前缀树的存储原理很简单，即合并字符串相同的字符前缀进行存储。

比如，存储dog、cat、doing三个字符串的树结构：

AOI（Area Of Interest）翻译过来称为“感兴趣的区域”，用于计算玩家与玩家（或其他 Entity）之间彼此进入、离开、移动视野的算法。通俗的解释比如，玩家离开某个地图时，计算出需要通知的其他玩家。

AOI 模块是多人联机游戏服务器中很重要的功能模块之一，AOI 模块的“好”与“坏”会很大程度上影响服务器的性能。

思路

当一个玩家进入场景后，首先要计算出场景中的其他所有玩家并放进对象集合（又称观察者集合），之后该玩家的进入、移动、离开或其他行为都将会一一通知该集合内的玩家，并且每个玩家都需要维护这样一个对象集合。

Watchers 观察者集合，即能够看到我的其他玩家或实体。

需要注意的是，该对象集合内的玩家列表会随着玩家的行为发生变化，在玩家离开场景后清空对象集合。

BitMap（位图）是一种以 bit 方式存储数据的数据结构，以此来提高空间利用率。

定义

BitMap，通过字面意思理解利用 bit 映射数据的存储结构。所以它应该有 Key、Value，Key 是 bit、Value 是要存储的具体的值。核心思想是通过 bit 来记录数据是否存储：0 不存在、1 存在。

定义一个长度为 8 的 bit 数组，从 0 ～ 7 分别映射对应的整型数值。

当整数 4 存储时，则改变对应 bit 的状态（值）。

这样做带来的好处，同样一个整数在数组中存储需要 4byte*8bit=32bit 空间，在 BitMap 中只需要 1bit 空间。

JPS 寻路算法是基于 A*计算过程中查找节点冗余、效率较低等问题优化的一种算法。

背景

A*是比较常见的寻路算法，但存在一个较为明显的问题，当移动到新的节点总是会把相邻节点（4、8）加入到待查找列表。这样带来两个问题

1. 在多条移动路径成本相同时，冗余查找。

2. 待查找节点过多，内存使用率过高。

寻路算法是游戏比较重要的组成部分之一，尤其在国内游戏很常见的自动寻路系统，比如操纵角色从 A 点到 B 点的移动。计算最短路径有很多不同的算法，比如：Dijkstra、AStar（A*）、NavMesh（多边形算法）、RVO 动态避障等等

A*寻路算法

寻路算法的移动路径核心有 2 点：最短、可移动。

所以首先需要确定起点坐标的相邻节点（4 方向、8 方向），然后通过计算最靠近终点坐标的相邻坐标（不考虑障碍物）确认检索方向，再去计算“相邻坐标”移动的下一个坐标（距离终点坐标最近 & 可移动），重复计算这个过程直至找到终点坐标，这就是 A*算法

A*算法是一类基于网格的寻路算法，也就是把地图看作一个由网格组成的矩阵，每个坐标就是一个网格。

一张 3x3 地图

链表是一种不需要连续空间存储的线性数据结构，通过指针把数据节点链接起来。数据节点的逻辑顺序取决于链表指针链接的先后顺序，同时，链表也有：单链表、双链表、循环链表等多类。

定义

链表是由一系列节点组成，除此之外链表还有几个基本概念：

• 数据节点

  一般由两块组成：数据域、指针域。

• 首元节点

  链表的第一个数据节点。

• 头节点

  非必要节点，放在第一个数据节点前。一般用于存储链表的信息（比如说链表长度等）和保证数据节点操作的统一性。

• 头指针

  指向第一个节点的指针，如果有头节点则指向头节点，否则指向首元节点。

单链表

最简单的一种链表，只支持一个遍历方向：链头 -> 链尾。两部分组成：当前节点的数据、指向后置节点的指针（尾节点指针指向nil）。

2009 年 Go 语言首次发布后，支持泛型一直以来呼声最高的功能之一。十年磨一剑！Go 官方终于在 2022 年 03 月 15 日发布 go1.18 stable 正式支持泛型

什么是泛型

泛型的核心是把类型参数化，通俗的来说就是允许使用时才指定类型的一种设计。

假设有个两变量相加的需求，且这俩变量可能是 int 或者 string，简单粗暴就直接定义两个函数分别支持 int、string

1
2
3
4
5
6
7
8
9

// 传统写法
func AddInt(arg1, arg2 int) int {
	return arg1 + arg2
}
func AddString(arg1, arg2 string) string {
	return arg1 + arg2
}
AddInt(1, 2)
AddString("a", "b")

那如果使用泛型来定义呢，它的写法大概是这样的

定义

Golang中的特殊函数，会先于main函数执行且不能被调用。该函数无入参、返回值，同时支持选择性定义。也可以选择定义多个init函数，但建议只定义一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

package main

import "fmt"

func init() {
	fmt.Println("init1")
}

func init() {
	fmt.Println("init2")
}

func main() {
	fmt.Println("main")
}
// init1
// init3
// main