要你走到一个目标,你怎么办?1.先想好如何走。 2.管它呢?先靠近再说。 你要么是预先想好,要么是凭借你的直觉。预先想好,电脑的工作方法有很多。可是直觉,电脑就不能和你比了。你的直觉拆开来是怎么样的呢? 起步,位置一、位置二,哪个离目标近走哪个。听起来好像挺简单,实际上还有一点问题,这里的近并不是空间直线距离,而是通常情况下从那个位置走到目标的距离,或者说步数。 例子: __O__ _+++_ _+_+_ __P__ _:地板 +:桌子 O:目标 P:You 如果这些符号伤害了你的感情,那么很对不起。你会向上走吗?只有两种可能!你想翻桌字;你是个思想叛逆的人。那么你为什么要向左或右走呢?很简单,从左或右边,离目标更近。 尽管空间直线距离变远了,但它离目标确实近了一步,让我们数出走到目标的步数(当然,你不能翻桌子): 21012 3+++3 4+8+4 56765 发明数字的人应该成为神,看,问题变得多么简单明了。我们只需证明:只要向着距离目标需要步数更少的方向前进,一定能到达目标。当然有一个前提:如果一点能走到目标,它周围一定还有一个离目标更近的点。 我不知道怎样很好的证明以上的结论,但相信你和我一样对它深信不疑,假如你怀疑,请不要相信本文其它内容。 一个奇怪的+混在里面是不是很麻烦,怎么办呢?不如这样: 253 254 255 254 253 252 000 000 000 252 251 000 247 000 251 250 249 248 249 250 啊哈,0:多美妙的数字,现在可以说,只要一直向着更大的数字走,一定能找到目标,前提:实际与目标连通。 把它扩展一下:一快地图,中间是255,依次铺开,记录着到中间的距离(255-当前值),在这块地图的任何一点,我们都知道如何走到中间。 … 254 … 254 255 254 … 254 … 如果我现在说一切都结束了,你会不会发现什么问题?这好像只能走到中间。也许你自己有一个答案:把目标看作中间就可以了。我不能说你错,但是有更合理的方法来利用这种数据。 这种数据对于传统的战棋游戏再合适不过了,首先我们来说说传统的战棋游戏。 首先你操作一个战斗单位移动,你要先知道它可以行走几步,在几步内可以到达的范围。然后它走到该范围内你指定的位置。 以单位为目标的距它 n步以内 的范围=从目标出发 n步以内所能到达的范围。我不想证明,你应该可以理解。 从战斗单位的位置走到指定位置的路线,可有它的反向路线再反向得到。 实际上,我通过一些尝试得到结论,这种类型的数据可以作为即时战略的预处理数据,可以大大提高寻路效率,当然不是直接使用,以后再说吧。
这种数据的计算,可参照如下伪代码
距离(目标x,目标y)=255’其它的均归零 For STEP= 1 to 步数 For a = 目标x-STEP to 目标x+STEP For b= 目标y-STEP to 目标y+STEP IF 周围最大距离(位置(a,b))〉距离(a,b) THEN 距离(a,b)=周围最大距离(位置(a,b))-1 END IF NEXT b NEXT a NEXT STEP
希望对你有帮助。^_^ 生物LIGHTS随时侯教。OICQ:1905202 E_MAIL:LIGHTS@WOCALL.COM
|