通过递归查找满足条件的多维数组的最后一个元素

Question

我知道递归的真实应用例子不多。今天我发现了一个例子，想以问答形式分享，因为我觉得很有趣。

我正在使用Phaser引擎开发我的游戏。当用户点击时，我需要找到用户点击的游戏元素。如果有多个元素重叠在一起，这就变得复杂了。然后，我需要检查它们的渲染顺序并选择最高的元素。

在Phaser中，所有显示对象的根是“world”。所有现有元素都是直接或间接的world子级。这是一个分支结构，游戏世界在顶部。子元素按其渲染顺序排序，意味着最后一个在顶部。

以下是一个示例，其中每个显示对象由一个数字表示：

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

这个数组中有三个层级和两个主要的“组”。在游戏术语中，第二个组在第一个组之后添加，因此它会显示在顶部。在第一个组中，最后一个元素会被渲染在顶部，这是一个组。在那个组内，最后一个元素再次被渲染在顶部，以此类推。在所有这些元素中，因为它是最后一个，所以位于最顶部的是7。

假设我点击鼠标，并且它恰好位于所有大于10（18，14和16）的元素上面。我需要的是16，因为它是最远下方的元素。

我该怎么做？

- dodov

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的答案，采用从后往前迭代，并在找到第一个匹配项后提前返回。

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

- Nina Scholz

---

关于第一个代码片段 - 使用 Array.forEach() 的好处是什么？如果我使用它，我还需要检查当前对象是否为数组，以避免在数字上调用它。使用 for 循环，如果我尝试循环数字，它的长度将为 undefined，并且不会进行循环。我想如果 length 函数存在，但实际上却不是数组，可能会有问题。关于第二个代码片段 - 你能解释一下它是如何工作的吗？我以前从未见过 reduce()，我很难理解发生了什么。我喜欢这段代码，不过。 - dodov

你可以在调用函数之前添加健全性检查，或者如果没有提供正确的类型，则返回。reduce迭代一个数组，接受一个回调函数和一个可选的起始值。然后它根据给定或最后一个值和实际值返回一个新值。在这种情况下，回调函数采用比较函数greaterThan10并返回一个回调函数iter。在函数内部，它检查数组并返回一个reduce值或一个已检查的值。使用reduce的另一个原因是，您可以编写很酷的句子表达式。 - Nina Scholz

对于“为什么使用forEach”这个问题，它只是一种传统的方法，使用一个外部变量来保存结果。 - Nina Scholz

Answer 2

要获取符合某些条件的多维数组的最后一个元素，您应该使用某种检查来确保元素是数组还是其他类型，以便知道是否需要进行递归调用。可以使用 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));

- 4castle

Answer 3

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。

- dodov