Sistema de trabajo y ruta de búsqueda

Mapa

En un artículo anterior, analicé cuál es el nuevo sistema Job , cómo funciona, cómo crear tareas, llenarlas con datos y realizar cálculos de subprocesos múltiples, y solo le expliqué brevemente dónde puede usar este sistema. En este artículo, intentaré analizar un ejemplo específico de dónde puede usar este sistema para obtener más rendimiento.

Dado que el sistema se desarrolló originalmente con el objetivo de trabajar con datos, es ideal para resolver tareas de búsqueda de rutas.

Unity ya tiene un buen navegador NavMesh , pero no funciona en proyectos 2D, aunque hay muchas soluciones listas para usar en el mismo activo . Bueno, e intentaremos crear no solo un sistema que buscará formas en el mapa creado, sino que hará que este mapa sea dinámico, de modo que cada vez que algo cambie en él, el sistema creará un nuevo mapa, y todo esto, por supuesto, lo calcularemos utilizando Un nuevo sistema de tareas, para no cargar el hilo principal.


En el ejemplo, se construye una cuadrícula en el mapa, hay un bot y un obstáculo. La cuadrícula se reconstruye cada vez que cambiamos cualquier propiedad del mapa, ya sea su tamaño o posición.

Para los aviones, utilicé un SpriteRenderer simple, este componente tiene una propiedad de límites excelente con la que puede averiguar fácilmente el tamaño del mapa.

Básicamente, eso es todo para empezar, pero no nos detendremos e inmediatamente nos pondremos manos a la obra.

Comencemos con los guiones. Y el primero es el script de obstrucción de obstáculos .


Dentro de la clase Obstáculo , detectaremos todos los cambios en los obstáculos en el mapa, por ejemplo, cambiando la posición o el tamaño de un objeto.
A continuación, puede crear la clase de mapa Map , en la que se construirá la cuadrícula, y heredarla de la clase Obstacle .


La clase Map también rastreará todos los cambios en el mapa para reconstruir la cuadrícula si es necesario.

Para hacer esto, complete la clase base Obstáculo con todas las variables y métodos necesarios para realizar un seguimiento de los cambios en los objetos.


Aquí, la variable de representación tendrá una referencia al componente SpriteRenderer , y las variables tempSize y tempPos se usarán para rastrear los cambios en el tamaño y la posición del objeto.

El método virtual Awake se usará para inicializar las variables, y el método virtual CheckChanges hará un seguimiento de los cambios actuales en el tamaño y la posición del objeto y devolverá un resultado booleano .

Por ahora, dejemos la secuencia de comandos Obstacle y pasemos a la secuencia de comandos Map map en sí, donde también la completaremos con los parámetros necesarios para el trabajo.


La variable nodeSize indicará el tamaño de las celdas en el mapa, aquí he limitado su tamaño de 0.1 a 1 para que las celdas en la cuadrícula no sean demasiado pequeñas, sino también demasiado grandes. La variable de desplazamiento se usará para sangrar el mapa al construir la cuadrícula para que la cuadrícula no se construya a lo largo de los bordes del mapa.

Como ahora hay dos nuevas variables en el mapa, resulta que sus cambios también deberán ser rastreados. Para hacer esto, agregue un par de variables y sobrecargue el método CheckChanges en la clase Map .


Listo Ahora puede crear un sprite de mapa en el escenario y lanzar un script de Mapa sobre él.



Haremos lo mismo con un obstáculo: crear un sprite simple en el escenario y lanzar el guión de Obstáculo sobre él.



Ahora tenemos objetos de mapa y obstáculos en el escenario.

La secuencia de comandos del Mapa será responsable de rastrear todos los cambios en el mapa, donde en el método de Actualización revisaremos cada cuadro para ver los cambios.


Por lo tanto, en el método UpdateChanges, el mapa solo rastreará sus cambios hasta ahora. Incluso puedes comenzar el juego ahora e intentar cambiar el tamaño del mapa o compensar el desplazamiento para asegurarte de que todos los cambios sean rastreados.

Ahora necesita rastrear de alguna manera los cambios de los obstáculos en el mapa. Para hacer esto, colocaremos cada obstáculo en una lista en el mapa, que a su vez actualizará cada cuadro en el método Actualizar .

En la clase Mapa , cree una lista de todos los obstáculos posibles en el mapa y un par de métodos estáticos para registrarlos.


