javascript - sistema - Obtener de manera eficiente las posiciones de cuadrícula isométricas dentro de un cuadro delimitador

perspectiva caballera militar e isometrica

Question

Tengo un sistema de cuadrícula isométrico cuyas coordenadas comienzan desde [0,0] en la esquina izquierda de la cuadrícula (La esquina que se muestra en la imagen de arriba) con x incrementándose hacia la parte inferior de la imagen ey aumentando hacia la parte superior (por lo tanto [ 0, altura] sería la esquina superior y [ancho, 0] sería la esquina inferior en forma de diamante con ancho y altura del tamaño de la cuadrícula, es decir, 200 x 200 cuadrados)

De todos modos, lo que necesito ayuda es obtener una variedad de posiciones de cuadrícula isométricas que están dentro del cuadro azul que se muestra en la imagen. Sin iterar sobre cada x, y pantalla de posición y obtener la posición de la cuadrícula correspondiente (Ver esta pregunta que planteé anteriormente sobre cómo convertir de una posición de pantalla a una posición de cuadrícula Obtener fila / columna en cuadrícula isométrica. ) No estoy seguro de cómo para lograr esto de manera eficiente.

Hubo una pregunta que encontré anteriormente que es casi exactamente el mismo enlace aquí. La respuesta fue convertir la cuadrícula en una imagen con diferentes colores para cada cuadrícula y luego detectar qué colores estaban presentes debajo del cuadrado. He implementado esta solución, pero es bastante lenta. Estoy casi pensando que revisar la posición de la cuadrícula para cada píxel en el cuadro de selección sería más rápido. ¿Por qué oh por qué javascript es tan lento en el bucle?

Realmente necesito una solución matemática para este problema basada en mi sistema de coordenadas, pero parece que no puedo encontrar algo que funcione (y maneja el cuadro de selección que también sale de la cuadrícula)

Por favor, avíseme si necesita más información.

Editar: Desafortunadamente las respuestas suministradas no han funcionado hasta ahora, ya que la selección es como tener un área seleccionada en una cuadrícula cuadrada, realmente no hay esquina superior izquierda, esquina inferior derecha para iterar a menos que me haya olvidado el punto de las respuestas. He optimizado el enfoque de renderizado pero en una selección grande, todavía agrega una caída notable en los cuadros, ya que recorre todo el color de control de píxeles y obtiene el cuadrado correspondiente

Answer 1

Creo que Aleksander tiene una muy buena idea sobre cómo resolver su problema.

Aquí hay una alternativa:

Una manera fácil de reducir el número de cuadrados de cuadrícula para verificar es encontrar las coordenadas de las esquinas del cuadro azul en coordenadas de cuadrícula. En su ejemplo, solo necesitaría verificar los cuadrados donde 1<x<13 and 3<y<16 .

alvaro da una respuesta breve y concisa sobre cómo verificar si un punto está dentro de una caja .

Answer 2

Mi enfoque que no vi que hiciera nadie más: 1. Transforma tu rectángulo de selección en la cuadrícula (toma la posición de cada esquina) 2. Ahora tenemos un problema 2d, que es: encontrar todos los puntos dentro de la cuadrícula rombo.

Esto podría hacerse de forma similar a: http://en.wikipedia.org/wiki/Flood_fill

Pero tal vez algo así es mejor:

1. Start at the topmost
2. Go down
3. Go right until we encounter the edge (can be calculated from the rombus line)
4. Do the same thing but go left.
5. Go to 2 until we are at the middle
6. Go right and down.
7. Go right until we encouter the edge
8. Go left and down.
9. Go left until we encouter the edge
10. Go to 6 until we are at the bottom

En cada azulejo que visitamos, lo agregamos.

Ahora el único problema que queda es determinar si hemos encontrado una ventaja ...

Answer 3

Teniendo en cuenta el diseño regular de las fichas, ¿no puede simplemente comenzar desde la esquina superior izquierda de la casilla de selección, pulsar la prueba para encontrar qué ficha y luego pasar a la siguiente casilla de acuerdo con la separación entre ellas?

Por ejemplo, si sus fichas son de 32x16, comenzaría en la esquina y avanzaría a lo largo de 32, luego cuando llegue al final, avanzará en la siguiente fila.

por ejemplo, en un extraño tipo de pseudocódigo ...

