Pathfinding

[Sacrifai]

 Una duda que he tenido siempre, es como se lo montan para hacer pathfinding en juegos con escenarios grandes como starcraft (aunque no es un buen ejemplo de pathfinding) o cualquier otro juego de estrategia. ¿ Todo el escenario está lleno de nodos o se crean en tiempo real los nodos ?

[TheAzazel]

 Basicamente, en todos los juegos de hoy en dia (ya sean 2D o 3D) la busqueda de rutas se calcula utilizando un algoritmo que es la caña: el A*.
Has puesto de ejemplo el starcraft...pues bien, ese tenia mapas de hasta 256x256 posiciones, a parte de tener un monton de bichos en pantalla, todos pidiendo rutas, recalculandolas....etc... no hubieran podido moverlo las CPU de aquel tiempo... pero, existen un monton de optimizaciones al A* que vale, no te da la ruta mas mas optima pero te da una que vale y muy rapidamente, amen de subdivivir el mapa en sectores mas pequeños, utilizar rutas precalculadas, te recomiendo esta pagina que es la mejor de todas en estas cosas:

http://www-cs-students.stanford.edu/~amitp...p/gameprog.html

cualquier duda...tirala por aki, un saludo

[Sacrifai]

 Muchas gracias por el link, estoy echandole un ojo. ¿Este sistema tambien es adecuado para aventuras gráficas?

[nsL]

 Un link que me dieron acerca de A* y en estos foro creo recordar es este

El cual te explica muy bien como usarlo y para que vale, ademas tb lo hay en español en la misma web via link :P

Saludos!  B)

[senior wapo]

 

Muchas gracias por el link, estoy echandole un ojo. ¿Este sistema tambien es adecuado para aventuras gráficas?

Si, solo que en vez de dividir el mapa en una rejilla de casillas cuadradas, el mapa es un grafo de poligonos convexos (similar al concepto de "sectores" en los mapas de DOOM1). Los polígonos no se dibujan, representan las areas donde puedes "pisar". Las implicaicones para A* son que cada nodo puede tener un numero arbitrario de vecinos.

Cada arista (segmento) de cada polígono tiene un puntero a cada uno de los 2 poligonos que usan esa arista. Técnicamente se le llama winged-edge structure (si, como la usada por Wings3D) o si eres menos pijo, un grafo de toda la vida (cada poly=nodo, cada arista=flecha del grafo).

Imagen y mapa poligonal extraidos de la demo jugable de Indiana Jones and the Fate of Atlantis, con el fin de cita académica. Copyright© LucasArts:


El workflow viene a ser:
1- Artista dibuja el escenario.
2 - Mapeador traza sobre esa imagen los poligonos 2D  (puedes ser 3D pero cambia un poco el tema) que representan el "suelo", las secciones donde el personaje puede estar de pie. Se le asigna a cada poligono un factor de escala (que luego se interpolará) para los personajes situados en dicho poligono (fingir acercamiento/alejamiento, puntos de fuga, etc...). La imagen no se modifica, y la geometría 2D de los poligonos se guarda aparte, con su conectividad.
3. Durante el juego cuando pulsas sobre una parte de la pantalla, localizas el poligono que la contiene, y de existir, usas un algoritmo de busqueda de caminos (A*, dijkstra, lo ke sea) para saber cual es el siguiente poligono al que debes moverte. La lista de aristas del poligono actual del personaje te indica que polígonos son vecinos.

Por cierto, una generalización 3D de este mapa de suelos se usa en juegos 3D para agilizar las colisiones, pero ya me desvio del tema...

Si quieres más infomación te recomiendo que mires el SCUMM Revisited y toda la ristra de proyectos que hay referentes al engine de Lucasfilm. También los de Sierra online (AGI de Sierra, es un sistema viejo sin pathfinding, pero las colisiones las implementaban con polígonos también, solo que los contornos representaban las áreas donde NO puedes pisar).

ScummVM
LucasHack!

[ethernet]

 una implementación que hice hace tiempo para un proyecto que, como todos los que he empezado, está en la carpeta fracasos.

Código [Seleccionar] Expand




typedef Vector2i PathNode;
typedef std::list<PathNode> Path;

class IPath
{
public:
 virtual bool GetPath(PathNode &ini,PathNode &end,Path &path) = 0;
};

class AStar : public IPath
{
public:


public:

enum ePathInfo
{
 PATH_INCOMPLETE,
 PATH_COMPLETE,
 PATH_NO_PATH

};

AStar(Map *_m):
m(_m)
{}

bool GetPath(PathNode &ini,PathNode &end,Path &p)
{
 path = &p;
 if(CalculePath(ini,end) != PATH_INCOMPLETE)
 {
  return false;
 }
 return true;  

}


protected:
Map *m;
struct Node
{
 Node(Vector2i &p,int _g = 0):
 g(_g),
 pos(p)
 {  
 }
 Vector2i pos;
 Node *parent;  
 float f,g,h;
 float calc_dist(Vector2i &dest)
 {
  //Vector2i v = dest-pos;
  h = fabs(dest[0]-pos[0]) + fabs(dest[1]-pos[1]);
  //h = vectorDist(Vector2f(v[0],v[1]));
  f = g + h;
  return f;
 }
 float weith()
 {
  f = g + h;
  return f;
 }

 
 struct compare
 {
 
