Pygame: Colisiones y áreas de desplazamiento..

[Bleed]

Hola chicos.

Este es mi primer mensaje en el foro y me parece que va a traer algo de guerra. No tengo mucho tiempo para dedicarme a esto, así que sólo puedo aprovechar los domingos y cuando las ganas me lo permiten. El problema que tengo está enfocado en otro contexto, pero he preparado un pequeño boceto para explicarlo mejor.

Ejemplo gráfico:


Lo que quiero hacer, es que un Sprite (el cuadrado rojo) se pueda mover por la pantalla y que cuando colisione con una línea se detenga. Conectando varias líneas limitaríamos el espacio por el cual puede desplazarse y por lo tanto, estaríamos definiendo las limitaciones de un mapa. Para entenderlo mejor, podéis ver la metáfora del Sprite dentro de una Isla.

El problema es que no se muy bien por donde empezar... ¿Guardo en una lista que píxeles limitan el mapa (1 a 1) y antes de mover el Sprite compruebo si el pixel de destino es un limitador? ¿Cómo resolveríais vosotros este problema?.Os pido ayuda y orientación. Gracias.

[endaramiz]

Hola no se si te servirá de mucho mi respuesta porque durante esta semana voy a ir bastante mal de tiempo por culta de los estudios. Yo estuve pensando algo así para un minigolf (pero aún no lo he implementado). Tuve la idea de dividir los polígonos en triángulos y así poder calcular si un punto (puede ser un vértice del cuadrado) está dentro de ese triángulo.
Lo siento pero no tengo más tiempo, esta semana es crucial para el resto del curso. Cuando la pase, con gusto te explico mi idea (que en teoría funciona, no la he probado) y escucho las de los demás a ver si entre todos encontramos la mejor manera.

Saludos.

[Bleed]

Muchas gracias por contestar, David.

No se me había ocurrido plantear así la solución, de todos modos, no me acaba quedado muy claro en que cosiste. Cuando tengas más tiempo, ya le echaremos un buen vistazo a tu algoritmo. Suerte con los exámenes y espero con ansia tu aportación.

¡Un saludo!

[hugoruscitti]

Saludos, creo que la idea de David puede funcionar muy bien. La idea
sería, según entiendo, verificar colisiones al momento de mover el
rectángulo. Las colisiones se verificarían entre las esquinas del
rectángulo y una serie de triángulos construidos con los polígonos
que nos muestras en las imágenes.

Partamos de tu gráfico inicial:



Como analizar el área de un polígono es una tarea difícil, la recomendación
de David nos puede servir: pensar el polígono como si se tratara de triángulos
pequeños:



Si bien juntos forman la figura, sería prudente almacenarlos en una estructura
que nos permita tratarlos por separado. Así, cuando queramos analizar la
superficie no importarán la cantidad de vértices, solo tendremos triángulos
y un cuadrado:




Ahora bien, imagina que comenzamos a desplazar el cuadrado por la pantalla
libremente; Si no detenemos su movimiento se pueden presentar dos
situaciones: que el cuadrado esté dentro o afuera del polígono original.

El movimiento simplemente tiene que permitir movimientos dentro del
polígono y prohibir movimientos fuera de él.

La condición que nos permite conocer, de manera sencilla, si el cuadrado
está dentro del triángulo son sus esquinas. Si está dentro del polígono, todas
sus esquinas están dentro de algún triángulo. En cambio bastará con que una de
sus esquinas esté fuera de un triángulo para considerar que el movimiento
es incorrecto:



Esto es similar a lo que ocurre en un juego de plataformas cuando quieres
controlar la caída de un personaje: solo tienes que realizar una prueba de
movimiento antes de desplazar el objeto, si el movimiento de prueba deja el
objeto dentro de la zona permitida confirmas el movimiento y en caso contrario
lo descartas.


