WEBVTT

00:11.460 --> 00:15.400
Sería imposible comenzar a hablar sobre los entresijos de A. YO.

00:15.420 --> 00:21.770
sin un breve trasfondo en 'Graph Theory'. Casi todos los A. YO. Las técnicas que utilizan

00:21.770 --> 00:27.870
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.

00:28.470 --> 00:31.950
Los nodos se representan gráficamente como círculos ... y los bordes

00:31.950 --> 00:38.430
son las líneas que los conectan. Un gráfico se puede visualizar como nodos que representan ubicaciones y

00:38.430 --> 00:40.490
bordes como caminos que los conectan.

00:40.650 --> 00:47.220
Un gráfico puede ser no dirigido (lo que significa que las rutas entre los nodos pueden atravesarse en ambas

00:47.490 --> 00:51.480
direcciones) o dirigirse (en cuyo caso las rutas son unidireccionales).

00:51.540 --> 00:54.260
Piense en esto como una diferencia entre las

00:54.300 --> 01:00.810
calles de doble sentido y las de un solo sentido. Los nodos y los bordes se pueden dibujar donde los nodos representan

01:00.810 --> 01:06.520
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.

01:06.990 --> 01:09.930
Tanto los nodos como los bordes pueden tener valores asociados.

01:10.110 --> 01:15.720
Estos valores podrían ser la distancia entre nodos (como los que representan distancias en el plan de vuelo) o

01:16.320 --> 01:20.850
el tiempo que lleva completar una acción (como un nodo en el plan de acción).

01:21.180 --> 01:26.910
Las formas en que los gráficos son útiles en el juego A. YO. será evidente a medida que avancemos en este curso.

01:27.630 --> 01:30.580
Si crees que los gráficos parecen familiares, es porque lo son.

01:30.900 --> 01:36.990
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

01:36.990 --> 01:43.080
pueden usar para una gran cantidad de aplicaciones en las que necesita recorrer de un estado a

01:43.080 --> 01:46.830
otro, ya sea un estado real o un estado conceptual.

01:46.830 --> 01:52.710
En este ejemplo, se está utilizando un gráfico para definir las ubicaciones en un juego basado en fichas y la

01:52.710 --> 01:59.130
cantidad de esfuerzo para moverse de una ficha a otra. Los valores colocados en los bordes generalmente se conocen como 'Valores de

01:59.130 --> 02:02.140
utilidad', ya sea que representen tiempos, distancias, esfuerzo, costos o

02:02.160 --> 02:08.790
cualquier otro valor que un NPC pueda usar para tomar una decisión. Consideremos la situación en la que

02:08.790 --> 02:13.300
un NPC quiere pasar de la casilla C2 a A2.

02:13.590 --> 02:17.760
Hay 2 caminos posibles. Para decidir qué ruta tomar,

02:17.760 --> 02:22.700
el NPC puede sumar todos los valores de utilidad a lo largo de cada ruta.

02:22.730 --> 02:29.090
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

02:29.090 --> 02:35.240
la ruta más larga (sobre el puente) será menos esfuerzo. Para trabajar con un gráfico, debe

02:35.240 --> 02:39.650
existir un método eficiente de búsqueda a través de los nodos.

02:39.650 --> 02:43.540
Hay dos algoritmos básicos de alto nivel para buscar a través de nodos.

02:43.760 --> 02:51.350
La primera se llama 'Búsqueda de amplitud primero'. En una búsqueda de amplitud, el NPC marca

02:51.410 --> 02:59.480
su ubicación actual (o nodo) como 1, luego numera todos los nodos adyacentes como 2, luego todos los

02:59.560 --> 03:04.590
nodos adyacentes como 3, etc. hasta que se haya alcanzado el nodo de destino.

03:04.610 --> 03:09.470
Luego cuenta hacia atrás, en 1s, hasta el inicio, para encontrar un camino hacia la meta.

03:09.680 --> 03:16.280
La búsqueda de amplitud examina todos los nodos posibles en el gráfico para encontrar la mejor ruta, pero debido

03:16.340 --> 03:23.630
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.

03:23.780 --> 03:31.250
En lugar de encontrar el MEJOR camino, encuentra un camino. Comenzando en la posición de la APN, se encuentra un nodo adyacente

03:31.250 --> 03:33.770
y se numera. Luego se encuentra y

03:33.800 --> 03:35.390
se numera un nodo adyacente a este.

03:35.390 --> 03:41.630
Esto continúa hasta que se llega a un punto muerto, momento en el cual volvemos al último nodo donde

03:41.630 --> 03:45.390
había otra dirección para intentar y nos dirigimos en esa dirección.

03:45.860 --> 03:51.560
Es como el enfoque que podría tomar para salir de un laberinto. Cuando se encuentra el destino, los nodos se

03:51.560 --> 03:57.770
cuentan de nuevo hacia atrás, para dar la ruta. El algoritmo más popular utilizado para encontrar rutas en gráficos

03:57.770 --> 04:03.300
que se usa en juegos debido a su eficiencia para poder encontrar la ruta más corta, es el

04:03.350 --> 04:04.360
algoritmo A *.

04:04.370 --> 04:08.230
Es un poco más complejo que los otros dos métodos y funciona así ...

04:08.240 --> 04:10.780
Primero, todos los nodos en el gráfico están numerados.

04:10.800 --> 04:15.050
Luego creamos dos listas: una lista 'abierta' y una lista 'cerrada'.

