4

I was going to to write a game (it's called "Qwirkle" if you ever heard of it) in which a 2-dimensional game field stores the position of stones which the players have put into it. The first player puts a stone anywhere and other players can connect to it from any side (left / right / top and bottom). The game field itself is not restricted to a fixed size which would ruin the game idea. However, the number of stones is limited to a value the player can define at start.

Because of the game logic I need to for-loop through the stones with an index. However, since the players can add stones from any side, I'd need a list which is expandable into any direction (e.g. into negative and positive index direction).

Performance is not unimportant since I need to check several stones in one turn.

The best thing would be to access a stone like _stones[-3,5] to access the one at position -3, 5, of course.

I thought a stack which can be pushed and popped from any side (like PushBack / PushFront) would be useful for this, but I'm not quite sure how to realize that in C#.

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

Ray
  • 7,940
  • 7
  • 58
  • 90
  • You could use a double-linked list - keeping track of the head & end node - adding accordingly. If you need o(1) indexing - this may not be good enough, though. – Dave Bish Mar 19 '13 at 15:04
  • 3
    Look at this question http://stackoverflow.com/questions/11837139/implementation-of-array-with-negative-indices – polybios Mar 19 '13 at 15:05
  • @polybios: The approach with the linked list into four directions (top bottom left right) already sounds pretty interesting and performance-wise compatible with my problem. – Ray Mar 20 '13 at 09:13
  • @PacMani: The first problem with a linked list approach is that it doesn't provide random access. The second problem with a linked list approach is how to efficiently handle adding (and later accessing) B1 when you currently have A2 and A3. If you only make one path, every lookup is a search. If you make many paths, insertions are an order of magnitude less efficient (both in terms of memory and in terms of performance. I prefer Eric Lippert's recommendation. – Brian Mar 21 '13 at 19:32
  • @Brian: Yeah, I have a look at it. I think I'll accept Eric's answer as the solution if I got further with it. – Ray Mar 21 '13 at 21:10

5 Answers5

5

The data structure you want is an immutable quadtree. If the board is mostly empty then using an immutable quadree enables you to represent boards that are essentially unlimited in size; a one-trillion-by-one-trillion cell board takes only a few bytes more memory than a 32-by-32 cell board. Immutable quadtrees can easily be indexed in the manner you describe, and computing a new quadtree given an old quadtree and an edit is straightforward.

I've written immutable quadtree algorithms several times over the years and I have been meaning for a long time to do a series of blog articles on them, but I never have. When I do I'll come back and update this answer.

In the meanwhile, this Dr. Dobbs article on Gosper's Algorithm is the one I used to learn how immutable quadtrees work.

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

Eric Lippert
  • 647,829
  • 179
  • 1,238
  • 2,067
  • This is a pretty interesting article (also because I just found out about the "Game of Life"), but I think it's a bit over-engineered for my problem. For fairness I have to say my question wasn't clear enough: The game field would ideally be infinite, but the number of stones the players can put is limited to a (initially variable but at game time) fixed value - but that does not make it really possible to calculate the needed size because of the many ways they can connect to each other. The game's called "Qwirkle" if you heard of that. – Ray Mar 20 '13 at 09:10
  • @PacMani: If you just use a mutable quadtree with getters and setters, it becomes very simple (but architecturally much less beautiful). This is sufficient for if the model is single-threaded. Get(X,Y) recurses, returning "Empty" if it hits a null. Set(X,Y) expands if necessary, then recurses, creating a new subtree if it hits null. It seems pretty straightforward to me. For added simplicity, skip the expand step but start out with a one trillion by one trillion cell board. – Brian Mar 20 '13 at 20:25
  • Accepted as answer since this seems to be the technically best approach. I'm also looking forward to your blog articles :) – Ray Mar 22 '13 at 17:29
2

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

Servy
  • 202,030
  • 26
  • 332
  • 449
  • 1
    Stephen Cleary's deque is a good implementation: http://nitodeque.codeplex.com/ (full of NuGetty goodness) – Matthew Watson Mar 19 '13 at 15:13
  • 1
    There's some good discussion of techniques for writing immutable deques here: http://stackoverflow.com/questions/3271256/implement-an-immutable-deque-as-a-balanced-binary-tree – Eric Lippert Mar 19 '13 at 16:21
  • However, the poster here wants an unlimited-size two dimensional board. A quadtree would be a better approach than a deque. – Eric Lippert Mar 19 '13 at 16:26
0

Dictionary could be an option, instead of thinking about indexes of a list, you could think of integer keys of a Dictionary. No matter what's the dimension.

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 issue is when you want to add a 2nd dimension which can get resource consuming (iterating over all 1st dimensions).

Florian F.
  • 4,700
  • 26
  • 50
  • 1
    Getting the "first" or "last" item is a very inefficient operation using this model, as is adding an item to the front or back. You need to know what the highest/lowest indices are at any given time, and that requires complete iteration of the collection. – Servy Mar 19 '13 at 15:16
  • @Servy Agreed, it is just a suggestion of implementation, you'd have to make a class inheriting/composing Dictionary and save indexes to make it bearable to use. Don't know about costs and optimization either but it surely isn't the best option. Depending on what you plan to do with it, it still is an easy-to-implement possibility. – Florian F. Mar 19 '13 at 15:22
0

I think you will learn more from implementing a custom data structure containing, say, two ArrayLists. One going forward and one going backward. Of course, in your implementation they will both go the same way but your implementation could have the data structure return a negation of the positive index plus one so that you don't get an index of -0 for the first element in the backward ArrayList.

Maybe I've misunderstood the problem, but that's how I would go about implementing a two-way expandable data structure.

Good luck!

parski
  • 104
  • 2
  • 8
-1

You could do something like:

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

Just a suggestion.

Vasant
  • 1