Estructura de datos inteligente para representar un círculo en capas

Question

Estoy haciendo un juego y necesito representar un círculo "estratificado" en una estructura de datos inteligente.

Un círculo puede tener cualquier cantidad de capas. Cada capa tiene una cantidad de "cortes", pueden ser de diferentes longitudes y pueden faltar piezas. La capa más interna es siempre un círculo completo. Cada segmento tiene un color, múltiples segmentos con el mismo color pueden estar uno al lado del otro.

circle with layers http://webbfarbror.se/dump/datastructure.gif

realista un círculo no tendrá más de aproximadamente 40 capas o sobre 1.500 rebanadas individuales.

Necesitaré poder encontrar fácilmente piezas adyacentes a una pieza específica, ver si una pieza está "colgando en el aire libre" (imagine la gravedad hacia el centro) y quitar las piezas dejando un agujero en su lugar.

Ya tengo algunas ideas sobre cómo almacenar esto, pero pensé que era una pregunta interesante, así que pensé que lo publicaría aquí para dar patadas.

Estaré codificando esto en Actionscript 3.0, pero no dude en publicar ideas en cualquier idioma.

Answer 1

Solo pensando rápidamente en esto, pude ver algún tipo de gráfico dirigido con diferentes tipos de bordes. Probablemente algo como esto

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 

Usted tendría dos nodos establecidos, siendo uno de ellos el círculo central y uno en representación de un círculo más Outter ficticio.

Luego puede navegar fácilmente entre niveles, desde el vecindario hasta el vecindario en cualquier dirección. Para encontrar todos los sectores que están "en el aire", puede comenzar desde el nodo interno o externo y buscar cualquier sector que no tenga un elemento primario o secundario.

Lo único que no se maneja es el caso en el que hay dos partes disjuntas en su círculo estratificado, es decir. con una capa que falta por completo Sin embargo, podría soportarlo agregando pesos en los bordes para representar la distancia.

Answer 2

Piense en la proyección de Mercator para un mapa del hemisferio norte (o si prefiere sur). Dibuja en algunas líneas de longitud y latitud. Ahora, teniendo en cuenta que una proyección de Mercator estándar no puede mostrar +/- 90 lat, piense que la banda de latitud superior representa el círculo alrededor del Polo de su mapa. Dibuja la grilla suficiente para tus propósitos. Ahora tiene una buena matriz bidimensional plana en la que puede representar sus datos con la propiedad de adyacencia que desea (sin olvidar ajustar el anti-meridiano principal). Deberá representar segmentos vacíos asignándoles un valor nulo.

Espero que esta explicación bastante apresurada sea suficiente, y lo siento si una matriz 2D no es una estructura de datos suficientemente inteligente.

Answer 3

Esa es una pregunta interesante. Estoy en el trabajo así que en este momento tendré que dar una respuesta rápida, pero voy a probar esto esta noche.

Me pregunto si una matriz/lista de lista de enlaces circular funcionaría? Puede marcar cada elemento de la lista con algún identificador para mostrar que está en un sector. Cuantos más elementos agregue a la matriz externa, más capas tendrá. No es muy interesante, pero es simple. Debería poder encontrar piezas adyacentes fácilmente de esta manera.

Answer 4

Simplemente pensando en voz alta y no es una solución completa, pero para cada banda hay 360 espacios vacíos que se pueden llenar (correspondiente a la cantidad de grados). Ahora que lo pienso, ¿por qué limitarlo a 360 grados enteros? Pero de todos modos, usted podría determinar si los segmentos en los niveles adyacentes se tocaban simplemente marcando el rango que ocupaban en cada nivel. Entonces, si el segmento x en el nivel n ocupa 120-240 y el segmento z ocupa 80-300 en el nivel n + 1, entonces son adyacentes.

Ahora que lo pienso, ¿cómo es que tu aplicación depende realmente de los atributos de los círculos concéntricos, o incluso en un círculo? Parece que puedes imaginar un montón de anillos apilados uno encima del otro para formar un tubo, o incluso un montón de filas lineales apiladas una sobre otra para formar una pared y la estructura de datos sería la misma en todos estos casos (dado lo que puedo deducir de su descripción del problema.) Entonces solo es cuestión de la implementación más eficiente de listas enlazadas o algo así.

Answer 5

No dijo nada sobre el comportamiento de las divisiones y las capas, lo que sería importante para desarrollar una estructura de datos que representaría algo más que la estructura geométrica pura de su campo de juego.

Haz una lista de capas. Las capas [0] son ​​la capa más interna.

Cada capa es una lista de sectores. Cada sector está definido por su ángulo de inicio y color. Si hay una rebanada en una capa, recorre toda la capa. Si hay más sectores, cada uno comienza en el ángulo inicial y termina donde comienza el siguiente, sin almacenar datos de forma redundante. Un agujero es un color especial. Una rebanada está colgando en el aire si la capa debajo de ella está coloreada "vacía" sobre su ángulo inicial y final. Las divisiones adyacentes en la misma capa son los siguientes índices en la lista de sectores, o el último y el primero en la lista. Rebanadas adyacentes en otras capas se encuentran de nuevo sobre los ángulos finales de fin de la porción.

Answer 6

¿Por qué no utilizar un graph (de la teoría de grafos). Simplemente agregue bordes (enlaces de conectividad entre espacios de colores) para cada vértice (cada espacio coloreado en su tablero de juego). Los gráficos están diseñados para que sea fácil recuperar una lista de vértices vecinos (espacios de colores en su caso).

Answer 7

Sólo una idea rápida, sin ofender si es estúpida - que es tarde aquí: P

• crear un vector de capas para empezar.
• Cada capa contiene un vector de piezas.
• cada pieza almacena un valor de la relación (0-1) y un color que, alternativamente puede ser nulo
• La suma de todas proporción del Piezas siempre es igual a 1.

En el comienzo de cada capa podría contener una Pieza única (con la proporción de 1).

Si ahora decide añadir una pieza azul de una proporción de 0,5 (180º) a una capa vacía en el 0,25 compensar este reemplazará los vacíos crear 3 piezas:

• [NULL 0,25 ] [azul 0,5] [NULL 0.25]

... y así una forma recursiva, por lo que terminan con algo como:

• [NULL 0.25] [azul 0,2] [ NULL 0] [rojo .1] [NULL .2] [negro.25]

suponiendo que quiere hacer algo interactivo con esto ... Esto puede ser útil si desea algunos espacios para ser estáticos mientras que otro ajuste, o si desea una pieza de color adyacente al ser magnéticos que acaba tiene que verificar si la pieza intermedia tiene una relación de cero/o suficiente para atraer al otro sin tener que hacer cálculos adicionales. Básicamente lo bueno es que los cálculos se realizarían cuando se modificara una Pieza. El resto sería solo lógica. Digamos que si una pieza se mueve, solo hay que tener en cuenta los valores de razón de espacio vacío izquierdo/derecho, y no es necesario iterar el resto calculando ángulos. De alguna manera sería bastante similar a la forma en que las IU elásticas se ajustan realmente.