在基于平铺的地形上平滑path查找,但是可以漫游玩家

对不起,如果这是一个很长的post,但我觉得好像细节应该有助于澄清灰色地带。 我会试着提供一个我想要达到的目标,我到目前为止的详细布局,以及我的问题在哪里/我被困住了。

(当看到它正确地生活时,可能会改变这篇文章的外观)

游戏概述:
我正在devise一个自上而下,单层,基于障碍的游戏,它将由基于瓦片的地形( 只有正方形)组成。 然而,玩家,敌人和物体将能够自由漫游,并且不会卡入任何网格。 玩家尤其会在大小和型号上有所不同,因此一般而言,他们可以是圆形,三角形,方形,X等等。

由于寻路将依靠坚实,这是我的目标布局:

  • 瓷砖将永远是固体不固体。
  • 玩家和敌人将永远不会坚实。
  • 如果物体不是这样的话,那将会很好,或者,如果不是,它们也可以是非固体的。

我的进度:
我已经在Tile [] []devise中设置了基于网格的地形。 由于每个(x,y)坐标只有1个瓦片,所以这允许干净的参考。 不过,瓷砖很less能通过触发器来改变。 所以一块不牢固的草地砖可能会变成一块坚硬的石砖,这是不可磨灭的。

玩家通过鼠标移动到位。 虽然这可能会被path查找覆盖,但是它目前可以将玩家从A点移动到B点。玩家类具有像素位置,图像,缩放和速度。 玩家将有1个网格单位(目前为40×40像素),并从那里缩放。 所以0.5的比例总是20x20px。

作为一个非常通用的devise,使用包围盒来实现轻微的盒子检测。 稍后,这可能会更改为一个像素检查hitbox方法。

我的问题/关注:
我可以参考的主要问题是我可以使用哪种寻路方法来知道我的单元不是基于网格的,可以正确地移动我的地图,而不是剪辑? 再次记住,玩家可以改变大小,瓷砖可以改变坚实。

我花了几天的时间寻找寻路的方法。 我已经研究过A *,HAA *,HPA *,NavMeshes,并且轻易地将其转换为D *和Dijkstraalgorithm。 然而,对于不直接在网格上移动的东西,一般而言,寻路对我来说是全新的。

参考资料:

例1例2

2×2蓝绿色盒子是玩家。 绿色2×2是目标。 如果他一次只上一格,球员的左上角就是点。 金线是我想要的path。

这HPA *方法似乎是可行的,但我不知道如何让path平滑工作。 我是否会经常看到列表中的下一个点是否可以直接进入而不删除,如果可以的话,将其删除?

结束语:
我不确定在这里发布一些结构代码会带来什么好处,因为我的问题是如何处理这个问题的方法,而不是我目前为止的方法。

我知道这里有一些话题。 我不能链接,因为我只限于两个,但我在这里看到一个标题为“ 在网格上的全瓷砖范围追踪 ”似乎要求类似的事情。 几乎所有path查找方法的示例图片的问题都使用一个无尺寸的例子。 (除了这一个 ,但它仍然在其中一个回合)

单位本身会有一个转弯速度,但我不认为这会影响转弯。 大多数情况下,如果更多的工作,我不需要光滑,汽车般的转向。

请让我知道,如果有什么我错过了,我应该清理,或者如果我忽略了一个深入到我正在问的深入的话题。 现在已经很晚了,我想在这里继续search。 我只是觉得在这个实现中输了。

大小和合适性可以被用来说明在path查找期间移动是否有效的启发式方法。 一旦path本身生成,就可以实现局部移动function,以处理在路上不会碰到的东西,称为path平滑。 也许平滑path将有助于产生一些适合你的想法。

上一次我做了这个,我用道路作为一个善意的建议,做了局部的预先整理之字形,然后一些黑客总是在拐角处变宽,并允许碰撞和滑向外面,在角落里面。

如果在生成特定path之后的任何时候网格发生变化,则必须重新生成path。

通过使用A *,我得到了很好的结果,然后从最后一个节点将光线投射回path中的每个节点,检查每条光线上的地形高度,以确定是否还可以走到那里(您可以在此添加自己的逻辑,水,敌人,建筑物等…我的是如果身高差异小于1单位每单位距离,那么你不能走),一旦我击中一个节点,射线testing失败,我用最后通过射线testing的节点,并从它投射光线到其余的节点,迭代到达到起点,并得到很好的path,在开放的地图上,你会得到一个直线之间的N开始和N端

A * = N(开始),N1,N2,N3 N4 N5 … N(结束)

for i = end ; i >= start ; i-- ray-test = true ii = i // ray must pass by default between 2 adjacent nodes while ray-test == true && ii != start ii-- from N(i) cast ray to N(ii) ray-test = check path along the ray N(i) --> N(ii) //here N(ii) failed the ray-test, //thats how we got outside the loop //ignore all nodes between the end/destination //node than the last node that fulfills the ray test N(i).parent = N(ii+1)