用于在2D网格上建立膨胀气体的算法

在2D网格上建立膨胀气体的算法通常用于游戏开发、地图导航和其他需要在网格上进行扩散和传播的场景。一种常用的算法是距离变换算法（Distance Transform Algorithm），它可以快速地计算出每个网格点到最近的障碍物的距离。

距离变换算法的主要步骤如下：

初始化输入矩阵和输出矩阵。输入矩阵包含所有障碍物的位置，输出矩阵将存储每个点到最近障碍物的距离。
对于输入矩阵中的每个障碍物，将输出矩阵中对应位置的值设为0。
使用BFS（广度优先搜索）算法，从输入矩阵中的每个障碍物位置开始，逐层向外扩散。在扩散的过程中，将扩散到的点到障碍物的距离设为当前层数。
当所有障碍物位置的扩散都完成后，输出矩阵中的每个点都将包含到最近障碍物的距离。

距离变换算法的优势在于它能够快速地计算出每个网格点到最近障碍物的距离，并且可以方便地应用于多种场景。

应用场景包括：

游戏开发：计算角色或敌人在地图上的可移动范围。
地图导航：计算车辆或行人在地图上的可行驶距离。
机器学习：计算图像中的对象与背景之间的距离，用于图像分割和物体检测等任务。

推荐的腾讯云相关产品：

距离变换算法的实现可能涉及到多种编程语言和技术，例如Python、C++、Java等。在实际应用中，可以根据具体需求和场景选择合适的编程语言和技术进行实现。

页面内容是否对你有帮助？

有帮助

没帮助

在给定距离变换的情况下寻找最佳路径

algorithm、search、image-processing、planning、motion-planning

给定带有障碍物的地图的距离变换，如何获得从起始像素到目标像素的最低成本路径？距离变换图像具有到原始地图的最近障碍物的距离(欧几里得)，在每个像素中，即，如果在原始地图中，像素(i，j)在障碍物的左侧3个像素，在障碍物下方2个像素，那么在距离变换中，像素将具有sqrt(4+9) = sqrt(13)作为像素值。因此，较暗的像素表示接近障碍物，较亮的值表示它们远离障碍物。我想使用这个距离变换提供的信息来规划从给定起点到目标像素的路径，并优化路径的成本，同时还有另一个限制，即路径永远不能到达距离障碍物小于'x‘像素的像素。我该怎么做呢？附注。一些关于算法的描述(或一些代码)将是有帮助的

浏览 5提问于2014-01-19得票数 2

4回答

最短路径和测地线

algorithm、math、graphics、computational-geometry、graph-algorithm

给定一个完全由四边形组成的网格，其中每个顶点都有价n(n >=为3)，并且不在同一平面上，我需要找出网格中每个顶点到一组封闭的种子顶点的距离。也就是说，给定一个或多个网格顶点(一个种子集)，我需要构建一个距离图，用于存储每个网格顶点与种子集之间的距离(它们之间的距离为0)。在花了一些时间寻找可能的解决方案后，我得到了以下图片： 1)它不是微不足道的，在过去的20年左右，已经开发出了不同的方法。 2)每种考虑3d区域的算法都被限制在一个三角形区域内说到这里，这是我得到的图片： Dijkstra算法可以用来寻找两个顶点之间的最短路径，沿着网格的边，但它非常不准确，会导致错误的测地线。La

浏览 4提问于2011-08-04得票数 18

回答已采纳

2回答

平台敌人AI

2d、ai、platformer

我目前正在研制一名血小板杀手。该游戏是多人游戏，虽然我的网络代码可以使用一些真正的工作，我已经拖延了一段时间，所以目前我正在尝试实现人工智能。游戏很简单，玩家在地图上跑来跑去，地图上装满了大量的僵尸，这些僵尸试图吃掉他们的大脑，我知道这是经典的和过度使用的。武器在地图周围随机间隔产卵。问题是，僵尸，当他们发现他们的祈祷，必须跟随它一段时间。这就是问题所在，运行AI导航代码似乎需要永远的时间。这就是我到目前为止想出的想法让AI更新在不同的间隔，最大的Y ms没有更新。把僵尸分配给一群僵尸。其中一个被任命为团队的领导者，他找到了通往玩家的道路--剩下的只是跟随着那个领导者。如果头目死了，小

