V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
assiadamo
V2EX  ›  算法

一个游戏中很常见的找路径问题,请各位算法大神帮忙

  •  
  •   assiadamo · 2023-01-06 15:47:11 +08:00 · 1084 次点击
    这是一个创建于 448 天前的主题,其中的信息可能已经有所发展或是发生改变。
    想在战棋游戏中实现类似 dota 中宙斯的弧形闪电技能:释放一道会跳跃穿越附近敌人的闪电。

    像 dota 这样实时的游戏,有可能宙斯释放技能时,目标的队友会走位离开闪电的跳跃范围,所以猜想的实现方式是递归寻找范围内的目标,找到一个就直接跳过去。

    但在战棋游戏中,回合行动时,其他人的位置是固定的,所以应该能找到一条路径,尽可能的电到最多敌人。

    在图中从一个顶点出发,找到一条能经过最多顶点数的最长路径,顶点不可重复,不知道这样描述是否清晰。
    11 条回复    2023-01-06 18:15:35 +08:00
    MeiJM
        1
    MeiJM  
       2023-01-06 16:32:27 +08:00 via Android
    不是动态障碍物 a*就可以 还有其他算法 可以搜一下路径规划
    MeiJM
        2
    MeiJM  
       2023-01-06 16:35:08 +08:00 via Android
    你这个有点不一样 要先算结束位置再匹配哪个路径可达
    takato
        3
    takato  
       2023-01-06 16:35:22 +08:00
    想到一个需要补充的点,如果弹跳范围内有两个可选的点,它会根据特定的规则寻找点还是随机选择一个?两个不同的选项可能影响最终结果。
    rrfeng
        4
    rrfeng  
       2023-01-06 16:36:58 +08:00
    棋盘上随机放置了 N 个棋子。

    从 A 棋子开始,跳转到任意相邻的棋子,重复此过程,求最长路径。
    assiadamo
        5
    assiadamo  
    OP
       2023-01-06 17:12:54 +08:00
    @MeiJM A*我一直以为需要有个终点
    assiadamo
        6
    assiadamo  
    OP
       2023-01-06 17:14:05 +08:00
    @takato 我这一个带 bug 的实现是都走完然后选最长的
    elmagnificogg
        7
    elmagnificogg  
       2023-01-06 17:53:36 +08:00
    GuardX
        8
    GuardX  
       2023-01-06 17:55:14 +08:00
    有点类似哈密尔顿通路?
    elmagnificogg
        9
    elmagnificogg  
       2023-01-06 17:57:59 +08:00
    或者求 极大连通子图 结果应该就是你想要的
    assiadamo
        10
    assiadamo  
    OP
       2023-01-06 18:13:02 +08:00
    @elmagnificogg 是的,看了一些算法,大多是输出最大的长度,而不是完整的路径,修改的时候脑子就不够用,有些算法根本不能改成路径
    MeiJM
        11
    MeiJM  
       2023-01-06 18:15:35 +08:00 via Android
    @assiadamo 是需要结束点 所以要查找所有结束点 再检验哪个点可达
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2843 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 14:34 · PVG 22:34 · LAX 07:34 · JFK 10:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.