Поиск последнего элемента многомерного массива, который удовлетворяет условию с помощью рекурсии

Question

Я знаю, что рекурсии не так много реальных примеров. Кажется, я нашел один сегодня, и я хочу поделиться им. Q & Стиль, потому что я думаю, что это захватывающе.

Я использую двигатель Phaser для игры в шахте. После щелчка пользователя мне нужно найти элемент игры, на который пользователь щелкнул. Это усложняется, когда есть несколько элементов один поверх другого. Затем мне нужно будет проверить их порядок рендеринга и выбрать элемент с наивысшим.

В Phaser корень всех отображаемых объектов является «миром». Все существующие элементы являются либо прямыми детьми мира, либо детьми детей. Это ветвящаяся структура с игровым миром сверху. Дети упорядочиваются по порядку их рендеринга, что означает, что последний находится сверху.

Вот пример этого, имея каждый объект отображения, представленный рядом:

var world = [ 
    [ 
     18, 
     3, 
     [ 
      1, 
      14, 
      2 
     ], 
     5, 
     9, 
     [ 
      3, 
      5 
     ] 
    ], 
    [ 
     16, 
     7 
    ] 
]; 

Существует три уровня в этом массиве с двумя основными «группами». В игровых терминах вторая группа добавляется после первого, поэтому она отображается сверху. Внутри первой группы последний элемент отображается сверху, который является группой. Внутри этой группы последний элемент отображается сверху и так далее. Из всех этих элементов тот, который отображается на самом верху, 7, так как он последний.

Предположим, что я нажимаю на мышь, и это оказывается поверх всех элементов, представленных большим числом, чем 10 (18, 14 и 16). Тот, который мне нужен, это 16, так как он самый далекий.

Как это получить?

Answer 1

Вы можете использовать Array#forEach с рекурсивным подходом.

function getValue(array, cb) { 
 
    var last; 
 
    array.forEach(function iter(a) { 
 
     if (Array.isArray(a)) { 
 
      a.forEach(iter); 
 
      return; 
 
     } 
 
     if (cb(a)) { 
 
      last = a; 
 
     } 
 
    }); 
 
    return last; 
 
} 
 

 
function check(v) { 
 
    return v > 10; 
 
} 
 

 
var world = [[18, 3, [1, 14, 2], 5, 9, [3, 5]], [16, 7]]; 
 

 
console.log(getValue(world, check));

версия с Array#reduce и закрытием над обратным вызовом.

function getLastValue(cb) { 
 
    return function iter(r, a) { 
 
     return Array.isArray(a) ? a.reduce(iter, r) : cb(a) ? a : r; 
 
    }; 
 
} 
 

 
function greaterThan10(v) { 
 
    return v > 10; 
 
} 
 

 
var world = [[18, 3, [1, 14, 2], 5, 9, [3, 5]], [16, 7]]; 
 

 
console.log(world.reduce(getLastValue(greaterThan10), null));

Добавление вдохновленный 4castle-х answer с итерации со спины и вернуться рано с первой находкой.

function getValue(array, cb) { 
 
    var i = array.length, r; 
 
    while (i--) { 
 
     if (Array.isArray(array[i])) { 
 
      r = getValue(array[i], cb); 
 
      if (r !== undefined) { 
 
       return r; 
 
      } 
 
     } 
 
     if (cb(array[i])) { 
 
      return array[i]; 
 
     } 
 
    }; 
 
} 
 

 
function check(v) { 
 
    return v > 10 && v < 16; 
 
} 
 

 
var world = [[18, 3, [1, 14, 2], 5, 9, [3, 5]], [16, 7]]; 
 

 
console.log(getValue(world, check)); // 14

Answer 2

function topElement(fn, object, data) { 
    if (fn(object) === true) { 
     data = object; 
    } 

    for (var i = 0; i < object.length; i++) { 
     data = topElement(fn, object[i], data); 
    } 

    return data; 
} 

function check(num) { 
    return (num > 10); 
} 

topElement(check, world); // 16 

Если бы я хотел другое состояние, я бы просто изменить метод check(). В моей игре другое условие - это место, где пользователь нажал. check() сравнивает игровой элемент с точкой, возвращает true, если он находится внутри него, а затем topElement() возвращает элемент, наиболее удаленный по порядку рендеринга, который соответствовал условию.

Вот fiddle.

Answer 3

Чтобы получить последний элемент многомерного массива, который соответствует определенным критериям, вы должны использовать какое-то проверку, чтобы убедиться, что элемент является массивом или нет, так что вы знаете, нужно ли делать рекурсивный вызов или нет. Выяснить, может ли быть что-то массив, можно сделать с помощью Array.isArray, или вы можете использовать утиную печать и проверить свойство length.

Зацикливание назад по массиву поможет вам быстрее найти верхний элемент.

function topElement(condition, array) { 
 
    for (var i = array.length - 1; i >= 0; i--) { 
 
    var val = array[i]; 
 
    if (Array.isArray(val)) { 
 
     var top = topElement(condition, val); 
 
     if (top !== undefined) { 
 
     return top; 
 
     } 
 
    } else if (condition(val)) { 
 
     return val; 
 
    } 
 
    } 
 
    return undefined; 
 
} 
 

 
function check(num) { 
 
    return num > 10; 
 
} 
 

 
var world = [[18, 3, [1, 14, 2], 5, 9, [3, 5]], [16, 7]]; 
 
console.log(topElement(check, world));