游戏开发中常用的基础算法

　　游戏开发这东西，有很多现成的代码了，主要看效率，起码要对常用算法有基本概念，那么在游戏开发中经常使用到的算法是有哪一些呢？下面将给大家进行介绍一下，有在学习游戏开发的朋友们可以参考学习一下。

　　算法一：快速排序算法

　　快速排序在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。在事实上，快速的一些排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环（innerloop）可以在大部分的架构上很有效率地被实现出来。

　　快速排序使用分治法（Divideandconquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

　　算法的步骤：

　　1.首先是从数列中挑出一个元素，称为“基准”（pivot），

　　2.需要重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

　　3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

　　递归的最底部情形，就是数列的大小是零或一，也就是永远都已经被排序好了。虽然是会一直递归下去，但是这个算法最终是会退出的，因为在每次的迭代（iteration）中，它至少是会把一个元素摆到它最后的位置去。

　　算法二：归并排序

　　归并排序（Mergesort）是建立在归并操作上的一种有效的排序算法。这个算法它是采用分治法（DivideandConquer）的一个非常典型的应用。

　　算法的步骤：

　　1.申请的空间，使其大小为两个已经排序序列之和，使用该空间用来存放合并后的序列

　　2.需要设定两个指针，最初位置分别为两个已经排序序列的起始位置

　　3.要去比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

　　4.需要去重复步骤3直到某一指针达到序列尾

　　5.将另一序列剩下的所有元素直接复制到合并序列尾

　　算法三：BFS也就是(广度优先搜索)

　　所谓的广度优先搜索算法（Breadth-First-Search），它是一种图形搜索的算法，可以简单的来说BFS它是从根节点开始，然后是沿着树(图)的宽度遍历树(图)的节点，如果所有节点均被访问，那么算法中止。BFS它同样属于盲目搜索，一般用队列数据结构来辅助实现BFS的算法。

　　算法的基础步骤：

　　1.首先将根节点放入队列中。

　　2.从队列中取出第一个节点，并检验它是否为目标。

　　如果找到目标，则结束搜寻并回传结果。

　　否则将它所有尚未检验过的直接子节点加入队列中。

　　3.如果说队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

　　4.最后是重复步骤2。

　　在游戏开发中使用到的算法还算是比较多的,以上是几个基本的算法的简介，希望能帮助到大家，算法它算是一个比较难的编程内容，不仅是要求有一定的数学逻辑思维，更重要的还是实际的一个使用操盘。