V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Game Engines
Unreal Engine
MyCryENGINE
liamxd
V2EX  ›  游戏开发

我实现的一个 A*算法,效率极低,不知道为啥。

  •  
  •   liamxd · 2015-09-07 13:25:19 +08:00 · 6046 次点击
    这是一个创建于 3357 天前的主题,其中的信息可能已经有所发展或是发生改变。

    我在我的小游戏中添加了 A*的寻路算法。

    结果寻路效率极低, open list 膨胀的特别快。稍微远点的路程就几乎死机状态。

    代码在这里:
    https://github.com/modouRPG/MoDouClient.git

    13 条回复    2015-09-08 12:20:46 +08:00
    MOsky
        1
    MOsky  
       2015-09-07 13:28:19 +08:00 via iPhone
    mark 下,睡一觉再看
    zhicheng
        2
    zhicheng  
       2015-09-07 13:33:00 +08:00
    https://github.com/zhicheng/pathfinder

    我以前写的一个,很快啊,不过代码写很烂,不要学我。
    liamxd
        3
    liamxd  
    OP
       2015-09-07 14:09:02 +08:00
    @zhicheng 看了一下,算法几乎相同啊。你那里不会遇到 open list 膨胀过快导致计算很慢的问题么?

    我这里在遇到墙比较长的时候,起点和重点刚好在墙两侧比较对称的位置的时候, open list 会变的很长。然后就几乎死机。
    zhicheng
        4
    zhicheng  
       2015-09-07 14:16:24 +08:00
    @liamxd 只是很早很早以前写的一个 demo ,你能跑起来吗?有个 OpenGL 写的测试。
    zhicheng
        5
    zhicheng  
       2015-09-07 14:29:18 +08:00
    @liamxd 修了个编译错误加了 License 。可以直接在 Mac 上编译了。左键是加障碍,右键第一下是设置起点,第二下是设置终点,然后计算出路径。
    yuchting
        6
    yuchting  
       2015-09-07 15:20:19 +08:00
    A*研究在学生时代研究良久,后来在工作全是用得广度优先了,效率完全跟得上。学生时代全是 std 容器,然后工作看别人写的全是数组,效率自然没法比,但是 std 容器多漂亮哇。。。
    liamxd
        7
    liamxd  
    OP
       2015-09-07 15:36:08 +08:00
    解决了。现在效率还可以了。

    改的地方就是:
    点是使用的 class 。因为要比较相等,所以重载了一个==操作符。
    在比较 A 点==B 点的时候使用操作符比较的。
    我换成了直接比较点的 X 和 Y 值之后,速度嗖嗖的了。

    真是叫人不解啊。
    zerh925
        8
    zerh925  
       2015-09-07 17:48:21 +08:00 via iPhone
    不错!
    也可以尝试 Dijkstra 或者蚁群算法 TSP 问题
    jiangzhuo
        9
    jiangzhuo  
       2015-09-07 18:30:18 +08:00
    出去程序实现上的问题,在有大块墙和封闭区间的时候加入 JPS 能快很多
    WKPlus
        10
    WKPlus  
       2015-09-07 18:41:50 +08:00
    你原来的代码比较的是两个指针是否相等,也就是比较两个指针是否指向同一个对象,而不是比较对象中的 x,y 值是否相等。改为*(*it ) == *point 才是调用重载的==进行比较。

    大概看了一下原来的代码, childrenList 每次都是新生成点对象的,对象当然和原来的 openlist 的对象不一样,所以你的 openlist 会一直变大。
    WKPlus
        11
    WKPlus  
       2015-09-07 18:43:38 +08:00
    另外, operator==接受的参数一般是对象的引用而不是指针。
    acros
        12
    acros  
       2015-09-07 19:01:23 +08:00
    直接打开看晕了···· 还是得下下来看才行。

    其实我只想吐槽两点:
    我写游戏还还真没用过 try catch··· 游戏引擎代码中,运行时的部分里也没有类似的印象。
    构建路径列表那里好多 new delete ,肯定快不了。
    sigroma
        13
    sigroma  
       2015-09-08 12:20:46 +08:00
    https://github.com/qiao/PathFinding.js
    以前写 A star 的时候参考了一下这个项目中的 Trace 算法
    这个算法会优先选择靠墙 /墙角的位置,面对大墙时速度比原始 A star 快很多
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1180 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 18:38 · PVG 02:38 · LAX 10:38 · JFK 13:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.