Como posso encontrar processualmente uma parede que separa dois ou mais pontos em um mapa baseado em grade?

8

Estou tentando gerar paredes que cortam um determinado ponto de outros pontos. A imagem em anexo mostra o tipo de coisa que eu procuro:

insira a descrição da imagem aqui

  1. Azul separado do vermelho.
  2. Azul separado de vermelho e amarelo.
  3. Azul separado do vermelho com obstruções de ladrilhos.
  4. Múltiplo Azul separado de vários Vermelhos.

Alguma idéia de como fazer isso?

IanLarson
fonte
11
Isso é um pouco amplo demais ... você quer minimizar o azul, ou talvez queira uma área igual, ou talvez a área não importe, mas queira minimizar o comprimento da parede, ou talvez tudo o que é irrelevante eo que realmente importa é encontrar uma solução rápida ... etc.
Theraot
11
Para dar a você, ou a outras pessoas, uma direção possível, isso parece relacionado a uma variante de "manhattan distance voronoi", dependendo da aparência que você está procurando ou apenas do voronoi comum.
Sirisian
Concordo com os outros dois comentários, meu primeiro pensamento foi "há um número infinito de soluções". Onde "infinito" pode não ser infinito por arbitrariamente grande. Não há restrições sobre o que permite isso e não isso .
Draco18s não confia mais em SE
Desculpe por não ser mais específico. Realmente, o único requisito estrito era que a parede separe os pontos dados, o que eu percebo que tem soluções quase infinitas. As imagens que eu forneci não foram realmente mais do que uma idéia geral do que eu estava tentando fazer, então sua edição, Draco, seria um resultado perfeitamente válido para os meus propósitos. Eu estava apenas procurando o tipo de método que produziria esse tipo de resultado, mesmo se houver um grande número de resultados.
21818 IanLarson

Respostas:

8

Vou apresentar um conceito geral e três soluções usando esse conceito.

O conceito é um mapa de influência : para cada local no mapa, você vai armazenar um número que representa a distância para cada ponto de cor. Dessa forma, para cada posição, você pode consultar a que distância fica azul, vermelho, verde etc. Chamamos o resultado de mapa de influência.

Para mais detalhes sobre motivação, criação e uso de mapas de influência em jogos, consulte: A Mecânica do Mapeamento de Influência: Representação, Algoritmo e Parâmetros .

Não faço ideia para que serve esse muro, minha cabeça é que estamos falando de um jogo de estratégia, e a IA está decidindo onde colocar os muros. Para fazer isso, existem muitas abordagens além das apresentadas aqui. Uma abordagem simples seria colocar paredes a uma distância fixa dos pontos de cor e combinar as áreas quando elas se sobrepõem - e, é claro, não as constroem sobre obstáculos - as vantagens deste método são que garante que as paredes não sejam muito longe para enviar tropas para defendê-los e é muito barato computacionalmente. Suponho que você queira algo mais complexo.

Solução 1 :

Para encontrar uma maneira de quebrar o azul, encontre a diferença entre a distância para o azul e qualquer outra coisa, para cada ponto. Adendo : A área em que a diferença é positiva é o domínio de influência do azul. Se você usar os domínios de influência para cada ponto de cor, poderá criar um diagrama de Voronoi . Obrigado a Sirisian por mencioná-los .

Podemos argumentar que, para um ponto próximo ao azul, a diferença será positiva e, para um ponto próximo a outro ponto de cor, a diferença será negativa. Dado que a distância é uma função contínua, pelo teorema do valor intermediário, podemos argumentar que pelo menos um ponto no meio a diferença se aproxima de zero. Uma solução seria traçar uma parede que minimiza a distância entre todas as peças onde a diferença se aproxima de zero.

Qualquer que seja a solução ou não que leve em consideração os obstáculos, depende da função de distância. Se você usar apenas as distâncias de Manhattan ou Euclidiana sem considerar os caminhos possíveis, a parede resultante não tirará vantagem dos obstáculos existentes no mapa.

Nota: esta solução se aproxima da mesma área para o azul e o restante em um cenário plano.

Solução 2 :

Em resumo, você pode encontrar pontos de estrangulamento entre a área de influência do azul e os outros e, em seguida, colocar as paredes lá. Isso colocará paredes em locais onde a influência não está em equilíbrio (as paredes ficam mais próximas de um lado), mas minimizará o comprimento das paredes.

Uma abordagem útil para encontrar pontos de estrangulamento é dividir o cenário em nós convexos e criar uma rede que represente o cenário. Você começará a supor que colocará paredes ao redor dos nós que possuem azul diretamente e, em seguida, começará a avançar pela rede (sempre aumentando a distância do azul) e considerando o comprimento da parede se a colocou ao redor do que avançou até agora. Sua solução é a posição que tinha comprimento mínimo (e os locais das paredes são os pontos de estrangulamento).

Na prática, o algoritmo é um pouco mais complicado que isso, porque pode haver ramificações no cenário. Você só precisa considerar cada ramificação uma vez e escolher a melhor posição para a parede para essa ramificação.

Solução 3 :

A primeira solução tem o problema de que pode levar a uma parede muito longa. A segunda solução tem o problema de levar a paredes muito distantes do azul.

Observe que, trabalhando com pixels, blocos ou trabalhando com uma rede, o conceito do mapa de influência, como uma representação da distância dos pontos de cor, é válido e útil. Assim, é possível aplicar a solução 1 na rede de nós convexos.

Minha terceira solução é combinar as abordagens acima. Depois de trabalhar na rede, você pode considerar o comprimento do muro e a diferença de influência - e qualquer outra métrica que desejar - como uma única métrica de indicador "custo" que você pode otimizar.

Theraot
fonte
11
Isso é super útil. Usar um mapa de influência soa exatamente como o que eu preciso. Obrigado pelos links e resposta detalhada.
IanLarson