gpt4 book ai didi

algorithm - 找到离其他 n 个点最远的点

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:02:53 24 4
gpt4 key购买 nike

我正在尝试创建一个“逃离”算法,并希望首先找到“安全”点。也就是说,它们与其他点相对较远的点。

这是二维的(不是很重要)并且发生在一个固定大小的圆圈内。

我猜测平方距离之和会产生一个很好的起始方程,其中最高分离得最远。

至于选择点,我认为不可能求解 X,Y,但近似值就足够了。

我做了一些阅读并确定为了覆盖一个圆的面积,你需要 7 个半尺寸的圆(中心形成一个六边形,第七个在中心)

我可以遍历这些,所有这些都在开始的圆圈内。当我选择得分最高的球体时,我可以继续将它们分成 7 个球体。当然,不包括任何落在原圆之外的点。

然后我可以迭代到所需的精度或所需的级别。

为了扩展该方法,假设到达某个位置需要时间,虽然该位置可能是安全的,但中间的行程可能不安全。我应该如何将距离纳入等式,以便得出一个好的解决方案。

我想我可以将到新点的距离平方,然后乘以分数,然后从那里开始迭代。它会强烈支持本地景点,但我认为这是一种很好的行为。它会尝试解决附近的安全点,然后在重新计算后找到“出路”并继续潜入安全地点。

对此有什么想法,或者这个问题以前解决过吗?我看的时候没能具体找到这个问题。

编辑:

Voronoi using Fortune's Algorithm

我引入了 Fortune 算法的 C# 实现,并在我的点周围添加了一些点以创建伪循环约束,因为我对算法的理解不够深入,无法手动调整它。

我现在意识到蓝线在节点之间创建了一条路径。我可以使用这些长度和周围点之间的距离来计算路径(遍历时间和危险)并将其与安全性(它试图到达的空心圆)进行权衡以确定最佳路线行动。通过研究这些相互作用的方式,我可以消除大部分我必须做的工作,只需使用 voronoi。此外,我的生成算法现在将使用它来确定 LEC 并在该位置生成。

最佳答案

你可以拿convex hull您的一组位置 - 凸包的顶点将为您提供一组“最远”点。接下来,取 centroid你逃离的点,然后确定凸包的哪个顶点离质心最远。例如,您可以通过将运动场划分为象限来加快速度 - 您只需要测试最远象限中的顶点(例如,如果质心位于正 x 正 y 象限中,那么你只需要检查负 x 负 y 象限中的顶点);如果运动场的形状不规则,那么这可能不是一个选择。

作为逃到最远点的替代方法,如果您有一个要逃离的起点(例如,您要逃离的点是敌人,并且玩家角色当前位于 X 点,这表示它起点),那么不是让玩家逃到最远的点,而是让玩家沿着最快将他们从敌人的质心带到他们的轨迹 - 从敌人的质心穿过玩家的位置绘制一条射线,那条射线会告诉你玩家应该逃离的方向。

如果玩家角色被包围,那么这两种算法都会给出无意义的结果,但在那种情况下,玩家角色实际上并没有任何可行的选择。

关于algorithm - 找到离其他 n 个点最远的点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17137962/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com