浏览 0提问于2012-09-26得票数 6

回答已采纳

2回答

从Kmeans中查找每个集群的传播

c++、opencv、cluster-analysis、k-means、variance

我正在尝试检测输入向量对给定聚类中心的拟合程度。我可以很容易地找到最佳匹配(到输入向量的欧几里德距离最小的中心是最好的)，然而，我现在需要计算这是一个多好的匹配。为此，我需要找到价差(标准差？)在构成质心的向量中，看看我的输入向量到中心的距离是否小于散度。如果它超过了分布，我应该能够说我没有集群来拟合它(假设最好的不能很好地拟合输入向量)。我不确定如何找到每个簇的分布。我有所有的中心向量，并且所有的训练向量都用它们最接近的簇进行标记，我只是不能很好地理解我需要做什么才能得到扩散。我希望这是清楚的？如果没有，我会试着改写它！蒂娅·伊恩

浏览 3提问于2010-02-24得票数 3

回答已采纳

4回答

用于多个目标的2D平铺地图的寻路

c++、path-finding

我正在尝试用C++创建一个简单的基于网格的游戏。寻路是其中必要的一部分。我一直在找，但并不完全是我要找的。规则很简单。有一张地图。大小一般不超过100 x 100平铺。1是地砖，0是墙。不允许对角线移动，因此每个网格只有4个方向。然而，大多数情况下都有不止一个目标。我想找一条最近的路。记住，我们不能只计算距离公式，哪一个是最近的。距离短的目标可以走更远的路，因为有墙。我认为使用一种已知的算法，并为每个目标重复，这不是一个好主意，因为它会变慢。你的意见呢？我该怎么办？

浏览 0提问于2015-03-04得票数 1

2回答

基于非平铺的二维地图路径搜索(可能是势场)

2d、path-finding

我正在开发一个自上而下的2d僵尸射击在AS3。我实现了对分段(从a点到点b)、多边形(点数组、凸)和圆形障碍物(中心和半径)的碰撞，玩家和敌人基本上是围绕障碍物移动的，具有不同的半径。现在，我对僵尸AI的寻路有困难。我读过关于势场的文章，我觉得它很吸引人，但我想不出如何使它适应一张非瓷砖地图。我可以计算出从一个点到最近的障碍物的距离，并得到那个点上的排斥势。不过，我不知道如何让这位球员在这一点上具有吸引力。在基于平铺的地图中，您使用A*算法，将每个可行走的块作为节点。这是我的第一个问题。一旦我计算出球员在某一点上的吸引潜力，我得到的就是一个数字。在以瓷砖为基础的地图中，我会根据相邻的8个瓷

浏览 0提问于2014-02-01得票数 1

回答已采纳

2回答

动态导航网格生成算法

javascript、navmesh

我正在做一个2D游戏(自上而下/塞尔达喜欢的视图) 我正在努力进行导航网格生成，在复杂的场景中，我的自制算法丢失了，而且速度太慢. 我真的很想看到一个关于Hertel-Melhorn算法的详细解释(如果你有任何资源的话)。我对其他好算法的建议是开放的，只要我能处理圆形和方形的障碍。我的地图是随机生成的，任何时候都可以添加障碍。我不想使用网格系统，我的实体是自由定位的。我的地图很大，所以我不能存储预先计算好的路径/我只是需要路径查找才能有效我在使用Javascript，我不能使用c++库，比如绕道/重铸编辑我正在寻找快速三角剖分算法的详细文档。如果我理解了导航网格生成的过程：输入

浏览 0提问于2016-04-05得票数 2

4回答

明星:多个目标的启发式

algorithm、a-star

让我们考虑一个简单的网格，其中任何点最多与其他4个点(东北-东-西-南邻域)相连。我必须编写程序，计算从选定的初始点到的最小路径，任何目标点的都是连通的(在任意两个目标之间存在由目标点组成的路径)。当然，网格上也会有障碍。我的解决方案很简单:我使用的是带有可变启发式函数h(x) -曼哈顿距离的A*算法，从x到最近的目标点。为了找到最近的目标点，我必须进行线性搜索(在O(n)中，其中有n个目标点)。下面是我的问题:是否有更有效的解(启发式函数)来动态地找到最近的目标点(时间< O(n))？或者A*不是解决这个问题的好方法？