Lamento no tener un ejemplo simple a mano, pero podría intentar escribir
uno (en python creo que sería mas ilustrativo). Tú, ¿que lenguaje estás
utilizando?.

Por cierto, he visto que existen funciones para determinar colisiones entre
puntos y triángulos. Si te parece buena la estrategia, podrías adaptar alguno
de estos para tu programa:

http://www.angelfire.com/fl/houseofbart ... e2tri.html
http://www.stratos-ad.com/forums3/viewtopic.php?t=10076

Un saludo grande.

[Bleed]

Gracias por contestar, Hugo. He estado ojeando el asunto de los triángulos y aunque parece una posible opción, la encuentro algo limitada (sólo permitiría definir regiones cerradas).

En un principio consideré el uso de líneas por la cantidad de posibilidades que estas ofrencen. Son muy flexibles ya que no sólo permiten definir polígonos. Quiero que echen un vistazo a este prototipo de RPG.

http://past.soywiz.com/web_game/

Como podréis ver, a base de líneas se ha implementado lo que os venía comentado. Cada línea (internamente creo que son rectángulos) se trata de forma individual y haciendo coincidir el inicio de una con el fin de otra, forman polígonos de formas extremadamente complejas. Por este mismo motivo, aunque el uso de triángulos pueda ser interesante, la potencia y quizás la sensillez de las líneas (he mirado por encima las clases que usa el RPG y no se extienden demasiado) puedan aportar un abanico de posibilidades.



A ver si este fin de semana puedo estudiar más a fondo el código Javascript del RPG y saco algo más en clave. Me da la sensación, que la solución está en combinar ambas técnicas y sobretodo aprovechar el tema de los triángulos para regiones cerradas.

Por cierto, en el ejemplo de la isla, añadí un pequeño lago para que también se tuviese en cuenta que cualquier parte del cuadrado fuese sensible a las colisiones.


Gif animado

PD: Mi idea es trabajar con Python y Pygame.

[hugoruscitti]

Es cierto, no había pensado que las lineas ofrecían tanta
versatilidad... el ejemplo web es muy interesante, sería bueno
tratar de hacer algo así, al menos como ejemplo.

Estuve buscando si existía alguna forma de hacer algo similar,
y en la página de pygame encontré funciones de utilidad para
buscar distancia entre un punto y una linea:

http://www.pygame.org/project/357/

con estas funciones busqué hacer un ejemplo mas simple, que
en lugar de mover un rectángulo sea un punto... pero bueno,
tendría que mejorarlo para que funcionen mejor las colisiones y,
si funciona bien, extenderlo a un rectángulo:



el programa muestra un punto rojo que se puede mover con el
teclado por toda la ventana, excepto cruzando lineas:

http://www.losersjuegos.com.ar/incoming ... eas.tar.gz

[endaramiz]

Perdón por olvidarme del tema.

En el caso de un minigolf se necesita trabajar con rectas matemáticas. Pero, en este caso, ¿no sería mejor trabajar con colisión por pixel? Igualmente, para poder dibujar el mapa podría ser necesaria una máscara de bits.
No puedo profundizar mucho en el tema porque me estoy iniciando en él. Aunque intentaré hacer algún ejemplo para dentro de unos cuantos días.

Respecto a lo de la triangulación, al ser un tema importante, hay bastantes algoritmos hechos.
Yo miraría si un punto está dentro de un triángulo. Dividiendo un triángulo en una recta y un vértice suelto. Y que compruebe si el punto está más cerca que el otro vértice. Esto se repetiría 2 veces más cogiendo la recta con vértices distintos.

¿Alguna idea mejor?¿Algún caso para el que mi idea no funciona?

Saludos.

[samu_dnet]

no se en pyton como funciona, pero no seria mas facil comprobar donde esta el cuadrado antes de mandarle la funcion de que se mueva?? por ej:

Código: Seleccionar todo

