¡Bienvenido al Equipo de Algoritmos Graciosos!
Como experimento, decidimos mantener "diarios" de desarrolladores en los que compartiremos experiencias y destacaremos algunos resultados interesantes de nuestros experimentos. Este es nuestro primer artículo sobre el proyecto "Pathfinder 3D", un activo para el motor del juego Unity, que le permite buscar rutas en un espacio tridimensional. En él, hablaremos sobre el camino desde el origen de la idea hasta un producto completo y sobre algunos de los problemas que encontramos. Este material será útil para las personas que desean comenzar su proyecto y apoyarlo en el futuro, así como para aquellos que desean implementar una búsqueda de un camino en el espacio.
Un equipo de dos personas comenzó a trabajar en el activo. El primero tenía algunos desarrollos que permitían acelerar el proceso de encontrar el camino más corto en gráficos complejos lo suficiente como para trabajar en tiempo real, y un deseo de encontrar una aplicación práctica para ellos, el segundo tenía algo de experiencia trabajando con Unity y estaba buscando una idea para una startup. Dado que a menudo se comunicaban entre sí, no es sorprendente que en algún momento surgiera la idea de la posibilidad de crear un activo para buscar un camino en el espacio tridimensional.
Al estudiar el catálogo de activos de Unity, se encontraron muchas soluciones para encontrar la ruta en un espacio bidimensional, pero no una en tridimensional. Se hizo evidente que esta era una gran oportunidad para ingresar al mercado de complementos de software de Unity, especialmente teniendo en cuenta la visibilidad y el entretenimiento del resultado esperado.
El objetivo era implementar directamente la búsqueda de una ruta en el espacio tridimensional y las capacidades típicas de las soluciones existentes para encontrar una ruta en el espacio bidimensional. Comenzamos a trabajar: uno desarrolló directamente el mecanismo de búsqueda de ruta, las segundas clases y métodos para administrar el proceso de búsqueda de ruta, las interfaces de configuración, las escenas de prueba, la documentación, el sitio del proyecto, y también participó en el registro y la configuración de las cuentas de servicio necesarias para vender el activo.
Poco después del inicio del trabajo, quedó claro que se necesitaba algún tipo de recurso común para que el equipo tomara notas: una lista de tareas y problemas que deben resolverse, información sobre las decisiones tomadas, ideas interesantes y resultados de investigación en el futuro. Después de analizar las soluciones existentes, nos detuvimos en
Trello , debido a su funcionalidad, simplicidad, conveniencia y una apariencia agradable. Como ha demostrado la práctica, este servicio es muy conveniente para equipos pequeños. Si el equipo tiene más de 5 personas, recomendamos utilizar un sistema de gestión de proyectos completo.
A continuación, describimos las decisiones tomadas durante el desarrollo de la primera versión del activo y la lógica que seguimos al tomarlas. Las personas que tienen experiencia con Unity y están familiarizadas con los algoritmos de búsqueda de rutas comprenderán de inmediato dónde surgirán los problemas en el futuro. En estos lugares, utilizamos una solución simple para reducir el tiempo de desarrollo hasta que se recibió la primera versión de trabajo del activo, para no quedar empantanado, porque el entusiasmo es limitado e inconstante. Por lo tanto, tratamos una de las razones más comunes para cerrar tales startups, debido a que muchos proyectos mueren sin nacer. Todas las áreas problemáticas se corrigieron después de la publicación del activo.
Para encontrar la ruta, se eligió el algoritmo
A * (una estrella) debido a su alta velocidad de operación en grandes espacios abiertos. La mayoría de los algoritmos de búsqueda de ruta funcionan en gráficos representados por una matriz discreta. Sería posible construir esta matriz de antemano, pero el proceso de una sola vez de su construcción en un espacio tridimensional con obstáculos en ese momento parecía una tarea bastante difícil. Además, no estaba claro cómo hacer esto sin sacrificar el rendimiento, ya que en el momento del comienzo del trabajo en el activo no había experiencia con procesos en segundo plano y subprocesos múltiples en Unity, así como con subprocesos múltiples en general. El gráfico se formó en tiempo real sondeando el espacio con rayos físicos (Physics.BoxCast) en la dirección de la búsqueda. Las trayectorias encontradas se redujeron a rotas con menos puntos intermedios, y luego se suavizaron mediante splines.
La principal dificultad era la imposibilidad de usar los métodos físicos del motor de forma asíncrona, ya que pueden funcionar exclusivamente en el hilo principal. En escenas no demasiado complejas, el uso de la función de búsqueda al mismo tiempo por no más de veinte agentes no afectó significativamente la velocidad de fotogramas. Para deshacerse de las fuertes y raras reducciones de FPS, la carga computacional se espació en el tiempo usando corutinas. Esto ralentizó la búsqueda, pero no significativamente.
Antes de enviar un activo para moderación, debe ordenar el código y redactar documentación detallada, de acuerdo con los
requisitos , registrarse y configurar el correo de soporte. También es aconsejable crear un sitio web del proyecto donde se muestren convenientemente noticias y demostraciones de desarrollo. Esta será una gran ventaja tanto durante el paso de la moderación, como al estudiar su activo por el usuario antes de comprar.
BeGet nos encargó los servicios de alojamiento y correo, ya que en ese momento ofrecía las ofertas más ventajosas y nos costaba 1000 r / año.
La moderación de activos duró 22 días y pasó la primera vez, ya que abordamos con mucho cuidado la documentación y el diseño de la página de activos en la tienda Unity. Después de la publicación, el activo cayó inmediatamente en el primer lugar en la categoría Scripting / AI. A partir de ese momento, comenzaron a llegar cartas al correo de soporte pidiendo ayuda para resolver ciertos problemas. A veces unos pocos por día, a veces no un mes. Si usted hace un promedio, entonces durante un mes 2 personas hicieron preguntas, cuya correspondencia tomó un total de 2-3 horas. No tanto, pero debe tenerse en cuenta que, independientemente de su carga de trabajo actual, debe responder muy rápidamente para que los usuarios enojados no escriban malas críticas sobre el producto, sino que, por el contrario, entusiasmados con el soporte de calidad, dejen comentarios positivos. Además, muchas preguntas llegan al correo como "¿funcionará su activo si ...". Dichas cartas tampoco deben ignorarse, ya que este es un comprador potencial que puede irse.
Cuando se recibieron las quejas de los primeros compradores, quedó claro que muchos usuarios usan activos en escenas complejas que tienen la configuración de un laberinto u otra cavidad conectada. En tales proyectos, nuestro esquema de búsqueda de ruta, basado en la verificación de colisiones, e incluso en la corriente principal, no fue lo suficientemente efectivo. Por lo tanto, comenzamos a implementar la construcción temprana del gráfico para que fuera posible buscar la ruta en el flujo lateral sin usar la física y acceder a los objetos de la escena.
La discreción del espacio tridimensional lo divide en cubos. El almacenamiento de información sobre todos los cubos de partición es redundante y requiere mucha memoria. Por lo tanto, es lógico almacenar solo las coordenadas de las células intransitables, lo cual se hizo.
Los obstáculos del juego son figuras poligonales y consisten en triángulos. Para tener en cuenta los obstáculos en el gráfico de búsqueda, debe encontrar todos los cubos de la partición que se cruzan con cualquier triángulo de cualquier obstáculo. Ya en esta etapa, se estableció la posibilidad de eliminar dinámicamente y agregar obstáculos al escenario, y no solo se guardaron las coordenadas de los cubos ocupados, sino también los identificadores de los obstáculos que estaban en ellos. Ahora es posible construir un gráfico de navegación antes del inicio del proceso del juego y, debido a la eliminación de una gran cantidad de cálculos complejos durante la búsqueda de una ruta, más de doscientos agentes podrían hacerlo simultáneamente sin sacrificar el rendimiento.
Otro problema conocido por nosotros también se hizo sentir: el algoritmo A * y sus modificaciones funcionan extremadamente mal en espacios confinados en gráficos de alta potencia. Dado que su algoritmo prefiere la dirección de la ruta hacia el punto objetivo, cualquier punto muerto que conduzca al objetivo ralentizó en gran medida la búsqueda de la ruta, ya que antes de elegir una dirección diferente de "germinación", el algoritmo primero "llena" todo el espacio dentro del callejón sin salida.
En tales situaciones, el
algoritmo de búsqueda de ondas (Algoritmo de Lee) demuestra ser muy efectivo debido al
menor número de operaciones requeridas para "llenar" el espacio. Por lo tanto, se agregó al activo como una alternativa. Al realizar pruebas en un escenario que es un laberinto, el tiempo de búsqueda de la ruta se redujo en más de 30 veces.
Para acelerar el procesamiento preliminar de la escena y encontrar el camino hacia el activo, se agregó la posibilidad de ejecución paralela de procesos, pero la eficiencia del paralelismo fue extremadamente baja, debido al hecho de que cuando se trabaja con un contenedor que almacena las coordenadas de las celdas ocupadas, es necesario sincronizar los flujos, que se realizó utilizando mutexes, ya que las colecciones competitivas y muchas otras herramientas para garantizar una sincronización eficiente
se implementaron solo en el estándar .NET Framework 4.5, y en Unity, la versión .NE se utilizó hasta la versión 2018. Marco T 3.5. Intentamos resolver este problema usando las herramientas disponibles, pero tenían un rendimiento muy mediocre, y solo obtuvimos el resultado deseado después de cambiar a la versión Unity 2018. El uso de colecciones competitivas también abrió la posibilidad de realizar el cambio dinámico de obstáculos en la escena.
En una cierta etapa, comenzaron a surgir desacuerdos en el equipo con respecto a la distribución de ganancias, y una tercera persona se unió al equipo, quien introdujo un sistema para evaluar la inversión de tiempo de cada miembro del equipo, y también comenzó a participar en la inspección y prueba del código, lo que mejoró significativamente la calidad del producto.
El sistema para estimar los costos de tiempo en este momento se realiza en forma de una tabla de Excel y es un sistema automatizado en el que una vez al mes es necesario ingresar información sobre ventas y tareas completadas durante el último mes. Los miembros del equipo deben evaluar cuánto tiempo necesitarían para resolver un problema en particular. Por lo tanto, al evaluar la complejidad temporal de las tareas, se tiene en cuenta la velocidad de cada participante. Una sobreestimación o subestimación anormal por parte de uno de los participantes se hace evidente de inmediato a partir de las estadísticas acumuladas de sus evaluaciones anteriores. Y, en ausencia de una explicación satisfactoria, este tema lo decide todo el equipo. Este enfoque demostró ser bueno durante seis meses de uso y permitió recopilar estadísticas interesantes. No encontramos una solución gratuita ya preparada que ofrezca las características descritas. Por lo tanto, en este momento, para equipos pequeños, la implementación en forma de tablas de Excel nos parece óptima. Para equipos relativamente grandes, lo más probable es que tenga que diseñar su base de datos, desarrollar la parte del servidor y el cliente, o implementar una extensión para uno de los sistemas de gestión de proyectos existentes.
Para resumir. Ha pasado un año desde el inicio del desarrollo hasta la primera versión con la funcionalidad mínima necesaria y el rendimiento suficiente para su uso en proyectos reales. Se pasaron otros seis meses para mejorar el rendimiento e implementar el trabajo de subprocesos múltiples del activo. Por el momento, estimamos los costos de tiempo para este proyecto en 1065 horas hombre (esta es una estimación bastante optimista), y la ganancia promedio para el mes es de 9.5t. Es fácil calcular que el costo promedio de una hora de trabajo en este momento es de aproximadamente 160 rublos, lo que no es tanto. Sin embargo, lo principal en este evento es la experiencia adquirida por cada participante. Incluyendo experiencia en trabajo en equipo y experiencia en soporte de productos de software. El proyecto puede considerarse exitoso.
Ahora nuestro equipo ha comenzado a implementar funcionalidades adicionales útiles: verificación de accesibilidad algorítmica; la capacidad de asignar objetos del juego a portales; soporte dinámico de obstáculos; Navegación local entre agentes para evitar colisiones y planificar rutas locales.
Esperamos que este material ayude a alguien a llevar su proyecto a la meta.