Bem-vindo à equipe de algoritmos graciosos!
Como experimento, decidimos manter “diários” de desenvolvedores nos quais compartilharemos experiências e destacaremos alguns resultados interessantes de nossos experimentos. Este é o nosso artigo de estreia no projeto "Pathfinder 3D" - um ativo para o mecanismo de jogo Unity, que permite pesquisar caminhos no espaço tridimensional. Nele, falaremos sobre o caminho desde a origem da idéia até um produto completo e sobre alguns dos problemas que encontramos. Este material será útil para pessoas que desejam iniciar seu projeto e apoiá-lo no futuro, bem como para aqueles que desejam implementar uma busca por um caminho no espaço.
Uma equipe de duas pessoas começou a trabalhar no ativo. O primeiro teve alguns desenvolvimentos que permitiram acelerar o processo de encontrar o caminho mais curto em gráficos complexos o suficiente para funcionar em tempo real e o desejo de encontrar uma aplicação prática para eles, o segundo possuía alguma experiência em trabalhar com o Unity e estava procurando uma ideia para uma startup. Como eles frequentemente se comunicam, não é de surpreender que em algum momento surgiu a idéia da possibilidade de criar um ativo para procurar um caminho no espaço tridimensional.
Ao estudar o catálogo de ativos do Unity, foram encontradas muitas soluções para encontrar o caminho no espaço bidimensional, mas não um no tridimensional. Tornou-se óbvio que essa era uma grande oportunidade para entrar no mercado de complementos de software Unity, principalmente considerando a visibilidade e o entretenimento do resultado esperado.
O objetivo era implementar diretamente a busca por um caminho no espaço tridimensional e os recursos típicos das soluções existentes para encontrar um caminho no espaço bidimensional. Começamos a trabalhar: desenvolvemos diretamente o mecanismo de busca de caminhos, as segundas classes e métodos para gerenciar o processo de busca de caminhos, interfaces de configuração, cenas de teste, documentação, o site do projeto e também estávamos envolvidos no registro e configuração de contas de serviço necessárias para a venda do ativo.
Logo após o início do trabalho, ficou claro que era necessário algum recurso comum para a equipe fazer anotações: uma lista de tarefas e problemas que precisavam ser resolvidos, informações sobre as decisões tomadas, idéias e resultados de pesquisa interessantes no futuro. Após analisar as soluções existentes, paramos no
Trello , devido à sua funcionalidade, simplicidade, conveniência e aparência agradável. Como a prática demonstrou, este serviço é muito conveniente para equipes pequenas. Se a equipe tiver mais de 5 pessoas, recomendamos o uso de um sistema completo de gerenciamento de projetos.
A seguir, descrevemos as decisões tomadas durante o desenvolvimento da primeira versão do ativo e a lógica que seguimos ao tomá-las. As pessoas que têm experiência com o Unity e estão familiarizadas com os algoritmos de localização de caminhos entenderão imediatamente onde os problemas surgirão no futuro. Nesses locais, usamos uma solução simples para reduzir o tempo de desenvolvimento até que a primeira versão de trabalho do ativo fosse recebida, para não ficarmos atolados, porque o entusiasmo é limitado e inconstante. Assim, lidamos com um dos motivos mais comuns para fechar essas startups, por causa dos quais muitos projetos morrem sem nascer. Todas as áreas problemáticas foram corrigidas após a publicação do ativo.
Para encontrar o caminho, o algoritmo
A * (estrela A) foi escolhido devido à sua alta velocidade de operação em grandes espaços abertos. A maioria dos algoritmos de busca de caminho funciona em gráficos representados por uma matriz discreta. Seria possível construir essa matriz antecipadamente, mas o processo único de sua construção no espaço tridimensional com obstáculos parecia na época uma tarefa bastante difícil. Além disso, não ficou claro como fazer isso sem sacrificar o desempenho, pois no início do trabalho no ativo não havia experiência com processos em segundo plano e multithreading no Unity, bem como com multithreading em geral. O gráfico foi formado em tempo real, sondando o espaço com raios físicos (Physics.BoxCast) na direção da pesquisa. As trajetórias encontradas foram reduzidas a quebradas com menos pontos intermediários e depois suavizadas por splines.
A principal dificuldade era a impossibilidade de usar os métodos físicos do mecanismo de forma assíncrona, pois eles podem trabalhar exclusivamente no segmento principal. Em cenas não muito complexas, o uso da função de busca ao mesmo tempo por não mais de vinte agentes não afetou significativamente a taxa de quadros. Para se livrar de raros rebaixamentos fortes do FPS, a carga computacional foi espaçada no tempo usando corotinas. Isso atrasou a pesquisa, mas não significativamente.
Antes de enviar um ativo para moderação, é necessário colocar o código em ordem e elaborar documentação detalhada, de acordo com os
requisitos , registrar e configurar o correio de suporte. Também é aconselhável criar um site do projeto no qual notícias e demonstrações de desenvolvimento sejam exibidas convenientemente. Essa será uma grande vantagem, tanto durante a aprovação da moderação, quanto no estudo de seu ativo pelo usuário antes da compra. Os serviços de hospedagem e correio foram solicitados por nós à
BeGet , pois na época ofereciam as ofertas mais vantajosas e nos custavam 1000r / ano.
A moderação de ativos durou 22 dias e passou pela primeira vez, pois abordamos com muito cuidado a documentação e o design da página de ativos na loja Unity. Após a publicação, o ativo caiu imediatamente em primeiro lugar na categoria Script / AI. A partir desse momento, começaram a chegar cartas ao correio de suporte pedindo ajuda para resolver certos problemas. Às vezes, alguns por dia, às vezes não um mês. Se você calcula a média, por um mês 2 pessoas fizeram perguntas, correspondências com as quais levaram um total de 2-3 horas. Não tanto, mas lembre-se de que, independentemente da sua carga de trabalho atual, você precisa responder muito rapidamente para que usuários irritados não escrevam críticas ruins sobre o produto, mas, pelo contrário, entusiasmados com o suporte de qualidade, deixem comentários positivos. Além disso, muitas perguntas chegam ao correio como "seu ativo funcionará se ...". Tais cartas também não devem ser ignoradas, porque este é um potencial comprador que pode sair.
Como as reclamações dos primeiros compradores foram recebidas, ficou claro que muitos usuários usam ativos em cenas complexas que têm a configuração de um labirinto ou outra cavidade conectada. Nesses projetos, nosso esquema de busca de caminhos, com base na verificação de colisões, e mesmo no fluxo principal, não foi suficientemente eficaz. Portanto, começamos a implementar a construção inicial do gráfico para que fosse possível procurar o caminho no fluxo lateral sem usar física e acessar objetos de cena.
A discretização do espaço tridimensional o divide em cubos. O armazenamento de informações sobre todos os cubos de partição é redundante e consome muita memória. Portanto, é lógico armazenar apenas as coordenadas das células intransitáveis, o que foi feito.
Os obstáculos do jogo são figuras poligonais e consistem em triângulos. Para explicar os obstáculos no gráfico de pesquisa, você deve encontrar todos os cubos da partição que cruzam qualquer triângulo de qualquer obstáculo. Já nesta fase, havia a possibilidade de remover dinamicamente e adicionar obstáculos ao palco, e não apenas as coordenadas dos cubos ocupados foram salvas, mas também os identificadores dos obstáculos que estavam neles. Agora é possível criar um gráfico de navegação antes do início do processo do jogo e, devido à eliminação de um grande número de cálculos complexos durante a busca por um caminho, mais de duzentos agentes poderiam fazê-lo simultaneamente sem sacrificar o desempenho.
Outro problema conhecido por nós também se fez sentir: o algoritmo A * e suas modificações funcionam extremamente mal em espaços confinados em gráficos de alta potência. Como o algoritmo deles prefere a direção da rota para se aproximar do ponto de destino, qualquer conflito que leva ao alvo diminui bastante a busca por um caminho, pois antes de escolher uma direção diferente de "brotamento", o algoritmo primeiro "preenche" todo o espaço dentro do beco sem saída.
Nessas situações, o
algoritmo de busca por ondas (algoritmo de Lee) mostra-se muito eficaz devido ao
menor número de operações necessárias para "preencher" o espaço. Portanto, foi adicionado ao ativo como uma alternativa. Ao testar em um palco que é um labirinto, o tempo de pesquisa para o caminho foi reduzido em mais de 30 vezes.
Para agilizar o processamento preliminar da cena e encontrar o caminho para o ativo, foi adicionada a possibilidade de execução paralela de processos, mas a eficiência do paralelismo foi extremamente baixa, devido ao fato de que, ao trabalhar com um contêiner que armazena as coordenadas das células ocupadas, é necessário sincronizar os fluxos, que foram realizados usando mutexes, uma vez que coleções competitivas e muitas outras ferramentas para garantir a sincronização eficiente
foram implementadas apenas no padrão .NET Framework 4.5 e no Unity, a versão .NE foi usada até a versão 2018. T Framework 3.5. Tentamos resolver esse problema usando as ferramentas disponíveis, mas eles tinham um desempenho muito medíocre e só obtivemos o resultado desejado depois de mudar para a versão 2018 do Unity. O uso de coleções competitivas também abriu a possibilidade de realizar a mudança dinâmica de obstáculos no cenário.
Em um certo estágio, começaram a surgir divergências na equipe em relação à distribuição de lucros, e uma terceira pessoa entrou na equipe, que introduziu um sistema para avaliar o investimento de tempo de cada membro da equipe e também começou a se envolver em inspeção e teste de código, o que melhorava significativamente a qualidade do produto.
O sistema para estimar custos de tempo no momento é feito na forma de uma tabela do Excel e é um sistema automatizado no qual uma vez por mês é necessário inserir informações sobre vendas e tarefas concluídas no mês passado. Os membros da equipe precisam avaliar quanto tempo precisariam para resolver um problema específico. Assim, ao avaliar a complexidade do tempo das tarefas, a velocidade de cada participante é levada em consideração. Uma superestimação ou subestimação anormal por um dos participantes imediatamente se torna evidente a partir das estatísticas acumuladas de suas avaliações anteriores. E, na falta de uma explicação satisfatória, esse problema é decidido por toda a equipe. Essa abordagem mostrou-se boa por seis meses de uso e permitiu coletar estatísticas interessantes. Não encontramos uma solução gratuita pronta para fornecer os recursos descritos. Portanto, no momento, para equipes pequenas, a implementação na forma de tabelas do Excel nos parece ótima. Para equipes relativamente grandes, você provavelmente precisará projetar seu banco de dados, desenvolver a parte do servidor e o cliente ou implementar uma extensão para um dos sistemas de gerenciamento de projetos existentes.
Para resumir. Um ano se passou desde o início do desenvolvimento para a primeira versão com a funcionalidade mínima necessária e desempenho suficiente para uso em projetos reais. Mais seis meses foram gastos na melhoria do desempenho e na implementação do trabalho multithread do ativo. No momento, estimamos os custos de tempo para este projeto em 1065 horas-homem (essa é uma estimativa bastante otimista), e o lucro médio do mês é de 9,5 t. É fácil calcular que o custo médio de uma hora de trabalho no momento é de cerca de 160 rublos, o que não é muito. No entanto, o principal neste evento é a experiência adquirida por cada participante. Incluindo experiência de trabalho em equipe e experiência em suporte a produtos de software. O projeto pode ser considerado bem-sucedido.
Agora, nossa equipe começou a implementar funcionalidades úteis adicionais: verificação de acessibilidade algorítmica; a capacidade de atribuir objetos de jogo a portais; suporte dinâmico de obstáculos; Navegação local entre agentes para evitar colisões e planejar rotas locais.
Esperamos que este material ajude alguém a levar seu projeto para a linha de chegada.