是否有一个将威胁范围与2D网格上的任意移动范围相结合的算法？ [英] Is there an algorithm for combining threat range with arbitrary move range on 2D grid?

问题描述

我正在构建一个简单的基于2D网格的游戏，并且正在寻找一种计算每个角色可以在游戏板上施加的威胁区域的方法。从现在的威胁很容易计算出来 - 这是下面的红色钻石。但是我想将这些信息与任意的可以走在这里区域（橙色）结合起来。

这个算法一起会让我我的角色可以从所有可用的移动和当前位置攻击的所有瓦片的组合。

当然，我可以迭代所有可能的动作，在那里应用钻石形状，并创建一组所有的威胁方块。有没有更好的方法？

解决方案

这里解决的问题类似于2D 旋转：

  --------- ------ --------------- ------- XX ------ 
 ------- X --- ---- --------------- ------ XXXX ----- 
 ------ XXX ------  - ----- XX ------ ----- XXXXXX ---- 
 ----- XXXXX ----- * ------ XXX ----- -  = ---- XXXXXXX ---- 
 ------ XXX ------ -------- X ------ ----- XXXXXX- --- 
 ------- X ------- --------------- ------ XXXX ----- 
 --------------- --------------- -------- X ------ $ b在你的情况下，只有一个元素被覆盖或覆盖（而不是包含一个标量或向量值），那么这个减少到形态学的扩展操作。有关高效实施扩张的许多论文和代码示例 -  这一个看起来特别适用于您的问题。
 
I'm building a simple 2D grid based game and am looking for a way to calculate the "threat" area that each character can exert on the game board. Threat from the current spot is easy to calculate - this is the red diamond below. But I'm looking to combine this information with an arbitrary "can walk here" area (orange). 

Together the algorithm will give me a combination of all tiles that my character can attack from all available moves and current position.



Of course I can just iterate over all possible moves, apply the diamond shape there and create a set of all threat squares. Is there a better way?
解决方案
The problem you are solving here is analogous to 2D Convolution:
---------------     ---------------     -------XX------
-------X-------     ---------------     ------XXXX-----
------XXX------     -------XX------     -----XXXXXX----
-----XXXXX-----  *  ------XXX------  =  ----XXXXXXX----
------XXX------     --------X------     -----XXXXXX----
-------X-------     ---------------     ------XXXX-----
---------------     ---------------     --------X------
In your case where an element is only either covered or uncovered (versus containing a scalar or vector value), this reduces to the Dilation operation in morphology.  There are many papers and code samples on efficient implementations of dilation - this one looks particularly applicable to your problem.

                        
这篇关于是否有一个将威胁范围与2D网格上的任意移动范围相结合的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！