Sistema de tarefas e caminho de pesquisa

Mapa

Em um artigo anterior, analisei o que é o novo sistema de tarefas, como funciona, como criar tarefas, preenchê-las com dados e executar cálculos multiencadeados e apenas expliquei brevemente onde você pode usar esse sistema. Neste artigo, tentarei analisar um exemplo específico de onde você pode usar esse sistema para obter mais desempenho.

Como o sistema foi originalmente desenvolvido com o objetivo de trabalhar com dados, é ótimo para resolver tarefas de localização de caminhos.

O Unity já possui um bom navegador NavMesh , mas não funciona em projetos 2D, embora existam muitas soluções prontas no mesmo ativo . Bem, e tentaremos criar não apenas um sistema que procure maneiras no mapa criado, mas tornar esse mapa dinâmico, para que toda vez que algo mude nele, o sistema criará um novo mapa, e tudo isso, é claro, calcularemos usando um novo sistema de tarefas, para não carregar o thread principal.


No exemplo, uma grade é construída no mapa, há um bot e um obstáculo. A grade é reconstruída toda vez que alteramos quaisquer propriedades do mapa, seja seu tamanho ou posição.

Para aviões, usei um SpriteRenderer simples, este componente possui uma excelente propriedade de limites com a qual você pode descobrir facilmente o tamanho do mapa.

Isso é basicamente tudo para começar, mas não vamos parar e começar imediatamente aos negócios.

Vamos começar com os scripts. E o primeiro é o script de obstrução de obstáculos .


Dentro da classe Obstacle , capturaremos todas as alterações nos obstáculos no mapa, por exemplo, alterando a posição ou o tamanho de um objeto.
Em seguida, você pode criar a classe de mapa Map , na qual a grade será construída, e herdá-la da classe Obstacle .


A classe Map também rastreará todas as alterações no mapa para reconstruir a grade, se necessário.

Para fazer isso, preencha a classe base Obstacle com todas as variáveis ​​e métodos necessários para controlar as alterações no objeto.


Aqui, a variável renderer terá uma referência ao componente SpriteRenderer , e as variáveis ​​tempSize e tempPos serão usadas para rastrear alterações no tamanho e na posição do objeto.

O método virtual Awake será usado para inicializar as variáveis, e o método virtual CheckChanges rastreará as alterações atuais no tamanho e posição do objeto e retornará um resultado booleano .

Por enquanto, vamos deixar o script Obstacle e seguir para o script Map map, onde também o preenchemos com os parâmetros necessários para o trabalho.


A variável nodeSize indicará o tamanho das células no mapa. Limitei seu tamanho de 0,1 a 1 para que as células na grade não sejam muito pequenas, mas também muito grandes. A variável de deslocamento será usada para recuar o mapa ao construir a grade, para que a grade não seja construída ao longo das bordas do mapa.

Como agora existem duas novas variáveis ​​no mapa, verifica-se que suas alterações também precisarão ser rastreadas. Para fazer isso, adicione algumas variáveis ​​e sobrecarregue o método CheckChanges na classe Map .


Feito. Agora você pode criar um sprite de mapa no palco e lançar um script de mapa nele.



Faremos o mesmo com um obstáculo - crie um sprite simples no palco e jogue o script Obstacle nele.



Agora, temos objetos de mapa e obstáculos no palco.

O script Map será responsável por rastrear todas as alterações no mapa, onde, no método Update , verificaremos cada quadro quanto às alterações.


Portanto, no método UpdateChanges, o mapa rastreará apenas suas alterações até o momento. Você pode até iniciar o jogo agora e tentar alterar o tamanho do mapa ou compensar o deslocamento para garantir que todas as alterações sejam rastreadas.

Agora você precisa acompanhar de alguma forma as mudanças dos obstáculos no mapa. Para fazer isso, colocaremos cada obstáculo em uma lista no mapa, que por sua vez atualizará cada quadro no método Update .

Na classe Mapa , crie uma lista de todos os obstáculos possíveis no mapa e alguns métodos estáticos para registrá-los.


