有's a duplicate question with an answer that I'试图在这里实施并遇到困难 . How to do pathfinding when a unit has inertia?
我有一个带有障碍物的网格，计算机可以在四个主要方向上移动，并使用A-star或Djikstra算法实现路径寻找 .
但后来我也想添加"velocity"，所以不是邻居 move left ， move right ， move up ， move down ，它是 accelerate left ，_ 27242411， accelerate up ， accelerate down ， do nothing . 在每次移动时，保留前一次移动的速度，并添加加速度的增量 . Accelerate <dir> 成本为0，而 Do nothing 成本为1 .
我试图用A-star在一维基础上实现这个，让它找到一条从 (X=0, velocity=0) 移动到 (X=100, velocity=0) 的路径 . 可用的选择始终是 (Accelerate Cost=0, Decelerate Cost=0, Wait Cost=1) .
它找到了成功完成任务的次优路径 . 加速仅两次，然后等待49次，减速一次，然后再等待2次，再减速一次降落（ X=100, velocity=0) .
最佳路径是：加速100次，等待一次，减速100次 .
看起来A星可以处理（X，Y）网格中的寻路，其中X和Y是独立的，但是不能处理（X，Y）网格，其中Y也依赖于X.
关于如何修改A *或Djikstra的任何想法，还是我可以使用涉及惯性的替代寻路算法？
您可以在https://gist.github.com/meric/93540d1cff502684aac2查看我的代码
取消注释第120行 filter = function(current) return current.v > 99 end, 会生成最佳路径，因为它会隐藏"wait"选项，直到速度为100 .
使用 lua a-star-velocity-demo.lua 运行 .
1 回答
Dijkstra / A-Star是基于图形的算法，经过验证可以在任何图形上工作 .
这是错的，A-Star和Dijkstra不关心网格 . 由于简单性，经常使用网格：底层图是隐式的（网格是节点，任何两个相邻图块之间都有一个顶点） .
图表表示
是否对您的示例起作用仅取决于您是否将您的系统正确表示为图形 .
首先要注意的是：
这不行 .
x=5, v=8处的船舶与x=5, v=-5处的船舶状态不同 . 因此，您的州由夫妻(x, v)代表 . 这不是一维问题 .要注意的第二件事是：
你没有动力到达'soon'，只是尽可能少地使用
Do nothing. 因此：出于多种原因是错误的：
给定惯性，一个最佳（最便宜）路径实际上是加速（10次），减速（10次）因为
1+2+3+4+5+6+7+8+9+10+9+8+7+6+5+4+3+2+1 = 100并且到达终点 in 19 steps for a cost of zero另一条最佳路径是加速一次，交替（加减速）49次，减速 . 然后到达终点 in ~102 steps for a total cost of zero
还有许多你不想要的类似'optimal'路径（零成本） .
要解决这个问题，无论采取什么行动，都要做一个常数，或者可能是欧几里得距离？ （恰恰相反，我会对应用推力施加一个固定的惩罚，以便在有几个可用时获得最节能的路径，但这是偏离主题的）
修复您的实施
如果您的A-Star实施在我们知道存在较低成本的路径时给出非零成本的结果，那么您有一个需要修复的错误 .
走X，Y
如果您计划在惯性的2D网格中导航，则需要4D节点表示（x，y，Vx，Vy） .
警惕两件事：
_49_在有障碍物的4D中，碰撞检测将比传统的细胞基础运动更复杂 . 为了确保你没有跳过墙壁，使用天真的光线投射，或者（更好）使用Bresenham's Line Algorithm轮询顶点移动 .