Diferencia entre revisiones de «Inteligencia artificial para videojuegos/Control de unidades en juego RTS»
Contenido eliminado Contenido añadido
m added Category:Informática using HotCat |
Sin resumen de edición |
||
Línea 32:
* Proyecto y juego web basado en A*: http://buildnewgames.com/astar/
=== Implementacion en Unity del A*===
* Implementacion de la busqueda
Para realizar la busqueda a una casilla objetivo (Ob) desde una casilla inicial (ini) se puede seguir el metodo del Algoritmo A*, este algoritmo nos permitira a traves de una serie de parametros, comprobar la distancia de las casillas vecinas a la nuestra, hasta la casilla Ob y elegir aquella que esta mas cerca del Ob para seguir expandiendose a partir de ahi. Este algoritmo tambien tiene en cuenta el coste de moverse entre los diferentes tipos de casillas y diferenciar entre suelo pisable y muros.
Las casillas se estructuraran por "nodos" cuyas caracteristicas seran:
* g_Cost -> A que distancia se encuentra el nodo del nodo inicial.
* h_Cost -> A que distancia se encuentra el nodo del nodo final.
* f_Cost -> g_Cost + h_Cost.
* Se pueden implementar mas caracteristicas al calcular el coste de los nodos como el coste de atravesar esa casilla sumandolo simplemente al f_Cost.
El algoritmo de A* ira buscando en los nodos vecinos al nodo actual y seleccionara el que tiene el menor f_Cost como el nuevo actual, de esta manera ira progresando a traves del tablero hasta llegar a la casilla objetivo por el camino mas rapido que haya encontrado.
Una vez encontrado el nodo objetivo se realizara un RetracePath, desde el objetivo hasta la casilla de inicio, a traves de los parents de los nodos, que devolvera la lista de casillas representando el camino mas rapido.
La estructura en pseudocodigo del algoritmo A* seria:
//--------------
//conjunto de nodos (casillas) a ser evaluadas
OPEN
//conjunto de nodos ya evaluados (conocemos su f_Cost)
CLOSED
loop
current = nodo en OPEN con el f_Cost mas bajo
eliminar current de OPEN
añadir current a CLOSED
if(current = casilla objetivo) //se encontro el camino
RetracePath()**
return
foreach(neighbour del nodo actual) //Miramos las casillas vecinas a la que nos encontramos
if (neighbour es muro o esta en CLOSED)
saltamos al siguiente neighbour
if (el camino nuevo al neighbour es mas corto que el camino anterior (el coste de f_Cost es menor) o el neighbour no esta en OPEN)
set f_Cost de neighbour
set parent de neighbour al nodo actual
if(neighbour no esta en OPEN)
añadimos neighbour a OPEN
else
actualizamos el valor del nodo neighbour
//---------------
El metodo RetracePath:
void RetracePath (Nodo startCasilla, Nodo endCasilla) {
List<Casilla> path = new List<Casilla>();
currentCasilla = endCasilla;
while (currrentCasilla != startCasilla){
path.Add(currentCasilla);
currentCasilla = currentCasilla.parent;
}
path.Reverse();
//path es el camino a seguir, guardarlo donde se necesite.
}
[[Categoría:Informática]]
| |||