En el método estático RegisterObstacle , registraremos un nuevo obstáculo Obstáculo en el mapa y lo agregaremos a la lista, pero primero es importante tener en cuenta que el mapa en sí también se hereda de la clase Obstáculo y, por lo tanto, debemos verificar si estamos tratando de registrar la tarjeta como un obstáculo.

El método estático UnregisterObstacle , por el contrario, elimina el obstáculo del mapa y lo elimina de la lista cuando permitimos que sea destruido.

Al mismo tiempo, cada vez que agregamos o eliminamos un obstáculo del mapa, es necesario recrear el mapa en sí, por lo que después de ejecutar estos métodos estáticos, establezca la variable requireRebuild en true .

Además, para tener fácil acceso al script del Mapa desde cualquier script, creé una propiedad de Instancia estática que me devolverá esta misma instancia del Mapa .

Ahora, volvamos a la secuencia de comandos Obstáculo donde registraremos un obstáculo en el mapa. Para hacer esto, agregue un par de métodos OnEnable y OnDisable .


Cada vez que creamos un nuevo obstáculo mientras jugamos en el mapa, se registrará automáticamente en el método OnEnable , donde se tendrá en cuenta al construir una nueva cuadrícula y nos eliminaremos del mapa en el método OnDisable cuando se destruya o desactive.

Solo queda realizar un seguimiento de los cambios de los obstáculos en el script Map en el método CheckChanges sobrecargado.


Ahora tenemos un mapa, obstáculos: en general, todo lo que necesita para construir una cuadrícula y ahora puede pasar a lo más importante.

Malla

La cuadrícula, en su forma más simple, es una matriz bidimensional de puntos. Para construirlo, necesita saber el tamaño del mapa y el tamaño de los puntos en él, después de algunos cálculos obtenemos el número de puntos horizontal y verticalmente, esta es nuestra cuadrícula.

Hay muchas formas de encontrar una ruta en una cuadrícula. Sin embargo, en este artículo, lo principal es entender cómo usar correctamente las capacidades del sistema de tareas, por lo que aquí no consideraré diferentes opciones para encontrar la ruta, sus ventajas y desventajas, pero tomaré la opción de búsqueda más simple A * .

En este caso, todos los puntos de la cuadrícula deben tener, además de la posición, las coordenadas y la propiedad de permeabilidad.

Con la permeabilidad, creo que todo está claro por qué es necesario, pero las coordenadas indicarán el orden del punto en la cuadrícula, estas coordenadas no están vinculadas específicamente a la posición del punto en el espacio. La imagen a continuación muestra una cuadrícula simple que muestra las diferencias de coordenadas desde una posición.


¿Por qué las coordenadas?
El hecho es que, en la unidad, para indicar la posición de un objeto en el espacio, se utiliza un flotador simple que es muy inexacto y puede ser un número fraccionario o negativo, por lo que será difícil usarlo para implementar una búsqueda de ruta en el mapa. Las coordenadas se hacen en forma de un int claro que siempre será positivo y con el que es mucho más fácil trabajar cuando se buscan puntos vecinos.

Primero, definamos un objeto de punto, esta será una estructura de Nodo simple.


Esta estructura contendrá la posición de posición en forma de Vector2 , donde con esta variable dibujaremos un punto en el espacio. La variable de coordenadas de los coords en forma de Vector2Int indicará las coordenadas de un punto en el mapa, y la variable id su número de cuenta numérico usándolo, compararemos diferentes puntos en la cuadrícula y verificaremos la existencia de un punto.

La permeabilidad del punto se indicará en forma de su propiedad booleana , pero como no podemos usar los tipos de datos convertibles en el sistema de tareas, indicaremos su permeabilidad en forma de un número int , para esto utilicé una enumeración simple NodeType , donde: 0 no es un punto transitable, y 1 es pasable.


Además, para la conveniencia de trabajar con un punto, sobrecargaré el método Equals para facilitar la comparación de puntos y también complementaré el método de verificación para la existencia de un punto.


Como el número de identificación del punto en la cuadrícula comenzará con 1 unidad, comprobaré la existencia del punto como condición de que su identificación sea mayor que 0.

Vaya a la clase Mapa donde prepararemos todo para crear un mapa.
Ya tenemos una verificación para cambiar los parámetros del mapa, ahora necesitamos determinar cómo se llevará a cabo el proceso de construcción de la cuadrícula. Para hacer esto, cree una nueva variable y varios métodos.


