在连续 2D 空间中进行基本寻路和避障
我正在编写一个模拟，其中生物对象应该能够向环境中的其他任意对象移动，绕过障碍物滑动，而不是进行任何智能寻路。 我并不是想让它规划一条路径——只是朝着一个大方向移动，并绕过障碍物。
这是一个 2D 环境（俯视图），每个对象都有一个用于碰撞检测的边界矩形。 没有网格，我也不是在寻找 A* 解决方案。
我还没有找到任何关于这种“愚蠢”的基于碰撞的寻路的教程，所以我可能不会使用最常见的术语来描述它。
关于如何实现这一点有什么建议（或教程链接）？
I'm writing a simulation in which a creature object should be able to move towards some other arbitrary object in the environment, sliding around obstacles rather than doing any intelligent pathfinding. I'm not trying to have it plan a path -- just to move in one general direction, and bounce around obstacles.
It's a 2D environment (overhead view), and every object has a bounding rectangle for collision detection. There is no grid, and I am not looking for A* solution.
I haven't been able to find any tutorials on this kind of "dumb" collision-based pathfinding, so I might not be describing this using the most common terms.
Any recommendations on how to implement this (or links to tutorials)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
扩展 Guillaume 关于避障的说法，一种适合您的技术是 反重力运动。 你将当地的障碍物视为反重力的点源，将目的地视为重力，并且你的计算机控制的角色将绕过障碍物滑动（像肥皂一样！）到达目的地。
Expanding on what Guillaume said about obstacle avoidance, a technique that would work well for you is anti-gravity movement. You treat local obstacles as point sources of antigravity, the destination as gravity, and your computer controlled character will slip (like soap!) around the obstacles to get to the destination.
您可以结合两种转向算法：
寻找：您在当前速度与目标速度之间的差值方向上施加转向力
避障：您使用长度为常数时间乘以车辆当前速度的盒子来预测车辆的未来。 任何与此框相交的障碍物都是潜在的碰撞威胁。 选择最近的此类威胁来避免。 为了避开障碍物，向障碍物中心施加相反的侧向转向力。 此外，还施加制动（减速）力。 这些力随紧急程度（从盒子尖端到潜在碰撞点的距离）而变化。 转向呈线性变化，制动呈二次变化。
您可以在网站上找到更多信息“自主角色的转向行为”
关于
Guillaume
PS ：这假设您正在使用点/速度/加速度方法来进行对象的运动。
you can combine two steering algorithm :
seek : you apply a steering force in the direction which is the difference between the current velocity and the desired velocity towards the target
Obstacle Avoidance : you anticipates the vehicle's future using a box whose length is a constant time multiplied by the current velocity of the vehicle. Any obstacle that intersects this box is a potential collision threat. The nearest such threat is chosen for avoidance. To avoid an obstacle, a lateral steering force is applied opposite to the obstacle's center. In addition, a braking (deceleration) force is applied. These forces vary with urgency (the distance from the tip of the box to the point of potential collision). Steering varies linearly, braking varies quadratically.
You can find more on the website "Steering Behaviors For Autonomous Characters"
regards
Guillaume
PS : this assume you're using a point/velocity/acceleration method for the object's movement.
也许你可以使用Pledge 的算法
Maybe you could use Pledge's algorithm
每当您的生物沿矢量方向
v行进时，与方向由矢量w表示的墙壁发生碰撞，您需要“滑动”的方向由矢量给出这是v到w的投影。 这可以使用.找到，其中 向量点积 和|w|是矢量w的大小 ( =sqrt(w . w))。 如果w是单位向量，则这只是简单地使用所得向量作为生物的速度，这意味着你的生物在“擦过”墙壁时移动速度很快，而在撞到墙壁几乎死掉时则移动缓慢 -在。 （这就是大多数第一人称射击游戏为人类玩家管理碰撞的方式。）
如果您希望您的生物始终全速行驶，则只需要
v 符号。 w——您将始终沿着墙面向的方向 (w) 或相反方向 (-w) 行驶。你将遇到的问题是当你的生物直接撞到墙上时。 在这种情况下，您的投影向量将为 (0, 0)，并且您需要一些其他技术来决定走哪条路（
w或-w）。 这里通常的方法是 A*，尽管如果您的环境拥有足够的结构，这可能是不必要的。Whenever your creature, travelling in vector direction
v, collides with a wall whose direction is represented by vectorw, the direction that you need to "slide" is given by the vector that is the projection ofvontow. This can be found usingwhere
.is the vector dot product and|w|is the magnitude of vectorw( =sqrt(w . w)). Ifwis a unit vector, this becomes simplyUsing the resulting vector as your creature's speed will mean your creature travels quickly when it just "grazes" the wall, and slowly when it hits the wall nearly dead-on. (This is how most first-person shooter games manage collisions for the human player.)
If instead you want your creature to always travel at full speed, you only need the sign of
v . w-- you will always be travelling either in the direction the wall faces (w) or the opposite direction (-w).The issue that you will have is when your creature hits the wall dead-on. In that case your projected vector will be (0, 0), and you need some other technique to decide which way (
wor-w) to go. The usual approach here is A*, although this may be unnecessary if your environment possesses enough structure.我不久前用 C# 发布了一个寻路算法
这是链接
您可以尝试使用它作为起点，即您可以修改检查下一个单元格的函数以查看检查障碍物是否有效，并且您可以为其提供较小的间隔而不是起点和终点，有点像多条迷你寻路路线。
（文本为西班牙语，但您可以从顶部的链接下载该应用程序）
I posted a pathfinding algorithm in C# a while back
Here's the link
You can try and use it as a starting point, ie, you could modify the function that checks the next cell to see if it's valid to check for the obstacles, and you could feed it small intervals instead of the starting and end points, kinda like multiple mini-pahfinding routes.
(The text is in spanish, but you can download the application from the link at the top)