表示为1d数组时查找2d数组的邻居 [英] Finding neighbors of 2d array when represented as 1d array

问题描述

我有一个2d数组，我将其转换为1d数组.在1d表示中，我如何找到一个单元的所有8个邻居，并考虑了回绕?

I have a 2d array that I converted to a 1d array. In the 1d representation, how can I find all 8 neighbors of a cell, accounting for wrap-around?

本文的背景是我有一个2d游戏板，将其作为1d内存块存储在内存中.我需要能够找到游戏板上所有8个相邻单元的内存位置.我遇到的问题是考虑了边缘的木板缠绕(特别是如果单元格位于2d阵列的一角).

The context of this is that I have a 2d game board that I store in memory as a 1d chunk of memory. I need to be able to find the memory locations of all 8 neighboring cells in the game board. The problem I am having is accounting for the board wrap-around on the edges (especially if the cell is in the corner of the 2d array).

例如，如果单元格位于右上角，则顶部邻居位于右下角，依此类推.

For example, if the cell is in the upper right corner, the top neighbor is at the bottom right corner, etc.

我在计算时知道板子的尺寸.

I know the board size when I am calculating this.

可能有必要提及我正在MIPS汇编中执行此操作...

It might be pertinent to mention that I am doing this in MIPS assembly...

推荐答案

您只需要一个函数即可将任意位置映射到数组中包含的位置.

You just need a function that can map an arbitrary position to a position that is contained within the array.

您必须分两个步骤分解问题:

You must decompose the problem in two steps:

• 包装
• 将2d坐标映射到1d

使用模运算符可以很容易地完成包装，例如

Wrapping can be done easily with modulo operator, something like

struct pos { int x,y };

pos wrap(pos p)
{
  pos p2 = p;

  if (p.x >= WIDTH)
    p.x %= WIDTH;
  else if (p.x < 0)
    p.x += WIDTH;

  if (p.y >= HEIGHT)
    ... same thing
}

那么您肯定会在数组内部包含一个位置，您需要将其映射为1d，这甚至更容易:

Then you'll have a position that is surely contained inside the array, you need to map it do 1d, that's even easier:

int flatten(pos p)
{
   return p.x*WIDTH + p.y;
}

因此您可以将它们组合在一起

so you can combine them:

int fpos = flatten(wrap({30,20}));

您就完成了.

这篇关于表示为1d数组时查找2d数组的邻居的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！