我需要让用户在网格上绘制路径但没有精确度 - 算法应该调整路径 .
示例图像,其中红线表示用户将绘制的连续路径,蓝点是最终路径
或
由于我不需要最佳路径,我无法逃脱寻路
我需要在每个用户输入上 update ( while drawing red line )
我正在考虑关于交叉点(红点)的事情,所以我会在列表中添加交集到路径查找,直到当前输入和可能是一些加权图方法,但没有最终的想法 . 对此我有任何建议 .
只是为了确保我看到它正确的方式:
直线表示使用最佳路径
曲线意味着尽可能接近它......
因此,将用户给定的路径作为一组点进行采样
删除所有不在路上的点
将它们与网格对齐
使用分段最佳路径查找
可以用我的A* algorithm
[笔记]
你可以一步完成2,3步骤
可以避免对相邻单元路径使用A *
可以使用上一篇文章中的A *数据(无需清除缓冲区,只需从上次使用的索引中继续...
除非你的输入路径是圆圈...
在任何时候你都可以改变X或改变Y,而不是两者,所以你可以使changeX成为一个布尔值,其中changeY为NOT . 假设changeX为true . 然后你只需要取用户输入的X坐标 . 反之亦然〜用户输入的changeX和Y坐标 .
变量changeX只能在交叉点改变 . 决定是否更新的一种方法是计算哪个下一个点最接近指针 . 您只需要比较距离的平方,这样就可以节省昂贵的平方根计算 .
你可以在那个基础上计算每一个下一个点,但是当网格是正方形时,这可能是过度的 .
2 回答
只是为了确保我看到它正确的方式:
直线表示使用最佳路径
曲线意味着尽可能接近它......
因此,将用户给定的路径作为一组点进行采样
删除所有不在路上的点
将它们与网格对齐
使用分段最佳路径查找
可以用我的A* algorithm
[笔记]
你可以一步完成2,3步骤
可以避免对相邻单元路径使用A *
可以使用上一篇文章中的A *数据(无需清除缓冲区,只需从上次使用的索引中继续...
除非你的输入路径是圆圈...
在任何时候你都可以改变X或改变Y,而不是两者,所以你可以使changeX成为一个布尔值,其中changeY为NOT . 假设changeX为true . 然后你只需要取用户输入的X坐标 . 反之亦然〜用户输入的changeX和Y坐标 .
变量changeX只能在交叉点改变 . 决定是否更新的一种方法是计算哪个下一个点最接近指针 . 您只需要比较距离的平方,这样就可以节省昂贵的平方根计算 .
你可以在那个基础上计算每一个下一个点,但是当网格是正方形时,这可能是过度的 .