矩形分离集的分离导向算法
Separation steering algorithm for separationg set of Rectangles
最近几天尝试自己实现 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();
}
在尝试弄清楚如何解决这个问题时,我阅读了一些问题并查看了它们的源代码。我发现他们不仅在找到每个重叠的邻居后移动空间,而且还会将邻居移动到另一个方向!
分离的定向行为如何?四舍五入为整数是我的错误或误解
性能怎么样?使用正态分布在半径为 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;
}
最近几天尝试自己实现 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();
}
在尝试弄清楚如何解决这个问题时,我阅读了一些问题并查看了它们的源代码。我发现他们不仅在找到每个重叠的邻居后移动空间,而且还会将邻居移动到另一个方向!
分离的定向行为如何?四舍五入为整数是我的错误或误解
性能怎么样?使用正态分布在半径为 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;
}