代码之家  ›  专栏  ›  技术社区  ›  CrossNox

在游戏板中找到我可以移动到的位置的算法

  •  2
  • CrossNox  · 技术社区  · 10 年前

    我的问题如下(简化):

    • 我有一块板,用n x m平方的矩阵表示(n可能等于m)
    • 在里面,有 p 游戏单品
    • 每个游戏片段都有一个预定义的速度,即它在回合中可以走多少步
    • 工件不能重叠
    • 有三种类型的细胞:那些不需要额外运动才能穿越的细胞(穿越时你会失去额外的速度),那些需要额外运动就能穿越的细胞,还有一些你根本无法穿过的细胞(比如墙)

    所以,给定一个特定的游戏片段 [i,j] 我想知道:
    a) 它能以它的速度移动到所有的地方
    b) 通往某个 [k,l] 在董事会中的位置

    求解a),b)几乎是微不足道的。 目前我使用的算法如下,假设一种语言,其中数组大小为 n 从 0 到 n-1 :

    • 创建一个速度*2+1大小的平方矩阵,表示移动的成本,就好像所有单元格都没有额外的成本要交叉一样(工件在位置[speed,speed]上)
    • 创建另一个速度*2+1大小的正方形矩阵,该矩阵具有每个单元格的额外成本(那些不能交叉的矩阵,因为它是一面墙或其中有另一块具有无限值)(该块位于位置[speed,speed])
    • 创建另一个速度*2+1大小的方阵,它是前两个的总和(工件位于位置[speed,speed])
    • 更正后一个矩阵,确保每个单元格的值为:所有相邻单元格的最小成本+1+单元格的额外成本。如果不是,我会更正它,然后重新开始矩阵。

    例如:
    P 都是碎片, W 是墙, E 是无需额外移动的空单元格, X 是需要 1. 要跨越的额外移动。

    X,E,X,X,X
    X,X,X,X,X
    W,E,E,E,W
    W,E,X,E,W
    E,P,P,P,P
    

    第一个矩阵:

    2,2,2,2,2    
    2,1,1,1,2    
    2,1,0,1,2    
    2,1,1,1,2    
    2,2,2,2,2 
    

    第二个矩阵:

    1,0,1,inf,1    
    1,1,1,1,1    
    inf,0,0,0,inf    
    inf,0,1,0,inf    
    0,inf,inf,inf,inf
    

    总计:

    3,2,3,3,3    
    3,2,2,2,3    
    inf,1,0,1,inf    
    inf,1,2,1,inf    
    inf,inf,inf,inf,inf  
    

    自从 [0,0] 不是 2+1+1 ,我更正它: 总计:

    4,2,3,3,3    
    3,2,2,2,3    
    inf,1,0,1,inf    
    inf,1,2,1,inf    
    inf,inf,inf,inf,inf  
    

    自从 [0,1] 不是 2+1+0 ,我更正它: 总计:

    4,3,3,3,3    
    3,2,2,2,3    
    inf,1,0,1,inf    
    inf,1,2,1,inf    
    inf,inf,inf,inf,inf
    

    自从 [0,2] 不是 2+1+1 ,我更正它: 总计:

    4,2,4,3,3    
    3,2,2,2,3    
    inf,1,0,1,inf    
    inf,1,2,1,inf    
    inf,inf,inf,inf,inf
    

    哪一个是正确答案?
    我想知道的是,如果这个问题有名字,我可以搜索它(找不到任何东西),或者是否有人可以告诉我如何解决这个问题 a) .

    请注意,我需要最佳解决方案,所以我使用了动态编程算法。随机漫步者可能更好吗?AFAIK,这个解决方案还没有失败,但我没有正确的证据,我想确保它能正常工作。

    1 回复  |  直到 10 年前
        1
  •  2
  •   keith    10 年前

    A星是一种标准算法,用于确定二维板上障碍物的最短路径和每平方移动的成本。你也可以用它来测试一个特定的移动是否有效,但要实际生成所有有效的移动,我只需从开始位置开始,在每个方向上移动一个方块标记,哪个方块是有效的,然后从每个新位置重复,确保不再访问同一个方块。它将是一个递归算法,每次调用最多调用自己4次,并将有效地生成有效的移动。如果有限制,比如你可以用不同的成本一次移动多少个方块,只需通过每个方块的累计距离即可。