负指数阵列的实现 [英] Implementation of array with negative indices

问题描述

我正在与在各个方向延伸无限世界游戏。这意味着，你可以在位置 X：50 ， Y：50 或 X： -50 ， Y：-50 。但是...我真的不能做到这一点与普通的C＃名单...

I am making a game with a world that extends infinitely in every direction. This means that you can be at position X:50, Y:50 or X:-50, Y:-50. But... I can't really do that with a normal C# List...

所有我想出的想法似乎过于复杂/低效的工作...

All the ideas I've come up with seem to be too complicated/inefficient to work...

推荐答案

要实现无限电网最简单的方法是用一个稀疏矩阵与要存储作为一个x，y对作为密钥和数据字典值。这是速度快，易于实现，和内存友好的，如果你的网格是稀疏。

The easiest way to implement infinite grid is using a sparse matrix with a dictionary with an x,y pair as the key and the data you want to store as the values. This is fast, easy to implement, and memory friendly if your grid is sparse.

另一种方式是一个链接的格（类似于链表，但与指针4的方向），或基于瓦片的方法来减少与电网的开销（瓦片是N×N个阵列的一个链接的网格）。瓷砖的实施是相当复杂的，而且是非常密集的网格存储和性能之间的很好的折衷。

Another way is a linked grid (similar to linked list, but with pointers to 4 directions), or a tile-based approach to reduce the overhead of linked grid (a tile is a linked grid of NxN arrays). Implementation of tiles is quite complicated, but is a good tradeoff between memory and performance for very dense grids.

不过，我个人最喜欢的方法是使用奇偶转型。所以，奇指数是积极的，而偶数均为负面。要从虚拟索引转换为物理索引，您可以使用公式 P = ABS（V * 2） - （V＆GT; 0？1：0）和转换物理虚拟索引你做 v =（p％2 == 1 + 1：-1）*（（2 * p + 3）/ 4）。这种关系的产生是因为有自然数和整数进行一一和到关系（双射）（0℃; - ＆0），（1 <<; - →1），（2'; - -1个），（3'; - →2），（4' - →-2），（5℃ - →3），（6≤ - →-3），。 .. 。这种方法快速，简单和优雅，但不是很大的内存明智的，当你从中线有非常稀疏的网格项目非常远。

But my personal favorite approach is to use the even-odd transformation. So odd indices are positive, while even numbers are negative. To transform from virtual index to the physical index, you use the formula p = abs(v * 2) - (v > 0 ? 1 : 0) and to convert physical to virtual index you do v = (p % 2 == 1 ? +1 : -1) * ((2*p + 3) / 4). This relation arises because there is one to one and onto relation (bijection) between natural numbers and integers (0 <-> 0), (1 <-> 1), (2 <-> -1), (3 <-> 2), (4 <-> -2), (5 <-> 3), (6 <-> -3), .... This approach is fast, simple and elegant, but not very great memory wise when you have very sparse grid with items extremely far from the center line.

这篇关于负指数阵列的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！