是否有一个算法，对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 ------
 

在你的情况下，一个元素只要么覆盖或未覆盖（与含有标量或矢量值），这样可减少到的在形态扩张操作。有许多论文和扩张的有效实现code样品 - 这个看起来特别适用于你的问题。

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屋！