In attempting to design an algorithm for simulating fluid spread and dissipation, I have encountered a problem caused by the branching recursive function spreadAboutCenter (see MCVE) entering an infinite cycle.
I had thought I’d covered every base case, but evidently not. Testing the original version of the script in my Minecraft Bedrock addon caused an Event 41 unexpected restart. After that, I added the depth <= 4 constraint to the ‘fluid drying up’ functions to prevent future crashes, and revised the quaternary part of the recursive function to include a stricter set of conditions.
Specifically, when determining whether to perform the recursive step in each of the 4 directions, there is now an extra check to ensure the next block will be further away from any nearby fluid source blocks than is the current block. This should prevent the recursive call to the adjacent block from triggering a circular recursive call back to the original block, as they can’t both be further away.
// Recursive calls on the 4 horizontally adjacent blocks
// Only proceed in a given direction if either no nearby sources were found, or else the adjacent block in that direction will be further from any/all sources than mB is (along either the x or the z axis).
// Not being able to move back in the direction of a source should prevent an infinite cycle of recursive calls from being generated (which seems to have been the problem with the previous version of this algorithm).
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjName = adjacents[i].cell.textContent;
if (adjName.includes("m") && (!sourceCoords || isMoreDistantFromAll(adjacents[i], mB, sourceCoords))) {
setTimeout(function() { return spreadAboutCenter(adjacents[i], x, z, recursionDepth + 1); }, miasmaSpreadInterval);
}
}
}
But, something is still causing unexpectedly high numbers of recursive calls to be generated in certain situations. (Now, this will only trigger the depth limit condition and print the “OVERFLOW” message.) I know that the problem must originate in the above for loop, because adding the line console.log("Depth " + recursionDepth); inside the loop causes Depth 5 to be printed before the overflow message is displayed.
I’ve looked over each base case multiple times and still can’t see what it is I’m missing.
Any help identifying the exact cause and how to fix it is greatly appreciated.
Background: The code in the snippet below is supposed to recreate Minecraft’s fluid spreading and dissipation physics: it is intended to be used with a custom fluid, called ‘miasma,’ which I’m planning on including as part of a Bedrock Edition Addon. The script will go in main.js. Miasma is a glowing purple liquid with a viscosity in between that of water and lava, which can be placed and picked up with a bucket.
-
When a miasma source block is placed, using a full bucket, it will branch out into a descending “+” shape if it is not above a solid surface, and if it is above solid blocks, it will spread out in increasingly shallower levels around the source, until it reaches the maximum spread level of 3.
-
When a miasma source block is picked back up using an empty bucket, the source gets replaced with air, and, starting from the newly empty center, each ring of surrounding miasma blocks gets shallower by 1 spread level until all have evaporated (i.e. reached spread level 3 and then been replaced by air).
-
Non-source miasma blocks cannot be picked up.
You can easily observe one of the problematic cases (causing the “OVERFLOW” message to be logged) by recreating the configuration in the image below (you’ll only need the second layer, which is the top right quadrant), then picking up the “m0” block next to the cursor with an empty bucket:
var tDiv = document.getElementById("tableDiv");
var tbl = document.createElement("table");
tbl.id = "chunk";
// References: https://stackoverflow.com/questions/8302166/dynamic-creation-of-table-with-dom and https://stackoverflow.com/questions/3319683/add-id-to-dynamically-created-div
var row;
var tCell;
var innerTbl;
var row2;
var tCell2;
for (var r = 0; r < 2; r++) {
row = document.createElement("tr");
tbl.appendChild(row);
for (var c = 0; c < 2; c++) {
tCell = document.createElement("td");
innerTbl = document.createElement("table");
tCell.appendChild(innerTbl);
row.appendChild(tCell);
for (var r2 = 0; r2 < 16; r2++) {
row2 = document.createElement("tr");
innerTbl.appendChild(row2);
for (var c2 = 0; c2 < 16; c2++) {
tCell2 = document.createElement("td");
if (r + c === 0) {
tCell2.textContent = "S";
} else {
tCell2.textContent = "A";
}
row2.appendChild(tCell2);
}
}
}
}
tDiv.appendChild(tbl);
const bounds = {
vMin: -1,
vMax: 4,
hMin: -1,
hMax: 16
}; // Values are exclusive: valid block coordinates must be > min and < max
const miasmaSpreadInterval = 1000; // 1000 ms = 1 second
const testArea = document.getElementById("chunk");
const layers = [
testArea.children.item(0).children.item(0).children.item(0),
testArea.children.item(0).children.item(1).children.item(0),
testArea.children.item(1).children.item(0).children.item(0),
testArea.children.item(1).children.item(1).children.item(0)
];
var blocks = [];
var Block = function(x, y, z, cell) {
this.x = x;
this.y = y;
this.z = z;
this.cell = cell;
};
for (let y = 0; y < layers.length; y++) { // Can't use 'var' here, because that would assign all array elements based on the *last* values of x, y and z
blocks[y] = [];
for (let x = 0; x < 16; x++) {
blocks[y][x] = [];
for (let z = 0; z < 16; z++) {
blocks[y][x][z] = new Block(x, y, z, layers[y].children.item(x).children.item(z));
blocks[y][x][z].cell.addEventListener("click", function() {
playerInteractWithBlock(blocks[y][x][z]);
});
}
}
}
function getBlockAbove(b) {
if (b.y + 1 < bounds.vMax) {
return blocks[b.y + 1][b.x][b.z];
}
}
function getBlockBelow(b) {
if (b.y - 1 > bounds.vMin) {
return blocks[b.y - 1][b.x][b.z];
}
}
function getBlockNorthOf(b) {
if (b.x - 1 > bounds.hMin) {
return blocks[b.y][b.x - 1][b.z];
}
}
function getBlockSouthOf(b) {
if (b.x + 1 < bounds.hMax) {
return blocks[b.y][b.x + 1][b.z];
}
}
function getBlockEastOf(b) {
if (b.z + 1 < bounds.hMax) {
return blocks[b.y][b.x][b.z + 1];
}
}
function getBlockWestOf(b) {
if (b.z - 1 > bounds.hMin) {
return blocks[b.y][b.x][b.z - 1];
}
}
// selectedItem can be "full bucket" or "empty bucket"
var player = {
selectedItem: "full bucket",
miasmaBucketCooldown: false
};
var selectedLabel = document.getElementById("selected");
document.getElementById("full").addEventListener("click", function() {
player.selectedItem = "full bucket";
selected.textContent = "Full Bucket";
});
document.getElementById("empty").addEventListener("click", function() {
player.selectedItem = "empty bucket";
selected.textContent = "Empty Bucket";
});
/* Miasma Block Variants: m0 (source), m1 (spread level 1), m2 (spread level 2), m3 (spread level 3), mv (vertically flowing), m0v (vertically flowing source) */
/* Other Possible Blocks: S (solid) and A (air) */
// Miasma flowing, spreading, and source-forming mechanics
function spreadMiasma(mB) {
const mBName = mB.cell.textContent;
if (!mBName.includes("m")) { // It's not a miasma block, and so can't spread
return;
} else {
const adjacents = [getBlockNorthOf(mB), getBlockSouthOf(mB), getBlockEastOf(mB), getBlockWestOf(mB)];
const belowB = getBlockBelow(mB);
var belowBName;
if (belowB !== undefined) {
belowBName = belowB.cell.textContent;
}
// VERTICAL FLOW (from miasma block of any numbered depth, or vertically flowing)
// Replace air or other miasma block variants with the vertically flowing miasma block
if (belowBName !== undefined && (belowBName === "A" || (belowBName.includes("m") && !belowBName.includes("v"))) && (mB.y - 1) > bounds.vMin) {
if (belowBName === "m0") {
// Convert source block to vertically flowing source block
belowB.cell.textContent = "m0v";
} else {
belowB.cell.textContent = "mv";
}
setTimeout(function() {
return spreadMiasma(belowB);
}, miasmaSpreadInterval); // Recursive call for newly placed vertical block under current block
}
// Vertically flowing miasma won't spread horizontally unless it is directly above a non-air, non-miasma block
if (mBName.includes("v")) {
if (belowBName !== undefined && belowBName !== "A" && !belowBName.includes("m")) {
// LET, not VAR! Function-scoped variables and closures don't get along well :D
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjName = adjacents[i].cell.textContent;
// If the flowing miasma is above anything other than air or vertically flowing miasma, spread lvl 1 miasma to each horizontally adjacent air or higher-spread-level miasma block
if (adjName === "A" || (adjName.includes("m") && Number(adjName[adjName.length - 1]) > 1)) {
adjacents[i].cell.textContent = "m1";
setTimeout(function() {
return spreadMiasma(adjacents[i]);
}, miasmaSpreadInterval);
}
}
}
}
} else {
const aboveB = getBlockAbove(mB);
var aboveBName;
if (aboveB !== undefined) {
aboveBName = aboveB.cell.textContent;
}
// SOURCE BLOCK CONVERSION
// Any miasma block adjacent (including vertically) to two or more source blocks is converted to a source block (= m0 or m0v)
var adjacentSourceBlocks = ((aboveBName === "m0" || aboveBName === "m0v") && (belowBName === "m0" || belowBName === "m0v")) ? 2 : (((aboveBName === "m0" || aboveBName === "m0v") || (belowBName === "m0" || belowBName === "m0v")) ? 1 : 0);
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjName = adjacents[i].cell.textContent;
if (adjName === "m0" || adjName === "m0v") {
adjacentSourceBlocks++;
}
}
}
if (adjacentSourceBlocks >= 2) {
if (aboveBName !== undefined && aboveBName.includes("m")) {
mB.cell.textContent = "m0v";
} else {
mB.cell.textContent = "m0";
}
}
// HORIZONTAL SPREADING
// Shallowest depth possible is "end:miasma_3" block
const lvl = Number(mBName[mBName.length - 1]);
// Convert source block to vertically flowing source block if there is another miasma block above it
if (lvl === 0) {
if (aboveBName !== undefined && aboveBName.includes("m")) {
mB.cell.textContent = "m0v";
}
}
if (lvl < 3) {
// LET, not VAR! (Same reason as above)
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined && getBlockBelow(adjacents[i]) !== undefined) {
let adjName = adjacents[i].cell.textContent;
let belowAdjName = getBlockBelow(adjacents[i]).cell.textContent;
// Only source blocks will spread horizontally in air, to prevent a giant cone from forming if every level could spread.
// Why test for >= instead of just >, when this means blocks will be re-set to the same thing? Because otherwise, blocks adjacent to placed sources won't be evaluated to be converted to new source blocks.
if (((belowAdjName !== undefined && belowAdjName !== "A" && !belowAdjName.includes("m")) || lvl === 0) && (adjName === "A" || (adjName.includes("m") && !adjName.includes("v") && Number(adjName[adjName.length - 1]) >= (lvl + 1)))) {
adjacents[i].cell.textContent = "m" + (lvl + 1);
setTimeout(function() {
return spreadMiasma(adjacents[i]);
}, miasmaSpreadInterval);
}
}
}
}
}
}
}
// Prevent excessive resource demands in case of an unexpectedly high number of recursive calls being generated
var numberOfRecursiveCalls = 0;
var maxDepth = 0; // Only increment this for horizontal spreading, not vertical, because recursion in the vertical direction is linear and not branching
var overflowed = false; // If this becomes true, the spreadAboutCenter function will exit early.
// DEBUGGING: remove this later! --------------------------------------------------------------------------
// It's OK to modify and access these global variables from different threads, because JS is guaranteed not to have simultaneous-access issues.
function progressReport() {
console.log("# of total recursive calls: " + numberOfRecursiveCalls);
console.log("Maximum depth reached: " + maxDepth);
if (overflowed) {
console.log("OVERFLOW");
}
}
setInterval(progressReport, 3000); // Every 3 seconds
// --------------------------------------------------------------------------------------------------------
// Return type of this function will vary.
// If any sources/vertical blocks are located within the specified distance, it will return an array of objects containing those blocks' x and z coordinates. (This evaluates to *true* in conditional statements.)
// Otherwise, it will return false.
function isSourceOrVerticalWithin4Blocks(x, y, z) {
var coords = [];
for (var xAway = -3; xAway < 4; xAway++) {
for (var zAway = -3; zAway < 4; zAway++) {
if ((Math.abs(xAway) + Math.abs(zAway) < 4) && ((x + xAway) > bounds.hMin && (z + zAway) > bounds.hMin && (x + xAway) < bounds.hMax && (z + zAway) < bounds.hMax)) {
const bName = blocks[y][x + xAway][z + zAway].cell.textContent;
if (bName.includes("m0") || bName === "mv") {
coords.push({
x: x + xAway,
z: z + zAway
});
}
}
}
}
return (coords.length) ? coords : false;
}
// 'next' and 'current' should be Block object references; 'comparisons' should be an array of objects of the form {x: Number, z: Number}
// Returns true if the distance of the x- and z-coordinates provided for 'next' is greater than that for 'current' from all the pairs of coordinates in the array, and false otherwise.
function isMoreDistantFromAll(next, current, comparisons) {
var compared = {};
for (var i = 0; i < comparisons.length; i++) {
// If 'next' is further than 'current' from the source in a given direction, the value for that direction will be *positive*. If it is an equal distance away, the value will be *0*. If it is closer, the value will be *negative*.
compared.x = Math.abs(next.x - comparisons[i].x) - Math.abs(current.x - comparisons[i].x);
compared.z = Math.abs(next.z - comparisons[i].z) - Math.abs(current.z - comparisons[i].z);
// If 'next' is closer than 'current' to the source *in either direction*, OR 'next' is *not* further than 'current' in *at least one* direction, return false
if ((compared.x < 0) || (compared.z < 0) || (compared.x + compared.z === 0)) {
return false;
}
}
return true;
}
// Starting at the lowest-spread-level (i.e. greatest depth) miasma block in each puddle, decrease its level by 1 increment per second, and do the same for each miasma block horizontally adjacent to it after a 1-second delay.
// Only dissipate numbered miasma blocks which remain disconnected from any source or vertical miasma blocks.
function spreadAboutCenter(mB, x, z, recursionDepth) {
numberOfRecursiveCalls++;
var xDist = Math.abs(mB.x - x);
var zDist = Math.abs(mB.z - z);
if (recursionDepth > maxDepth) {
maxDepth = recursionDepth;
}
if (recursionDepth > 4) {
overflowed = true;
return;
} else if (xDist < 3 && zDist < 3 && (xDist + zDist < 3)) { // Dist is one less than it would be for a source (so, 3 instead of 4), because the minimum spread level of the center blocks for this function is 1, not 0
var blockName = mB.cell.textContent;
// Somehow, this function got called on something other than a numbered, non-source miasma block.
if (blockName.includes("v") || !blockName.includes("m") || blockName === "m0") {
return;
} else {
var sourceCoords = isSourceOrVerticalWithin4Blocks(mB.x, mB.y, mB.z);
// Replace highest spread level miasma block with air (unless there's another source or vertical miasma block nearby)
if (blockName === "m3" && !sourceCoords) {
mB.cell.textContent = "A";
}
// Replace any other spread level miasma block with the block 1 spread level greater than it
else {
const adjacents = [getBlockNorthOf(mB), getBlockSouthOf(mB), getBlockEastOf(mB), getBlockWestOf(mB)];
var lvl = Number(blockName[blockName.length - 1]);
// Don't dissipate the puddle if there's another source or vertical miasma block nearby
if (!sourceCoords) {
mB.cell.textContent = "m" + (lvl + 1);
// Recursive call on original block
setTimeout(function() {
return spreadAboutCenter(mB, x, z, recursionDepth + 1);
}, miasmaSpreadInterval);
}
// Recursive calls on the 4 horizontally adjacent blocks
// Only proceed in a given direction if either no nearby sources were found, or else the adjacent block in that direction will be further from any/all sources than mB is (along either the x or the z axis).
// Not being able to move back in the direction of a source should prevent an infinite cycle of recursive calls from being generated (which seems to have been the problem with the previous version of this algorithm).
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjName = adjacents[i].cell.textContent;
if (adjName.includes("m") && (!sourceCoords || isMoreDistantFromAll(adjacents[i], mB, sourceCoords))) {
setTimeout(function() {
return spreadAboutCenter(adjacents[i], x, z, recursionDepth + 1);
}, miasmaSpreadInterval);
}
}
}
}
}
}
}
// Miasma dissipating when the source is removed: any ground-level numbered miasma block that is not within 4 blocks of a source (or of a flowing block under a source) has its spread level increase by 1
// per spreadInterval, starting with the deepest (or topmost) block; any vertically flowing block (and any miasma block floating in air) will disappear instantly if not connected vertically to a source.
function dissipateMiasma(mB, x, z, recursionDepth) {
numberOfRecursiveCalls++;
if (recursionDepth > maxDepth) {
maxDepth = recursionDepth;
}
if (recursionDepth > 4) {
overflowed = true;
return;
} else {
const mBName = mB.cell.textContent;
// If a source is encountered, do not continue. Also don't check any blocks that are not some variant of miasma, or are more than 4 blocks away from the current center.
// When a source is removed with a bucket, the center is initialized to the coords of the removed source. When a vertical flowing block is encountered, the center is reset to that block's x and z coords.
var xDist = Math.abs(mB.x - x);
var zDist = Math.abs(mB.z - z);
if ((xDist < 4 && zDist < 4 && (xDist + zDist < 4)) && mBName.includes("m") && !mBName.includes("m0")) {
const adjacents = [getBlockNorthOf(mB), getBlockSouthOf(mB), getBlockEastOf(mB), getBlockWestOf(mB)];
var mB_above = getBlockAbove(mB);
var mB_below = getBlockBelow(mB);
var aboveBName;
var belowBName;
if (mB_above !== undefined) {
aboveBName = mB_above.cell.textContent;
}
if (mB_below !== undefined) {
belowBName = mB_below.cell.textContent;
}
if (mBName === "mv") {
// There is another non-source miasma block above mB: perform *instant* recursive call upwards, and do not increment the depth
if (aboveBName !== undefined && aboveBName === "mv" || (aboveBName.includes("m") && !aboveBName.includes("m0"))) {
dissipateMiasma(mB_above, mB_above.x, mB_above.z, recursionDepth);
}
// mB is the topmost flowing block -- replace it with air and perform *delayed* recursive step downwards if block below is not a source
else if (aboveBName !== undefined && !aboveBName.includes("m")) {
mB.cell.textContent = "A";
// If mB is directly above a flowing source, replace the flowing source block with a still source block and exit the function
if (belowBName !== undefined && belowBName === "m0v") {
mB_below.cell.textContent = "m0";
return;
}
// The block below mB is a non-source block: either "mv" or a non-miasma block
else if (belowBName !== undefined && belowBName !== "m0") {
// If the block under mB is not miasma, perform *delayed* recursive steps on the 4 adjacent blocks, without changing the center coordinates
if (!belowBName.includes("m")) {
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
setTimeout(function() {
return dissipateMiasma(adjacents[i], x, z, recursionDepth + 1);
}, miasmaSpreadInterval);
}
}
} else {
// If it is miasma, perform a *delayed* recursive step on the block below mB, and do not increment the depth
setTimeout(function() {
return dissipateMiasma(mB_below, mB_below.x, mB_below.z, recursionDepth);
}, miasmaSpreadInterval);
}
}
}
}
// All numbered miasma blocks
else if (mBName.includes("m")) {
var lvl = Number(mBName[mBName.length - 1]);
var neighbor;
var hasLessSpreadNeighbor = false;
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
neighbor = adjacents[i];
nName = neighbor.cell.textContent;
// Encountered a miasma source block (either "m0" or "m0v") connected to mB: do not continue.
if (nName.includes("m0")) {
return;
}
// Encountered vertically flowing miasma or a lower-spread-level miasma block: perform *instant* recursive step horizontally, without changing the center coordinates, and update boolean.
// USE <, NOT <=, or else it will be an infinite cycle!
else if (nName === "mv" || (nName.includes("m") && Number(nName[nName.length - 1]) < lvl)) {
hasLessSpreadNeighbor = true;
dissipateMiasma(neighbor, x, z, recursionDepth + 1);
}
}
}
// If no adjacent block has a lower spread level, then mB must be cut off from all source blocks.
if (!hasLessSpreadNeighbor) {
// If mB is floating, replace it with air (no delay is required here, since there was already a delay from the vertical base block).
if (belowBName === "A" || belowBName === "mv") {
mB.cell.textContent = "A";
// If the block below the dissipated one is flowing miasma, that should also dissipate after a delay. Reset the center coordinates to the vertically flowing block's coordinates.
if (belowBName === "mv") {
setTimeout(function() {
return dissipateMiasma(mB_below, mB_below.x, mB_below.z, recursionDepth + 1);
}, miasmaSpreadInterval);
}
}
// Ground-level (or above a miasma source block)
else {
// The current block should begin to evaporate (as it is the lowest-spread-level block in its group, the 'center' about which the miasma puddle should dry up)
spreadAboutCenter(mB, mB.x, mB.z, 0);
}
}
}
}
}
}
function playerInteractWithBlock(b) {
if (player.selectedItem === "full bucket" && b.cell.textContent !== "S" && !player.miasmaBucketCooldown) {
setTimeout(function() {
b.cell.textContent = "m0";
}, 1);
setTimeout(function() {
spreadMiasma(b);
}, miasmaSpreadInterval);
// Start bucket use cooldown
player.miasmaBucketCooldown = true;
setTimeout(function() {
player.miasmaBucketCooldown = false;
}, 1000);
} else if (player.selectedItem === "empty bucket" && (b.cell.textContent === "m0" || b.cell.textContent === "m0v") && !player.miasmaBucketCooldown) {
// Remove miasma block
setTimeout(function() {
b.cell.textContent = "A";
}, 1);
// Invoke spreading mechanics on lowest-spread-level miasma block adjacent to the new air block
var leastSpread = {
lvl: 4
}; // Starts 1 level ABOVE the highest possible spread level for miasma. If it is still 4 after the loop, that means there was no adjacent miasma.
const adjacents = [getBlockNorthOf(b), getBlockSouthOf(b), getBlockEastOf(b), getBlockWestOf(b), getBlockAbove(b), getBlockBelow(b)];
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjName = adjacents[i].cell.textContent;
// Here, count vertically flowing miasma blocks as if they were lvl 0, since both sources and vertically flowing blocks spread lvl 1 to adjacents.
if (adjName.includes("m") && (adjName === "mv" || Number(adjName[adjName.length - 1]) < leastSpread.lvl)) {
leastSpread.lvl = ((adjName === "mv") || (adjName === "m0v")) ? 0 : Number(adjName[adjName.length - 1]);
leastSpread.block = adjacents[i];
}
// Determine whether to invoke decay mechanics on each adjacent miasma block that is not a source block
if (adjName.includes("m") && !adjName.includes("m0")) {
setTimeout(function() {
return dissipateMiasma(adjacents[i], adjacents[i].x, adjacents[i].z, 0);
}, miasmaSpreadInterval);
}
}
}
if (leastSpread.block !== undefined) {
setTimeout(function() {
return spreadMiasma(leastSpread.block);
}, miasmaSpreadInterval);
}
// Start bucket use cooldown
player.miasmaBucketCooldown = true;
setTimeout(function() {
player.miasmaBucketCooldown = false;
}, 1000);
}
}table {
font-size: 10px;
}
table {
td {
table {
td {
width: 12px;
height: 12px;
}
}
}
}
#bucket {
width: 400px;
height: 50px;
}
#empty {
background-color: lightgray;
color: black;
}
#full {
background-color: purple;
color: white;
}
#selected {
color: green;
}<div id="bucket">
<p><span id="full"> Full Bucket </span>     <span id="empty"> Empty Bucket </span>     Selected: <span id="selected">Full Bucket</span></p>
</div>
<div id="tableDiv"></div>