如何在Houdini地牢生成器的最小生成树（MST）中添加环

我正在用Houdini开发地牢生成器，已经用Prim算法实现了最小生成树（MST）的地牢路径，现在希望添加1-2个环，让地牢结构更贴近自然形态。当前使用的VEX代码如下：

int pts[]  = expandpointgroup(0, 'unconnected_rooms');  

float dist_min = 100000;   
int pt_0 = -1;
int pt_1 = -1;

foreach(int pt; pts)
{
    vector pos = point(0, 'P', pt);
    int pt_near = nearpoint(0, '!unconnected_rooms', pos);  
    vector pos_near = point(0, 'P', pt_near);   
    float dist = distance(pos, pos_near);
    if(dist < dist_min) 
    {
        dist_min = dist;
        pt_0 = pt;
        pt_1 = pt_near;
    }
}

addprim(0, 'polyline', pt_0, pt_1);
setpointgroup(0, 'unconnected_rooms', pt_0, 0, 'set');

实现思路 #

要在最小生成树基础上加环，关键就是给两个已经连通的房间节点多连一条路——毕竟最小生成树本身没环，随便加一条连通已存在节点的边，自然就形成环了。为了让地牢看起来更自然，最好选距离适中的节点对，别加太近或太远的，不然环会很突兀。

具体做法 #

1. 先等最小生成树生成完，确保所有房间都进了连通组（也就是unconnected_rooms这个组是空的）。
2. 挑合适的节点对：
   • 先把所有房间节点都收集起来；
   • 随机选两个不一样的节点，算它们之间的距离；
   • 可以设个距离门槛，跳过太近或太远的，保证环的大小合理。
3. 给选中的节点对加一条新的路径（polyline），这样就形成环了。

修改后的VEX代码示例 #

你可以在原来生成最小生成树的代码跑完后，加上这段代码（可以放在同一个Wrangle里，也单独用一个Wrangle节点）：

// 先确认所有房间都连通了，也就是unconnected_rooms组为空
if (expandpointgroup(0, 'unconnected_rooms').length() == 0) {
    // 收集所有房间节点，这里假设你用'rooms'组标记所有房间
    int all_pts[] = expandpointgroup(0, 'rooms'); 
    int total_rooms = len(all_pts);
    
    // 要生成的环数量，用参数控制，默认1个
    int loop_count = chi("loop_count"); 
    
    for (int i = 0; i < loop_count; i++) {
        // 随机选两个不同的节点
        int idx_a = int(rand(i) * total_rooms);
        int idx_b = int(rand(i+100) * total_rooms);
        // 确保两个节点不一样
        while (idx_a == idx_b) {
            idx_b = int(rand(i+200) * total_rooms);
        }
        int room_a = all_pts[idx_a];
        int room_b = all_pts[idx_b];
        
        // 计算距离，跳过太近的（可选，根据你的地牢尺寸调）
        vector pos_a = point(0, 'P', room_a);
        vector pos_b = point(0, 'P', room_b);
        float dist = distance(pos_a, pos_b);
        float min_dist = chf("min_loop_distance"); // 比如设成5，避免相邻房间直接连
        
        if (dist >= min_dist) {
            // 加一条新路径，形成环
            addprim(0, 'polyline', room_a, room_b);
        } else {
            // 距离太近就重选一次
            i--;
        }
    }
}

小技巧 #

• 把环的数量、最小距离做成Houdini的可调参数，方便你试不同的地牢形态；
• 可以记录已经加过的边，别重复连同一对房间；
• 如果想让环的大小更均匀，可以算两个房间在最小生成树里的路径长度，选路径长度适中的来加边，这样生成的环不会太小或太大。

内容的提问来源于stack exchange，提问作者Filippo Biancone