4. Descripción de los algoritmos desarrolladas - AndreyGarro/League-of-Gems GitHub Wiki

Algoritmos de busquedad de ruta mas corta

Para buscar una eficacia en el desplazamiento de los soldados usados por el jugador son implementados varios algoritmos de busqueda de ruta los cuales se describen a continuacion:

Linea-Vista

Esta forma de buscar una ruta de un punto a otro consiste en seguir en linea recta desde el punto de partida hasta el destino y si en el camino se encuentra un obstaculo que empida seguir la linea recta entonces se intenta bordiarlo hasta lograr pasar y seguir en linea hasta el destino. Esta forma de buscar una ruta es la menos eficiente pues debido a la poca planificacion del camino es posible que se termine recorriendo la distancia mas larga, sin embargo este algoritmo es el menos complejo de desarrollar.

PRIM

El algoritmo PRIM trabaja sobre un grafo conexo, es usado para obtener el arbol de minima expresion(MST), es el algoritmo mas simple de trabajar para obtener el MST de un grafo, para crear el MST se escoge un vertice de inicio, luego se mueve hacia el siguiente vertice que tenga el menor peso y asi hasta que todos los vertice esten visitados. En el proyecto es utilizado para calcular el menor recorrido desde el punto de inicio hasta el destino,en el grafo de entrada cada vertice representa puntos intermedios y cada punto esta conectado con otros puntos, el peso de cada arista es la distancia que existe entre punto y punto en el mapa.

KRUSKAL

Este algoritmo realiza la misma funcion que el PRIM pero el proceso para obtener el resultado es diferente, primero se debe ordenar las aristas de menor a mayor por medio de los pesos, luego se va creando el MST tomando los vertices que conectan cada arista hasta que todos los vertices esten conectados. El grafo de entrada se crea de la misma forma que para el algoritmo PRIM.

DIJKSTRA

Este algoritmo busca la ruta mas corta desde un vertice de inicio hacia un vertice de destino de un grafo, el mecanismo utilizado comienza con calcular el un peso total a todos los vertices adyacentes al vertice de inicio y moverse al que tenga un peso menor, luego se vuelve a calcular el peso de los vertices adyacentes tomando como referencia el peso del vertice al que se movio y de la misma manera se mueve hacia el vertice con menor peso y se vuelve a realizar el proceso hasta que se este en el vertice destino. Este algoritmo buscara garantizar la ruta mas cercana para moverse de un punto a otro en el mapa.

A*

El algoritmo A* permite calcular la ruta mas corta de un punto a otro corrigiendo un factor que otros algoritmos no toman en cuenta y es que a veces realizar movientos intermedios requieren de un coste elevado, por esta razon al algoritmo A* usa dos factores para tomar la decision a la hora de moverse, el vertice seleccionado para moverse sera que el que tenga un menor valor f, donde f se compone de una suma entre g y h, que a su vez

• g indica la distancia del camino desde el punto origen hasta punto a moverse.

• h expresa la distancia estimada desde el punto origen hasta el nodo destino

De esta forma A* podria moverse a un punto con mayor peso pero que sumado al peso total resultara mas beneficioso.