检查2D数组中每个邻居的最快方法 [英] Fastest way to check each neighbor in 2D array

问题描述

我正在研究随机地牢生成器，只是为了娱乐/作为学习一些新事物的辅助项目.我编写了一个函数，该函数为任何给定的单元格返回整数哈希值，该函数为您提供有关该游戏对象应为哪种类型的信息.也就是说，如果它是一堵墙，面向哪个方向，是一个拐角等，则此功能当前的外观.

I am working on a random dungeon generator just for fun / as a side project to learn some new things. I have written a function that returns an integer hash value for any given cell, which gives you information about what type of gameobject it should be. i.e. if it is a wall, what direction to face, is it a corner, etc. Here is what the function currently looks like.

    private int CellHashValue(int xIndex, int yIndex, char centerTile)
    {
        int hashValue = 0;
        if (dungeon2DArray[xIndex - 1, yIndex + 1] == centerTile)
        {
            hashValue += 1;
        }
        if (dungeon2DArray[xIndex, yIndex + 1] == centerTile)
        {
            hashValue += 2;
        }
        if (dungeon2DArray[xIndex + 1, yIndex + 1] == centerTile)
        {
            hashValue += 4;
        }
        if (dungeon2DArray[xIndex - 1, yIndex] == centerTile)
        {
            hashValue += 8;
        }
        if (dungeon2DArray[xIndex + 1, yIndex] == centerTile)
        {
            hashValue += 16;
        }
        if (dungeon2DArray[xIndex - 1, yIndex - 1] == centerTile)
        {
            hashValue += 32;
        }
        if (dungeon2DArray[xIndex, yIndex - 1] == centerTile)
        {
            hashValue += 64;
        }
        if (dungeon2DArray[xIndex + 1, yIndex - 1] == centerTile)
        {
            hashValue += 128;
        }
        return hashValue;
    }

我的问题是，有没有一种我可能没有想到的更有效，更快捷的方法来进行这些检查?地牢数组的大小范围从100x100到1000x1000，尽管并未在每个单元格上调用该函数.我有一个单独的List，其中包含房间，并且在迭代实例化对象的每个方向上都有开始索引和结束索引.

My question is, is there a more efficient and faster way to do these checks that perhaps I am not thinking of? The dungeon array ranges in size from 100x100 to 1000x1000, though the function is not called on each cell. I have a separate List that contains rooms and there start and end indexes for each direction that I iterate over to instantiate objects.

推荐答案

您正在执行的操作本质上是使用卷积形式.在没有更多关于如何调用方法或如何使用返回的哈希值的上下文的情况下，您正在执行的操作似乎接近迭代3x3网格的最有效方法.假设您的dungeon2dArray是char [] []并且是全局的，那么我认为这会更加清楚和简洁(您必须根据迭代顺序来调整如何解释结果之和).

What you're doing is essentially applying a form of convolution. Without more context as to how your method is being called or how you're using the returned hash value, what you're doing seems to be close to the most efficient way to iterate a 3x3 grid. Assuming your dungeon2dArray is a char[][] and is global, this is what I believe to be a bit clearer and more concise (you'll have to adjust how to interpret the resulting sum based on the order of iteration).

private int CellHashValue(int x, int y) {
    int hashSum = 0;   // Hash sum to return
    int hashValue = 1; // Increases as power of 2 (1,2,4,8,...128)
    char centerTile = dungeon2DArray[x, y]; // Cache center tile

    for (int r = -1; r <= 1; r++) {
        for (int c = -1; c <= 1; c++) {
            if (r == 0 && c == 0) continue; // Skip center tile
            if (dungeon2DArray[x + c, y + r] == centerTile) {
                hashSum += hashValue;
            }
            hashValue *= 2; // Next power of two
            //could also bit shift here instead 
            // hashValue <<= 1
        }
    }
    return hashSum;
}

注意:此方法不进行任何边界检查，因此，如果x或y索引沿边，则索引将失败.

Note: This method doesn't do any boundary checking, so if x or y index is along edge, indices will fail.

每个数组访问为O(1)，并且在整个地牢数组中进行迭代的时间为O(n ^ 2)，因此获得更高效率的唯一方法是组合每个单元格方法调用，但这仍然仅仅是常数，因此效率实际上并没有提高，但是取决于计算方式可能会稍微提高性能.

Each of the array accesses is O(1) and iterating over your entire dungeon array is O(n^2), so the only way to get better efficiency would be to combine per cell methods calls, but this is still only a constant factor, so not really more efficient, but depending on the calculation could boost performance a little bit.

这篇关于检查2D数组中每个邻居的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！