Optimizing Shortest Path Networks

calendar_today

03.03.2025

label

Vegetation

mouse

Houdini 20.5

Description

Optimizing network efficiency by incrementally mapping shortest paths back onto the base mesh with interactive nodes to randomize path order and adjust weighting. A heat output attribute highlights frequently used paths.

1 Initializing the base mesh

On a base mesh we initialize a weight attribute to map traveling costs and a heat attribute to track how often each point was traversed.

// INITIALIZE
f@weight = 1.0;
f@heat = 0.0;

To guide the shortest path node, we add "starts" and "ends" point groups, and optionally randomize the "ends" order to affect iterative pathfinding.

// SHUFFLE POINTS
int seed = chi('seed');

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

float vals[];
resize(vals, len(pts));
foreach(int i; float v; vals){
    vals[i] = rand(i, seed);
}
int idx[] = argsort(vals);

i[]@ends = reorder(pts, idx);

2 Weighting the network

Within a for loop, we use the iteration number to select each "ends" group point sequentially, placing it into a new "end" group as the sole target for the shortest path node.

int pts[] = detail(0, 'ends', 0);

int iter = detail(-1, 'iteration', 0);
setpointgroup(0, 'end', pts[iter], 1, 'set');

We output the shortest path with its original mesh point number @origpt and previous mesh point @prevpt, adding the edge to the "network" group. We then reduce the weight for this mesh point to make it more attractive for the path of the next iteration and increment the heat to indicate this path has been used.

float weight = chf('weight');

foreach(int i; int pt_orig; i[]@origpt){
    setedgegroup(0, 'network', pt_orig, i[]@prevpt[i], 1);
    setpointattrib(0, 'weight', pt_orig, weight, 'set');
    setpointattrib(0, 'heat', pt_orig, 1.0, 'add');
}

3 Extracting Curves

The "curve from edges"-node extracts the "network" edge group from the base mesh while the color node maps the accumulated heat.

4 Network variations

While the base mesh points are weighted as 1.0, traversed mesh points as seen on the image received lower weights such as 0.0, 0.2, 0.4, 0.6, 0.8 or again 1.0.

download

Downloads