una studio programacion obtener móviles longitud latitud guardar google geolocalizacion ejemplos direccion desarrollo curso coordenadas aplicaciones java map tile coordinate

studio - Java: ¿Cuál es una buena estructura de datos para almacenar un mapa de coordenadas para un mundo de juego infinito?



manual de programacion android pdf (11)

Estoy acostumbrado a la codificación en PHP, pero no soy muy hábil con Java y esto ha sido un problema desde hace un tiempo. Espero que sea una solución bastante fácil, sin embargo, no puedo encontrar ningún buen código de ejemplo en la forma en que lo busco, así que aquí va:

Estoy programando un juego que tiene lugar en un 2do mundo infinito generado aleatoriamente en un mapa basado en mosaicos (algo curioso: sé que no será verdaderamente infinito. Solo espero que el mundo sea bastante grande). El enfoque habitual de la matriz multidimensional map [x] [y] comenzó como una idea básica, pero dado que Java no proporciona una forma de shenanigans de matriz no entera (es decir, negativa) como PHP, no puedo tener una (- x, + x, -y, + y) sistema de coordenadas con teclas de matriz.

Necesito poder encontrar los objetos en un mosaico en una coordenada x, y específica, así como encontrar "mosaicos adyacentes" de un cierto mosaico. (Trivial si puedo getObjectAt (x, y), puedo obtener (x + 1, y) y así sucesivamente)

He leído sobre quad trees y R-trees y similares. El concepto es emocionante, sin embargo, no he visto ninguna implementación de ejemplo buena y simple en Java. Y, además, no estoy realmente seguro de si eso es exactamente lo que necesito.

Cualquier consejo es bienvenido

Gracias

Árboles, árboles cuádruples, árboles binarios, árboles rojos y negros, y todos los demás tipos de árboles son INÚTILES para ti (a menos que planees tener un mapa con un gran bosque).

Las estructuras de datos especializadas tienen sus usos específicos. A menos que tengas una buena razón por la cual tu juego necesita un índice espacial, no construyas uno. Si su escenario típico es "iterar sobre el área visible, descubrir qué mosaico es visible en cada uno de los cuadrados", entonces necesita una estructura que le proporcione acceso rápido y aleatorio a un valor almacenado en una clave específica. Tal estructura es un HashMap (lo que PHP usa es una especie de LinkedHashMap, pero probablemente no estaba usando la parte "vinculada").

Debes seguir el consejo de xephox (y darle el crédito), y eso es:

  • hacer una clase que describa una ubicación (Pair, Location, Point, whatever);
  • hacer todos los campos (probablemente x e y) final. Es importante que un lugar en sí mismo no pueda cambiar (hará que tu vida sea MUCHO más fácil);
  • generar métodos equals y hashcode (cada IDE te ayudará con eso. Recuerda que las implementaciones DEBEN usar tanto x como y - un asistente en tu IDE te ayudará);
  • su mapa será: Map map = new HashMap ();

Lo mejor: si continúa usando la interfaz de Map, no estará bloqueado y podrá realizar muchas mejoras. Como envolver el HashMap en un objeto que crea partes del mapa usando algunas técnicas algorítmicas.

¿Qué hay de dividir el mapa en trozos (sí, fanáticos de Minecraft, sé dónde se usa esto también: P)? Entonces tienes dos sistemas de coordenadas, ambos con el mismo origen:

  • coordenadas x/y
  • c1/c2 chunk coordenada

Un fragmento es siempre un tamaño fijo de coordenadas del mundo real (digamos 128x128). Luego tienes un Chunk clase en el que tienes una matriz fija (128x128) con toda la información para cada píxel. Y almacenas tus fragmentos en un Map<ChunkCoordinates, Chunk> como ya lo explicaron otros. Yo recomendaría un HashMap .

Cada vez que su reproductor esté en una región determinada, los trozos necesarios se cargan desde el mapa y luego puede acceder a la matriz de tamaño fijo allí. Si el trozo lo sabe, donde está ubicado en coordenadas x/y , incluso puede tener alguna función de soporte como Pixel Chunk#getPixel(long x, long y) o eso ...

Por cierto: esto también te da una manera fácil de posponer la generación del mundo entero hasta que realmente se necesita: al principio, no se genera nada y tan pronto como se accede a un Chunk en el mapa, que aún no se ha generado, puedes simplemente generar es entonces O puede llenarlo al inicio si eso es más fácil para usted. (llenar un mundo infinito llevará mucho tiempo, aunque sea pseudo infinito)

1) En lugar de una matriz, puede usar un Map<Integer, Map<Integer, Tile>> o Map<Point, Tile> , lo que, por supuesto, permitiría índices negativos

2) Si conoce las dimensiones de su mundo desde el principio, puede modificar su getter para permitir que la API acepte negativos y [linealmente] los transforme en positivos. Entonces, por ejemplo, si tu mundo tiene 100x1000 fichas y quieres (-5, -100), tendrías WorldMap.getTile(-5,-100) que se traduciría en return tileArray[x+mapWidth/2][y+mapHeight/2]; que es (45,400)

Escribí un par de estructuras de datos de repuesto en Java que podrían interesarte.

