Algoritmo persecución?

Consulte acerca de programas, técnicas, algoritmos etc.

Algoritmo persecución?

Notapor Nathaniel » Mié Jul 28, 2010 11:05 am

Estoy realizando un juego de coches con el engine de Hugo y no acabo de dar con la forma de hacer que un coche persiga a otro. En una dimension es muy sencillo, el problema me sale al aplicar las dos dimensiones y los angulos.

Aquí el código importante, si alguien lo quiere entero y con las imágenes que lo diga:

Código: Seleccionar todo
class Car2(pygame.sprite.Sprite):
   def __init__(self):
      pygame.sprite.Sprite.__init__(self)
      self.original_image = pygame.image.load("ima/Car2.png")
      self.rect = self.original_image.get_rect()
      self.x,self.y = 692,345
      self.angle = 180
      self.velocity = 0
      
   def update(self):
      if Coche.rect.x > self.rect.x:
         self.mov(-1)
      elif Coche.rect.x < self.rect.x:      
         self.mov(1)
      #Aquí faltaría la otra parte del codigo   
         
      angle = radians(self.angle)
      self.dx = cos(angle) * self.velocity
      self.dy = sin(angle) * self.velocity
      
      self.update_image()
      self.update_position()
      self.check_limits()
      
      
   def mov(self,sentido):
      self.velocity += ACCEL * sentido
      if self.velocity > MAX_SPEED:
         self.velocity = MAX_SPEED
      elif self.velocity < -MAX_SPEED:
         self.velocity = -MAX_SPEED
         
   def update_image(self):
      self.image = pygame.transform.rotate(self.original_image, -self.angle)
      self.rect.w = self.image.get_width()
      self.rect.h = self.image.get_height()
      
   def update_position(self):
      self.rect.x = int(self.x) - self.rect.w / 2
      self.rect.y = int(self.y) - self.rect.h / 2
      self.x += self.dx
      self.y += self.dy
      
      screen.blit(self.image,self.rect)


Este es el coche persecusor, el otro está en otra clase inicializada por la variable Coche (Coche.rect.x por ejemplo) y la estructura es muy parecida a este asi que no hace falta que lo añada. Si a alguien se le ocurre algo..
Gracias :)
Nathaniel
 
Mensajes: 8
Registrado: Sab Feb 14, 2009 8:00 pm

Re: Algoritmo persecución?

Notapor endaramiz » Mié Jul 28, 2010 11:42 am

El coche básico gira a la izquierda cuando pulsas la tecla izquierda y lo mismo para la derecha. En el nuevo coche solo tienes que modificar la condición para moverse. Un algoritmo muy sencillo (con resultados no muy buenos) es girar a la izquierda si el coche a perseguir está a la izquierda y a la derecha en caso contrario. Donde, a la derecha, me refiero a la derecha de la trayectoria (a partir del vector velocidad y la posición).
Para hacer este cálculo, solamente tienes que hacer el determinante del vector (posición del perseguido - posición del perseguidor) y del vector velocidad del perseguidor. Si el coche perseguido está a la izquierda este determinante dará positivo, si está a la derecha, negativo y si está ya en su trayectoria, 0.

Lo hago de cabeza, espero no haberme equivocado en algo.

Saludos.
Avatar de Usuario
endaramiz
 
Mensajes: 283
Registrado: Vie Ago 31, 2007 9:25 am
Ubicación: Barcelona

Re: Algoritmo persecución?

Notapor carlostex » Mié Jul 28, 2010 11:12 pm

Hola, se me ocurre algo pero no se si es lo que estes buscando, pues la solucion es muy simple, tal ves como nosotros buscamos algo.
Pues solo es calcular el angulo que hay entre los dos coches y le aplicas un vector velocidad con el angulo que obtuviste eso producira que se hacerque el coche el linea recta, si calculas ese vector en cada bucle del juego, el vector se actualizará y generará un movimientos curvo, pues cada vez el angulo va cambiando, y te aseguras que siempre lo siga a donde tu lo muevas.

endaramiz escribió:Para hacer este cálculo, solamente tienes que hacer el determinante del vector (posición del perseguido - posición del perseguidor)


No se si te referias al determinate de las matematicas, pero yo solo conosco uno, y solo se puede aplicar a matrizes que sean cuadradas.Solo lo aclaro, no es que me haga al sabiondo jaja, pero lo mensiono para no tener informacion incorrecta aun que no nos afecte en mucho
El conocimiento de unos es conocimiento de todos.
Avatar de Usuario
carlostex
 
Mensajes: 249
Registrado: Mar Jul 14, 2009 4:13 am
Ubicación: mexico

Re: Algoritmo persecución?

Notapor endaramiz » Mié Jul 28, 2010 11:53 pm

