Home Sign Up Sign In
badbye
V2EX  ›  算法

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

  •   
  •   badbye · Jan 6, 2023 · 2481 views
    This topic created in 1397 days ago, the information mentioned may be changed or developed.
    想在战棋游戏中实现类似 dota 中宙斯的弧形闪电技能：释放一道会跳跃穿越附近敌人的闪电。

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

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

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

    从 A 棋子开始，跳转到任意相邻的棋子，重复此过程，求最长路径。
    badbye
    badbye
    OP
    Jan 6, 2023
    5
    @MeiJM A*我一直以为需要有个终点
    badbye
    badbye
    OP
    Jan 6, 2023
    6
    @takato 我这一个带 bug 的实现是都走完然后选最长的
    GuardX
    GuardX
    Jan 6, 2023
    8
    有点类似哈密尔顿通路？
    elmagnificogg
    elmagnificogg
    Jan 6, 2023
    9
    或者求 极大连通子图 结果应该就是你想要的
    badbye
    badbye
    OP
    Jan 6, 2023
    10
    @elmagnificogg 是的，看了一些算法，大多是输出最大的长度，而不是完整的路径，修改的时候脑子就不够用，有些算法根本不能改成路径
    MeiJM
    MeiJM
    Jan 6, 2023 via Android
    11
    @assiadamo 是需要结束点 所以要查找所有结束点 再检验哪个点可达
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   3071 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 11:39 · PVG 19:39 · LAX 03:39 · JFK 06:39
    ♥ Do have faith in what you're doing.