Canvas HTML5: detección de colisión de mouse y polígono

Question

Así que estoy haciendo un juego de tower defense con HTML5 y Javascript. Mi único problema es detectar cuándo el mouse entra en contacto con la ruta del atacante, lo que es necesario para evitar que el jugador construya torres en la ruta. La ruta de los atacantes se determina en el archivo MAP.js (ver el enlace en la parte inferior), mediante una matriz bidimensional (una matriz que contiene pares x e y), por lo que tengo que trabajar es una serie de puntos que hacer un camino cuando está conectado. Simplemente quiero prohibir que el jugador coloque torres dentro de, digamos, 50 píxeles de la ruta. Para ser sincero, soy horrible con la detección de colisiones, por lo que sería de mucha ayuda.

Aquí está el enlace a todo el código: http://shapeshifting.comuv.com/Tower_Defense/td/

Como se puede imaginar, sólo los archivos .js son aplicables, pero la mayor parte del código en cuestión se encuentra dentro del archivo objects.js. (Por favor, disculpe el desorden)

Answer 1

Me gustaría abordar esto en pasos. Veamos con qué empiezas. Tiene una ruta definida por puntos: los pares de puntos definen un segmento de línea. Entonces, lo que realmente tienes es un camino hecho de segmentos de línea. Cuando el usuario mueve el mouse, obtendrá las coordenadas x, y de la posición actual. Lo que quiere hacer es encontrar la distancia del punto del mouse a todos los segmentos de línea. Si está a menos de 50 píxeles de cualquier segmento de línea, entonces no desea permitir que se generen allí.

Para encontrar la distancia entre un punto y un segmento de línea, el pseudo código se ve así. Suponga que los puntos A y B representan ambos extremos de un segmento de línea y el punto C es el punto del mouse.

float distancePoint2LineSegment(Point a, Point b, Point c) { 
    Vector ab = b - a 
    Vector ac = c - a 
    Vector bc = c - b 

    float e = dotProduct(ac, ab) 
    if (e <= 0.0) 
    return sqrt(dotProduct(ac, ac)) 

    float f = dotProduct(ab, ab) 
    if (e >= f) 
    return sqrt(dotProduct(bc, bc)) 

    return sqrt(dotProduct(ac, ac) - e * e/f) 
} 

Esto respondería a su pregunta de detección de colisión, pero creo que entonces debería considerar el rendimiento. ¿Cuántos segmentos de línea habrá en su camino y desea calcular la distancia a cada segmento de línea cada vez que el usuario mueve su mouse? Puede colocar los segmentos de línea en un árbol cuádruple para que solo tenga que probar las colisiones de puntos del mouse contra un número menor de segmentos de línea.

Answer 2

Probablemente sea más simple y rápido definir las áreas en las que el usuario puede colocar torres de manera implícita en el archivo de mapa ... Defina cada área como un polígono convexo (posiblemente incluyendo los bordes del mapa, divida polígonos cóncavos, prefiera horizontal o vertical líneas, entonces la prueba del ratón se encuentra en uno de los polígonos, ver esta respuesta para una implementatio

How to test if a point is inside of a convex polygon in 2D integer coordinates?

descomposición de triángulos hace que la prueba aún más simple

Answer 3

detección de colisiones es uno de esos viejos, escondido problemas de codificación de un juego. Típicamente la gente toma darkpenguin enfoque de precalcular de alguna manera donde en su mapa estático es y no se puede ubicar. El siguiente paso es encontrar una forma de especificar el mapa de colisión más eficiente.

No desea que su juego haga una tonelada de matemática en respuesta al movimiento del usuario del mouse, necesita ser corto y rápido, por lo que es fundamental realizar un cálculo previo de algo rápido.

Si su mapa es una cuadrícula, entonces tiene su respuesta allí mismo - el mapa de colisión es una matriz 2D precalculada - básicamente una imagen en blanco y negro muy pequeña con un píxel para cada lugar en la cuadrícula. Los píxeles blancos (1) son seleccionables y los píxeles negros (0) no. Solo usa esta matriz 2D de verdadero/falso como búsqueda. Si desea guardar memoria, puede agrupar cada franja de 32 espacios en la cuadrícula en un solo indicador de bit.

Si su mapa no es una cuadrícula, entonces aún desea precalcular las cosas, pero la estrategia es un poco más compleja. La primera posibilidad es realizar cálculos matemáticos como Hitesh para producir un mapa collide de resolución ligeramente superior, y el resto es exactamente como la estrategia de cuadrícula, por ejemplo, si cada bloque de píxeles 4x4 fue una entrada en colisión, entonces, si una torre puede ser colocado es una prueba de si sus coordenadas prueban que están encima de suficientes 1 - puede requerir que el 100% de las pruebas sean 1, o puede dejar que alcancen un poco y digamos que el 75% de las pruebas sean 1.

Si esto todavía no es suficiente detalle, puede hacer estas pruebas de polígono más complejas, pero desea que sean lo más simples posible. Cuando no se utiliza una cuadrícula precalculada, la prueba de colisión 2D más simple es de 2 círculos: se calcula la distancia entre sus centros y se comprueba si es mayor o menor que la suma de sus radios. Si precalcula su camino de monstruos en una estela de círculos, el siguiente paso es dividir esos círculos en ... adivina qué ... una grilla. Esto evita que cada cheque tenga que probar cada círculo en el mapa. Esto le permite tener una gran cantidad de estos círculos en el mapa de colisión, ya que la prueba de colisión es primero una búsqueda de las entradas de la cuadrícula en las que está actualmente la torre, y luego verifica si está colisionando con los círculos más cercanos, en lugar de todo el mapa Es importante tener en cuenta que esta grilla precalculada de listas de círculos a menudo tendrá el mismo círculo en múltiples entradas de cuadrícula vecinas, ya que cada entrada de grilla que contenga cualquier porción de un círculo dado debe tener ese círculo en su lista de verificación en colisión.

Una de las cosas buenas de los primeros 2 enfoques de cuadrícula es que es muy fácil realizar un control de calidad usted mismo: literalmente almacenar el mapa de colisión como una imagen e inspeccionarlo visualmente para asegurar que se ve bien para el mapa en el que se basa. También puede dibujarlo a mano si no desea escribir el código para generarlos.

El enfoque de círculo le proporciona curvas legítimas y puede conducir a detalles de borde de colisión más finos, pero obviamente es más difícil de probar y garantizar que ningún mapa tenga mapas de colisión incorrectos. También es más trabajo escribir la herramienta de generación de mapas.

¡Buena suerte!