Python Libtcod : How to do pathfinding with variable move cost terrain?

Question

我正在使用 Libtcod 和 Python 构建一个回合制策略游戏。游戏 map 具有可变地形，每个方 block 可以是 5 种类型中的一种:

• 平原 - 移动成本 1
• 森林 - 成本 2
• 河流 - 成本 4
• 希尔 - 成本 3
• 山 - 不可逾越

每种类型都有自己的移动成本，例如，穿过平原比穿过森林需要更少的“移动点”。我想显示一个单位在给定移动范围/起始移动点后可以移动到的所有方 block 。

Libtcod 具有为 A* 和 Dijtskra 构建的寻路功能，并且在不考虑地形的情况下显示给定范围内的所有方 block 是微不足道的。

但是，我不知道如何在不必编写自己的寻路算法的情况下实现地形成本。查看文档我知道它与以下内容有关:

def path_func(xFrom,yFrom,xTo,yTo,userData) : ...
path_new_using_function(宽度，高度，path_func，user_data=0，diagonalCost=1.41)
dijkstra_new_using_function(width, height, path_func, user_data=0, diagonalCost=1.41)

但我不知道自定义函数应该做什么。根据文档，它应该

...return the walk cost from coordinates xFrom,yFrom to coordinates xTo,yTo. The cost must be > 0.0f if the cell xTo,yTo is walkable. It must be equal to 0.0f if it's not.

但是，这不是 dijtskra 算法的出发点吗？也就是说，该算法应该考虑每个瓦片的可变成本，然后相应地构建路径。

map 本身已经应用了地形和移动成本，我只需要一种方法将这些数据与寻路联系起来。

Answer 1

我自己实现了用于美学步行路径生成的 A* 算法；根据 A*，考虑到增加的步数，其中包括仅在可能时才放置的桥:

https://github.com/lillian-lemmer/sshrpg/blob/master/plotbrush/mapgen.py#L622

如您所见，您需要做的就是操纵 A* 算法来增加 map 上特定类型/属性的图 block /点的暂定分数(开始成本)。

如果您查看第 660 行，我将水的 tentative_g_score(从开始开始的成本)增加了 8，所以这就像说“如果备选方案是走 8~ 步就可以建一座桥”周围。”在您的 A* 算法中包含切片数据，而不仅仅是笛卡尔坐标，是根据 map 的属性对算法进行调整的好方法。