矩形分离集的分离导向算法

Question

最近几天尝试自己实现 TinyKeep 的地牢生成算法。

Link to TinyKeep's dungeon generation algorithm

我不是 100% 完全理解它，因为我在这里 :)

首先我生成了一组圆形的房间去集合中的每个房间。选择它并再次使用另一个 for 循环来比较每个房间的交叉点。

如果房间相交，我加力，我将应用分离。在该嵌套循环结束后，我根据该力矢量从第一个循环移动当前房间。等等。直到每个房间都不与其他房间重叠为止。

我还选择了矩形的中心（中间）点（x+width/2f、y+height/2f）来计算力向量

如果矢量被归一化，那么房间会挤满，但如果没有 - 房间之间有很多 space...

我只想重新创建并理解 TinyKeep 的算法，但结果不一样...

我也得到奇怪的结果，然后 tall/wide 房间或总是在角落里，高的去地图的左上角，宽的 - 右下角。而且有时都有整体对角线分开的方向

// Main method
private void Separate()
        {
            do
            {
                for (int i = 0; i < rooms.Count; i++)
                {
                    Vector2 force = Vector2.zero;
                    int overlapCounter = 0;

                    for (int j = 0; j < rooms.Count; j++)
                    {
                        if (i == j) continue;

                        if (!rooms[i].IsOverlapped(rooms[j])) continue;

                        force += rooms[j].Middle - rooms[i].Middle;
                        overlapCounter++;
                    }

                    if (overlapCounter == 0) continue;

                    force /= overlapCounter;
                    force.Normalize();
                    force *= -1f;

                    rooms[i].Move(force);
                }

            } while (IsAnyRoomOverlapped());

            StopTimer(true);
        }

// Room.Move()
public void Move(Vector2 move)
        {
            x += Mathf.CeilToInt(move.x)* TILE_SIZE;
            y += Mathf.CeilToInt(move.y)* TILE_SIZE;
        }

// Constructor
public Dungeon(int roomAmount, int seed,float radius)
        {
            StartTimer();

            this.roomAmount = roomAmount;
            this.radius = radius;
            Seed = seed;

            InitializeRandom();
            PopulateDungeonWithRooms();
        }

Answer 1

在尝试弄清楚如何解决这个问题时，我阅读了一些问题并查看了它们的源代码。我发现他们不仅在找到每个重叠的邻居后移动空间，而且还会将邻居移动到另一个方向！

分离的定向行为如何？四舍五入为整数是我的错误或误解

性能怎么样？使用正态分布在半径为 128 单位的圆内生成 512 个房间得到 1100 毫秒

现在，代码如下所示：

private void SeparateRooms()
        {
            do
            {
                for (int current = 0; current < rooms.Count; current++)
                {
                    for (int other = 0; other < rooms.Count; other++)
                    {
                        if (current == other || !rooms[current].IsOverlapping(rooms[other])) continue;

                        var direction = (rooms[other].Middle - rooms[current].Middle).normalized;

                        rooms[current].Move(-direction, TILE_SIZE);
                        rooms[other].Move(direction, TILE_SIZE);
                    }
                }
            }
            while (IsAnyRoomOverlapped());

            StopTimer(true);
        }

和 Room 的 Move() 方法：

public void Move(Vector2 move,int tileSize=1)
        {
            x += Mathf.RoundToInt(move.x)*tileSize;
            y += Mathf.RoundToInt(move.y)*tileSize;
        }

矩形分离集的分离导向算法

Separation steering algorithm for separationg set of Rectangles

c#

algorithm

unity3d

procedural-generation