evento_teclapulsada(derecha)
{
      if (cuadrado_lateralderecho.x == punto_delalinea_en_X)
         {
                //no hacer nada
          }
       else
       {
            cuadrado.x += 1;
        }
}


lo mismo con la coordenada y.

No se en pyton como se manejan los cuadrados pero si por ejemplo la coordenada del cuadrado es igual al punto central de este, si por ejemplo el cuadrado hace 20 x 20, diriamos que cuadrado lateral derecho seria cuadrado +10.

[Juanxo]

Respecto a la sugerencia dada por david, no valdría el uso de triángulos en este caso, puesto que puede darse el caso de que no se cumpla.

He tratado de poner un ejemplo en la imagen, pero no se si se entenderá.

http://img135.imageshack.us/my.php?image=dibujoe.jpg

Intentar calcular(a ojo) las distancias entre la arista opuesta a un vertice y el punto, y esta será siempre menor que la distancia entre la arista opuesta y el vertice

[endaramiz]

Respecto a la sugerencia dada por david, no valdría el uso de triángulos en este caso, puesto que puede darse el caso de que no se cumpla.

Es verdad. No había tenido en cuenta ese caso. Intentaré buscar una solución algún día que tenga suficiente tiempo libre como para aburrirme.

¿A alguien se le ocurre alguna otra idea?

Saludos.

[Geo]

Perdón si no he entendido muy bien el tema, pero a primera vista, lo que yo haría sería usar colisión pixel a pixel de la siguiente forma:

- Primero verifico si hay colisión por rectángulo (bounding boxes), (basándome en la imagen que colocó Bleed donde define cada línea dentro de un rectángulo).
- Si hay colisión por rectángulo, entonces procedo a verificar por cada pixel que define la recta.

Hugo: no he podido ver las imágenes que colocaste.
Bleed: tampoco he podido acceder al RPG al que enlazas.

[endaramiz]

Gracias Hugo! He vuelto a revisar el código con detenimiento y me ha dado muy buenas ideas. Pude parecer que funciona mal, pero es porque se desplaza demasiado rápido el punto.

Lo de las rectas da mucho juego, pero respecto a lo de un punto en un triángulos, ya llevaba tiempo sin hacer una de mis publicaciones poco útiles así que allá voy:
Siguiendo la linea que llevaba, creo que se podría sacar, pero se complicaría demasiado. Me explicaron un método más sencillo para lograrlo:
Si tienes 3 puntos, A, B y P, donde A y B son 2 puntos de la recta, puedes saber si el punto P se encuentra a la "derecha" o a la "izquierda" (o justo encima) de la recta haciendo el determinante (simplificación para 2D del producto vectorial). Por ejemplo, si det((B-A), (P-A)) > 0: el punto está girando en sentido antihorario ("izquierda" si miramos de A a B) a partir de la recta.
Teniendo esto como base, si tenemos un triángulo A, B, C, y un punto P, si el punto P está en el mismo lado para AB, BC y CA, entonces el punto P está dentro del triángulo.

También hay otro método (habrán muchos...) que leí en este tutorial: http://nehe.gamedev.net/data/articles/a ... article=10


También me puse a investigar un poco sobre el tema de triangulación y al final conseguí resultados. El algoritmo consiste en saber si el polígono está dibujado de forma antihoraria o al revés, entonces se van cogiendo 3 puntos y con el método que he explicado antes, se mira si el punto del medio forma un ángulo agudo en el polígono, si tampoco hay ningún otro vértice en el triángulo que forman los 3 puntos, entonces se puede añadir a la lista de triángulos y borrar el vértice del medio.

Como mis explicaciones son bastante malas, os pongo el código:

Código: Seleccionar todo

#include <iostream>
#include <SDL/SDL.h>
#include <GL/gl.h>
#include <cmath>
#include <list>
using namespace std;


struct V {
    double x, y;
    V operator -(const V&) const;
};

struct T {
    V p1, p2, p3;
};