04:15.170 --> 04:18.620
Estos harán un seguimiento de los nodos que hemos visitado y procesado.

04:18.710 --> 04:22.940
A cada nodo se le dan 4 valores que se utilizan para calcular la ruta.

04:22.940 --> 04:26.750
Primero se les da un valor 'heurístico' representado por 'H'.

04:26.870 --> 04:32.320
El 'heurístico' es el costo estimado de llegar desde un nodo individual al destino.

04:32.540 --> 04:35.980
Puede usar cualquier método que desee para calcular ese valor.

04:36.260 --> 04:42.060
Puede usar una 'distancia lineal' o contar el 'número de filas y columnas'.

04:42.190 --> 04:46.180
El segundo valor es 'Costo de movimiento' representado por 'G'.

04:46.450 --> 04:51.370
Este valor es esencialmente la utilidad para pasar al nodo desde otro nodo.

04:51.370 --> 04:55.140
Esto podría basarse en la distancia real de un nodo a otro o en el costo de

04:55.480 --> 05:02.660
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

05:02.660 --> 05:09.650
y G y llamamos a eso 'F' y almacenamos los nodos principales, que es el nodo más cercano

05:09.650 --> 05:12.240
a lo largo de la ruta.

05:12.470 --> 05:14.490
Echemos un vistazo a un ejemplo.

05:14.510 --> 05:16.490
Comenzamos colocando el nodo inicial (en este caso,

05:16.550 --> 05:23.180
50) en la lista 'Cerrado', ya que esta es la ubicación que hemos visitado. Luego buscamos vecinos que no estén bloqueados y

05:23.180 --> 05:28.250
que no estén en la lista cerrada y los agregamos a la lista 'Abrir'.

05:29.070 --> 05:35.640
Luego calculamos la heurística para cada nodo en la lista abierta. En este caso, utilizaremos la

05:35.640 --> 05:39.830
distancia lineal desde el nodo hasta el destino.

05:39.920 --> 05:43.820
Luego calculamos nuestro costo de movimiento para pasar del nodo inicial al vecino.

05:44.060 --> 05:50.450
Nuevamente, usamos una distancia lineal. Los vecinos horizontales y verticales están a una distancia de 1, con vecinos

05:50.450 --> 05:57.230
diagonales a una distancia de 1. 4) El costo de pasar a esos nodos se convierte en su valor G. A partir de eso,

05:57.320 --> 06:00.340
se calcula 'F', que es H + G.

06:00.410 --> 06:05.120
Mientras hacemos esto, todos los vecinos están vinculados de nuevo al nodo actual, lo

06:05.120 --> 06:11.420
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

06:11.420 --> 06:13.340
lista abierta con el valor F más bajo.

06:13.370 --> 06:18.860
Esto se convierte en una nueva ubicación para comenzar a buscar a los vecinos nuevamente. El nuevo nodo de ubicación

06:18.860 --> 06:25.880
se agrega a la lista cerrada como visitado. Cualquier vecino no bloqueado, cerrado o que ya esté en la lista abierta se

06:26.000 --> 06:27.350
agrega a la lista abierta.

06:27.350 --> 06:31.850
El valor H se calcula para cualquier nuevo nodo en la lista abierta.

06:31.850 --> 06:38.380
El valor G también se calcula, pero esta vez es el "costo de movimiento + el costo de movimiento anterior".

06:38.660 --> 06:48.170
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

06:48.170 --> 06:48.790
1.

06:49.010 --> 06:57.680
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

06:57.680 --> 07:06.050
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

07:06.050 --> 07:07.720
actual, el valor

07:07.970 --> 07:13.880
G de los nodos se cambia y su padre se actualiza a la ubicación actual.

07:13.970 --> 07:23.450
En este ejemplo, un nuevo valor G proveniente del nodo 41 sería 1, más un costo de movimiento horizontal

07:23.450 --> 07:29.020
de 1, lo que da como resultado un valor de 2.

07:29.150 --> 07:32.530
2 no tiene menos de 40s de valor G actual y,

07:32.690 --> 07:35.220
por lo tanto, el nodo permanece sin cambios.

07:35.330 --> 07:41.840
Cualquier vecino sin padre se asigna a la ubicación actual y el proceso comienza nuevamente, buscando el

07:41.840 --> 07:45.650
nodo con el valor F más pequeño en la lista

07:45.640 --> 07:50.360
abierta para visitar a continuación. El proceso finaliza cuando estamos a un nodo del final.

07:50.480 --> 07:55.710
En este punto, tenemos un enlace de padres que lo guían hasta el inicio, que cuando se invierte,

07:55.710 --> 08:02.440
proporciona un camino desde la ubicación de inicio hasta el destino. Unity utiliza el algoritmo A * para encontrar rutas

08:02.510 --> 08:03.980
en su navmesh.

08:03.980 --> 08:09.590
Esta construcción nos brinda una forma poderosa de programar la navegación y la evasión en nuestros proyectos.

08:09.590 --> 08:15.340
Cuando lo piensas, los gráficos y sus nodos y bordes son realmente una cosa muy simple. A medida que avanzamos en el curso,

08:15.680 --> 08:20.840
los verá aparecer por todos lados, ya que son un elemento básico en

08:20.840 --> 08:22.110
la inteligencia artificial.

08:22.340 --> 08:28.140
Si bien existen numerosos algoritmos para recorrer gráficos, cuando se trata de juegos, nada supera a A

08:28.370 --> 08:31.060
* y encontrará muchos recursos para respaldarlo.