No método estático RegisterObstacle , registraremos um novo obstáculo no mapa e o adicionaremos à lista, mas, antes de tudo, é importante considerar que o próprio mapa também é herdado da classe Obstacle e, portanto, devemos verificar se estamos tentando registrar o cartão como um obstáculo.

O método estático UnregisterObstacle , pelo contrário, elimina o obstáculo do mapa e o remove da lista quando permitimos que ele seja destruído.

Ao mesmo tempo, toda vez que adicionamos ou removemos um obstáculo do mapa, é necessário recriar o mapa em si; portanto, após a execução desses métodos estáticos, defina a variável requireRebuild como true .

Além disso, para ter acesso fácil ao script Map a partir de qualquer script, criei uma propriedade Instance estática que retornará para mim essa mesma instância do Map .

Agora, voltemos ao script Obstacle, onde registraremos um obstáculo no mapa.Para fazer isso, adicione alguns métodos OnEnable e OnDisable a ele.


Cada vez que criamos um novo obstáculo enquanto jogamos no mapa, ele será registrado automaticamente no método OnEnable , onde será levado em consideração ao criar uma nova grade e nos removeremos do mapa no método OnDisable quando ele for destruído ou desativado.

Resta apenas rastrear as alterações dos obstáculos no script Map no método CheckChanges sobrecarregado.


Agora temos um mapa, obstáculos - em geral, tudo o que você precisa para construir uma grade e agora pode passar para a coisa mais importante.

Malha

A grade, em sua forma mais simples, é uma matriz bidimensional de pontos. Para construí-lo, você precisa conhecer o tamanho do mapa e o tamanho dos pontos, depois de alguns cálculos, obtemos o número de pontos horizontal e verticalmente, esta é a nossa grade.

Existem muitas maneiras de encontrar um caminho em uma grade. Neste artigo, no entanto, o principal é entender como usar corretamente os recursos do sistema de tarefas; portanto, não considerarei opções diferentes para encontrar o caminho, suas vantagens e desvantagens, mas utilizarei a opção de pesquisa mais simples A * .

Nesse caso, todos os pontos na grade devem ter, além da posição, as coordenadas e a propriedade de permeabilidade.

Com permeabilidade, acho que tudo fica claro por que é necessário, mas as coordenadas indicam a ordem do ponto na grade, essas coordenadas não estão ligadas especificamente à posição do ponto no espaço. A imagem abaixo mostra uma grade simples, mostrando as diferenças de coordenadas de uma posição.


Por que as coordenadas?
O fato é que, em unidade, para indicar a posição de um objeto no espaço, é usado um flutuador simples que é muito impreciso e pode ser um número fracionário ou negativo; portanto, será difícil usá-lo para implementar uma pesquisa de caminho no mapa. As coordenadas são feitas na forma de um int claro, que sempre será positivo e com o qual é muito mais fácil trabalhar ao procurar pontos vizinhos.

Primeiro, vamos definir um objeto de ponto, essa será uma estrutura de nó simples.


Essa estrutura conterá a posição position na forma de Vector2 , onde, com essa variável, desenharemos um ponto no espaço. A variável de coordenadas de coords na forma de Vector2Int indicará as coordenadas de um ponto no mapa, e a variável id , seu número numérico de conta, usando-o, compararemos diferentes pontos na grade e verificaremos a existência de um ponto.

A perviedade do ponto será indicada na forma de sua propriedade booleana , mas como não podemos usar os tipos de dados conversíveis no sistema de tarefas, indicaremos sua perviedade na forma de um número int , para isso usei uma enumeração simples NodeType , em que: 0 não é um ponto passável, e 1 é aceitável.


Além disso, para facilitar o trabalho com um ponto, sobrecarregarei o método Equals para facilitar a comparação de pontos e também complementarei o método de verificação para a existência de um ponto.


Como o número de identificação do ponto na grade começará com 1 unidade, vou verificar a existência do ponto como uma condição para que sua identificação seja maior que 0.

Vá para a classe Map, onde prepararemos tudo para criar um mapa.
Já temos uma verificação para alterar os parâmetros do mapa, agora precisamos determinar como o processo de construção da grade será realizado. Para fazer isso, crie uma nova variável e vários métodos.


