Pathfinding Algorithms - notFrost/TP-Quoridor GitHub Wiki
1. Algorítmos
1.1. Algoritmo BFS:
El algoritmo de BFS, nos permitirá evaluar, en base a la situación del tablero de Quoridor, cual es el camino más corto hacia la meta como jugador. En caso de ser utilizado para una inteligencia artificial, se implementará el BFS para determinar el camino más corto posible cuando este ya decidió entre moverse o colocar una pared, de esa manera, el análisis será exacto al momento de realizar jugadas. Su complejidad es O(n^2).
1.2. Algorítmo A*
El algoritmo de A* es considerado un algoritmo de búsqueda de coste uniforme, es de tipo o(n2), además tiene como objetivo encontrar el primer camino más práctico en un grafo, durante el juego. Esto permite ayudar al jugador a determinar dónde moverse o a la IA a reconocer qué movimiento debe ir. Cabe recalcar que si existen dos soluciones exactamente iguales en simplicidad el algoritmo optará por la primera. Este algoritmo utiliza los dos métodos de dos conocidas búsquedas, la de por anchura y por profundidad.
1.3. Algorítmo DFS
El algoritmo DFS un algoritmo eficiente para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo. Este se encarga de formar un camino a partir de otro ya existente. Este algoritmo trabaja por etapas bajo el principio de la optimalidad, tomando en cada etapa la mejor solución sin considerar consecuencias futuras; donde el óptimo encontrado puede modificarse posteriormente si surge una solución mejor. El algoritmo utiliza backtracking para regresar a los nodos anteriores y verificar si puede seguir otro camino.
2. Espacios de Búsqueda
La programación mediante matrices nos ayuda a encontrar una solución mediante el sistema de colisiones. Estos se basarán en caso de la programación realizada y utilizada para movimientos simples. Sin embargo, se volvería un código inmutable, de manera de que si se termina el proyecto no podrá mejorar con futuras actualizaciones debido a que se ha programado para realizar ciertas acciones sin fluidez.
La programación realizada mediante grafos y algoritmos, nos permitirá la creación y desarrollo del juego en base a búsquedas. Lo que nos abre a nuevas posibilidades, desde la búsqueda de nuevas jugadas como jugador hasta la implementación de nuevas jugadas y movimientos por parte de la IA que puede ser implementada a futuro. Gracias a ello, el juego permitirá nuevos movimientos y acciones.
3. Experimentos
Se han analizado los algoritmos de A*, “BFS” y “DFS” se ha logrado verificar la ruta más corta que se puede crear entre dos puntos en los dos extremos del mapa.
3.1 Algorítmo BFS
El algoritmo de BFS o “Best First Search”, realiza una búsqueda por anchura por todos los grafos. Desde el grafo inicial(jugador) empieza su recorrido, expandiéndose alrededor del jugador. Si encuentra un muro, hace como si no lo pudiera pasar, de esta manera recorre todo el grafo. En el momento que encuentra el objetivo, vuelve por los grafos que recorrió y determina la ruta más corta como se puede apreciar en la siguiente figura.
3.2. Algorítmo A*
Es una versión informada del algoritmo BFS, este se concentra en grafos muy pesados, posee como objetivo mediante su ejecución partir hacia adelante donde se encuentra el objetivo o destino. si por alguna razón o motivo se encuentra con una colisión, el algoritmo expande un poco el foco de búsqueda y continuará su recorrido. Continuará de esta manera hasta que se logre hacer contacto con el destino. De ahí se trazará de regreso el camino más corto que debe recorrer. Aquí se muestra un ejemplo en la siguiente figura.
3.3. Algorítmo DFS
El algoritmo DFS se encarga de calcular el camino mínimo entre dos puntos, que forman parte de un grafo. Ese camino está formando por un número de vértices unidos entre sí por aristas de diferentes costes. Desde el punto de partida, el algoritmo se expande alrededor de la matriz. A continuación, en la figura que se encuentra a continuación, se muestra un ejemplo del funcionamiento del algoritmo DFS.
