现在的位置: 首页 > 综合 > 正文

HTML5–TD游戏之A*算法

2013年09月02日 ⁄ 综合 ⁄ 共 575字 ⁄ 字号 评论关闭

使用 A* 算法(Dijkstra算法?)寻找从 (x1, y1) 到 (x2, y2) 最短的路线

如果输入的坐标已经是终点了

-2 表示未探索过,-1 表示不可到达

当前一步探索的格子

* 得到指定坐标的邻居,即从指定坐标出发,1 步之内可以到达的格子
* 目前返回的是指定格子的上、下、左、右四个邻格

* 取得当前一步可到达的 n 个格子的所有邻格

 * 从终点倒推,寻找从起点到终点最近的路径
* 此处的实现是,从终点开始,从当前格子的邻格中寻找值最低(且大于 0)的格子,
* 直到到达起点。
* 这个实现需要反复地寻找邻格,有时邻格中有多个格子的值都为最低,这时就从中
* 随机选取一个。还有一种实现方式是在一开始的遍历中,给每一个到达过的格子添加
* 一个值,指向它的来时的格子(父格子)。

// 在邻格中寻找最小的 v

// 找出所有 v 最小的邻格

// 从 v 最小的邻格中随机选取一个作为当前格子

 * 到达终点

 * 道路被阻塞

/**
* 下一次迭代
* @return {Boolean} 如果返回值为 true ,表示未到达终点,并且道路
*      未被阻塞,可以继续迭代;否则表示不必继续迭代
*/

/**
* 从起点到当前格子的耗费
* 这儿只是简单地把从起点到当前格子需要走几步作为耗费
* 比较复杂的情况下,可能还需要考虑不同的路面耗费也会不同,
* 比如沼泽地的耗费比平地要多。不过现在的版本中路况没有这么复杂,
* 先不考虑。
*/

// 不可通过或有建筑挡着

抱歉!评论已关闭.