Archive

Archive for February, 2008

推箱子游戏的AI求解算法(二)

February 25th, 2008 2 comments

上篇。前面有4个小问题没有解决。具体的问题可以在上篇搜“子问题n”

  • 问题1

这实际上是一个寻路问题,最简单的用一个广度优先搜索就可以找到最短路径。从角色当前位置开始,每次向所有可能方向展开一层,如下图直到扩展到目标位置。根据节点的父子关系能反推出移动步骤。如下图

25_000807_pusher Read more…

Categories: 程序/算法 Tags: ,

推箱子游戏的AI求解算法(一)

February 24th, 2008 1 comment

只有算法,没有代码,希望不会编程的也能看懂(俺每次都这么说,但结果每次都很受伤……)

推箱子游戏大家都玩过吧,在封闭的关卡里分布着若干箱子,玩家控制主角把所有箱子推到指定位置即可过关。

以下是关于游戏规则的一些表述:

  • 关卡中的每一格要么是墙,要么是空地
  • 主角和箱子只能呆在空地上,不能穿墙
  • 主角不能穿过箱子
  • 箱子的目标位置在空地上
  • 箱子数量和目标位置数量相等(但每个箱子并不和唯一的目标位置一一对应)
  • 主角只能往前推动箱子,不能向后或向侧面拉箱子

这是个典型的递归/回溯(好像是这个字吧)搜索问题,栈数据结构的典型应用。和算法课上常常举的老鼠走迷宫的例子差不多,只是一些细节上稍稍复杂一点。

Read more…

Categories: 程序/算法 Tags: ,

法线图可以镜像映射吗?

February 21st, 2008 No comments

早先美术问过我法线图是否可以象diffuse纹理一样应用镜像映射,所谓镜像映射是指对称的模型只画一半的纹理,一半模型正常映射另一半翻转映射。

当时我想了五秒钟回答说不可以,因为很容易想到虽然图像被翻转了,但是像素颜色所代表的法线方向并没有相应翻转,所以凹凸会变反。

但是昨天美术做了个实验却发现采用了镜像映射以后光照的结果看起来却是对的……

回家自己画了图才发现原来想错了。原理很简单,镜像映射的部分UV轴(之一,取决于哪个轴的镜像)也被翻转了。如下图,法线图上偏红的表示法线向U方向偏移(对应纹理空间就是向“右”偏移);做了U轴镜像后,实际上红色就变成表示向左偏移了(仍然是向U轴偏移)。

21_010440_mirror

Read more…

Categories: 程序/算法 Tags: ,