var altRow = false;
var selectedTiles = [];
for (int y = selectorBox.top; y < selectorBox.top+selectorBox.height; y+=TILE_HEIGHT/2) {
    for (int x = selectorBox.left ; x < selectorBox.left+selectorBox.width; x+= TILE_WIDTH) {
        selectedTiles.add(tileAtPoint(x + (altRow ? - TILE_WIDTH/2 : 0), y);
    }
    altRow = !altRow;
}

Answer 4

Supongo que puede obtener las coordenadas de las esquinas del cuadro de selección asignadas a los cuadrados de la cuadrícula. Esto le da un problema de trazado con una prueba algebraica simple para la solución. Si comenzamos con las esquinas en iso cuadrados (x1, y1) y (x2, y2), sabemos que debemos probar a lo largo de las líneas con pendiente 1 y -1 que pasan por estos puntos,

entonces las cuatro líneas son y-y1 = x-x1, y-y1 = x1-x, y-y2 = x-x2, y-y2 = x2-x. Se encuentran en los cuadrados iso que contienen las esquinas de la caja de selección con la que comenzó.

Si asumimos por conveniencia que x2 e y2 son mayores que x1 y y1 respectivamente, solo necesitamos iterar sobre la cuadrícula de iso para valores de x1 a x2, y de y1 a y2, aceptando solo iso-cuadrados cuyas coordenadas y sean menores que las dos líneas "más grandes" y más pequeñas que las dos líneas "más pequeñas".

Answer 5

El álgebra lineal es la respuesta. Aquí hay dos sistemas de coordenadas de interés: coordenadas de pantalla y coordenadas isométricas. La conversión de las esquinas de la región seleccionada de las coordenadas de la pantalla a las coordenadas isométricas será de gran ayuda.

Deje que theta sea el ángulo entre los ejes xey de las coordenadas isométricas, medido en la pantalla y la unidad sea la longitud de píxel de un paso en las coordenadas isométricas. Entonces

var c = Math.cos(theta/2);
var s = Math.sin(theta/2);
var origin = [oX, oY]; //the pixel coordinates of (0, 0)
var unit = 20;
var iso2Screen = function(iso) {
  var screenX = origin[0] + unit * (iso[0] * c + iso[1] * c);
  var screenY = origin[1] + unit * (iso[0] * -s + iso[1] * s);
  return [screenX, screenY];
}

Invertir esta relación, obtenemos

var screen2Iso = function(screen) {
  var isoX = ((screen[0] - origin[0]) / c - (screen[1] - origin[1]) / s) / unit;
  var isoY = ((screen[0] - origin[0]) / c + (screen[1] - origin[1]) / s) / unit;

Ahora convierta las coordenadas de la pantalla de cada esquina del cuadro de selección en coordenadas isométricas y obtenga el mínimo y máximo x e y.

var cornersScreen = ...//4-element array of 2-element arrays
var cornersIso = [];
for(var i = 0; i < 4; i++) {
  cornersIso.push(screen2Iso(cornersScreen[i]));
}
var minX, maxX, minY, maxY;
minX = Math.min(cornersIso[0][0], cornersIso[1][0], cornersIso[2][0], cornersIso[3][0]);
maxX = Math.max(cornersIso[0][0], cornersIso[1][0], cornersIso[2][0], cornersIso[3][0]);
minY = Math.min(cornersIso[0][1], cornersIso[1][1], cornersIso[2][1], cornersIso[3][1]);
maxY = Math.max(cornersIso[0][1], cornersIso[1][1], cornersIso[2][1], cornersIso[3][1]);

Todos los puntos isométricos seleccionados se encuentran dentro de la casilla isométrica [minX, maxX] x [minY, maxY], pero no todos los puntos en esa casilla están dentro de la selección.

Podría hacer muchas cosas diferentes para descartar los puntos en esa casilla que no están en la selección; Sugeriría iterar sobre valores enteros de isométrico xey, convertir las coordenadas isométricas en coordenadas de pantalla, y luego probar para ver si esa coordenada de pantalla se encuentra dentro del cuadro de selección, a saber:

var sMinX, sMaxX, sMinY, sMaxY;
sMinX = Math.min(cornersScreen[0][0], cornersScreen[1][0], cornersScreen[2][0], cornersScreen[3][0]);
sMaxX = Math.max(cornersScreen[0][0], cornersScreen[1][0], cornersScreen[2][0], cornersScreen[3][0]);
sMinY = Math.min(cornersScreen[0][1], cornersScreen[1][1], cornersScreen[2][1], cornersScreen[3][1]);
sMaxY = Math.max(cornersScreen[0][1], cornersScreen[1][1], cornersScreen[2][1], cornersScreen[3][1]);
var selectedPoints = [];
for(var x = Math.floor(minX); x <= Math.ceil(maxX); x++) {
  for(var y = Math.floor(minY); x <= Math.ceil(maxY); y++) {
    var iso = [x,y];
    var screen = iso2Screen(iso);
    if(screen[0] >= sMinX && screen[0] <= sMaxX && screen[1] >= sMinY && screen[1] <= sMaxY) {
      selectedPoints.push(iso);
    }
  }
}

Answer 6

Soy estudiante haciendo juegos XNA por hobby. Estoy trabajando en juegos clásicos en 2D basados ​​en cuadrados ( Project Squared ). Este juego tuyo me recordó mi trabajo, así que decidí ayudarte.

Creo que debería hacerse usando matemáticas, no gráficos como mencionaste.

Primero, debe saber qué casilla (posición en la cuadrícula) está al inicio de "caja azul" (probablemente cuadro de selección) y al final de la selección. Entonces ahora sabes un principio y un final de tu lista.

Dado que en los cuadrados de tu juego probablemente tengas un tamaño estático (o que amplíes la cámara, pero nunca aumentes el ancho / alto) puedes calcular fácilmente qué casillas hay en tu casilla de selección.

Ahora, sabes que tus cuadrados están movidos a 45 ° r / l.

(Estoy hablando de XNA como Coordsys - arriba a la izquierda 0,0)

If ( selectedStartSquare.selectionY <= square.height )
    startY = selectedStartSquare.selectionY
else startY = selectedStartSquare.selectionY + 1; 

if (selectedEndSquare.selectionY > square.height)
    endY = -||-.selectionY
else endY = -||- + 1;

esto le dará los índices de altura inicial y final de los cuadrados. Lo mismo que debe hacer para los índices X.

Ahora tienes todo lo que necesitas para obtener todos los cuadrados. Pase por X desde selectedStartSquare.X a endX y a través de Y con for loop desde selectedStartSquare.Y hasta endY, pero cambie de inicio cada vez (startYIndex ++ cada ciclo)

Este es solo un ejemplo cercano ya que nunca he trabajado con juegos isométricos. Esto probablemente necesite algunos ajustes pero ¡"¡¡¡pienso !!" Esto debería funcionar. (Escribí esto antes de dormir y sin siquiera un papel ya que estaba en la cama ya ... buena suerte)

Perdón por mi inglés, soy de Croacia, así que ...