Indicate which indexes are expandable in both directions?

Question

I was going to write a game (it’s called “Qwirkle” if you ever heard of it), in which a two-dimensional playing field stores the position of the stones that the players put into it. The first player puts the stone anywhere, while other players can connect to it from any side (left / right / top and bottom). The playing field itself is not limited to a fixed size, which will destroy the idea of ​​the game. However, the number of stones is limited by the value that the player can determine at launch.

Due to the logic of the game, I need to loop stones with an index. However, since players can add stones from any direction, I need a list that can be expanded in any direction (for example, in the direction of negative and positive indices).

Performance is not negligible, since I need to check several stones in one move.

It would be best to access the stone, for example _stones [-3.5], to access it in position -3, 5, of course.

I thought a stack that could be pushed and pushed from either side (e.g. PushBack / PushFront) would be useful for this, but I'm not quite sure how to implement this in C #.

Are there any predefined lists / stacks like the one I'm thinking of, or is my approach completely weird?

Answer 1

The data structure you want is an immutable quadrant. If the board is mostly empty, then using an immutable square allows you to imagine boards that are essentially unlimited in size; a one-trillion-per-trillion card occupies just a few bytes of memory than a 32-by-32 card. Unchangeable quadrants can be easily indexed as you describe, and calculating a new quadrant with the old quadrant and editing is easy.

I have written several unchanged quadtree algorithms several times over the years, and for a long time I had in mind a series of blog articles, but I never had them. When I do this, I will return and clarify this answer.

At the same time, this article by Dr. Dobbs on the Gospers algorithm is the one I used to find out how fixed quadrants work.

http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478

Answer 2

What you want is a double queue queue (known as deque, pronounced "deck"). There is no implementation in .NET BCL (unfortunately), but there are third-party implementations (see Google).

Answer 3

A dictionary may be an option, instead of thinking about list indexes, you might think about the integer keys of the Dictionary. Regardless of size.

Dictionary<int,Dictionary<int,Stone>> stones = new Dictionary<int,Dictionary<int,Stone>>(); // do some initialisation for the base field size ... // access it this way Stone s = stones[-1][-5]; 

Only problem is when you want to add a second dimension that a resource can get (iterate over all 1st dimensions).

Answer 4

I think you will learn more about the implementation of a custom data structure that contains, say, two ArrayLists. One goes forward and one goes back. Of course, in your implementation they will go the same way, but your implementation may lead to the fact that the data structure will return the negation of a positive index plus one, so that you do not get the index -0 for the first element in the return array ArrayList.

I may have misunderstood the problem, but I would like to introduce a two-way extensible data structure.

Good luck

Answer 5

You can do something like:

_stones [- (i), i] and / or _stones [i, - (i)]

Just an offer.