Qual rota será a mais segura, onde estão os inimigos e qual é o kit de primeiros socorros mais próximo? Todos esses problemas freqüentemente encontrados nas relações espaciais podem ser efetivamente resolvidos usando partições matemáticas chamadas "diagramas de Voronoi". Nesta postagem, você aprenderá como analisar cartões de jogo e receber informações que garantem o realismo e o sucesso da inteligência artificial.
Relação espacial
Uma relação espacial é qualquer informação que descreva como um objeto no espaço está relacionado a outro. Exemplos: a distância entre eles, a área coberta por cada um deles espaço e a interseção dessas áreas, o número de objetos localizados em uma área.
Tais relacionamentos são constantemente usados em videogames e podem fornecer informações de IA muito úteis, bem como para o próprio jogador.
Voronoi tem uma resposta
O diagrama de Voronoi descreve a relação espacial entre pontos espaçados ou seus vizinhos mais próximos. Este é um conjunto de polígonos conectados obtidos de pontos ou locais. Cada linha da "área" de Voronoi está localizada no meio entre dois pontos.
Para entender, dê uma olhada na imagem:
Como você pode ver, cada linha está exatamente no meio, entre dois pontos, e todas elas estão conectadas no centro. Adicione mais alguns pontos à cena e veja o que acontece:
A imagem se tornou mais interessante! Já temos áreas reais.
O que cada uma das áreas nos diz? Sabemos que estar na área tem a garantia de estar localizado mais próximo de um ponto, que também está na área. Isso nos diz muito sobre o que está próximo; essa é a relação espacial fundamental nos diagramas de Voronoi.
Vire Voronoi do avesso: triangulação em Delaunay
O sistema oposto ao diagrama de Voronoi é chamado triangulação de Delaunay. Este diagrama consiste em linhas de cada ponto até seus vizinhos mais próximos, e cada linha é perpendicular à aresta de Voronoi que cruza. Aqui está o que parece:
Branco marca a linha Delaunay. Cada linha de Delaunay corresponde a uma e apenas uma borda Voronoi. A princípio, parece que alguns deles atravessam várias arestas, mas olhando atentamente, você perceberá que isso não é verdade.
Na figura, a linha verde de Delaunay corresponde à costela rosa de Voronoi. Imagine que a costela rosa vai além e você vê que elas se cruzam.
Graças à triangulação de Delaunay, vemos que, em vez de polígonos, agora temos muitos triângulos. Isso é incrivelmente útil porque dividimos a área em triângulos que podem ser renderizados. Esta técnica pode ser usada para mosaico ou triangulação de figuras. Ótimo!
Além disso, essa é uma ótima maneira de criar um gráfico a partir de vários pontos, caso desejemos passar de um ponto para outro. Por exemplo, pontos podem indicar cidades.
Estrutura de dados Voronoi
Já sabemos como é o diagrama de Voronoi; Agora vamos ver como ficará sua estrutura de dados. Primeiro, precisamos salvar os pontos que são a base do diagrama de Voronoi:
class VoronoiPoint { float x float y VoronoiRegion* region }
Cada
VoronoiPoint possui um local
(x, y) e um link para a área em que está localizado.
Em seguida, precisamos descrever o
VoronoiRegion :
class VoronoiRegion { VoronoiPoint* point Edge *edges[]
A área armazena um link para seu
VoronoiPoint , bem como uma lista de bordas do
VoronoiEdges .
Vamos ver como é o
VoronoiEdges :
class VoronoiEdge { VoronoiPoint* pointA VoronoiPoint* pointB float distance
A aresta conhece dois pontos que a definem, bem como a distância entre eles. Para exibição visual, bem como para construir a forma da região poligonal, precisamos armazenar os pontos inicial e final da aresta.
E isso é tudo. Com essas informações, podemos facilmente criar um diagrama de Voronoi. Abaixo, aprenderemos como o diagrama de Voronoi é gerado. Mas, por enquanto, vejamos alguns exemplos de como esses dados podem ser usados.
Encontre o seu armário de remédios mais próximo
Mais uma vez, observe o diagrama de Voronoi para obter pontos.
Se cada ponto denota um kit de primeiros socorros, podemos determinar rapidamente onde está o mais próximo de nós, mas primeiro precisamos determinar a área em que estamos. Os diagramas de Voronoi não fornecem uma maneira eficaz de definir uma região; no entanto, para acelerar a pesquisa, podemos armazenar um link para cada região na
árvore do
quadrante ou na
árvore-R . E tendo aprendido a região, seremos capazes de reconhecer seus vizinhos e os vizinhos de seus vizinhos.
Por exemplo, se não houver mais kits de primeiros socorros em sua área, será necessário encontrar um caminho para outro mais próximo. A partir da estrutura de dados e do pseudo-código mostrado acima, podemos entender que, conhecendo a região, podemos reconhecer suas bordas. E com a ajuda dessas costelas, podemos ter vizinhos. Vamos pegar o vizinho mais próximo e ver se há um kit de primeiros socorros.
Você também pode aplicar a triangulação de Delaunay aqui. Consiste em linhas entre os kits de primeiros socorros. Em seguida, você pode contorná-lo usando o algoritmo de busca de caminho A * para encontrar o kit de primeiros socorros mais próximo.
Procure uma rota segura
Substitua todos os kits de primeiros socorros por torres de vigia inimigas. Você precisa encontrar a rota mais segura entre eles para não ser pego. A maneira padrão de passagem de gráfico em videogames é usar
o algoritmo A * . Como o diagrama Voronoi é um gráfico, é muito fácil implementar uma pesquisa. Nós apenas precisamos do algoritmo A *, que suporta estruturas gerais de gráfico; planejar com antecedência e isso o ajudará no futuro.
Depois de preparar o gráfico, você precisa atribuir peso a cada aresta. Para nós, o valor do peso será a distância dessas torres de vigia, e você pode obtê-lo diretamente da estrutura de dados: cada
VoronoiEdge já sabe sua distância entre dois pontos. Normalmente, quanto menor o valor na borda A *, melhor, mas, no nosso caso, maior o valor, porque indica a distância da torre.
É assim que o gráfico inicial se parece se queremos passar do ponto A para o ponto B:
Aplicando peso a cada aresta, veremos qual rota é melhor escolher:
As nervuras vermelhas indicam os contatos mais próximos com as torres. Laranja indica os mais longos; amarelo ainda mais distante e, finalmente, verde - o mais seguro. Depois de executar A * com esses pesos, obtemos o seguinte caminho:
Com esse uso da balança, não será
o mais rápido , mas
o caminho
mais seguro será escolhido, e é disso que precisamos. A IA deve aderir a esse caminho e não se desviar dele!
Você pode dar outro passo para
garantir um caminho seguro: elimine todas as arestas mais próximas que a distância mínima segura. Por exemplo, se cada torre de vigia tem um raio de visibilidade de 30 unidades, todas as arestas, a distância em que os pontos são mais curtos, podem ser removidas do gráfico e não ignoradas.
Você também pode usar esse método para encontrar a rota mais ampla para unidades grandes que não conseguem passar por gargalos. Cada aresta tem uma distância entre dois pontos, então sabemos se eles podem passar nesse espaço.
Você também pode executar a operação oposta - use o diagrama de triangulação de Delaunay e obtenha as linhas provenientes de cada torre de vigia. A IA dos guardas poderá determinar rapidamente quais outras torres estão próximas e, se necessário, ir em seu auxílio.
Procure um conjunto de itens compactado
Suponha que precisamos soltar um pacote de catnip de um avião para um monte de focas sentadas no chão. Onde é a melhor maneira de largá-lo para que o maior número de gatos possa usá-lo? Isso pode ser extremamente caro. Felizmente, porém, podemos fazer uma suposição razoável usando a triangulação de Delaunay.
Dica: não esqueça que a triangulação de Delaunay é apenas o inverso do diagrama de Voronoi. É formado conectando cada ponto Voronoi com pontos vizinhos obtidos da lista de arestas.
Com esta coleção de triângulos, você pode explorar a área coberta por cada um dos triângulos. Se encontrarmos o triângulo com a menor área, teremos três pontos mais próximos, ou gatos. Pode não ser o cluster médio mais denso na superfície, mas será uma boa suposição. Se pudéssemos descartar algumas parcelas com hortelã, marcaríamos apenas os triângulos já selecionados e passaríamos para os próximos em tamanho crescente.
A designação dessas áreas também é chamada de
círculos circunscritos da triangulação de Delaunay. Cada círculo é o maior círculo que pode caber nos pontos do triângulo. Aqui está uma imagem dos círculos circunscritos para o diagrama de Voronoi:
Você pode usar o centro exato dos círculos para determinar o centro da área para onde o catnip é enviado. De fato, o raio do círculo é uma maneira mais adequada de determinar o melhor triângulo a dobrar em vez da área do triângulo, especialmente se os dois pontos do triângulo estão muito próximos um do outro e o terceiro está longe; então obtemos um triângulo muito nítido com uma área pequena, mas os pontos que o definem são realmente muito distantes.
Implementação de diagramas de Voronoi
Existem várias maneiras de gerar diagramas de Voronoi, e a escolha do método usado depende do horário em que recebemos os dados.
Algoritmo da Fortuna
O caminho mais rápido é chamado
algoritmo da Fortune . É executado em
O(n log(n)) e requer que todos os pontos usados para gerar o gráfico sejam conhecidos no momento em que a geração começa. Se você adicionar novos pontos posteriormente, precisará gerar novamente o gráfico inteiro. Se houver alguns pontos, isso pode não causar problemas, mas se você tiver 100 mil deles, isso poderá levar muito tempo!
A implementação desse algoritmo não é trivial. Parábolas cruzadas e casos especiais. No entanto, este é o método mais rápido. Felizmente, existem muitas implementações desse algoritmo de código aberto que você pode usar, e forneci links para eles abaixo.
Vamos ver como isso funciona.
O algoritmo consiste em deslizar uma linha (vertical ou horizontal) sobre uma área com pontos. Quando ele encontra um ponto, ele começa a desenhar uma parábola, que continua com uma linha arrebatadora. Aqui está a animação deste processo:
Parábolas que se cruzam formam as costelas de Voronoi. Mas por que parábolas?
Para entender isso, imagine cada ponto como contendo um balão inflável que incha até colidir com outra bola. Você pode transferir essa ideia para círculos que se expandem em um plano 2D. Faremos outra bola avançar e colocaremos em cada ponto um cone invertido com um ângulo de inclinação de 45 graus, aumentando para o infinito. Imagine uma linha de varredura na forma de uma linha, também a 45 graus, que desliza até ela colidir com os cones. Como o plano e os cones estão localizados no mesmo ângulo, quando se cruzam, formam parábolas.
Crescendo, os cones, mais cedo ou mais tarde, se cruzam com um ou mais outros cones. Se olharmos para a interseção dos cones ou círculos, obtemos linhas retas das arestas de Voronoi. Na figura, a linha vermelha indica a interseção dos cones. Se os cones crescerem ainda mais (verticalmente até o infinito), a linha vermelha continuará a se esticar.
Quando o avião desliza e o primeiro contato com o cone ocorre, a linha resultante será assim:
Com o movimento adicional do avião ao longo dos cones, veremos como as parábolas se formam:
O avião continua a se mover pela cena. Para cada ponto encontrado, ele examina os pontos vizinhos na linha de varredura que já possuem parábolas e inicia uma nova parábola nesse ponto. Ela continua a seguir em frente e a crescer até que essa nova parábola comece a se sobrepor, não à que foi sobreposta anteriormente. Então essa parábola anterior se fecha. Este é o ponto no qual as linhas de três pontos de Voronoi se encontram.
Como afirmado acima, isso é bastante difícil de entender, portanto, aqui estão os links para implementações de código aberto que você pode usar e aprender:
Inserção Incremental de Triângulos
Outro método é inserir incrementalmente um ponto de cada vez, começando com um triângulo base de três pontos fora da área possível de todos os outros pontos. Este método é executado com
O(n^2) e não requer todos os pontos no momento da geração.
Quando você insere um novo ponto, ele define a área existente na qual ele cai. Essa área é subdividida e novas áreas são criadas.
Aqui está um exemplo de código aberto para usar e aprender:
Conclusão
Agora você deve imaginar o que os diagramas de Voronoi podem dar ao seu jogo e à sua IA. Se você tiver um gráfico adequadamente estruturado de nós e arestas, poderá solicitar informações importantes para que todos obtenham seus kits de primeiros socorros, catnip e passem pelas torres inimigas.