admin管理员组文章数量:1313131
I have an NxM grid of square cells. traversal can only happen in North, South, East and West directions in the cells. Some of the cells are blocked and cannot be traversed.
A bot is given a start and end location and needs to find the path that takes the least amount of time.
Traversing between neighboring cells costs 1 unit of time. So N cells traversed should be equal to N units of time.
However in this problem there as slight issue. If a bot ends up making a 90 degree turn in any direction. The turn itself (which is in place) will cost 2.3 units of time.
I currently have a simple A* search implementation that is able to accomplish the normal path finding, however I'm stuck on how to incorporate the turn cost, as it can only be known in the third cell that is traversed - in short maintaining a window of length 3 in the path and determining if a turn has occurred.
What is the best way(s) to incorporate such a turn penalty in A* search?
I have an NxM grid of square cells. traversal can only happen in North, South, East and West directions in the cells. Some of the cells are blocked and cannot be traversed.
A bot is given a start and end location and needs to find the path that takes the least amount of time.
Traversing between neighboring cells costs 1 unit of time. So N cells traversed should be equal to N units of time.
However in this problem there as slight issue. If a bot ends up making a 90 degree turn in any direction. The turn itself (which is in place) will cost 2.3 units of time.
I currently have a simple A* search implementation that is able to accomplish the normal path finding, however I'm stuck on how to incorporate the turn cost, as it can only be known in the third cell that is traversed - in short maintaining a window of length 3 in the path and determining if a turn has occurred.
What is the best way(s) to incorporate such a turn penalty in A* search?
Share Improve this question asked Jan 31 at 1:26 Lucinda RigettiLucinda Rigetti 6166 silver badges13 bronze badges 2 |1 Answer
Reset to default 5One simple way is to encode the unit's direction as part of the graph itself. You can do this by making four copies of the graph - one for each direction - and then connecting the each node in each graph to its neighbors in the appropriate graphs.
For example, in the "facing up" graph, each node would be connected to:
- The node above it, in the same graph and with the usual length
- The node to the left in the "facing left" graph, with the cost to turn added to its usual weight
- Similarly with the node on the right
Once the graph is setup, you can run any off-the-shelf pathfinding implementation.
本文标签: algorithmAdding bot turn costs to A* search in pathfinding within a gridStack Overflow
版权声明:本文标题:algorithm - Adding bot turn costs to A* search in pathfinding within a grid - Stack Overflow 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.betaflare.com/web/1741929453a2405487.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
global_min_cost = min(global_min_cost, current_cost)
– aaa Commented Jan 31 at 1:33