单位有惯性时如何寻路？ [英] How to do pathfinding when a unit has inertia?

问题描述

我目前正在为单位正在移动但具有惯性的游戏进行寻路。大多数典型的寻路算法（A *，Djikastra等）都只是为了最小化路径的长度而设计。

I'm currently working for pathfinding for a game where units are moving, but they have inertia. Most typical pathfinding algorithms (A*, Djikastra, etc.) are simply designed to minimize the length of the path.

但是，就目前而言，这些技术并不适用我知道，在单位具有惯性的情况下。如果单位具有惯性，则根据您要移动的方向，将瓷砖留在特定方向上的成本会有很大差异。

However, these techniques do not apply, as far as I know, to instances where the unit has inertia. If the unit has inertia, then there is a significant difference in the cost to leave a tile in a particular direction based on the direction you want to go.

例如，如果您从东方进入瓷砖，则离开北方前进的费用要比从南方进入瓷砖的费用高得多。 （在前一个示例中，您必须放慢速度以阻止东西向运动，而在后一个示例中，您可以直接通过。）

For example, the cost of leaving a tile proceeding North is significantly higher if you entered the tile from the East than if you entered from the South. (In the former example, you would have to slow down to halt you East-West velocity, while in the latter, you could go straight through.)

系统具有惯性，这意味着要转弯，您可能必须在转弯之前充分减速。迄今为止，我最好的想法是您计算出减速所需的额外时间，然后将其添加到移动的启发式成本中。但是，这似乎意味着您永远不能在封闭列表中添加图块，因为从另一个方向进入可能会从根本上改变移动的成本。

The fact that the system has inertia means that in order to make a turn, you may have to slow down well in advance of making the turn. My best thought to date is that you calculate the additional time it would take to slow down, and then add it to the heuristic cost of moving. However, this would seem to imply that you could never add a tile to the closed list, as entering from another direction could fundamentally change the cost of moving.

推荐答案

创建图的顶点是tile + inertia的各种组合的图形，然后执行该图中的普通寻路算法。

Create a graph whose vertices are various combinations of tile+inertia and then do a normal pathfinding algorithm in that graph.

这篇关于单位有惯性时如何寻路？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！