说道寻径，就会说到A*。其实我对A*并不十分熟悉，在一个游戏制作参考书中看到过。作者提出了使用A*的几点注意：不要使用C型地图。

　　以前观察《星际》中的人物寻径，觉得很不可思意。无论是C型还是面条型，它都能立即做出正确的反应。

　　如果地图可以看做一张数据结构图，由点/线构成，则有以下概念（我称之为“路径分析”）：

1，挂支：树结构的路径，它的树根连接在某个“区域”上；

2，区域：图中消除挂支后，由“桥”独立出来的子图，定义为一个区域；

3，桥：  同数据结构中图的桥，但排除了挂支；

4，广义区（连通分量）：互相可到达的路径的集合，包括区域、挂支。而桥只是一个抽象概念，一个路标；

5，整图：由单个/多个广义区组成。两个广义区之间是互不可达的；

// 区域/挂支为人物可能存在的位置，即区域/挂支组成了整个地图，桥等只是抽象出来的某个坐标范围。

　　一旦能够整理出上面的信息，则地图寻径将变得非常之简单。通常，一张看上去很复杂的图形，“路径分析”后将变得非常简单。看下面这张普通的地图，和路径分析后的路径图：

（图中白色表示可行的区域，xx色表示不可行，红线表示路径分布）

这是一张实际《星际》地图的简化图。分析后，整图包括1个广义区；该广义区包括1个区域，0个桥；该区域包括1个分支；该分支为深度为1的树！

人物平时处于某个区域/分支中（在此图只能是分支了），任何两个地点间的寻径，都是同分支内寻径，直接用树寻径就可以了。

另外：参见此图：如果路径分析后的信息足够多，比如包括分支（树）的结点号，层次，则同一分支（树）内的寻径，直接比较层次和结点号，就能立刻迈出第一步！！CPU反应周期应在50以内！！！

实际上可以看到，“路径分析”后，除了区域内的寻径比较麻烦外，其它都是树寻径，非常简单。对于一半的地图，可在区域中建立固定路由，这样，所有的寻径将非常之快速！！！

如果两个地点间是不可到达的，则有信息表明它们位于不同的“广义区/连通分支”内；

缺点：

    1，由于利用了图的分析，该图的简化程度太过火了，导致有时会失真。如果加上失真处理，编程将更复杂，但效率不会影响太大；

    2，该算法主要是对“分支”的裁减，利用树寻径来加速地图寻径。所以，对环路太多的地图效率不高；我分析过，地图为255*255的星际地图，最多可能有30*30=900左右的环路，建立固定路由的话，需要900*900=810，000约1M单位；（但我们可以对此类地图不采用固定路由，如A*，别忘记了哦？）

　　关于算法“路径分析”：这个算法花了我一些时间，计算后，还需要调整，具体不难，，但我不知道该不该公开它。。。。
　

-----------2003.6.20 新增  算法介绍----------

一、矩形分析（建议利用纸/笔实践）

1，任何地图模型必须转换为矩阵，比如 int Map[256][256]。并且 Map[i][j]  代表了该坐标可能的地图类型，如：平地、边缘、高地、水池等。并且，（i,j）到（i,j+1）是否可行决定与 Map[i][j]是否等于Map[i][j+1]；

2，对每一个可行的单元（2个for循环），如果改单元没有被计算，则：

　　2.1，以该单元为左上角，长/宽=1，建立一个矩形；

　　2.2，往右/下扩张该矩形，使得其四个顶点都至少与1个“障碍”相领（关键）；

　　2.3，尽量扩张2，可选择 宽度或高度优先；（次要）

 3，重复2，直到所有的地图单元都被计算，所有可行的单元都应该属于且只属于1个矩形；所有的矩形被保存，包括了位置信息（可以对非可行单元也建立矩形，但无必要）

二、路径/门

简述：所有的矩形充满了整个地图，并且这些矩形是不叠加的。“矩形算法”使得矩形间的相邻只可能在单个边上。并且，任意2个矩形只可能有1段相邻边，该范围称之为“门”，它是矩形到矩形路由的必经之路！

　　最重要的，由于矩形的4个顶点都必须与障碍相邻，则不可能出现三个矩形相邻于1个单元的情况！

1，分析所有的门：对每个矩形，扫描它的四条边，如果发现有其它矩形的痕迹（检查该单元所属的矩形号），则识别了该门（该算法没什么难度）；

2，所有的矩形中心点到各门，画一条线。由于门是被2个矩形共有的，所以，该线也将连接所有的矩形，所有的路径。实际上，它的样子就是我在上面给出的图形！

3，还需要许多新的概念，比如连续多个矩形连成1个长条，则它们可合并为一条“路”。任何两点间寻径，如果是同属于1个矩形，则直线走即可等等。。。

------------ The End. ----------

实际上需要许多调整，比如按照宽度优先取得的矩形“偏宽”，则需要切割/合并，使得误差减少。。。

环路太多，且周长很小，则可以分析该环路与周围各“门”的远近，在一定的误差率下忽略它。。。

如果各位有空，利用程序实现它，会发现很好玩的 :)