Mundo Maker
¡Bienvenid@ a Mundo Maker!

¿Quieres aprender todo sobre el RPG Maker?



Regístrate y forma parte de Mundo Maker.
Conectarse

Recuperar mi contraseña

Temas importantes
----------------------------------------
Páginas con recursos RPG Maker
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
----------------------------------------
Afiliados
Estadísticas
Tenemos 4191 miembros registrados.
El último usuario registrado es Victor Inkheart.

Nuestros miembros han publicado un total de 85160 mensajes en 12122 argumentos.

[IA en juegos] Ejemplo Path Finding

Ver el tema anterior Ver el tema siguiente Ir abajo

[IA en juegos] Ejemplo Path Finding

Mensaje por mrhawi el 2015-07-26, 18:31

Buenas a todos, ando un poco ocioso y es un día de lluvia, así que por hoy compartiré conocimiento (aunque quizás esté un poco trillado). Hablaré un poco de path finding, pero con una solución basada en problemas de búsqueda. Intentaré ser lo más breve y conciso posible.

El problema general es, qué secuencia de pasos debiese un agente seguir para llegar desde un lugar, un lugar objetivo. La idea es encontrar la secuencia de estados, que permitan al agente desde un estado inicial a un estado objetivo. Ahora un estado sería una representación del mundo en el cual está inmerso el agente. Claramente existe más de una representación para un problema determinado, pero la idea es tener una representación que requiera el mínimo número de componentes, para poder optar a una mejor eficiencia. Propondré dos ejemplos típicos, el puzzle de las 8 piezas y el problema del laberinto.




Pareciera ser que para un problema de búsqueda necesitamos un estado inicial y final; sin embargo falta algo. Para poder realizar acciones en el mundo, necesitamos definir un conjunto de operadores. Un ejemplo podría ser en el caso del puzzle de las 8 piezas: "mover las piezas adyacentes al espacio vacío". En el caso del laberinto, un ejemplo podría ser: "Avanzar un paso hacia adelante, rotar 90, o avanzar n, s, e, o". Continuando con la idea, cuando un agente aplica una acción, cambia el mundo en que lo rodea; Por ahora supondremos que solo el agente cambiará el entorno (No necesariamente es así), pero dependiendo de la acción tendremos diferentes resultados. Por ejemplo:



Tal "árbol" de estado, o espacio de búsqueda se va generando a medida que el agente busca un camino hacia su objetivo.

La pregunta que salta ahora es ¿cómo buscar? Dejo el pseudo-código del algoritmo de búsqueda:

function TreeSearch(problema, estrategia) returns una solución, o falla
----inicializar el árbol de búsqueda utilizando el estado inicial del problema
----loop do
--------if no se puede expandir el nodo actual then return failure
--------escoger un nodo para la expansión de acuerdo a la estrategia
--------if el nodo contiene un estado objetivo then return la solución correspondiente
--------else expandir el nodo y agregar los nodos sucesores al árbol de búsqueda
----end

Hasta ahora hemos definido el problema, pero no la estrategia. La estrategia será la forma en que expandiremos los nodos del árbol, en otras palabras, las acciones que el agente tomará para realizar la búsqueda. A pesar de que existen muchas estrategias para ello, sólo mencionaré las típicas:

Depth First Search::

Busca en en profunidad, es decir, llega hasta el fondo y luego retrocede para explorar estados que no se hayan visitado.

Spoiler:

Básicamente utiliza una estructura de datos tipo LIFO (Ultimo en entrar, primero en salir => stack, o pila). Donde la operación push, inserta un elemento, y pop retorna el último elemento insertado.

- Costo en memoria lineal.
- No es completo (puede estancarse en loops)
- No es óptimo (No encontrará el "camino más corto")

Breadth First Search:

Busca por anchura, primero prueba todas las acciones posibles y luego baja al siguiente nivel.

Spoiler:

Utiliza una estructura tipo FIFO (primero en entrar, primero en salir => queue, fila, cola)

- Costo en memoria exponencial.
- Completo
- Óptimo si el costo de cada camino es constante.

Uniform Cost Search:
Es un equivalente al algoritmo Dijkstra. Básicamente explora de acuerdo al costo del camino, teniendo conocimiento de las acciones "anteriores", por ejemplo:

Spoiler:

La estructura de datos a utilizar se conoce como priority queue, que básicamente extrae el mínimo o máximo elemento dentro de la estructura (acá para "medir" cada elemento, se utilizaría el costo actual para llegar a tal estado). Existe una implementación que permite inserción en tiempo constante y extracción en tiempo proporcional a n (número de elementos). Sin embargo, se utilizan operaciones sink y swim para obtener tiempos proporcionales al log(n) en inserción y extracción (y así una mejor eficiencia). Hay varias implementaciones y se puede buscar en internet.

- Es óptimo
- Costo en memoria exponencial.
- Si el costo es constante, se comporta como breadth first search (es equivalente)

A* (A estrella, A star):

La idea es similar a Uniform Cost Search, pero además se tiene "información". Se realiza una "estimación" de cuánto falta para llegar al objetivo, por ejemplo en el caso del laberinto se puede utilizar como estimación la distancia en "tiles" (distancia manhattan) desde la posición actual hasta el objetivo:

distancia = abs(y1 - y0) + abs(x1 - x0)

O también la distancia euclideana