A propriedade reconstruir indicará se o processo de malha está em andamento. O método Rebuild coletará dados e tarefas para a construção da grade, o método OnRebuildStart iniciará o processo de criação da grade e o método OnRebuildFinish coletará dados das tarefas.

Agora vamos mudar um pouco o método UpdateChanges para que a condição da grade seja levada em consideração.


Como você pode ver agora no método UpdateChanges , há uma condição de que, enquanto a construção da malha antiga não está começando a começar a construir uma nova, e também no método Reconstruir , a primeira ação verifica se o processo de malha já está em andamento.

Resolução de problemas

Agora um pouco sobre o processo de construção de um mapa.
Como usaremos o sistema de tarefas e construiremos a grade em paralelo para construir o mapa, usei o tipo da tarefa IJobParallelFor , que será executada um certo número de vezes. Para não carregar o processo de construção com nenhuma tarefa separada, usaremos o conjunto de tarefas agrupadas em um JobHandle .

Na maioria das vezes, para construir uma grade, use dois ciclos aninhados um ao outro para criar, por exemplo, horizontal e verticalmente. Neste exemplo, também construiremos a grade horizontalmente e depois verticalmente. Para fazer isso, calculamos o número de pontos horizontais e verticais no método Rebuild , depois no método Rebuild percorremos o ciclo ao longo dos pontos verticais e vamos construir pontos horizontais em paralelo na tarefa. Para imaginar melhor o processo de criação, dê uma olhada na animação abaixo.


O número de pontos verticais indicará o número de tarefas, por sua vez, cada tarefa criará pontos apenas horizontalmente, após a conclusão de todas as tarefas, os pontos serão somados em uma lista. É por isso que preciso usar uma tarefa como IJobParallelFor para passar o índice do ponto na grade horizontalmente para o método Execute .

E, como temos a estrutura de pontos, agora você pode criar a estrutura da tarefa Job e herdá-la da interface IJobParallelFor , tudo é simples aqui.


Retornamos ao método Rebuild da classe Map , onde faremos os cálculos necessários para a medição da grade.


No método Rebuild , calculamos o tamanho exato do mapa mapSize , levando em consideração o recuo e, nas verticais , escrevemos o número de pontos verticalmente, e nas horizontais o número de pontos horizontalmente. Se o número de pontos verticais for 0, paramos de construir o mapa e chamamos o método OnRebuildFinish para concluir o processo. A variável de origem indicará o local de onde começaremos a construir a grade - no exemplo, este é o ponto inferior esquerdo no mapa.

Agora você pode ir para as tarefas e preenchê-las com dados.
Durante a construção da grade, a tarefa precisará de uma matriz NativeArray onde colocaremos os pontos, também porque temos obstáculos no mapa, também precisaremos passá-los para a tarefa, para isso usaremos outra matriz NativeArray e , em seguida, precisaremos do tamanho dos pontos no problema , a posição inicial de onde iremos construir os pontos, bem como as coordenadas iniciais da série.


Marquei a matriz de pontos com o atributo WriteOnly, pois na tarefa será necessário " gravar " os pontos recebidos na matriz, pelo contrário, a matriz de limites de obstáculos é marcada com o atributo ReadOnly, pois na tarefa apenas " leremos " dados dessa matriz.

Bem, por enquanto, vamos prosseguir com o cálculo dos pontos depois.

Agora, de volta à classe Map , onde denotamos todas as variáveis ​​envolvidas nas tarefas.
Aqui, primeiro, precisamos de um identificador global de tarefas, uma série de obstáculos na forma de NativeArray , uma lista de tarefas que conterá todos os pontos recebidos na grade e Dicionário com todas as coordenadas e pontos no mapa, para que seja mais conveniente procurá-las mais tarde.


Agora, novamente, retornamos ao método Rebuild e continuamos a construir a grade.
Primeiro, inicialize o conjunto de obstáculos dos limites para passá-lo à tarefa.