El más interesante fue el Octreap que es lo que creo que es un cruce completamente novedoso entre un Treap y un Octree , que tenía las siguientes características:

  • Coordenadas mundiales de 60 bits (aproximadamente 1,000,000 * 1,000,000 * 1,000,000 de cuadrícula)
  • Coordenadas negativas compatibles
  • El espacio vacío no requiere almacenamiento (admite mundos altamente dispersos)
  • Comprime volúmenes de celdas idénticas (por ejemplo, bloques grandes del mismo material se almacenarían de manera eficiente)
  • O (log n) para lecturas y escrituras

Estas son dos preguntas separadas: cómo simular indices de matriz negativos para que pueda tener un mapa "infinito" y cómo almacenar los mosaicos de manera eficiente.

En la primera pregunta, un truco sería mantener cuatro matrículas separadas (¿matrices?), Una para cada cuadrante. Entonces todos los índices pueden ser positivos.

En la segunda pregunta, necesitas un mapa disperso. Una forma no muy eficiente es tener un hashmap de hashmaps. De hecho, eso podría resolver el primer problema también:

HashMap<String, HashMap> x = new HashMap() HashMap<String, Tile> y = new HashMap() // get the tile at coordinates 1,2 Tile myTile = x.get("1").get("2"); // this would work as well myTile = x.get("-1").get("-2");

Podrías hacer tu propia implementación de mapas que tomara enteros como claves y fuera mucho, mucho más eficiente.

Las soluciones de estilo hashmap son terribles para los cálculos de adyacencia, requieren una iteración de todo el conjunto de datos.

Algo como un quadree o un octree es perfecto, EXCEPTO que no es infinito, es un tamaño arbitrario (el mundo de la diferencia allí).

Sin embargo, si lo piensas bien, una ArrayList no es infinita, es solo un tamaño arbitrario que crece, ¿verdad?

Así que un quadtree es escaso y muy buenos cálculos de adyacencia ad, a excepción de la provisión "infinita" que es perfecta. ¿Por qué no usar uno de esos tamaños de hasta 100 veces lo que crees que necesitarías (es escaso, no es realmente un gran problema). Si alguna vez llega al punto en el que está cerca del borde, asigne un nuevo quadtree que sea mucho más grande.

Creo que si tienes cuidado (es posible que tengas que implementar tu propio quadtree) puedes "actualizar" el quadtree con muy poco esfuerzo y sin copiar, debería ser simplemente una cuestión de prefijar todas tus direcciones existentes con algunos bits (las direcciones están en cuadrículas binarias; cada bit representa dividir el universo existente por la mitad en una dimensión u otra).

Llegué a este hilo con el mismo problema, pero mi solución fue utilizar Map/HashMaps , pero estos son unidimensionales.

Para superar esto, en lugar de usar un mapa dentro de un mapa (que sería desordenado y muy ineficiente), utilicé una clase de Pair genérica (no es algo que encontrarás en la biblioteca de stock de Java) aunque podrías reemplazarla por una clase de posición (prácticamente el mismo código, pero no genérico, en lugar de enteros o flotantes).

Por lo tanto, al definir el mapa: Map<Pair, Tile> tiles = new HashMap<Pair, Tile>;

Para colocar objetos de mosaico en el mapa utilicé tiles.put(new Pair(x, y), new GrassTile()); y para recuperar el objeto tiles.get(new Pair(x, y)); .

[x / y sería cualquier coordenada que desea colocar (¡ esto permite las coordenadas negativas sin ningún problema!), "nuevo GrassTile ()" es solo un ejemplo de colocar un mosaico de cierto tipo durante la creación del mapa. Obviamente, como se dijo anteriormente, la clase Pair es reemplazable.]

¿Por qué no ArrayLists puede preguntar? Debido a que las listas de arreglos son mucho más lineales que la asignación, y en mi opinión son más difíciles de agregar y recuperar fichas, especialmente en 2 dimensiones.

Actualizar:

Para cualquiera que se pregunte por qué no hay una clase Pair () en Java, aquí hay una explanation .

No soy un experto en programación de juegos, pero si las matrices están bien, simplemente puedes traducir tus coordenadas de (-x, + x) a (0, 2x) (idem para el eje y).

O si está acostumbrado a arreglos asociativos como PHP, use la estructura correspondiente en Java, que es un Mapa (HashMap estaría bien): defina una clase Coordinate con los métodos equals y hashCode apropiados, y use un HashMap<Coordinate> . Hacer que Coordinate sea inmutable hace que el código sea más robusto y permite almacenar en caché el hashCode.

Probablemente quiera usar una implementación de Map. HashMap, SortedMap, etc. según la cantidad de datos que pretenda almacenar y sus patrones de acceso (Sorted Map es muy bueno para el acceso secuencial, HashMap es mejor para el acceso aleatorio).

Puede usar Mapas bidimensionales o convertir sus indecisos de 2-d en una clave para un Mapa de 1-d.

Si quieres ser realmente rápido y realmente escalable, definitivamente usa Sparse Octree.

Octree

No conozco ninguna implementación en Java, pero es trivial. Simplemente almacene en un solo byte un campo de bits para el cual los nodos están actualmente vinculados y use una lista vinculada para mantener esas referencias (para cada nodo Octree una lista separada de un máximo de 8 entradas).