V V::operator-(const V& p2) const{
   V tmp = {x-p2.x, y-p2.y};
   return tmp;
}

double hyp(const V& p1, const V& p2) {
    return sqrt(pow(p1.x-p2.x,2.)+pow(p1.y-p2.y,2.));
}

int det(const V& p1, const V& p2) {
   return p1.x*p2.y-p1.y*p2.x;
}

bool p_in_triangle2(const V& p0, const V& p1, const V& p2, const V& p3) {
    int o1 = det(p2-p1, p0-p1);
    int o2 = det(p3-p2, p0-p2);
    int o3 = det(p1-p3, p0-p3);
   return((o1 > 0 and o2 > 0 and o3 > 0)
   or     (o1 < 0 and o2 < 0 and o3 < 0));
}

bool p_in_triangle1(const V& p0, const V& p1, const V& p2, const V& p3) {
    double a1 = hyp(p1, p2);
    double b1 = hyp(p1, p0);
    double c1 = hyp(p0, p2);
    double A1 = acos((pow(a1,2)-(pow(b1,2)+pow(c1,2)))/double(-2*b1*c1));

    double a2 = hyp(p3, p2);
    double b2 = hyp(p3, p0);
    double c2 = hyp(p0, p2);
    double A2 = acos((pow(a2,2)-(pow(b2,2)+pow(c2,2)))/double(-2*b2*c2));

    double a3 = hyp(p3, p1);
    double b3 = hyp(p3, p0);
    double c3 = hyp(p0, p1);
    double A3 = acos((pow(a3,2)-(pow(b3,2)+pow(c3,2)))/double(-2*b3*c3));

    return (A1+A2+A3) > 2*M_PI-(2*M_PI/1000.);
}

bool a_la_izq(const V& v1, const V& v2) {
    return det(v1, v2) > 0;
}

void triangular(std::list<V>& vertices, std::list<T>& triangles) {
   std::list<V>::iterator imax, ip;
   imax = ip = vertices.begin();
   while (ip != vertices.end()) {
      if (imax->y > ip->y) imax = ip;
      ++ip;
   }
   int max_x = imax->x;
   while (imax->x == max_x) {
      ++imax;
      if (imax == vertices.end())
         imax = vertices.begin();
   }
   bool clockwise = imax->x < max_x;

   std::list<V>::iterator iv1 = vertices.begin();
   std::list<V>::iterator iv2 = iv1; ++iv2;
   std::list<V>::iterator iv3 = iv2; ++iv3;
   while (vertices.size() > 3) {
       bool oreja = false;
       while (not oreja) {
           if ((a_la_izq(*iv2 - (*iv1), *iv3 - (*iv1)) and !clockwise) or
              (!a_la_izq(*iv2 - (*iv1), *iv3 - (*iv1)) and clockwise)) {
               std::list<V>::iterator ip = vertices.begin();
               oreja = true;
               while (oreja and ip != vertices.end()) {
                   if (p_in_triangle2(*ip, *iv1, *iv2, *iv3) and
                       ip != iv1 and ip != iv2 and ip != iv3) {
                       oreja = false;
                   }
                   else ++ip;
               }
           }
           if (not oreja) {
               ++iv1;
               if(iv1 == vertices.end()) iv1 = vertices.begin();
               ++iv2;
               if(iv2 == vertices.end()) iv2 = vertices.begin();
               ++iv3;
               if(iv3 == vertices.end()) iv3 = vertices.begin();
           }
       }
       T t = {*iv1, *iv2, *iv3};
       triangles.push_back(t);
       iv2 = vertices.erase(iv2);
       if(iv2 == vertices.end()) iv2 = vertices.begin();
       ++iv3;
       if(iv3 == vertices.end()) iv3 = vertices.begin();
   }
   T t = {*iv1, *iv2, *iv3};
   triangles.push_back(t);
}


