Sería imposible comenzar a hablar sobre los entresijos de A. YO.
sin un breve trasfondo en 'Graph Theory'. Casi todos los A. YO. Las técnicas que utilizan
juegos dependen de que los programadores comprendan los gráficos. Los gráficos en este contexto se refieren a una colección de nodos y aristas.
Los nodos se representan gráficamente como círculos ... y los bordes
son las líneas que los conectan. Un gráfico se puede visualizar como nodos que representan ubicaciones y
bordes como caminos que los conectan.
Un gráfico puede ser no dirigido (lo que significa que las rutas entre los nodos pueden atravesarse en ambas
direcciones) o dirigirse (en cuyo caso las rutas son unidireccionales).
Piense en esto como una diferencia entre las
calles de doble sentido y las de un solo sentido. Los nodos y los bordes se pueden dibujar donde los nodos representan
coordenadas, como aquellos en un plan de vuelo, o como estados simbólicos donde la ubicación física en el gráfico no tiene sentido.
Tanto los nodos como los bordes pueden tener valores asociados.
Estos valores podrían ser la distancia entre nodos (como los que representan distancias en el plan de vuelo) o
el tiempo que lleva completar una acción (como un nodo en el plan de acción).
Las formas en que los gráficos son útiles en el juego A. YO. será evidente a medida que avancemos en este curso.
Si crees que los gráficos parecen familiares, es porque lo son.
Ya hemos hecho un gráfico de puntos de referencia y hemos cruzado nuestro NPC entre ellos. Los gráficos son tan flexibles que se
pueden usar para una gran cantidad de aplicaciones en las que necesita recorrer de un estado a
otro, ya sea un estado real o un estado conceptual.
En este ejemplo, se está utilizando un gráfico para definir las ubicaciones en un juego basado en fichas y la
cantidad de esfuerzo para moverse de una ficha a otra. Los valores colocados en los bordes generalmente se conocen como 'Valores de
utilidad', ya sea que representen tiempos, distancias, esfuerzo, costos o
cualquier otro valor que un NPC pueda usar para tomar una decisión. Consideremos la situación en la que
un NPC quiere pasar de la casilla C2 a A2.
Hay 2 caminos posibles. Para decidir qué ruta tomar,
el NPC puede sumar todos los valores de utilidad a lo largo de cada ruta.
En este caso, los valores de utilidad no se refieren a la distancia, sino a la dificultad del terreno. Sumar los valores a lo largo de cada ruta revela que
la ruta más larga (sobre el puente) será menos esfuerzo. Para trabajar con un gráfico, debe
existir un método eficiente de búsqueda a través de los nodos.
Hay dos algoritmos básicos de alto nivel para buscar a través de nodos.
La primera se llama 'Búsqueda de amplitud primero'. En una búsqueda de amplitud, el NPC marca
su ubicación actual (o nodo) como 1, luego numera todos los nodos adyacentes como 2, luego todos los
nodos adyacentes como 3, etc. hasta que se haya alcanzado el nodo de destino.
Luego cuenta hacia atrás, en 1s, hasta el inicio, para encontrar un camino hacia la meta.
La búsqueda de amplitud examina todos los nodos posibles en el gráfico para encontrar la mejor ruta, pero debido
a su minuciosidad, lleva mucho tiempo y no es óptima. Una 'Búsqueda de profundidad primero' es mucho más simple y rápida, pero menos efectiva.
En lugar de encontrar el MEJOR camino, encuentra un camino. Comenzando en la posición de la APN, se encuentra un nodo adyacente
y se numera. Luego se encuentra y
se numera un nodo adyacente a este.
Esto continúa hasta que se llega a un punto muerto, momento en el cual volvemos al último nodo donde
había otra dirección para intentar y nos dirigimos en esa dirección.
Es como el enfoque que podría tomar para salir de un laberinto. Cuando se encuentra el destino, los nodos se
cuentan de nuevo hacia atrás, para dar la ruta. El algoritmo más popular utilizado para encontrar rutas en gráficos
que se usa en juegos debido a su eficiencia para poder encontrar la ruta más corta, es el
algoritmo A *.
Es un poco más complejo que los otros dos métodos y funciona así ...
Primero, todos los nodos en el gráfico están numerados.
Luego creamos dos listas: una lista 'abierta' y una lista 'cerrada'.
Estos harán un seguimiento de los nodos que hemos visitado y procesado.
A cada nodo se le dan 4 valores que se utilizan para calcular la ruta.
Primero se les da un valor 'heurístico' representado por 'H'.
El 'heurístico' es el costo estimado de llegar desde un nodo individual al destino.
Puede usar cualquier método que desee para calcular ese valor.
Puede usar una 'distancia lineal' o contar el 'número de filas y columnas'.
El segundo valor es 'Costo de movimiento' representado por 'G'.
Este valor es esencialmente la utilidad para pasar al nodo desde otro nodo.
Esto podría basarse en la distancia real de un nodo a otro o en el costo de
atravesar un tipo de tren, como el ejemplo de mosaico que vimos con el puente. Luego almacenamos un cálculo que suma los valores H
y G y llamamos a eso 'F' y almacenamos los nodos principales, que es el nodo más cercano
a lo largo de la ruta.
Echemos un vistazo a un ejemplo.
Comenzamos colocando el nodo inicial (en este caso,
50) en la lista 'Cerrado', ya que esta es la ubicación que hemos visitado. Luego buscamos vecinos que no estén bloqueados y
que no estén en la lista cerrada y los agregamos a la lista 'Abrir'.
Luego calculamos la heurística para cada nodo en la lista abierta. En este caso, utilizaremos la
distancia lineal desde el nodo hasta el destino.
Luego calculamos nuestro costo de movimiento para pasar del nodo inicial al vecino.
Nuevamente, usamos una distancia lineal. Los vecinos horizontales y verticales están a una distancia de 1, con vecinos
diagonales a una distancia de 1. 4) El costo de pasar a esos nodos se convierte en su valor G. A partir de eso,
se calcula 'F', que es H + G.
Mientras hacemos esto, todos los vecinos están vinculados de nuevo al nodo actual, lo
que hace que el nodo inicial sea su padre. Sin más nodos para examinar en la lista abierta, ahora obtenemos el nodo en la
lista abierta con el valor F más bajo.
Esto se convierte en una nueva ubicación para comenzar a buscar a los vecinos nuevamente. El nuevo nodo de ubicación
se agrega a la lista cerrada como visitado. Cualquier vecino no bloqueado, cerrado o que ya esté en la lista abierta se
agrega a la lista abierta.
El valor H se calcula para cualquier nuevo nodo en la lista abierta.
El valor G también se calcula, pero esta vez es el "costo de movimiento + el costo de movimiento anterior".
Entonces, en este caso, el nodo 32 obtiene el 'movimiento G' de 41 + el 'costo de movimiento' de 41 a 32, que también es
1.
Esto da un valor G final de 2 ... y para 32, su valor F será 7. Para cualquiera de los vecinos de la ubicación actual todavía
en la lista abierta (en este caso, 40) se calcula un nuevo valor de G. Si el nuevo valor G es menor que el valor G
actual, el valor
G de los nodos se cambia y su padre se actualiza a la ubicación actual.
En este ejemplo, un nuevo valor G proveniente del nodo 41 sería 1, más un costo de movimiento horizontal
de 1, lo que da como resultado un valor de 2.
2 no tiene menos de 40s de valor G actual y,
por lo tanto, el nodo permanece sin cambios.
Cualquier vecino sin padre se asigna a la ubicación actual y el proceso comienza nuevamente, buscando el
nodo con el valor F más pequeño en la lista
abierta para visitar a continuación. El proceso finaliza cuando estamos a un nodo del final.
En este punto, tenemos un enlace de padres que lo guían hasta el inicio, que cuando se invierte,
proporciona un camino desde la ubicación de inicio hasta el destino. Unity utiliza el algoritmo A * para encontrar rutas
en su navmesh.
Esta construcción nos brinda una forma poderosa de programar la navegación y la evasión en nuestros proyectos.
Cuando lo piensas, los gráficos y sus nodos y bordes son realmente una cosa muy simple. A medida que avanzamos en el curso,
los verá aparecer por todos lados, ya que son un elemento básico en
la inteligencia artificial.
Si bien existen numerosos algoritmos para recorrer gráficos, cuando se trata de juegos, nada supera a A
* y encontrará muchos recursos para respaldarlo.