distancia = sqrt((y1 - y0)^2 + (x1 - x0)^2)

Y también se utiliza el conocimiento de las movidas anteriores, esquemáticamente sería así:

Spoiler:

En palabras simples es utilizar información del pasado y una estimación del futuro para poder descartar acciones y tomar "mejores decisiones". También se utiliza una priority queue, que evalúa f(n) = h(n) + g(n) que no es más que la estimación desde el nodo actual y el costo para llegar desde el inicio al nodo actual.

- Es completo
- Es óptimo sí y sólo sí la heurística es admisible y consistente.
Admisibilidad en términos básicos es que la heurística nunca sobre-estima el costo para llegar al objetivo más cercano desde el nodo actual. Es decir 0 <= h(n) <= h*(n).
Consistencia, es que la "distancia" medida desde dos heurísticas entre nodos es menor o igual que el costo de viajar desde un nodo a un nodo adyacente, es decir h(actual) <= costo(actual, siguiente) + h(siguiente).

- Ventajas sobre Uniform Cost Search: Converge más rápido, expande menos nodos en la búsqueda porque toma "mejores decisiones".

Existen otros algoritmos que utilizan estrategias de programación dinámica (Floyd Warshall), pero se deja al lector investigar sobre eso.

NOTA: Se puede mejorar la eficiencia de los métodos descartando estados repetidos. Esto se puede hacer mediante SET, o utilizando tablas hash (pero debiese hacerse un override a los métodos equals y hash o hashCode para que sea adaptable al lenguaje en cuestión, podrá variar el nombre...).

Finalmente dejo un ejemplo de cómo funciona cada método (una implementación que hice):



Saludos.


Última edición por mrhawi el 2015-07-27, 19:31, editado 1 vez

mrhawi
Aventurero
Aventurero

0/3

Créditos 2668

Gracias : 89

Volver arriba Ir abajo

Re: [IA en juegos] Ejemplo Path Finding

Mensaje por orochii el 2015-07-27, 16:48

Desde que conocí un script que lo utilizaba, he sido fiel al A* sin siquiera saber cómo diantres funcionaba xD!. Tan sólo leía A* Pathfinding script y lo mandaba al saco de cosas para usar. Pero pues ahora veo que, exceptuando el DFS que sí que hace caminos muy tontos (pero podría valer para inteligencias tontas xD), las demás funcionan bastante bien.

Igual el A* tiene mejor rendimiento que el UCS y el BFS, ¿no?

Nunca pensé en implementar un pathfinding, pero creo que ya me estoy sintiendo mínimamente más motivado, xD.
avatar
orochii
Caballero Shiro
Caballero Shiro

0/3

Créditos 6680

Gracias : 337

Volver arriba Ir abajo

Re: [IA en juegos] Ejemplo Path Finding

Mensaje por mrhawi el 2015-07-27, 16:58

orochii escribió:Desde que conocí un script que lo utilizaba, he sido fiel al A* sin siquiera saber cómo diantres funcionaba xD!. Tan sólo leía A* Pathfinding script y lo mandaba al saco de cosas para usar. Pero pues ahora veo que, exceptuando el DFS que sí que hace caminos muy tontos (pero podría valer para inteligencias tontas xD), las demás funcionan bastante bien.

Igual el A* tiene mejor rendimiento que el UCS y el BFS, ¿no?

Nunca pensé en implementar un pathfinding, pero creo que ya me estoy sintiendo mínimamente más motivado, xD.

Exacto, o sea depende. Si utilizas A* tienes que utilizar una heurística admisible, pero para el path-finding usar la distancia manhattan que es admisible y consistente te asegura encontrar el óptimo. La otra ventaja de A* es que como toma "mejores" decisiones en la búsqueda expandes menos nodos y eso hace que tenga una mejor eficiencia. Un problema de A* es encontrar la heurística admisible, idealmente si tuvieses una "heurística perfecta" expanderías la menor cantidad de nodos que te lleven al óptimo global (Cosa que no ocurre con DFS, BFS). UCS es un caso particular de A*, si utilizas A* con una heurística trivial, es decir h(n) = 0 para cualquier nodo, entonces sería UCS. Pero esta es la regla de oro, mientras más cerca esté tu heurística del ideal (estimar el costo real del camino para llegar al objetivo más cercano), expandes menos nodos. SI estás mas cerca del 0, expandes más nodos, por eso mejor A*. La implementación es relativamente sencilla, lo que sí, debieses intentar usar un "set cerrado" (tipica estructura de datos que es como un array que no permite elementos repetidos) y un priority queue para la expansión; pero hay varias implementaciones en internet. Esto lo digo, porque una mala implementación puede llevar a que el algoritmo demore más de lo que debiese (Aparte pasar por "estados repetidos" es contraproducente xD).

Quizás me animo y escribo otro tutorial para inteligencia de grupos de "agentes".

Anímate e implementalo, ya me cuentas qué sale, saludos!

mrhawi
Aventurero
Aventurero

0/3

Créditos 2668

Gracias : 89

Volver arriba Ir abajo

Re: [IA en juegos] Ejemplo Path Finding

Mensaje por Contenido patrocinado


Contenido patrocinado


Volver arriba Ir abajo

Ver el tema anterior Ver el tema siguiente Volver arriba


Permisos de este foro:
No puedes responder a temas en este foro.