浏览 9提问于2011-12-26得票数 11

回答已采纳

2回答

矩阵上相同最小距离点数的求法

c++、algorithms、graph

我试图找出矩阵中具有相同最小距离的点数。从MxN矩阵开始，其中M和N< 50000。给出了一组不动点及其各自的坐标。问题是要找出矩阵中的点数，例如从集合中的任意点到集合中至少两个点的最小距离。距离是通过水平或垂直移动一个单位的时间来测量的。你不能斜移。举个例子可以让事情变得更清楚。假设我们有三个不动点：(1,3)，(3,1)和(3,6)。这里的点(3,3)是一个点，因为最小距离是2个单位，它可以到达集合中的前两个不动点。然而，点(4,4)并不满足需求。虽然距离(1,3)和(3,1)是相同的，4单位，最小距离是3单位。我的想法是使用整数坐标的任意一点，它位于一个段的平分线上，

浏览 0提问于2014-03-19得票数 4

3回答

2d数组元素之间的距离

c++、algorithm、multidimensional-array

我试着解决这个问题：有一个大小为n*m的矩形位图。位图的每个像素要么是白色的，要么是黑色的，但至少有一个是白色的。第一行和第j列中的像素称为像素(i，j).两个像素p1=(i1，j1)和p2=(i2，j2)之间的距离定义为： d(p1,p2)=|i1-i2|+|j1-j2|. 任务编写一个程序，其中：从标准输入读取位图的描述，对于每个像素，计算到最近的白色像素的距离，将结果写入标准输出。输入测试用例的数量t位于输入的第一行，然后t测试用例以空行分隔。在每个测试用例的第一行中，有一对整数n，m由单个空格1<=n <=182，1<=m<=182分隔。在测试用例

浏览 4提问于2011-04-02得票数 2

1回答

Google地图上离散值的热图可视化

google-maps、google-maps-api-3、maps、visualization、heatmap

我正在研究以下场景:我有一个地理位置，我需要创建一个热图可视化的旅行时间(通过汽车)从该地点到任何地方。我计划使用谷歌距离矩阵API来获得旅行时间。但是，由于它对API调用的no有限制，所以我需要以某种方式限制调用。到目前为止，我的计划是:计算一组点的旅行时间(基本上是一个数值)，这些点平均分布在给定位置周围的一个网格上(例如，向东0.5公里，向东0.5公里，向北0.5公里，向东0.5公里，向北1公里等等)。这个点代表正方形区域的中心，我会把到中心的旅行时间看作是到达区域内任何地方的旅行时间。这些区域在谷歌地图上以热图的形式显示为彩色方块。一个看上去很像的例子是：。所以，我的问题是：

浏览 2提问于2013-11-07得票数 1

1回答

如何在自上而下的低算法复杂度的透视游戏中表示地图？

2d、algorithm、maps

这是我第一次开发电子游戏，我有点迷失了。我想知道如何在自上而下的透视游戏中表示2D地图. (就像这个:venGadorg.github.io/1/game.html btw，这是我开发的第一个游戏) 到目前为止，我找到了一种在自上而下的透视游戏中表示2D地图的方法：使用矩阵。当一个正常的楼层用某个数字(或字符)表示时，障碍物用一个不同的数字来表示，而敌人则用另一个不同的数字表示。这个矩阵可以让我运行图论算法和疯狂的东西，但是我认为它在算法上是非常复杂的，因为这个图实际上是填充的和密集的。因此，所有的精灵都应该是相同的大小，否则，矩阵会非常非常大。还有其他(更好的)方法吗？在算法复杂度方

浏览 0提问于2014-08-06得票数 2

回答已采纳

2回答

网格地图中若干节点的最短路径算法

algorithm、graph、shortest-path

我有一个网格映射，我需要找到两个节点之间的最短路径，但是路径必须包括一些节点。我已经考虑过尝试所有的排列，但是映射的大小和必须节点的数目都是可变的，所以我想使用最优的算法。该地图将类似于以下内容： -Dark brown square at Y18 is the start point -Light brown squares from B20 to S20 are the end point (can make just one end point if needed) -White squares are walls (you cannot go through them) -Blue

浏览 0提问于2017-05-09得票数 1

回答已采纳

1回答

如何处理跨越不同尺度的短障碍碰撞？

collision-detection、path-finding

