Otra pregunta de Novatos

[Jviruss]

Buenas!!!,
pues mi duda es la siguiente.Sobre la teoria de pathfinding e leido ya bastante,ademas no es la primera vez ke implemento un algoritmo de este tipo,pero mi problema esta en como se construye el el diagrama de nodos a partir de un mundo 3d.Por favor explikenme los pasos por ke no enkuentro documentacion.Entendieron mi pregunta????.

Supongamos ke mi mundo es:
0->nada
1->muro
2->roca

y la matriz del mundo es:

1,1,1,1,1,1,1,1
1,0,0,0,0,0,0,1
1,0,0,2,0,0,0,1
1,0,0,0,0,0,0,1
1,1,1,1,1,1,1,1

claramente asi ya podria aplicar un pathfinding pero komo paso de un mundo en 3d a una matriz de este tipo.Esta es mi pregunta,espero ke haya kedado klara.Muchas Gracias!!!!

[Daemon]

Hola,

primero decir que por aqui seguro que hay gente que tiene mas experiencia que yo en el tema de IA y 3D (o sea que lo que diga seguro que se puede mejorar).

Creo que para un algoritmo de pathfinding que el mapa sea en 2D o en 3D no deberia variar demasiado la forma en que se realiza la busqueda de caminos. Como tu bien has expuesto, para un algoritmo de este tipo la busqueda se puede realizar en una matriz, que se puede simplificar a que sea binaria, en donde las casillas libres se marcarian con 0 y las ocupadas con 1. Supongo que tu terreno en 3D sera una matriz de puntos en el espacio (x, y, z), junto con una lista de objetos que se tratan como obstaculos y que se representan como otra serie de puntos (x, y, z). Pues creo que pasar de esta representacion 3D a la matriz en 2D es sencillo, basta con que trates la matriz de terreno como espacios libres (a 0) o como mucho que consideres un limite de altura en donde no se puede pasar. Posteriormente  coges los obstaculos y cada punto (x, y) de los mismos se pone a 1 (sin importar z). Esta es una forma simple de pasar de un terreno 3D a una representación 2D, en donde la distancia entre nodos en la matriz 2D es la misma que entre los puntos del espacio 3D. Si quieres simplificar siempre puedes coger un nodo como una cuadricula de puntos 3D (y promediar las alturas para ver si el nodo se considera obstaculo o no).

Un problema que quizas se pueda presentar es que el archivo de terreno tenga "cuevas", es decir que haya varios caminos posibles en un mismo conjunto de (x, y) pero a alturas diferentes. Para solucionar esto bastaria con formar un grafo de nodos con las distintas matrices de alturas diferentes, etiquetando los arcos que dan a uno u otro camino con el z en el que comienzan.

Creo que puede ser una forma, espero que te sea util.


Un saludo.

[Warchief]

Depende del tipo de mapas que quieras usar (y tipo de juego).

Puedes construirlo mediante un grafo de nodos puestos en el editor de mapas, mediante nodos autocalculados a partir de objetos o información específica en el mapa, por floodfill a partir de un punto transitable (comprobando las direcciones en las que puede viajar un objeto que se encuentra en dicho punto), con trayectorias largas precalculadas y radios de libertad, simples colisiones estáticas.

No es necesario que sean tiles, aunque si quieres trabajar con tiles lo mejor en mi opinión sería el floodfill.

Opción 1)
Parte de un punto transitable (puedes ponerlo en el editor de mapas). Comprueba las 8/4/N direcciones en las que se puede mover mediante una esferea o cilindro de colisión (según personaje), si no hay colisión, puede pasar, si hay colisión ese camino A -> B y B -> A no son transitables.
Esto te da un mapa de tiles donde cada tile guarda la información de a qué vecinos se puede viajar desde él.

Opción 2)
Dispara un rayo de colisión (de radio el ancho del personaje) en el eje vertical sobre cada celda. Si hay colisión no es transitable, si no hay colisión es transitable.

Opción 3)
En vez de por colisión, si tienes acceso a los objetos del mapa (leyendo el mapa), puedes coger su bounding box (no alineada) y para cada celda que hay contenida en ella, si ciertos puntos entran dentro no es transitable. (Ciertos puntos = al menos 2 esquinas, al menos 2 esquinas y el centro, 3 esquinas, todos, etc; depende de la estrategia que quieras). Para saber si una celda está dentro, o mejor uno de sus puntos, puedes clasificar el punto en los 4 planos laterales de la bbox (asumiendo que los objetos están en el suelo obviamos las tapas). Si es el punto es interior a los N planos, está dentro. Si cumple la estrategia (N puntos dentro, ..) no es transitable.

En fin. Son algunas ideas, que pueden no ser las mejores, pero que funcionan. Ten en cuenta que es preprocesado, por lo que no tiene que ser extremadamente rápido. (Aunque si es extremadamente lento algún diseñador de mapas se quejará :))

[Jviruss]

Se agradecen 2 respuestas en menos de 24h.Muchas gracias.Me gusta la version de tirar el rayo hacia arriba pues la version del personaje me da la impresion de ke se podria kedar ataskado si pretendo andar por todo el mapa.

Ke me aconsejais como tamaño minimo de celda??,el del personaje,el del objeto mas pekeño colisionable del mapa.O quizas harias dos ficheros de colisiones,uno del tamaño del personaje  otro mas profundo del tamaño del objeto mas pequeño.Asi no perderia tanto tiempo kalkulando rutas,y si hay colisiones a tamaño mayor miro en el de mas precision.

Solicito mas respuestas,no se las callen!!!!

[fjfnaranjo]

Creo (en mi opinión, etc etc) que para tu caso mejor buscar otro algoritmo de pathfinding, que se base en nodos, áreas y grafos, como el de half-life >>> google

[Elthan]

Secundo lo dicho por Warchief.

En cuanto al numero de nodos te recomiendo q primero establezcas escalas en tus personajes: pequeños(gatos), medianos(hombre), grandes(ogros). Soy partidario de crear un mapa de nodos para cada tamaño ya q en escala un mapa para un duende tiene muchisimos más nodos q un hombre aunq la regla de oro es q un duende puede usar el mapa de un hombre, pero un gigante no. Hacer pasar a un gigante por una puerta normal es muy complicado....

En lo referente al tamaño de cada celda te recomiendo q uses el de el propio personaje con una salvedad; divide la celda en 9 nodos: 1 central más las 8 direcciones posibles. ¿Que para qué sirve esto? Cuando hagas un editor (o el propio modelo q uses de nivel) te darás cuenta que quizá haya paredes u obstaculos delgados o menudos pero intransitables. Eso lo tendría en cuenta.

Esto ultimo depende del realismo q kieras conseguir.

Te recomiendo que la matriz en la que guardes el mapa de nodos no guarda otra información más que la de pasar o no pasar. A lo sumo guardaría en ella el coste de desplazamiento en caso necesario.

Te recomiendo tb q le eches un vistazo a esto:
http://portalxuri.dyndns.org/darkbasico/descargas/descargasdbpro/tutoriales/ameba.zip
Es un tutorial sobre pathfinding muy sencillo que hice.

[Jviruss]

Nadie aporta mas????Ke pena no enkontrar respuestas hoy aki.Buahh!!!!