用未知的连接线均匀分布的矩形的algorithm

我对游戏开发并不熟悉,但是我正在试图找出一个好的algorithm来定位给定表面区域的矩形(任何宽度和高度),并将它们与任何线条的变化连接起来。 两个矩形永远不会有多于一条线连接它们。

我会在哪里开始处理这样的问题? 这只是一个二维曲面。 我读了关于图论的内容,似乎这是一个很好的代表。 矩形将被视为一个节点,连接它们的线将被视为图论中的一条边。

Solutions Collecting From Web of "用未知的连接线均匀分布的矩形的algorithm"

这听起来像是在为游戏寻找一个不寻常的问题:给一堆带有连接边的矩形,把它们放在一起,这样没有任何矩形或边( 我猜 )重叠。 通常布局在地图生成过程中发生,这意味着它是微不足道的。

一般的问题是,用一组目标(尽可能减less重叠,边长尽可能)来布置平面图,这是graphics绘制中的一个主要研究领域。 人们写这些东西的文件,这可能很酷,但可能是一个新的游戏开发的人有点沉重。

因此,我建议你采用现有的graphics布局algorithm ,并修改它以包含矩形重叠准则 。 取决于你想做什么,它可能是微不足道的,或者你可能需要深入到algorithm的肠子。

请记住,你绝不保证没有重叠; 回想起没有解决scheme的三个公用事业难题 (但绝不会混淆networking)。

这是你可以做到的一个方法。 要理解的最简单的graphics布局algorithm之一是以力为导向的algorithm – 它们将graphics模拟为相互排斥的节点,以及弹簧般的边缘,并尝试尽可能缩短边界。 甚至还有一个开源的javascript版本,这里叫做springy.js ( GitHub , demo ):

弹性的演示图

你可以做这两件事之一:

  • 添加长度足够长的边以保证矩形不重叠。 但是,如果您有细长的矩形,则可能会得到非常稀疏的布局。
  • tick函数中 ,如果检测到矩形重叠,则添加一个应用较大排斥力的函数。

不幸的是,经典的强制定向图布局algorithm不能很好地解决边缘重叠问题。 幸运的是,由于它的dynamic特性,它对初始条件非常敏感,所以您可以重复运行该algorithm,直到获得好的结果。