Implementing an array with negative indices

Question

I make a game with a world that is endlessly developing in all directions. This means that you can be in the X:50 , Y:50 or X:-50 , Y:-50 position. But ... I can't do this with a regular C # list ...

All the ideas I came up with seem too complicated / inefficient to work ...

Answer 1

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

Another way is a linked grid (similar to a linked list, but with pointers to 4 directions) or a tile-based approach to reduce the overhead of a linked grid (a tile is a linked grid of NxN arrays). The implementation of the tile is rather complicated, but it is a good compromise between memory and performance for very dense meshes.

But my personal favorite approach is to use even conversion. Thus, odd indices are positive, and even ones are negative. To convert from a virtual index to a physical index, you use the formula p = abs(v * 2) - (v > 0 ? 1 : 0) and to convert the physical to virtual index, you do v = (p % 2 == 1 ? +1 : -1) * ((2*p + 3) / 4) . This ratio arises because there is one to one relationship (bijection) between natural numbers and integers (0 <-> 0), (1 <-> 1), (2 <-> -1), (3 <-> 2), (4 <-> -2), (5 <-> 3), (6 <-> -3), ... This approach is a quick, simple and elegant, but not very good memory when you have a very rare grid with elements very far from the center line.

Answer 2

If you do not have TON (yes, TON bit ...) cells, you can use dictionaries. Combine this with System.Drawing.Point as the key and you will get a good deal:

 Dictionary<Point,YourGridObject> myMap = new Dictionary<Point,YourGridObject>(); 

Edit: in addition to the dictionary, each cell can have a link to neighboring cells, so you can use the dictionary to directly jump somewhere, but then navigate with the adjacent one. I used this method to implement the A * search algorithm in a hexadecimal grid.

Edit 2: For example, if you want to access a specific coordinate, you can simply

 var myTile = myMap[new Point(25, -25)]; 

Then you want to get the East fragment, you can

 var eastTile = myTile.East; 

Your mesh object can also implement the offset method so that you can get the West 2, North 5 plate on

 var otherTile = myTile.Offset(-2, 5); 

Answer 3

How to use two lists for extensions in two different directions?

Answer 4

I'm not sure if this is more complicated than you want to deal with, but do you consider using polar coordinates instead of Cartesian ones? There are no negative numbers in this coordinate system. I understand that at first it is difficult at first, but as soon as you wrap your head around you, it becomes second nature.

Answer 5

You can use a dictionary that has all the features of an array, except for explicitly negative indices.

Answer 6

Computers cannot store infinite arrays. There should be a border to your array, remind you that somewhere in the code you declared a certain size during the initialization of your array. You may resize it somewhere, but that still leaves a range of numbers from 0 to .. max.

So what you should do is write a function that allows you to relatively position yourself on such a map. This way you save the current map [x, y] as a position. And your ability to increase, having a function that adds / subtracts from your current position relativistically. This makes code easier to understand.

If you are not dealing with game maps, but with ranges of numbers, say vectors, you can create a list of n points or a 2d dictionary.

I post it here because your problem can cause people to write the wrong code.

Also an addition for other people in situations where there is a border around the map (typical in game scenarios and image manipulation). where your data comes from [-1..width + 1], just measure it as [0, width + 2] then run it starting with 'for (int x = 1; x <Width + 1; x ++) ''