Aqui, criamos uma instância do NativeArray por meio de um novo construtor com três parâmetros. Examinei os dois primeiros parâmetros em um artigo anterior, mas o terceiro parâmetro nos ajudará a economizar um pouco de tempo criando uma matriz. O fato é que gravaremos dados na matriz imediatamente após sua criação, o que significa que não precisamos garantir que eles sejam limpos. Este parâmetro é útil para NativeArray, que será usado apenas no modo de leitura na tarefa.

E assim, então preenchemos a matriz de limites com dados.


Agora podemos começar a criar tarefas, para isso, percorreremos um ciclo por todas as linhas verticais da grade.


Para começar, em xPos e yPos , obtemos a posição horizontal inicial da série.


Em seguida, criamos um NativeArray simples onde os pontos da tarefa serão colocados, aqui para a matriz, você precisa especificar quantos pontos serão criados horizontalmente e o tipo de alocação Persistente , porque a tarefa pode demorar mais de um quadro.
Depois disso, crie a própria instância da tarefa Job , coloque as coordenadas iniciais da série startCoords , a posição inicial da série startPos , o tamanho dos pontos nodeSize , a matriz de obstáculos de limites e a própria matriz de pontos no final.
Resta apenas colocar a tarefa em controle e a lista de tarefas global.


Feito. Temos uma lista de tarefas e seu identificador comum, agora podemos executá-lo chamando seu método Complete no método OnRebuildStart .


Como a variável de reconstrução indicará que o processo de malha está em andamento, o próprio método UpdateChanges também deve especificar a condição em que esse processo terminará usando o identificador e sua propriedade IsCompleted .


Depois de concluir as tarefas, o método OnRebuildFinish será chamado onde já coletamos os pontos recebidos em uma lista geral do Dicionário e, o mais importante, para limpar os recursos ocupados.


Primeiro, limpamos o dicionário de nós dos pontos anteriores, depois usamos o loop foreach para classificar todos os pontos que recebemos das tarefas e os colocamos no dicionário de nós , onde a chave são as coordenadas ( NÃO a posição !) Do ponto e o valor é o próprio ponto. Com a ajuda deste dicionário, será mais fácil procurar pontos vizinhos no mapa. Após o preenchimento, limpamos a matriz do array usando o método Dispose e, no final, limpamos a própria lista de tarefas dos trabalhos .

Você também precisará limpar os limites dos obstáculos se ele tiver sido criado anteriormente.

Depois de todas essas ações, obtemos uma lista de todos os pontos no mapa e agora você pode desenhá-los no palco.


Para fazer isso, na classe Map , crie o método OnDrawGizmos onde desenharemos os pontos.


Agora, através do loop, desenhamos cada ponto.


Depois de todas essas ações, nosso mapa parece um pouco chato, para realmente obter uma grade, você precisa que os pontos sejam conectados um ao outro.


Para procurar pontos vizinhos, basta encontrar o ponto desejado por suas coordenadas em 8 direções; portanto, na classe Map , criaremos uma matriz estática simples de direções de Direções e o método de pesquisa de células por suas coordenadas GetNode .


O método GetNode retornará um ponto por coordenadas da lista de nós , mas você precisa fazer isso com cuidado, porque se as coordenadas Vector2Int estiverem incorretas, ocorrerá um erro; portanto, aqui usamos o bloco try catch exception , que ajudará a ignorar a exceção e não " travará " o aplicativo inteiro com um erro.

Em seguida, percorreremos um ciclo em todas as direções e tentaremos encontrar pontos vizinhos no método OnDrawGizmos e, o mais importante, não se esqueça de considerar a permeabilidade do ponto.


Agora você pode iniciar o jogo com segurança e ver o que aconteceu.


Neste exemplo, construímos apenas o próprio gráfico usando tarefas, mas foi o que aconteceu depois que eu parafusei no sistema o próprio algoritmo A * , que também usa o sistema Job para encontrar o caminho, a fonte no final do artigo .


Assim, você pode usar o novo sistema de tarefas para seus objetivos e criar sistemas interessantes sem muito esforço.

Como no artigo anterior, o sistema de tarefas é usado sem o ECS , mas se você usar esse sistema em conjunto com o ECS , poderá obter resultados simplesmente surpreendentes nos ganhos de desempenho. Boa sorte !

Origem do Projeto Path Finder