use*_*037 8 algorithm performance distance
我在2D网格上进行寻路.
我需要计算距离作为我的启发式算法之一.
此外,如果找不到完整路径,我需要返回最近的点.
计算到双精度的精确距离似乎是不必要的开销.有没有我可以使用的快速近似值,它仍然足够准确以满足我的需求？(在1的舍入精度内)
顺便说一句,路径长度通常只有5-30个节点,所以在最后使用更准确的功能是不值得的.
aio*_*obe 10
如果找不到完整路径,我需要返回最近的点.
在这种情况下,您可以跳过距离计算中的平方根运算,即使用just比较平方距离dy * dy + dx * dx.
这适用,因为一个2 <B 2当且仅当A <B为两个任意距离一个和b.
在2D网格中,这将纯粹用整数实现.
如果你需要非整数值,我可能会选择doubles,直到证明它是一个瓶颈.