Код в фрагменте стека должен работать следующим образом:
propagateChanges, будет через определенные промежутки времени записываться в консоль. Оно никогда не должно превышать 4, так как это наибольшее количество шагов, которые алгоритм должен выполнить, чтобы карта достигла стабильной конфигурации. (Это означает, что все плитки либо достигнут значения 4, либо будут находиться в пределах 4 шагов от «центральной» плитки (числовое значение = 0).)Вместо этого, когда я щелкаю крайнюю правую верхнюю ячейку таблицы, алгоритм, похоже, выдает правильный результат. Карта (представленная таблицей HTML) выглядит визуально корректной, то есть все номера плиток преобразуются в окончательные значения, которые они ожидают и должны иметь.
Но рекурсивные вызовы продолжают генерироваться из цикла for в нижней части propagateChanges, даже после того, как кажется, что карта достигла окончательной, стабильной конфигурации.
У меня есть условный оператор рекурсивного шага, который гарантирует, что оценивается каждый тайл:
Второе условие, я считаю, должно препятствовать тому, чтобы алгоритм создавал «циклы», когда соседние плитки генерируют рекурсивные вызовы друг к другу.
Итак, что здесь не так? Очевидно, что я каким-то образом упускаю базовый вариант, поскольку происходит бесконечная рекурсия, но, просматривая код несколько раз, я все еще не понимаю, что это такое.
const rows = document.getElementsByTagName('tr');
var tiles = [];
for (var r = 0; r < rows.length; r++) {
tiles[r] = [];
for (var c = 0; c < rows[r].cells.length; c++) {
// Store table cell's row and column indices, along with the cell itself, to simplify later accesses
tiles[r][c] = {
r: r,
c: c,
tile: rows[r].cells[c]
};
}
}
// Helper function: avoid out-of-bounds errors when accessing array elements by returning a table cell only if its indices exist in the 'tiles' array
function getTile(r, c) {
if (r > -1 && r < 4 && c > -1 && c < 5) {
return tiles[r][c];
}
}
// If the current tile is NOT within 4 steps of any centers (i.e. tiles numbered 0), increase its number by 1 until it reaches the maximum value of 4. Then do the same for each neighboring tile, after a 1-second delay.
// Eventually, after a *maximum* of 4 iterations, the grid should stabilize, meaning all numbers should have reached their final values.
// All tiles will either have value 4, or else be within 4 steps of a center tile (numbered 0), in which case their values will NOT increase.
function propagateChanges(currentTile, R, C, depth) {
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else if (rDist < 3 && cDist < 3 && (rDist + cDist < 3)) {
var val = Number(currentTile.tile.textContent);
// Somehow, this function got called on a tile with value <= 0 or >= 4. This shouldn't happen: exit without performing any recursive steps.
if (val >= 4 || val <= 0) {
return;
} else {
var centerCoords = isCenterWithin4Tiles(currentTile.r, currentTile.c);
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
// Don't increase the tile's number value if there's a center nearby (i.e. within 4 steps)
if (!centerCoords) {
currentTile.tile.textContent = val + 1;
// Perform recursive call on original block after 1 second delay
setTimeout(function() {
propagateChanges(currentTile, R, C, depth + 1);
}, 1000);
}
// Recursive calls on the 4 adjacent tiles
// Only proceed in a given direction if either no nearby centers were found, or else the adjacent tile in that direction will be further from any/all centers than currentTile is (in either the row [r] or column [c] direction).
// Not being able to move back in the direction of a center is intended to prevent an infinite cycle of recursive calls from being generated.
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjVal = Number(adjacents[i].tile.textContent);
if (adjVal < 4 && adjVal > 0 && (!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords))) {
/* THIS IS WHERE THE PROBLEM OCCURS */
setTimeout(function() {
propagateChanges(adjacents[i], R, C, depth + 1);
}, 1000);
}
}
}
}
}
}
// Find the lowest numbered tile within 4 steps of the origin (i.e. the tile the user clicked), and invoke the propagateChanges function on it IF it is not a true center (which are numbered 0)
function locateCenter(currentTile, R, C, depth) {
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else {
const val = Number(currentTile.tile.textContent);
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
// If a center is encountered, do not continue. Don't check any tiles that are more than 4 steps away from the origin coordinates.
if (val > 0 && (rDist < 4 && cDist < 4 && (rDist + cDist < 4))) {
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
var hasLowerNumberedNeighbor = false;
var adjVal;
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
adjVal = Number(adjacents[i].tile.textContent);
// Encountered a center within 4 steps of the origin: do not continue.
if (adjVal == 0) {
return;
}
// Encountered neighboring tile with value less than that of the current tile, and < 4: perform *instant* recursive step horizontally and update boolean.
// USE <, NOT <=, or else it will be an infinite cycle!
else if (adjVal < 4 && adjVal < val) {
hasLowerNumberedNeighbor = true;
locateCenter(adjacents[i], R, C, depth + 1);
}
}
}
// If no adjacent tile has a lower number, then currentTile must be cut off from all centers.
if (!hasLowerNumberedNeighbor) {
// The current tile should begin counting up to 4, and propagate changes outward to its neighbors
propagateChanges(currentTile, currentTile.r, currentTile.c, 0);
}
}
}
}
/* Return type of this function will vary. If any centers (tile value == 0) are located within the specified distance, it will return an array of objects containing their x and z coordinates.
(This evaluates to *true* in conditional statements.) Otherwise, it will return false. */
function isCenterWithin4Tiles(r, c) {
var coords = [];
for (var rAway = -3; rAway < 4; rAway++) {
for (var cAway = -3; cAway < 4; cAway++) {
if ((Math.abs(rAway) + Math.abs(cAway) < 4) && ((r + rAway) > -1 && (c + cAway) > -1 && (r + rAway) < 4 && (c + cAway) < 5)) {
const val = tiles[r + rAway][c + cAway].tile.textContent;
if (val == 0) {
coords.push({
r: r + rAway,
c: c + cAway
});
}
}
}
}
return (coords.length) ? coords : false;
}
// Returns true if the coordinates for 'next' are further from ALL centers (i.e., coordinate pairs in the 'comparisons' array) than are the coordinates for 'current', and false otherwise.
function isFurtherFromAll(next, current, comparisons) {
var compared = {};
for (var i = 0; i < comparisons.length; i++) {
// 'next' is further than 'current' from the center in a given direction: Value for that direction will be *positive*.
// 'next' and 'current' are an equal distance from the center: Value will be *0*.
// 'next' is closer to center than current: Value will be *negative*.
compared.r = Math.abs(next.r - comparisons[i].r) - Math.abs(current.r - comparisons[i].r);
compared.c = Math.abs(next.c - comparisons[i].c) - Math.abs(current.c - comparisons[i].c);
// 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.r < 0) || (compared.c < 0) || (compared.r + compared.c === 0)) {
return false;
}
}
return true;
}
// Limit max recursion depth to 4, as the function reaching a greater depth than this indicates the algorithm will never terminate
var maxDepth = 0;
var overflowed = false; // If this becomes true, the function will exit without generating further recursive calls.
function progressReport() {
console.info("Maximum depth reached in recursive function: " + maxDepth);
if (overflowed) {
console.warn("OVERFLOW");
} else {
setTimeout(progressReport, 3000); // Every 3 seconds
}
}
progressReport();
// When the tile in the top right corner is clicked, set its number to the max value (4) and invoke the incrementation algorithm on it
var clicked = false;
document.getElementById("clickHere").addEventListener('click', function() {
if (!clicked) {
clicked = true;
tiles[0][4].tile.textContent = 4;
locateCenter(tiles[0][4], 0, 4, 0);
}
});table {
font-size: 18px;
}
table {
td {
width: 20px;
height: 20px;
}
}<body>
<table>
<tr>
<td>2</td>
<td>2</td>
<td>2</td>
<td>1</td>
<td id = "clickHere">0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>2</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
</tr>
</table>
</body>