carlostex escribió:Hola, se me ocurre algo pero no se si es lo que estes buscando, pues la solucion es muy simple, tal ves como nosotros buscamos algo.
Pues solo es calcular el angulo que hay entre los dos coches y le aplicas un vector velocidad con el angulo que obtuviste eso producira que se hacerque el coche el linea recta, si calculas ese vector en cada bucle del juego, el vector se actualizará y generará un movimientos curvo, pues cada vez el angulo va cambiando, y te aseguras que siempre lo siga a donde tu lo muevas.
Esto provoca un comportamiento irreal en el coche. Con lo que comentas, un coche podría llegar a girar 180º en un solo frame. Aunque si en vez de un coche, fuese una nave espacial o algo de eso, pues se podría hacer cualquier cosas sin que quede demasiado irreal.

carlostex escribió:
endaramiz escribió:Para hacer este cálculo, solamente tienes que hacer el determinante del vector (posición del perseguido - posición del perseguidor)


No se si te referias al determinate de las matematicas, pero yo solo conosco uno, y solo se puede aplicar a matrizes que sean cuadradas.Solo lo aclaro, no es que me haga al sabiondo jaja, pero lo mensiono para no tener informacion incorrecta aun que no nos afecte en mucho
Has dejado media frase sin citar. Quizás me he expresado mal, aunque pensé que se entendería ya que, como dices, los determinantes se hacen en matrices cuadradas. La matriz se forma a partir de los dos vectores:
- (posición del perseguido - posición del perseguidor)
- vector velocidad del perseguidor
Como estamos en 2D, los vectores tienen 2 valores (x e y). Así que queda una matriz 2x2, cuadrada, y se puede hacer el determinante sin problemas.

Saludos.
Avatar de Usuario
endaramiz
 
Mensajes: 283
Registrado: Vie Ago 31, 2007 9:25 am
Ubicación: Barcelona

Re: Algoritmo persecución?

Notapor carlostex » Jue Jul 29, 2010 3:53 am

ha claro, esque entendi mal, pense que el signo "-" era de resta, pero veo que es de guión.
Eso que puse tampoco lo he provado, siento que si funcionaria, lo que comentas solo pasaria cuando empieza el juego, pues el coche perseguidor empezara en un angulo cualquiera, y se ajustara al angulo para llegar al otro coche, si embargo, mientras el otro coche se este moviendo, el perseguidor se ira ajustando poco a poco. Pero mejor lo pruebo para saber si de verdad funciona, y subo un video.
El conocimiento de unos es conocimiento de todos.
Avatar de Usuario
carlostex
 
Mensajes: 249
Registrado: Mar Jul 14, 2009 4:13 am
Ubicación: mexico

Re: Algoritmo persecución?

Notapor Nathaniel » Jue Jul 29, 2010 2:11 pm

Gracias por las ideas, las pruebo y os cuento!
Nathaniel
 
Mensajes: 8
Registrado: Sab Feb 14, 2009 8:00 pm

Re: Algoritmo persecución?

Notapor carlostex » Vie Jul 30, 2010 2:03 am

Hola, pues te traigo lo prometido, Segui la idea que havia propuesto, creo que quedo bien, no se si querias un movimiento asi.Pero te dejo el video para que lo veas, http://www.youtube.com/watch?v=2LDH0p1XURg, esta en baja la calidad por que el archivo en alta es demaciado grande.

pues hay va como lo hice. primero el codigo:
Código: Seleccionar todo
#include<game.h>
#include<math.h>

bool nearmodul(float a, float b, float range)
{
    if(a<b)
    {
        return ((b-a)<a+(range-b));
   
    }
    else
    {
        return ((a-b)>(b+(range-a)));

    }

}

