I’ve recently been implementing an animated graph flood-fill algorithm, the main feature of which is the animated transition of an “impulse” between selected vertices of the graph. Let me briefly explain:
- Graph Structure: This is how the graph structure looks:
{
"1": {
"coordinates": [0.1, 0.4, -1],
"connections": [3, 5]
},
"2": {
"coordinates": [0.2, -0.4, 0.2],
"connections": [1]
},
"3": {
"coordinates": [1, -0.3, 0.9],
"connections": [1, 2]
},
"4": {
"coordinates": [-0.5, 0.4, 0.9],
"connections": []
},
"5": {
"coordinates": [0.0, 0.1, -0.2],
"connections": [4, 2]
}
}
- FloodFill Class: I use a
FloodFillclass with two async methods:animateImpulseandfill.
function startImpulseFromAttributes() {
const graph = parseGraphDict();
const floodFill = new FloodFill(graph, animationSpeed);
floodFill.fill(startVertex, impulsePower, (impulse, vertex) => {
post("Impulse", JSON.stringify(impulse), " active at vertex ", JSON.stringify(vertex));
});
}
var activeObjects = []; // List to track created objects
function cleanupAllObjects() {
activeObjects.forEach(obj => obj.freepeer());
activeObjects = []; // Clear the list
}
class FloodFill {
constructor(graph, animationSpeed) {
this.graph = graph;
this.animationSpeed = animationSpeed;
}
async animateImpulse(startCoord, endCoord, speed) {
return new Promise((resolve) => {
const gridshape = new JitterObject("jit.gl.gridshape", contextName);
gridshape.shape = "cone";
gridshape.color = [Math.random(), Math.random(), Math.random()];
const animNode = new JitterObject("jit.anim.node");
gridshape.anim = animNode.name;
animNode.movemode = "local";
animNode.scale = impulseScale;
animNode.position = startCoord;
animNode.lookat = endCoord;
const animDrive = new JitterObject("jit.anim.drive");
animDrive.targetname = animNode.name;
animDrive.move(0, 0, speed);
const goalVector = endCoord.map((v, i) => v - startCoord[i]);
const checkPosition = new Task(() => {
const pos = animNode.worldpos;
const currentVector = pos.map((v, i) => v - startCoord[i]);
if (veclength(currentVector) >= veclength(goalVector)) {
post("Animation completen");
gridshape.freepeer();
animNode.freepeer();
animDrive.freepeer();
checkPosition.cancel();
resolve();
// post("Resolved promisen");
}
});
checkPosition.interval = worldposQueryInterval;
checkPosition.repeat();
})
}
async fill(startVertexId, stepsLeft, actionCallback) {
if (stepsLeft <= 0) {
post("Stopped at vertex: ", startVertexId, ", no steps leftn");
return;
}
const connections = this.graph[startVertexId]?.connections || [];
post("Connections for vertex ", startVertexId, ": ", JSON.stringify(connections), "n");
if (connections.length === 0) {
post("Stopped at vertex: ", startVertexId, ", no connectionsn");
return;
}
const powerPerConnection = Math.floor(stepsLeft / connections.length);
post("Power per connection: ", powerPerConnection, "n");
if (powerPerConnection <= 1) {
post("Power per connection too low, stopping recursionn");
return;
}
try {
await Promise.all(connections.forEach(async (nextVertexId) => {
post("Calling animateImpulse with start: ", JSON.stringify(this.graph[startVertexId]?.coordinates), " and end: ", JSON.stringify(this.graph[nextVertexId]?.coordinates), "n");
try {
await this.animateImpulse(
this.graph[startVertexId]?.coordinates,
this.graph[nextVertexId]?.coordinates,
animationSpeed * scaleToAnimationSpeed(this.graph[startVertexId], this.graph[nextVertexId])
);
} catch (e) {
post("Error in animateImpulse: ", e, "n");
}
await this.fill(nextVertexId, powerPerConnection - 1, actionCallback);
}));
} catch (e) {
post("Error resolving Promise in fill: ", e, "n");
}
}
}
The animateImpulse method is written for the Max/MSP Jitter API, which is why I’m using the Max/MSP API function post() instead of console.log. Essentially, it spawns a single 3D object and drives it from one coordinate to another, which takes some time. It can be replaced by a random timeout without changing its overall meaning. The important thing to note is that it returns a promise that resolves when the animation is complete (i.e., the point has reached its destination). It also uses something called Task, which checks the position of the object being animated at regular intervals.
The fill method is a recursive flood-fill algorithm. If you think of the directed graph as a tree, it traverses the graph with the ability to revisit nodes. I am avoiding cycles and iterations in this algorithm because I wanted the animation to be smooth, with no animations waiting for others to complete. This is also why I opted for recursion.
The Problem
During testing, I noticed that the algorithm behaves inconsistently between executions. The patterns of this unexpected behavior include:
-
Skipped Animations: It sometimes skips animations for certain paths. This doesn’t happen randomly; it always skips specific paths. Logs show that for some paths, the promise resolves before the animation even starts.
-
Unexpected Animations: It occasionally calls
animateImpulsefor vertices it is not supposed to animate.
These issues usually occur when one or many time-consuming animations are still in progress.
Is there something I might be overlooking in the design of the algorithm or its implementation that could cause these behaviors? Or is it a problem of MaxMsp JS API? Any suggestions or pointers would be greatly appreciated!
Let me know if you’d like further refinements! I’ll leave the files and a video of how the animation looks like.
https://drive.google.com/drive/folders/1ISaK6ISGsSeO-CKO12QlM-p-0J8CVM_8?usp=drive_link