![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)


Проблема с кодом в вашем вопросе связана с тем, как вы определяете «в пределах 4 шагов от «центральной» плитки».
Похоже, что как только вы доберетесь до плитки, вы захотите выполнять рекурсивные вызовы для каждой соседней плитки только в том случае, если ни текущая, ни соседняя плитка не находятся в пределах 4 шагов от любой «центральной» (значение = 0) плитки.
Это должно быть намерением, поскольку вы указали, что не хотите, чтобы количество плиток уменьшалось, если они находятся в пределах 4 блоков от «центра», и, как только будет определено, что никакие дальнейшие изменения не будут внесены в данную плитку. числовое значение, нет причин вызывать рекурсивную функцию для этой плитки.
В настоящее время ваше условное утверждение:
if (adjVal < 4 && adjVal > 0 && (!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords))) {
проверяет только то, что центральные плитки находятся в пределах 4 шагов от текущей плитки, и не выполняется проверка близости «центра» к соседней плитке.
Это означает, что плитка на самом краю области, окружающей «центр», будет находиться на расстоянии 3 шагов от центра, а следующая соседняя плитка будет на расстоянии 4 шагов (в результате чего isFurtherFromAll(adjacents[i], currentTile, centerCoords) будет оцениваться как true, поскольку 4 > 3). Итак, существует несоответствие между значением вашего условного оператора и тем, собираетесь ли вы фактически выполнить рекурсивный вызов adjacents[i]. На самом деле рекурсия не должна происходить, потому что соседний тайл находится в 4 шагах от любого/всех центров, но на самом деле это никогда не проверяется!
Добавление дополнительной проверки на то, что соседняя плитка находится в пределах 4 шагов от любого центра, решает проблему.
Итак, условный оператор рекурсивного вызова внутри цикла на самом деле должен быть таким:
if (adjVal < 4 && adjVal > 0 && ((!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords)) && (!adjCenterCoords || isFurtherFromAll(adjacents[i], currentTile, adjCenterCoords)))) {
Полный (рабочий) код:
const rows = document.getElementsByTagName('tr');
var tiles = [];
for (var r = 0; r < rows.length; r++) {
tiles[r] = [];
for (var c = 0; c < rows[r].cells.length; c++) {
// Store table cell's row and column indices, along with the cell itself, to simplify later accesses
tiles[r][c] = {
r: r,
c: c,
tile: rows[r].cells[c]
};
}
}
// Helper function: avoid out-of-bounds errors when accessing array elements by returning a table cell only if its indices exist in the 'tiles' array
function getTile(r, c) {
if (r > -1 && r < 4 && c > -1 && c < 5) {
return tiles[r][c];
}
}
// If the current tile is NOT within 4 steps of any centers (i.e. tiles numbered 0), increase its number by 1 until it reaches the maximum value of 4. Then do the same for each neighboring tile, after a 1-second delay.
// Eventually, after a *maximum* of 4 iterations, the grid should stabilize, meaning all numbers should have reached their final values.
// All tiles will either have value 4, or else be within 4 steps of a center tile (numbered 0), in which case their values will NOT increase.
function propagateChanges(currentTile, R, C, depth) {
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else if (rDist < 3 && cDist < 3 && (rDist + cDist < 3)) {
var val = Number(currentTile.tile.textContent);
// Somehow, this function got called on a tile with value <= 0 or >= 4. This shouldn't happen: exit without performing any recursive steps.
if (val >= 4 || val <= 0) {
return;
} else {
var centerCoords = isCenterWithin4Tiles(currentTile.r, currentTile.c);
var adjCenterCoords; // Will be used to test whether each tile adjacent to the current one is near a center, inside the loop at the end of this function
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
// Don't increase the tile's number value if there's a center nearby (i.e. within 4 steps)
if (!centerCoords) {
currentTile.tile.textContent = val + 1;
// Perform recursive call on original block after 1 second delay
setTimeout(function() {
propagateChanges(currentTile, R, C, depth + 1);
}, 1000);
}
// Recursive calls on the 4 adjacent tiles
// Only proceed in a given direction if either no nearby centers were found, or else the adjacent tile in that direction will be further from any/all centers than currentTile is (in either the row [r] or column [c] direction).
// Not being able to move back in the direction of a center is intended to prevent an infinite cycle of recursive calls from being generated.
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
let adjVal = Number(adjacents[i].tile.textContent);
adjCenterCoords = isCenterWithin4Tiles(adjacents[i].r, adjacents[i].c);
// This time, ensure the adjacent tile is further NOT ONLY from any center tiles near *currentTile*, BUT ALSO from any centers near *itself*!
if (adjVal < 4 && adjVal > 0 && ((!centerCoords || isFurtherFromAll(adjacents[i], currentTile, centerCoords)) && (!adjCenterCoords || isFurtherFromAll(adjacents[i], currentTile, adjCenterCoords)))) {
/* WITH THE EXTRA CONDITION, THIS WILL NO LONGER GENERATE INFINITE BACK-AND-FORTH CYCLES BETWEEN ADJACENT TILES */
setTimeout(function() {
propagateChanges(adjacents[i], R, C, depth + 1);
}, 1000);
}
}
}
}
}
}
// Find the lowest numbered tile within 4 steps of the origin (i.e. the tile the user clicked), and invoke the propagateChanges function on it IF it is not a true center (which are numbered 0)
function locateCenter(currentTile, R, C, depth) {
if (depth > maxDepth) {
maxDepth = depth;
}
if (depth > 4) {
overflowed = true;
return;
} else {
const val = Number(currentTile.tile.textContent);
var rDist = Math.abs(currentTile.r - R);
var cDist = Math.abs(currentTile.c - C);
// If a center is encountered, do not continue. Don't check any tiles that are more than 4 steps away from the origin coordinates.
if (val > 0 && (rDist < 4 && cDist < 4 && (rDist + cDist < 4))) {
const adjacents = [getTile(currentTile.r - 1, currentTile.c), getTile(currentTile.r + 1, currentTile.c), getTile(currentTile.r, currentTile.c - 1), getTile(currentTile.r, currentTile.c + 1)];
var hasLowerNumberedNeighbor = false;
var adjVal;
for (let i = 0; i < adjacents.length; i++) {
if (adjacents[i] !== undefined) {
adjVal = Number(adjacents[i].tile.textContent);
// Encountered a center within 4 steps of the origin: do not continue.
if (adjVal == 0) {
return;
}
// Encountered neighboring tile with value less than that of the current tile, and < 4: perform *instant* recursive step horizontally and update boolean.
// USE <, NOT <=, or else it will be an infinite cycle!
else if (adjVal < 4 && adjVal < val) {
hasLowerNumberedNeighbor = true;
locateCenter(adjacents[i], R, C, depth + 1);
}
}
}
// If no adjacent tile has a lower number, then currentTile must be cut off from all centers.
if (!hasLowerNumberedNeighbor) {
// The current tile should begin counting up to 4, and propagate changes outward to its neighbors
propagateChanges(currentTile, currentTile.r, currentTile.c, 0);
}
}
}
}
/* Return type of this function will vary. If any centers (tile value == 0) are located within the specified distance, it will return an array of objects containing their x and z coordinates.
(This evaluates to *true* in conditional statements.) Otherwise, it will return false. */
function isCenterWithin4Tiles(r, c) {
var coords = [];
for (var rAway = -3; rAway < 4; rAway++) {
for (var cAway = -3; cAway < 4; cAway++) {
if ((Math.abs(rAway) + Math.abs(cAway) < 4) && ((r + rAway) > -1 && (c + cAway) > -1 && (r + rAway) < 4 && (c + cAway) < 5)) {
const val = tiles[r + rAway][c + cAway].tile.textContent;
if (val == 0) {
coords.push({
r: r + rAway,
c: c + cAway
});
}
}
}
}
return (coords.length) ? coords : false;
}
// Returns true if the coordinates for 'next' are further from ALL centers (i.e., coordinate pairs in the 'comparisons' array) than are the coordinates for 'current', and false otherwise.
function isFurtherFromAll(next, current, comparisons) {
var compared = {};
for (var i = 0; i < comparisons.length; i++) {
// 'next' is further than 'current' from the center in a given direction: Value for that direction will be *positive*.
// 'next' and 'current' are an equal distance from the center: Value will be *0*.
// 'next' is closer to center than current: Value will be *negative*.
compared.r = Math.abs(next.r - comparisons[i].r) - Math.abs(current.r - comparisons[i].r);
compared.c = Math.abs(next.c - comparisons[i].c) - Math.abs(current.c - comparisons[i].c);
// 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.r < 0) || (compared.c < 0) || (compared.r + compared.c === 0)) {
return false;
}
}
return true;
}
// Limit max recursion depth to 4, as the function reaching a greater depth than this indicates the algorithm will never terminate
var maxDepth = 0;
var overflowed = false; // If this becomes true, the function will exit without generating further recursive calls.
function progressReport() {
console.info("Maximum depth reached in recursive function: " + maxDepth);
if (overflowed) {
console.warn("OVERFLOW");
} else {
setTimeout(progressReport, 3000); // Every 3 seconds
}
}
progressReport();
// When the tile in the top right corner is clicked, set its number to the max value (4) and invoke the incrementation algorithm on it
var clicked = false;
document.getElementById("clickHere").addEventListener('click', function() {
if (!clicked) {
clicked = true;
tiles[0][4].tile.textContent = 4;
locateCenter(tiles[0][4], 0, 4, 0);
}
});table {
font-size: 18px;
}
table {
td {
width: 20px;
height: 20px;
}
}<body>
<table>
<tr>
<td>2</td>
<td>2</td>
<td>2</td>
<td>1</td>
<td id = "clickHere">0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>2</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>2</td>
<td>3</td>
</tr>
</table>
</body>
Вы можете видеть, что когда вы щелкаете ячейку таблицы в правом верхнем углу, карта приобретает ту же конфигурацию, что и в коде вопроса, но теперь рекурсивная функция достигает максимальной глубины 3 (вместо 5+), а консоль не отображает предупреждение «ПЕРЕПОЛНЕНИЕ».