Pathfinding

El Pathfinding consiste básicamente en encontrar un camino esquivando los obstáculos que puedan interponerse. Existen varios algoritmos que encuentran un camino. El de Dijkstra, el A* y el BFS son sólo algunos de los más importantes; siendo el A* el que obtiene el resultado óptimo en la menor cantidad de tiempo.

Pero, es bastante complicado. Por lo que estuve trabajando en un algoritmo distinto que fuera más fácil de entender.

Básicamente, tenemos un área con distintos nodos interconectados que forman un grafo. Para movernos entre los nodos lo que hacemos es simplemente convertir el grafo en un tree expandiendo desde el nodo inicial hasta llegar al destino. Una vez que lo alcanzamos, recorremos el tree hacia arriba hasta encontrar el nodo inicial. Lo que obtenemos es el camino invertido (nos podríamos ahorrar el paso de invertir el camino si comenzamos a expandir desde el destino hasta encontrar el punto de partida).

En realidad, el sistema es bastante similar al algoritmo de Dijkstra, pero más fácil de entender. Encuentra siempre el camino que requiere recorrer menos nodos.

Pueden ver un ejemplo de su funcionamiento aquí (seleccionen el nodo haciendo click en él y luego hagan click en el destino).

Pueden descargar el .fla aquí.

Ta-Te-Tí imbatible

El ta-te-tí es un juego sumamente simple. Por lo que crear una IA que juegue siempre de forma perfecta es relativamente sencillo.




Las instrucciones para la IA son bastante simples:

1. Si el casillero central está libre ubicar una ficha ahí, caso contrario continuar
   
2. Verificar si, ubicando una ficha, podemos ganar el juego, en ese caso lo hacemos, caso contrario, continua el algoritmo
   
3. Verificar si, ubicando una ficha, el oponente puede ganar el partido, en ese caso, bloqueamos el casillero
   
4. Buscamos una estrategia particular que puede ganarnos. En caso de que reconozcamos la estrategia, tomamos medidas para evitarla.
   
5. Si no ocurre ninguna de las anteriores, ubicamos una ficha en una posición más o menos aleatoria. Con la condición de que si la ficha central es nuestra, lo hacemos en un casillero diagonal.

Pueden bajar el .fla aquí.

Hello world

Guau, el primer post, y no sé que decir... Es raro, a partir de éste los tengo planeados, pero no puedo decidir qué poner en éste, quizá lo ideal sería dejarlo en blanco.