La propiedad de reconstrucción indicará si el proceso de mallado está en progreso. El método Reconstruir recopilará datos y tareas para construir la cuadrícula, luego el método OnRebuildStart comenzará el proceso de construcción de la cuadrícula y el método OnRebuildFinish recopilará datos de las tareas.

Ahora cambiemos un poco el método UpdateChanges para que se tenga en cuenta la condición de la cuadrícula.


Como puede ver ahora en el método UpdateChanges , existe la condición de que, mientras que la construcción de la malla antigua no comienza a construir una nueva, y también en el método Reconstruir , la primera acción verifica si el proceso de mallado ya está en progreso.

Resolución de problemas

Ahora un poco sobre el proceso de construcción de un mapa.
Como usaremos el sistema de tareas y construiremos la cuadrícula en paralelo para construir el mapa, utilicé el tipo de tarea IJobParallelFor , que se ejecutará un cierto número de veces. Para no cargar el proceso de construcción con ninguna tarea separada, utilizaremos el conjunto de tareas empaquetadas en un JobHandle .

Muy a menudo, para construir una cuadrícula, use dos ciclos anidados entre sí para construir, por ejemplo, horizontal y verticalmente. En este ejemplo, también construiremos la cuadrícula primero horizontalmente y luego verticalmente. Para hacer esto, calculamos el número de puntos horizontales y verticales en el método Reconstruir , luego en el método Reconstruir pasamos por el ciclo a lo largo de los puntos verticales, y construiremos los horizontales en paralelo en la tarea. Para imaginar mejor el proceso de construcción, eche un vistazo a la animación a continuación.


El número de puntos verticales indicará el número de tareas, a su vez, cada tarea creará puntos solo horizontalmente, después de completar todas las tareas, los puntos se suman en una lista. Es por eso que necesito usar una tarea como IJobParallelFor para pasar el índice del punto en la cuadrícula horizontalmente al método Execute .

Y así tenemos la estructura de puntos, ahora puede crear la estructura de la tarea Trabajo y heredarla de la interfaz IJobParallelFor , todo es simple aquí.


Regresamos al método de Reconstrucción de clase de Mapa , donde haremos los cálculos necesarios para la medición de la cuadrícula.


En el método Reconstruir , calculamos el tamaño exacto del mapa mapSize , teniendo en cuenta la sangría, luego en verticales escribimos el número de puntos verticalmente, y en horizontales el número de puntos horizontalmente. Si el número de puntos verticales es 0, entonces dejamos de construir el mapa y llamamos al método OnRebuildFinish para completar el proceso. La variable de origen indicará el lugar desde donde comenzaremos a construir la cuadrícula; en el ejemplo, este es el punto inferior izquierdo del mapa.

Ahora puede ir a las tareas mismas y llenarlas con datos.
Durante la construcción de la cuadrícula, la tarea necesitará una matriz NativeArray donde colocaremos los puntos, también dado que tenemos obstáculos en el mapa, también tendremos que pasarlos a la tarea, para esto usaremos otra matriz NativeArray , luego necesitamos el tamaño de los puntos en el problema , la posición inicial desde donde construiremos los puntos, así como las coordenadas iniciales de la serie.


Marqué la matriz de puntos como un atributo con WriteOnly, ya que en la tarea solo será necesario " escribir " los puntos recibidos en la matriz, por el contrario, la matriz de límites de obstáculos está marcada con el atributo ReadOnly ya que en la tarea solo " leeremos " datos de esta matriz.

Bueno, por ahora, procedamos al cálculo de los puntos mismos más adelante.

Ahora volvamos a la clase Map , donde denotamos todas las variables involucradas en las tareas.
Aquí, en primer lugar, necesitamos un manejo global de tareas, una serie de obstáculos en forma de NativeArray , una lista de tareas que contendrá todos los puntos recibidos en la cuadrícula y el Diccionario con todas las coordenadas y puntos en el mapa, por lo que sería más conveniente buscarlos más tarde.


Ahora, nuevamente, volvemos al método Reconstruir y continuamos construyendo la cuadrícula.
Primero, inicialice la matriz de límites de obstáculos para pasarla a la tarea.


