小编son*_*cis的帖子

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

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

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

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

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