Implementation of array with negative indices

Question

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...

Answer 1

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.

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.

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.