好 先来朵花 渲染一下气氛
早先写了个寻路的demo 现在总结分享下
核心算法采用流行的A*寻路算法
Demo大概是这样的：通过cegui(界面库)添加些障碍物 地形用一个简单的平面来代替(因为demo的重点是寻路 能简化
的就简化了) 场景中有几个主角人物乔峰(天龙里的模型) 通过左键选择一个或多个主角 右键确认寻路目标点 主角会绕开障碍物进行寻路 感兴趣的可以从这里下载
http://wildpigdev.googlecode.com/svn/trunk/ 

 整个寻路主要有3部分组成：1.寻路准备 2.寻路 3.优化路径点
1.寻路准备
在选定要移动的角色后 右键确定目标点 首先发生的是寻路准备
寻路准备是指确认角色要搜寻的范围，开始位置，目标位置 在demo中 我们以人物为中心建立了一个N*N的搜寻方格 一般说来 方格的数量越多 那么搜寻就越费时 方格的大小决定了搜寻的精度 我们在检查此方格是否可以通行时
是以方格的大小作为碰撞的包围盒大小 如果此方格的包围盒和障碍物的包围盒产生碰撞 我们就认为此方格是不可
通行的 在寻路时将排除该方格 如果方格越小 同样的搜寻范围就需要更多的方格 但产生的路径就越精细
2.寻路
贪心算法的思想 算法有两个列表称之为开放列表和闭合列表 一开始都为空 开放列表加入开始方格 每次都从开放列表中选择一个算法认为是最接近目标点的方格 我们称之为代价最小的方格 然后 从开放列表中删除该方格
接下来 判断此方格是否为目标方格 如果是 寻路结束 如果不是 加入到闭合列表 检查该方格周围的8个邻居 对每个邻居 如果该方格不在开放列表 也不在闭合列表 并没有和障碍物发生碰撞 那么 把该方格加入到开放列表中 并在同时计算代价 还要注意为该方块记录其行走路径 也就是从哪个方块走到哪个方块的 一直循环到开放列表为空
或找到目标方格 在找到目标方格后 根据其行走路径可以往前倒推到开放方格 形成一条路径 当然 也可能找不到
路径
3.优化路径点
优化路径点的思想是尽量使路径直线化 demo中没有做这步优化 算法比较容易实现 从起始点到最后一个点 对于路径中的每一个路径点A 依次检查位于其后的每个路径点B1,B2... 如果A与B1是互相可见(中间无障碍物)的且A与B2也是互相可见的 则B1点是可以去掉的 于是路径变成了A,B2...
放几张截图：




动态寻路：
增加动态寻路的角色更新逻辑：
为了避免重复寻路 每个角色有一个碰撞列表

1. 初始化该角色的碰撞列表为空
2. 得出和该角色发生碰撞的其他角色colChas
3. 如果colChas为空，更新碰撞列表为空，goUpdate()
4. 如果colChas不为空，检查是否有新的碰撞角色(即原碰撞列表中没有的角色)
5. 如果没有 goUpdate() 更新列表
6. 如果有 判断优先级(只判断状态为go状态的) 如果是最高的 重新寻路 更新列表 如果不是 不作什么 更新列表