Aquí creamos una instancia de NativeArray a través de un nuevo constructor con tres parámetros. Examiné los dos primeros parámetros en un artículo anterior, pero el tercer parámetro nos ayudará a ahorrar un poco de tiempo creando una matriz. El hecho es que escribiremos datos en la matriz inmediatamente después de su creación, lo que significa que no necesitamos asegurarnos de que se borre. Este parámetro es útil para NativeArray, que solo se usará en modo de lectura en la tarea.

Y así, luego llenamos la matriz de límites con datos.


Ahora podemos pasar a crear tareas, para esto pasaremos por un ciclo a través de todas las filas verticales de la cuadrícula.


Para empezar, en xPos e yPos obtenemos la posición horizontal inicial de la serie.


A continuación, creamos una matriz nativa simple donde se colocarán los puntos en la tarea, aquí para la matriz que necesita especificar cuántos puntos se crearán horizontalmente y el tipo de asignación Persistente , porque la tarea puede tomar más de un fotograma.
Después, creamos la instancia de la tarea Job en sí, colocamos las coordenadas iniciales de la serie startCoords , la posición inicial de la serie startPos , el tamaño de los puntos nodeSize , la matriz de límites de obstáculos y, al final, la matriz de puntos en sí.
Solo queda poner la tarea en control y la lista de tareas global.


Listo Tenemos una lista de tareas y su identificador común, ahora podemos ejecutar este identificador llamando a su método Completo en el método OnRebuildStart .


Dado que la variable de reconstrucción indicará que el proceso de mallado está en marcha, el método UpdateChanges también debe especificar la condición en la que este proceso terminará usando el identificador y su propiedad IsCompleted .


Después de completar las tareas, se llamará al método OnRebuildFinish donde ya recopilaremos los puntos recibidos en una lista general del Diccionario , y lo más importante, para eliminar los recursos ocupados.


Primero, borramos el diccionario de nodos de los puntos anteriores, luego usamos el bucle foreach para clasificar todos los puntos que recibimos de las tareas y ponerlos en el diccionario de nodos , donde la clave son las coordenadas (¡ NO la posición !) Del punto, y el valor es el punto en sí. Con la ayuda de este diccionario, será más fácil para nosotros buscar puntos vecinos en el mapa. Después de llenar, borramos la matriz de matriz usando el método Dispose y al final borramos la lista de tareas de trabajo en sí .

También deberá despejar los límites de obstáculos si se creó anteriormente.

Después de todas estas acciones, obtenemos una lista de todos los puntos en el mapa y ahora puede dibujarlos en el escenario.


Para hacer esto, en la clase Map , cree el método OnDrawGizmos donde dibujaremos los puntos.


Ahora a través del ciclo dibujamos cada punto.


Después de todas estas acciones, nuestro mapa se ve de alguna manera aburrido, para realmente obtener una cuadrícula, necesita que los puntos estén conectados entre sí.


Para buscar puntos vecinos, solo necesitamos encontrar el punto deseado por sus coordenadas en 8 direcciones, por lo que en la clase Mapa crearemos una matriz estática simple de direcciones de Direcciones y un método de búsqueda de celdas por sus coordenadas GetNode .


El método GetNode devolverá un punto por coordenadas de la lista de nodos , pero debe hacerlo con cuidado, porque si las coordenadas de Vector2Int son incorrectas, se producirá un error, por lo que aquí usamos el bloque de omisión de la excepción try catch , que ayudará a evitar la excepción y no " colgar " toda la aplicación con un error.

A continuación, veremos el ciclo en todas las direcciones e intentaremos encontrar puntos vecinos en el método OnDrawGizmos y, lo más importante, no olvidemos considerar la permeabilidad del punto.


Ahora puedes iniciar el juego de forma segura y ver qué sucedió.


En este ejemplo, construimos solo el gráfico en sí mediante tareas, pero esto es lo que sucedió después de que atornillé en el sistema el algoritmo A * , que también utiliza el sistema Job para encontrar la ruta, la fuente al final del artículo .


Por lo tanto, puede utilizar el nuevo sistema de tareas para sus objetivos y crear sistemas interesantes sin mucho esfuerzo.

Como en el artículo anterior, el sistema de tareas se usa sin ECS , pero si usa este sistema junto con ECS , puede lograr resultados simplemente sorprendentes en ganancias de rendimiento. Buena suerte !

Buscador de ruta Fuente del proyecto