int main()
{

    game g;
    g.init_video(800,600,32);

g.scene.set_world("../images/terreno/path");
g.scene.add_sprite("../images/E-P8.854.png",1);



g.scene.add_actor(0,true,true);
g.scene.add_actor(0,true,true);
g.scene.set_posicion_actor(0,punto(300,200));
g.scene.set_posicion_actor(1,punto(200,350));

g.scene.set_actor_p_refer(0,punto(20,20));
g.scene.set_actor_p_refer(1,punto(20,20));
g.scene.entity_manager.actores[0]->object.add_punto(punto(7,3));
g.scene.entity_manager.actores[0]->object.add_punto(punto(29,2));
g.scene.entity_manager.actores[0]->object.add_punto(punto(29,12));
g.scene.entity_manager.actores[0]->object.add_punto(punto(37,13));
g.scene.entity_manager.actores[0]->object.add_punto(punto(37,27));
g.scene.entity_manager.actores[0]->object.add_punto(punto(30,28));
g.scene.entity_manager.actores[0]->object.add_punto(punto(29,37));
g.scene.entity_manager.actores[0]->object.add_punto(punto(7,37));
g.scene.entity_manager.actores[0]->object.add_punto(punto(7,3));
g.scene.entity_manager.actores[1]->object=g.scene.entity_manager.actores[0]->object;
bool done = true;
evento ev;
g.fps1=40;
int vel=0, ang=0,vel_p=0;
int cont=0;
punto scroll(0,0);
float angulo_p=0,retardo=0, angulo_parado=0;


while (done) {

    ev.poll();
    ev.get_states_key();

    if(cont%3==0)
    {
       
        angulo_p=360-angulo_2point(g.scene.entity_manager.actores[0]->get_posicion().neg(),g.scene.entity_manager.actores[1]->get_posicion().neg());
        if(vel_p==30)
        {
            if(abs(retardo-angulo_p)>1.5){
            if(nearmodul(retardo,angulo_p,360))
            {
                retardo+=3;
                if(retardo>360)retardo=0;


            }else
            {
                retardo-=3;
                if(retardo<0)retardo=360;

            }
            }
        }
   
    }

    if (ev.test_state(SDLK_q)==true) done=false;
    if (ev.test_state(SDLK_UP)==true) vel=60;
    if (ev.test_state(SDLK_DOWN)==true) vel=-60;

    if (ev.test_state(SDLK_w)==true)scroll.y-=1;
    if (ev.test_state(SDLK_s)==true)scroll.y+=1;
    if (ev.test_state(SDLK_a)==true)scroll.x-=1;
    if (ev.test_state(SDLK_d)==true)scroll.x+=1;
    if(cont%5==0){
        if (ev.test_state(SDLK_LEFT)==true) ang+=4;
        if (ev.test_state(SDLK_RIGHT)==true) ang-=4;
        if (ev.test_state(SDLK_f)==true)
    {

        if(vel_p==0) {vel_p=30;retardo=angulo_parado;}
        else {vel_p=0;angulo_parado=angulo_p;}

    }

    }
    system("clear");
    cout<<"Seek Behaivor\nF para activar desactivar perseguir"<<endl;
    cout<<"Angulo entre los dos: "<< angulo_p<<"\nAngulo que se ajusta: "<<retardo<<endl;
    g.scene.set_scroll_mapa(scroll);
    g.scene.set_actor_vel(0,Vector(vel,ang));
    g.scene.set_actor_vel(1,Vector(vel_p,vel_p?retardo:angulo_parado));
   
    vel=0;
    g.render();
    g.time();
    cont++;
}


}


pues la función nearmodul(float, float, float) evalua cual es la direccion mas corta para llegar a un numero que quiero, dentro de un rango de numeros, los cuales son como una lista circular, por ejemplo:

1,2,3,4,5,6,7,8,9
Si parto del 2 y quiero llegar al 8 es mas rapido recorrer 2,1,9,8 que 2,3,4,5,6,7,8
Esta funcion la uso para saber si debo sumar o restar una constante a retardo, cuado retardo es menor a 0 regresa a 360.
Esa comprobacion la hago solo cuando la diferencia entre los dos angulos es menor a 1.5, par que no se este tambalenado.
y el coche perseguidor lo muevo el angulo que lleva retardo, en esencia es llevar la variable retardo al valor del angulo entre los dos actores.

esta implementacion la hice con un motor de juegos propio, pero la parte importante es esta.

Ha lo que hace el coche perseguidor se le conoce como comportamientos, existen bibliotecas hechas para esta tarea, la unica que conozco es opensteer, pues creo que los desarrolladores crean sus propias funciones para manejar los comportamientos.y mi idea la tome de la forma en la que funcionan.
A cada actor se le puede agregar un comportamiento, en este caso seguir, pero que tal si quiero que varios coches lo sigan, para empezar debo evitar que los coche choquen entre ellos, lo cual es otro comportamiento, mantener una distancia, la funcion que realiza el comportamiento solo devuelve un vector,luego se la pasa a una funcion que priorise esos movimientos, para que el resultado sea, que sigua el coche, pero si alguno se hacerca demaciado se elejen sin perder el obejetivo principal que es seguir al coche.
Es muy interesante, el problema es que opensteer no tiene documentación y tampoco pude compilar sus fuentes y ejemplos, sin emvargo no es algo dificil de hacer, aver si alguien se une y hacemos una biblioteca de funciones para comportamientos
El conocimiento de unos es conocimiento de todos.
Avatar de Usuario
carlostex
 
Mensajes: 249
Registrado: Mar Jul 14, 2009 4:13 am
Ubicación: mexico

Re: Algoritmo persecución?

Notapor Juanxo » Vie Jul 30, 2010 10:46 am

una pequeña optimizacion ( sobre todo a nivel visual) y que es más natural para el ser humano es predecir donde estará el coche.

Sería algo así:

Código: Seleccionar todo
    pos_siguiente = pos_actual + (velocidad * numero_de_segundos_que_predecimos)


y pasaríamos a perseguir dicha posición
Avatar de Usuario
Juanxo
 
Mensajes: 437
Registrado: Sab Ene 31, 2009 2:34 am
Ubicación: Madrid(España)


Volver a General

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 2 invitados

cron