Clever data structure to represent layered circle.

Question

I'm making a game and I need to represent a "layered" circle in some clever datastructure.

A circle can have any number of layers. Each layer has a number of "slices", they can be of different lengths and pieces can be missing. The innermost layer is always a full circle. Each segment has a color, multiple segments with the same color can be next to each other.

Realistically a circle wont have more than about 40 layers or about 1500 individual slices.

I will need to be able to easily find adjacent pieces to a specific piece, see if a piece is "hanging in free air" (imagine gravity towards the center), and to remove pieces leaving a hole in their place.

I've already got a few ideas for how to store this, but I thought it was an interesting question so I figured I'd post it here for kicks.

I will be coding this in Actionscript 3.0, but feel free to post ideas in any language.

Answer 1

Think of the Mercator projection for a map of the Northern (or if you prefer Southern) hemisphere. Draw on some lines of longitude and latitude. Now, bearing in mind that a standard Mercator projection cannot show +/-90 lat think of the topmost latitude band as representing the circle around the Pole of your map. Draw the grid sufficient for your purposes. Now you have a nice planar 2D array on which to represent your data with the adjacency property that you want (remembering to wrap at the prime anti-meridian). You'll have to represent empty slices by assigning some null value to them.

I hope this rather hurried explanation is sufficient, and I'm sorry if a 2D array isn't a clever enough data structure.

Regards

Mark

Answer 2

That is an interesting question. I am at work so at the moment I will have to give a quick answer but will test this out tonight.

I wonder if an array/list of circular linkedlist would work? You can mark each element in the list with some identifier to show it is in a slice. The more elements you add to the outer array the more layers you have. It isn't too interesting but it is simple. You should be able to find adjacent pieces easily this way.

Answer 3

Just thinking out loud and not a complete solution, but for each band there are 360 empty slots that can be filled (corresponding to number of degrees). Come to think of it, why limit it to 360 integer degrees. But anyway you could determine if segments on adjacent levels were touching by merely checking the range they occupied on each level. So if segment x on level n occupied 120-240 and segment z occupied 80-300 on level n+1 then they are adjacent.

Come to think of it, how is your application even really dependant on attributes of concentric circles, or even on a circle. It seems you could image a bunch of rings stacked on top of each other to form a tube, or even a bunch of linear rows stacked on top of each other to form a wall and the data structure would be the same in all these cases (given what I can glean from your description of the problem.) Then its just a matter of the most efficient implemntation of linked lists or something.

Answer 4

Just thinking quickly about this, I could see some kind of directed graph with different kind of edges. Probably something like this

Node:
 + List<Node *> ParentLevel: a list of nodes at the level above (ie. more external)
 + List<Node *> ChildrenLevel: a list of nodes at the level below (ie. more internal)
 + Node * ClockwiseNeighbourgh
 + Node * AntiClockwiseNeighbourg

You would have two set nodes, one being the center circle and one representing a ficticious most outter circle.

You can then easily navigate between levels, from neighbourgh to neighbourgh in any direction. To find all the slices which are "in the air", you can start from the inner or outer node and find any slice that does not have a parent or a child.

The only thing this does not handle is the case where there is two disjunct parts to your layered circle, ie. with a fully missing layer. It could support it though by adding weights on the edges to represent the distance.

Answer 5

You didn't say anything about the behavior of the slices and layers, which would be important to develop a data structure that would represent more than the pure geometric structure of your playing field.

Make a list of layers. Layers[0] is your innermost layer.

Each layer is a list of slices. Each slice is defined by its starting angle and color. If there is one slice in a layer it goes around the whole layer. If there are more slices each one begins at the starting angle and ends where the next one starts, without storing data redundantly. A hole is a special color. A slice is hanging in the air if the layer below it is colored "empty" over its start and end angle. Adjacent slices on the same layer are the next indexes in the list of slices, or the last and first one in the list. Adjacent slices in other layers are again found over the starting end ending angles of the slice.

Answer 6

Why not use a graph (from graph theory). Just add edges (connectivity links between colored spaces) for each vertex (each colored space on your game board). Graphs are designed for it to be easy to retrieve a list of neighboring vertices (colored spaces in your case).

Answer 7

Just a quick idea, no offense if it's stupid - it's late here :P

• Create a vector of Layers to start.
• Each Layer contains a Vector of Pieces.
• Each Piece stores a ratio value (0-1) and a color that can alternatively be NULL
• The sum of all the Pieces's ratio always equals 1.

In the beginning each Layer could contain a single Piece (with the ratio of 1).

If you now decide to add a blue piece of a ratio of .5 (180º) to an empty Layer at the offset .25 this will replace the empty create 3 pieces :

• [NULL .25][blue .5][NULL .25]

... and so an recursively, so you end up with something like :

• [NULL .25][blue .2][NULL 0][red .1][NULL .2][black .25]

Supposing you want to do something interactive with this ... This can be handy if you want some spaces to be static whereas other adjust, or if you want an adjacent color piece to be magnetic you just have to check if the Piece in between has a ratio of zero / or enough to attract the other without having to do any extra calculations. Basically the nice thing is that the calculations would be done when a Piece is altered. The rest would just be logic. Say if a piece is moved, you only have to be aware of the left/right empty space ratio values, and do not need to iterate the rest calculating angles. Would somehow be quite similar to the way elastic UIs adjust actually.