我有一个通过约束德洛内三角剖分表示的区域。我正在尝试解决在两点之间查找路径的问题。我参考了Marcelo Kallmann提供的论文来处理这个问题。然而，与Kallmann在论文中提出的使用Chazelle漏斗算法不同，我计划使用A*搜索算法，因为它在网格环境中规划路径非常有效。

对于启发式成本函数，我使用当前节点到目标节点的欧几里得距离来选择邻居节点，我从当前点p到三角形边缘的中点绘制线段。[这个想法是由kallmann提出的]到邻居节点的成本也由它们之间的欧几里得距离给出。

这是Kallmann展示使用边缘中点技术生成通向包含目标节点的三角形的各种路径的图示。

现在，当一个区域的三角形密度不是很大时，这种技术工作得很好。但假设对于一组点的生成三角剖分看起来像这样

我想知道是否有其他技术，如IDA*或ID-DFS，可以提高算法的效率？已经提出了三角剖分减少A*（TRA*），但由于其定义过于正式，我无法理解。TRA*方法的详细信息可以在Demyen的论文第5节中找到。

我很乐意听取一些想法。如果需要分享一些代码，我会编辑这个帖子。

回答：

请注意，ID算法通过重复工作来权衡A*带来的簿记成本，因此可能会使它们更慢（但希望不会慢很多）。因此，您试图提高效率的衡量标准将影响这些算法的有用性。