【求助】斜45度瓦片地图A星寻路启发函数(对角线距离)问题求助

/**
   * 对角启发函数
   * @param node
   * @return
   */
  diagonal(row1, col1, row2, col2) {
    var dx = Math.abs(col1 - col2)
    var dy = Math.abs(row1 - row2)
    var diag = Math.min(dx, dy)
    var straight = dx + dy

    return this._diagCost * diag + this._straightCost * (straight - 2 * diag)
  }

在斜45度地图中,通过如上启发函数计算h值,最终寻找出来的路径不对。如上图所示从(42,14)走到(38,12)格子路径不对,白线是正确的路线,红线是错的。我觉得原因是启发函数有点问题,希望大佬们帮忙看看解决一下,跪谢。

Git 源码地址:https://github.com/cengbin/web-example/blob/master/example/mygame/AStar.js#L144-L151

Demo演示地址:
https://cengbin.github.io/web-example/example/mygame/index.html

1赞

你的答案在这里,可以参考里面的寻路算法 有做大型RPG或SLG游戏需求的朋友请进,有在线地图编辑器

启发算法有问题,注释一下你的思路再说吧

不是算法有问题,和楼主沟通过了,他截图里面的屏幕坐标不能用于寻路,必须做转换为以斜向的坐标作为寻路坐标

好像是消耗不对吧

楼主用我的方法已经解决问题了。是他的坐标不对,必须转换斜向坐标。

找不到 git启发函数源码地址 的服务器 IP 地址。

各位问题已经得到解决。解释一下:如上图所示,在斜45度瓦片地图中,需要把斜45度瓦片地图的网格坐标转换成斜45度砖石地图的网格。例如:(0,0)是斜45度瓦片地图的网格坐标,然后通过上图中的右下方公式计算得出斜45度砖石地图的网格(0,4)。然后通过斜45度砖石地图的网格坐标计算h值(也就是目标点到终点的预估代价值),通过曼哈顿距离算法求h值即可。非常感谢@tangxuanli2014大佬的热心帮助和支持,笔芯。

2赞

插个眼。。。