Monthly Archives: June 2011

读书

黑客与画家

《黑客与画家》,不管这本书的内容如何,至少这个书名是吸引我的。

Hackers同画家一样,同样是创造者。不同的是画家用的是画笔,Hackers用的是Code。

如同绘画一样,具备必要的技能是必不可少的,但真正重要的不是技术,而是创造力。技术只是将想法具体化的一个手段。

vicalloy的庄家

LBForum新主题V2EX发布

V2EX主题演示地址: http://vik.haoluobo.com/lbforum2/
项目地址: https://github.com/vicalloy/LBForum
站点工程地址: https://github.com/vicalloy/lbforum-site

LBForum原始界面(http://vik.haoluobo.com/lbforum/)用的是FluxBB的模板。
V2EX出来后很喜欢V2EX的UI,一直想再做套V2EX的SKIN,直到最近才真在开始动手。
V2EX的设计思想和传统的论坛还是有些不同,有些地方和LBForum的设计不太兼容,针对V2EX的模板添加了部分设置。

lbforum-site项目默认用的是FluxBB的主题,如果希望切换到V2EX的主题只需要新创建一个配置文件local_settings.py,并在其中加上SETTINGS = ‘v2ex_settings’即可。

vicalloy的庄家 编程

Snake Challenge算法思路

Snake Challenge是GuruDigger推出的一个活动。游戏脱胎于经典的贪吃蛇,双方用程序控制snake,在规定步数内吃到最长的为获胜方。该平台的SDK以及范例放在BitBucket上,部署好的比赛平台在 http://pythonvsruby.org 。比赛平台上4四个房间,可以任意选择一个房间开始比赛(访问速度好像很悲催,我的snake一直掉线)。

我的AI程序在:https://bitbucket.org/vicalloy/snake-challenge 对应的目录为:snake-challenge/examples/vicalloy

下面简单的介绍一下主要的算法思路:

地图的表示

简单的说就是将地图上的障碍物实物等标记出来,这是整个程序中最简单的一部分。地图可以简单的用二维数组(python中实际为list)表示,数组中的值代表地图上的物品,如 0:BLANK 10:EGG 20:WALL。

查找目标食物

选择哪个食物

服务端会返回所有的egg和gem信息,要找到食物是很容易的,真正的问题是具体要选那个。

我们当然希望去吃最近的食物,或扎堆的食物(虽然远点,不过食物多),只是在真实环境下问题会非常多。如何才是最近,有些食物虽然看起来近,但算上绕过障碍物的距离就不近了。扎堆的食物看起来不错,问题是你没等你到那里,食物已经被别人给吃光了。如果想做到最优,那绝对不是一件容易的事。

既然不管怎么做都很难做到最优,倒不如简单些,直接选择忽略障碍物后距离最近的食物。

面对顺道的食物该怎么办

snake challenge中食物是会慢慢增加的,可能走到一半,你发现身边有个食物离得更近。这时候是否应优先去吃更近的?首先,我们说的更近都是忽略障碍物的情况下,虽然看上去近,但不一定真的近。其次原先的食物,虽然看上去更远,但不少路程已经探索过了,绕过新食物的路径是完全没有探索过的,更换目标也并不见得更好。路边的野花还是等下来采吧。

绝对不能吃的食物

有些食物刚好放在了陷阱里,吃完后无论如何都逃不出去。根据上面一条不吃野食的规定,你会绕着食物团团转,死不了也活不了。

我们加个步数的限制,如果食物距离5步以内,但你已经走了15步都没能将食物吃到,这时候还是换个目标吧。

寻路算法

寻路,就是如何才能最快的到达目的地。寻路算法中听的最多的就是A*算法。A*算法的核心思想是:

  1. 查看下一步能去的位置(去除障碍物等)
  2. 从下一位置中剔除已经走过的位置
  3. 算出所有:下一位置到起始位置的距离+下一位置到起始位置到目的地位置的具体
  4. 选择总距离最短的位置
  5. 将当前位置加入已经走过的位置列表
  6. 没看明白的自行google

对我们的贪吃蛇来说,可以将A*算法做到非常的简化。首先snake无法走斜线,无法后退,snake能去的位置只有三个,而且离当前位置的距离都为1。因此,我们只需要计算3个位置中那个位置离食物最近即可。在计算到食物的距离时,延续查找最近食物的方法,忽略障碍物。

除障碍物外,地图上还会有些危险物品,敌方的食物或是已经走路。

地方的食物,吃过后会变短,但还不至于挂掉。已经走过的路,虽然尽量不要走,但无路可走的时候,反倒也是个选择。

我们根据地图属性,给位置打分,然后选择得分最高的位置。

空(远离目标): -9

空(靠近目标):9

空(不变):0

敌方食物:-20

已经走过的路: -40

墙:-999

蛇:-888

陷阱

地图上总会有些小陷阱,进去后发现是个死胡同,怎么都出不来。

做个递归,查看N步内是否有解,如果没解,那这步就别走了。