3D RPG中的朴素碰撞系统可能会导致暴徒被困在几何图形上，他们会现实地跨过去，这对许多玩家来说是一个很大的麻烦。对于大多数游戏来说，解决方案相当简单:禁用小对象上的冲突，因为从游戏的角度来看，它们并不重要。这是可行的，但假设暴徒的大小大致相同。引入更多的“大小类别”，从侏儒到龙，将需要仔细管理碰撞列表，并可能打破奇怪的角落案例。这同样适用于3D游戏中的导航网格，这些游戏都是机械的2D游戏。因此，我很好奇如何建立一个自适应系统来自动处理碰撞。约束和注意事项：我们可以假设所有相关的几何都是静态的，允许使用加速度结构。小物体对撞机组装成更大的结构，应该作为一个大的结构来碰撞。解决方案应

浏览 0提问于2021-10-20得票数 0

1回答

如何将矩形分成大小相等的部分，每个部分都与周边相连？

algorithm、geometry

我正在进行地图缩减设置中的Viewshed算法，并考虑到一个非常可靠的算法()，为了使其工作，我需要在下面的算法行中添加一些内容，我现在将对其进行解释：输入:所需区域数N、光栅(仅为矩阵) R和光栅/矩阵P中的一个点输出:n个区域，每个区域都是一个多边形(三角形或4个角多边形)，其中一个角在P处，其他角与R的周长相连。让我给你们举个例子输出可能是这样的，其中P位于中间：很明显P不需要站在中间。有谁知道这方面的好算法吗？

浏览 0提问于2015-01-07得票数 0

回答已采纳

2回答

一次生成二维距离网格

grid

我试图生成一个2D网格，用于导航，其中每个网格点保持距离最近的障碍(如无法通过的地形，或一座已建造的建筑物)。例如，一个包含障碍物的网格点是0，它旁边的网格点是1，下一个更远的网格点是2，等等。到目前为止，我已经能够通过多次传球来完成这个任务。每过一次，对于每个网格点，我从所有邻居处取最低值，并添加一个。如果我想测量出一个最大的距离，比如说，10个网格点，我必须通过10次，慢慢地递增最大距离的网格点。我的问题是，是否有一种方法可以在一次传递中生成这样的网格？这个网格将在游戏期间定期更新，并且可能非常大，所以我不想重复多次，如果我没有必要的话。

浏览 0提问于2014-04-13得票数 1

回答已采纳

3回答

最小出租车距离图

code-golf、matrix、binary-matrix

挑战描述在出租车计量学中，两点之间的距离 📷 定义为： 📷 考虑一个只有0和1的矩阵： 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 让我们将每个1映射到矩阵中最接近的不同1的距离(当然，假设相邻的两个行/列之间的距离等于1)： 0 0 0 3 0 2 0 0 0 0 0 0 0 0 0 1 0 0 3 0 1 0 0 0 0 对于这个挑战，给定一个矩阵，找到上面所示的距离图。示例 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 4 0 0 0 0 0 0 0 4 0 0 0 0 ----- 0 0 0 0 0

浏览 0提问于2017-08-09得票数 13

1回答

使用微软必应地图的谷歌距离矩阵

bing-maps

有没有像使用谷歌距离矩阵一样使用必应地图驱动REST服务的方法？我想能计算出距离： p1 -> p2 p1 -> p3 p1 -> p4 ... p1 -> p15 使用Google距离矩阵，我可以通过一个请求获得15条路线的距离，但是使用Bing我找不到一种方法(每个距离计算只有15个请求)。

浏览 3提问于2015-04-20得票数 0

回答已采纳

1回答

在不是障碍的网格中找到最接近目标的可用单元格，并且尽可能接近起始单元格？

python、algorithm

我得到的输入是:一个起始位置单元格，一个目标位置单元格，和一个占用网格(矩阵)，我需要返回从起点到目标的路径。(我会和Astar一起做) 问题是，我的目标可能在障碍物上或无法到达，而起始单元承诺是可用的。如果我的目标是一个被占用的单元格，我需要返回最接近可达目标的单元格，如果可能，我还希望它尽可能靠近起始单元格，这意味着如果我有两个都可用的单元格，并且离目标的距离最小，我将选择离起始单元格最近的一个。 Example 1: S 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0

浏览 1提问于2018-12-22得票数 0

2回答