使用(部分)统一网格表示减少3D A*寻路中的节点数量

Question

我正在计算网格中的寻路,我已经建立了一个统一的网格.节点(3D网格中的单元格)接近我认为的"可站立"表面我标记为可访问,并且它们用于我的寻路.为了获得大量的细节(比如能够找到小楼梯的情况),我的网格中可访问单元的数量已经变得非常大,数千个大型建筑物.(每个网格单元格为0.5x0.5x0.5 m,网格是具有真实世界尺寸的房间).即使我只使用网格中的一小部分实际单元进行寻路,但巨大的ammount会降低算法的速度.除此之外,它工作正常,并使用加权曼哈顿距离启发式找到通过网格的正确路径.

想象一下,我的网格看起来就像那样,网格在里面(可以是或多或少的立方体,但它总是立方体),但是路径查找不会计算在所有小立方体上,只有少数标记为可访问(通常位于底部)网格,但这可能取决于网格有多少层.

我希望减少寻路的搜索空间...我已经看过像HPA*这样的聚类以及像马尔科夫这样的其他聚类算法,但它们似乎最好用于节点图而不是网格.一个显而易见的解决方案是仅增加构建网格的小立方体的大小,但是在路径查找中我将失去很多细节,并且它不会那么强大.我怎么能聚集这些小立方体？这是我进行寻路时典型搜索空间的样子(蓝色可访问,绿色是路径):

如你所见,有很多立方体可以搜索,因为它们之间的距离非常小!不要紧,网格现在是一种不理想的寻路解决方案.

有没有人知道如何减少我必须搜索的网格中的立方体数量以及在减少空间后如何访问邻居？:)现在它只在扩展搜索空间时查看最近的邻居.

Answer 1

想到几种可能性.

更高级别的寻路

首先,您的A*搜索可能正在搜索整个问题空间.例如,你住在德克萨斯州的奥斯汀,想进入加拿大艾伯塔省某个特定的建筑物.在最终搜索加拿大建筑之前,一个简单的A*算法将搜索许多墨西哥和美国.

考虑创建第二层A*来解决这个问题.你首先要找出哪些州到达加拿大,然后去哪些省份到达艾伯塔省,然后到达卡尔加里,然后到达卡尔加里动物园.从某种意义上说,您从概述开始,然后用更详细的路径填充它.

如果你有巨大的等级,例如天际,你可能需要在城镇(多个建筑物),地区(多个城镇)甚至国家(多个地区)之间添加寻路层.如果您正在制作GPS系统,您甚至可能需要大陆.如果我们成为星际,我们的宇宙飞船可能包含行星,扇区甚至星系的寻路层.

通过使用图层,您可以显着缩小搜索范围,特别是如果不同区域不使用相同的坐标系统!(如果其中一个区域需要纬度 - 经度,另一个是3d-cartesian,那么估计一个A*探路者的距离相当困难,而下一个需要在时间维度上寻路.)

更高效的算法

在3维中寻找有效的算法变得更加重要,因为在搜索时有更多的节点需要扩展.扩展x ^ 2个节点的Dijkstra搜索将搜索x ^ 3,其中x是起点和目标之间的距离.4D游戏在寻路方面需要更高的效率.

基于网格的寻路的一个好处是可以利用路径对称等拓扑属性.如果两条路径由不同顺序的相同运动组成,则无需同时查找它们.这是一个非常有效的算法,称为跳转点搜索.

这是A*(左)和JPS(右)的并排比较.扩展/搜索节点显示为红色,墙壁为黑色:

请注意,他们都找到相同的路径,但JPS很容易搜索到不到A*所做的十分之一.

截至目前,我还没有看到官方的三维实现,但我帮助其他用户将算法推广到多维度.

简化网格(图形)

在搜索过程中摆脱节点的另一种方法是在搜索之前删除它们.例如,您是否真的需要在开放区域中的节点,您可以信任更愚蠢的AI来找到它的方式？如果要构建不更改的级别,请创建一个脚本,将其解析为仅包含重要节点的最简单网格.

这实际上称为"离线寻路"; 基本上找到在需要找到它们之前计算路径的方法.如果您的级别保持不变,则每次更新级别时运行脚本几分钟将轻松减少90%的路径查找时间.毕竟,在紧急工作之前,你已经完成了大部分工作.就像你在长大的城市中找到自己的方式一样; 了解地标意味着您并不真正需要地图.

这种算法的创建者Daniel Harabor介绍了Jump Point Search使用的"对称性破解"的类似方法.在他的一个讲座中提到了它们,并允许您预处理级别以仅在路径寻找网格中存储跳转点.

聪明的启发式

许多学术论文都指出A*的成本函数f(x) = g(x) + h(x),这并不能说明你可以使用其他函数,增加成本函数的权重,甚至实现领土或最近死亡的热图作为函数.这些可能会创建次优路径,但它们可以极大地提高搜索的智能性.当你的对手有一个阻塞点并且很容易派遣任何人通过它时,谁在乎最短的路径？更好的是确保AI能够安全地达到目标,而不是让它变得愚蠢.

例如,您可能希望阻止算法让敌人访问秘密区域,以便他们避免将其暴露给玩家,以便他们AI似乎不知道它们.实现这一目标所需要的只是在那些"禁区"区域内的任何一点的统一成本函数.在这样的游戏中,在路径变得过于昂贵之后,敌人会放弃追捕玩家.另一个很酷的选择是玩家最近的"气味"区域(通过暂时增加未访问位置的成本,因为许多算法不喜欢负成本).

如果您知道哪些地方不需要搜索,但无法在算法的逻辑中实现,那么简单地增加其成本就可以防止不必要的搜索.有很多方法可以利用启发式方法来简化和告知您的寻路,但您最大的收获将来自Jump Point Search.

编辑:跳转点搜索使用与A*相同的启发式隐式选择寻路方向,因此您可以在很小程度上实现启发式算法,但它们的成本函数不会是节点的成本,而是成本在两个节点之间旅行.(A*通常搜索相邻的节点,因此节点的成本与前往它的成本之间的区别往往会中断.)

摘要

尽管八叉树/四叉树/ b树在碰撞检测中很有用,但它们不适用于搜索,因为它们根据坐标划分图形; 不是它的联系.将图形(词汇表中的网格)分层为超级图形(区域)是一种更有效的解决方案.

希望我已经涵盖了你会发现有用的任何东西.祝好运!