void draw_vertices(std::list<V>& vertices) {
   glMatrixMode(GL_MODELVIEW);
   glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
   glLoadIdentity();
   glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
   std::list<V>::iterator it = vertices.begin();
   std::list<V>::iterator its = it;
   ++its;
   while (it != vertices.end() and its != vertices.end()) {
       glBegin(GL_LINES);
           glVertex2f((*it).x, (*it).y);
           glVertex2f((*its).x, (*its).y);
       glEnd();
       ++it;
       ++its;
   }
   glBegin(GL_LINES);
       glVertex2f((*(--vertices.end())).x, ((*(--vertices.end())).y));
       glVertex2f((*vertices.begin()).x, (*vertices.begin()).y);
   glEnd();
   SDL_GL_SwapBuffers();
}

void draw_triangles(std::list<T>& triangles) {
   glMatrixMode(GL_MODELVIEW);
   glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
   glLoadIdentity();
   std::list<T>::iterator it = triangles.begin();
   while (it != triangles.end()) {
       int x, y;
       SDL_GetMouseState(&x, &y);
       V p = {x, y};
       if (p_in_triangle2(p, (*it).p1, (*it).p2, (*it).p3))
           glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
       else
           glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
       glBegin(GL_TRIANGLES);
       glVertex2f((*it).p1.x, (*it).p1.y);
       glVertex2f((*it).p2.x, (*it).p2.y);
       glVertex2f((*it).p3.x, (*it).p3.y);
       ++it;
       glEnd();
   }
   SDL_GL_SwapBuffers();
}

void initGL() {
   glClearColor( 0.0f, 0.0f, 0.0f, 0.0f );
   glPointSize(3);
   glLineWidth(3);
   glMatrixMode(GL_PROJECTION);
   glLoadIdentity();
   glOrtho(0.0, 640.0, 480.0, 0.0, -1.0, 1.0);
}

int main() {
   if (SDL_Init(SDL_INIT_VIDEO) == -1)  cout << "no se ha iniciado SDL" << endl;
   
   SDL_Surface* screen = SDL_SetVideoMode(640, 480, 16,
      SDL_OPENGL | SDL_GL_DOUBLEBUFFER |
      SDL_HWPALETTE | SDL_HWSURFACE | SDL_HWACCEL);
   SDL_GL_SetAttribute(SDL_GL_RED_SIZE, 8);
   SDL_GL_SetAttribute(SDL_GL_GREEN_SIZE, 8);
   SDL_GL_SetAttribute(SDL_GL_BLUE_SIZE, 8);
   SDL_GL_SetAttribute(SDL_GL_DEPTH_SIZE, 24);
   SDL_GL_SetAttribute(SDL_GL_DOUBLEBUFFER, 1);
   
   if (screen == NULL) {
       cout << "No se ha iniciado la ventana OpenGL" << endl;
       return 0;
   }
   initGL();

   std::list<V> vertices;
   SDL_Event event;
   SDL_WaitEvent(&event);
   while (event.type != SDL_KEYDOWN) {
       SDL_WaitEvent(&event);
       if (event.type == SDL_MOUSEBUTTONDOWN) {
           int x, y;
           SDL_GetMouseState(&x, &y);
           V p = {x, y};
           vertices.push_back(p);
       }
       draw_vertices(vertices);
   }
   std::list<T> triangles;
   triangular(vertices, triangles);
   bool exit = false;
   
   while (not exit) {
      SDL_Event event;
      while (SDL_PollEvent(&event)) {
         switch (event.type) {
            case SDL_QUIT:
               exit = true;
            break;
            case SDL_KEYDOWN:
               if (event.key.keysym.sym == SDLK_ESCAPE)
                  exit = true;
            break;
         }
      }   
      draw_triangles(triangles);
   }
   SDL_Quit();
}


Se van poniendo vértices con el clic izquierdo y luego se pulsa una tecla.

Puede que la forma de utilizar OpenGL no sea la correcta, que estoy comenzando.

Saludos.