游戏开发中常用的转载算法

1.与数组相关的算法:

快速排序(分而治之思想的应用):并不是所有情况都适用。数据量小的话，没有冒泡快，但是快速排序真的很优秀。

堆排序:可用于制作游戏排行榜榜首，根据最大K数或最小K数建立最大堆和最小堆，然后将最大/最小堆的根节点与最后一个子叶节点交换，最后调整堆，重复两步，直到得到K数。当然这种问题也可以用红黑树实现的set来做。

二分搜索法:用来找出有分数的玩家。

2.树相关算法

四叉树和八叉树可用于检测大量对象之间的碰撞总数。

3.图形相关算法

1.可以在小游戏中使用的简单寻路算法:

随机寻路算法:当NPC遇到障碍物或边界时(使用碰撞检测)，它会随机选择一个前进方向，继续行走。

跟踪算法:当游戏中的主角进入NPC的“警戒区域”时，游戏的AI可以轻松获取目标的位置，然后控制NPC物体向被跟踪的物体移动。

回避算法:与追踪算法完全相反，即当游戏中的主角进入NPC的“警戒区域”时，主角可以追着NPC跑。

2.大型游戏一般使用A寻路算法:应用最广泛的寻路算法，简单说一下A寻路算法:

公式:f(n)=g(n)+h(n)，g(n)表示起点到任意点n的实际直线距离，h(n)表示任意顶点n到目标点的估计距离(曼哈顿距离公式常用于估计h (n): | x1-x2 | +| y1。

将待处理的方块a存储在“开放列表”中，开放列表是待检查方块的列表；“封闭列表”中充满了不需要再次检查的方块。

每次从开放列表中选择具有最小f(n)的节点时，它被添加到CLOESE列表中。同时，相邻节点被扩展并添加到开放列表中。开放列表可以看作一个优先级队列，键值为f(n)，优先级最高的排在最前面。

最后，直到端点被添加到开放列表，指针指向被计算。所以最后的路径是，从终点沿着父指针到起点，最后回到起点，这样最短的路径就找到了: