请教如果地图太大的情况下A*算法应该怎样处理能提高效率?

samvon · 发表于 2005-10-17 13:12:00

请问如果如果我的地图太大,比如说5000*5000的地图,那么障碍表也会很大,光是读障碍表就已经很慢,这个问题怎么解决??是要新建立一个线程来读取吗?
另外这么大的地图如果是A*算法的话怎样解决效率问题,如果起点和终点是在地图的对角的话,也就是说两点相距很长的话,搜索路径的时间会非常长,请教有没有办法解决这个问题,谢谢!

桃根仙 · 发表于 2005-10-17 15:28:00

化整为零，把地图分成若干的小区域，尽量分时完成，较短的时间只完成一部分

Whistler · 发表于 2005-10-17 15:29:00

samvon: 请教如果地图太大的情况下A*算法应该怎样处理能提高效率?

请问如果如果我的地图太大,比如说5000*5000的地图,那么障碍表也会很大,光是读障碍表就已经很慢,这个问题怎...

可以把它分成几个帧来运行。看一下这个源代码:
http://racc.bots-united.com/releases/racc-template-2.exe

Liker · 发表于 2005-10-17 17:08:00

铺路点……

lingjingqiu · 发表于 2005-10-17 19:29:00

IDA，手工分片，预定义向导。。。

bluespark · 发表于 2005-10-19 00:27:00

Whistler: Re: 请教如果地图太大的情况下A*算法应该怎样处理能提高效率?

可以把它分成几个帧来运行。看一下这个源代码:
http://racc.bots-united.com/releases/racc-template-2.exe

能说一下这个程序的功能吗？我怎么编译通不过啊？是不是少什么文件呢？

Whistler · 发表于 2005-10-19 10:24:00

那个是一个 CS 的机器人程序。还需要 Half-Life SDK 才能编译
里面的 pathmachine.cpp 中有其 A* 实现

PassByYou · 发表于 2005-10-19 12:10:00

我的地图900*900*3*3*64*64，3个轴，xyz

~分区建方向罗盘系统~然后寻片区~入区以后才开始精确计算~

影响A*的有数据回检~试试添加一些转弯标志~可以大幅度降低回检频率~

hlsl · 发表于 2005-10-21 12:42:00

关键看你的数据结构效率，简单的格子已经不能适应了

铺路点——Visiblity Point图
或者生成NavMesh，通过NavMesh测试之间的Visibility以生成图

这样相比格子效率已会大大提高。如果能使用层次化的数据结构则更好。现在很多引擎都是通过编译场景生成LUT直接查找就完事了

samvon · 发表于 2005-10-21 13:44:00

谢谢大家热心的帮助~~

账号		自动登录	找回密码
密码			立即注册

请教如果地图太大的情况下A*算法应该怎样处理能提高效率?

Re:请教如果地图太大的情况下A*算法应该怎样处理能提高

Re: 请教如果地图太大的情况下A*算法应该怎样处理能提高

Re:请教如果地图太大的情况下A*算法应该怎样处理能提高

Re:请教如果地图太大的情况下A*算法应该怎样处理能提高

Re: Re: 请教如果地图太大的情况下A*算法应该怎样处理能提

Re:请教如果地图太大的情况下A*算法应该怎样处理能提高

Re:请教如果地图太大的情况下A*算法应该怎样处理能提高

Re:请教如果地图太大的情况下A*算法应该怎样处理能提高

Re:请教如果地图太大的情况下A*算法应该怎样处理能提高