基于导航网格寻路的单位转向

我正在做一个RTS游戏,我正在使用navmeshes进行单元寻路。 我知道如何在navmesh中find一个通用path,但是如何确定单元是否有足够的空间来转向?

我有不同形状的单位(主要是不同尺寸的矩形),并有不同的转弯半径。 另外一些单位可以转到位,有些可以反向移动。

那么,如何find一个单位可以遵循的path,考虑到它不容易旋转?

首先是警告。 你试图解决的问题非常复杂,大多数职业游戏甚至不打扰,除非它是游戏的一个关键部分。 所以我的建议是尽可能多地作弊。

对于车辆半径,我会尝试使用最坏的情况(最大尺寸),然后将车辆视为一个圆柱体(或一个二维的圆圈)进行寻路。 使用导弹,你可以有不同的网格,考虑到不同的半径,或者使探路者远离墙壁一定的距离。 在任何一种情况下,图片向内推挤navmesh的边缘和四角(这在技术上被称为Minkowski总和)。 那么你可以把这辆车作为一个点,在这个扩大navmesh。

如果你想考虑转向,你将不得不在探路者本身编码这些规则,因为它扩大了。 例如,如果车辆不能以较小的半径转弯,则必须同时丢弃一些以当前连接forms提供的多边形,并在拉动线路时优化path时使用该信息。 一般来说,你也希望在启发式中对这些逻辑进行编码,这样path就尽量减less转向,看起来尽可能的自然。

如果您可以定义特定单位需要能够通过的最小宽度,那么您可以减去该宽度以缩小导航网格上候选路线上的多边形。 如果一个部分消极,那么你会发现它可以通过。 也许你可以用这种方法创建一个可以通过的解决scheme,即使只是通过为这些单元手动定义安全的宽度要求。

这并不是完美的,因为没有考虑到很长的车辆如何难以陡峭转弯。 我想有一些algorithm来适应容器内的形状,并检测它们是否不合适(一个简单的交叉检查会这样做,但我不知道如何拿出候选人来检查,除了蛮力)。 即使这样也不会考虑转弯半径和单位是否可以扭转。

显然走廊地图方法 (CMM)是这个类似的问题, 3D RTS寻路接受的答案

这似乎考虑到转向的转弯半径,但我没有看到任何关于车辆的尺寸,所以不是我想你的问题的完整解决scheme。