  bool operator()(Node*& u, Node*& v)
  {
   if(u->weith() > v->weith())
    return true; //para que open.Top sea el menor
   return false;
  }
 };
 


};

typedef std::list<Node*> NodeList;
std::list<Node*> close;
Path *path;
std::priority_queue<Node*,std::vector<Node*>,Node::compare> open;

Node *root;
ePathInfo CalculePath(Vector2i& ini,Vector2i& fin)
{
 int max = 0;
 Node *min;
 root = new Node(ini);
 root->calc_dist(fin);
 root->parent = 0;
 open.push(root);
 debuglog << "calculando path "<< endl;


//  assert()
 while(max++ < 1000)
 {
  min = GetBest();
 
  if(!min)
  {
   debuglog << "caminante, no hay camino" << endl;
   return PATH_NO_PATH;
  }
  if(min->pos == fin)
  {
   BuildPath(min);
   return PATH_INCOMPLETE;
  }
  CreateChild(min,fin);  
 
  close.push_back(min);  

 }
 BuildPath(min);
 return PATH_COMPLETE;

}
void FreeMemory()
{
 while(!open.empty())
 {
  delete open.top();
  open.pop();
 }
 std::list<Node*>::iterator i = close.begin();
 for(;i!= close.end(); ++i)
 {
  delete  *i;  
 }
 close.clear();

}
Node *GetBest()
{
 if(open.empty())
 {
  return 0;
 }
 Node *n = open.top();
 assert(n);
 open.pop();
 if(!open.empty())
  while(n->pos == open.top()->pos) open.pop();
 return n;
}
void BuildPath(Node *d)
{
 path->push_front(d->pos);
 while(d->parent != root )
 {
  path->push_front(d->parent->pos);
  d = d->parent;
 }
 path->push_front(d->parent->pos);
 FreeMemory();

}
Node* SearchInNodes(Vector2i &n)
{
 std::list<Node*>::iterator i = close.begin();
 for(;i!= close.end(); ++i)
 {
  if((*i)->pos == n)
  {
    return *i;
  }
 }
 return 0;
}
void CreateChild(Node* min,Vector2i &dest)
{
 
 int v[8]= {1,0,-1,0 ,
      0,1,0,-1};
 Tile *t;
 Node *n;  
 for (int i = 0; i< 4;++i )
 {
  t = m->GetTile(min->pos[0]+v[i],min->pos[1]+v[i+4]);
  assert(t);  
  if(t && !t->IsSolid())
  {
   Vector2i v(min->pos[0]+v[i],min->pos[1]+v[i+4]);
  // debuglog << "[" << v[0] << ","<< v[1]<< "]" << endl;
   if(!SearchInNodes(v))
   {
    n = new Node(v);
    assert(n);
    n->parent = min;
    n->g = 1;
    //if(n->pos == dest) return n;
    n->calc_dist(dest);
    open.push(n);
   }
  }
 
 }  
 
}
};



[Sacrifai]

 Muchas por las respuestas. Por cierto, senior wapo, según el metodo que me comentas, a no se que lo haya captado mal, no habria mucha precisión ¿no?
Estoy echandole un ojo al scumm porque puedo sacar cosas muy interesantes de él.

[senior wapo]

 

Muchas por las respuestas. Por cierto, senior wapo, según el metodo que me comentas, a no se que lo haya captado mal, no habria mucha precisión ¿no?
Estoy echandole un ojo al scumm porque puedo sacar cosas muy interesantes de él.

¿ A que te refieres con precisión ?

- Si te refieres a que los polígonos solo representan una aproximación de los bordes del suelo, es cierto. Dichos juegos no tenían mucha precisión a la hora de pegar el personaje a superficies curvas. Tendrías que usar mucho polígonos o recurrir a trucos. No me voy a extender en este post, pero hay maneras muy eficientes (computacionalmente) de hacerlo, parecidas a un span buffer calculado sobre una máscara de bits similar a las de transparecia de sprites, pero para elementos de fondo (que lo lio explicandolo! xD).  Los artistas a lo mejor te maldicen, eso si  :D

- Si con precisión te refieres al escalado del personaje con la distancia, pues, depende. Eran juegos de la época 16 bits, casi siempre sin procesador matemático, pero hoy en dia puedes usar poligonos 3D, o simplemente asignar a mano una Z por vértice si los fondos son ilustraciones, o guardar el bufferZ (estilo resident evil) si son renders. En el primer caso el personaje lo escalas interpolando sus coordenadas baricéntricas en el polígono con los valores Z de los vértices. Eso te da la coordenada Z del personaje y la usas para escalar. Con el segundo método, el buffer Z, simplemente la recuperas del valor del bufferZ en el pixel correspondiente al centro de los pies del personaje. Sacas la inversa (1/z) y con un par de ajustes tienes el factor de escala del personaje (o guardas el bufferZ ya "precocinado").

¿ Me estoy enrollando demasiado ?  O_O

PD: Algun hosting bueno y gratis de imagenes? Tengo que darle a boton derecho/mostrar imagen para que salgan mi avatar y la imagen que he pegado antes.

[Sacrifai]

 En fin, usare el metodo de los polys.

El mejor host de imagenes que conozco:
http://www.imageshack.us/