No jogo 2D com o qual estou trabalhando, o mecanismo de jogo pode me fornecer, para cada unidade, a lista de outras unidades que estão em seu alcance.
Eu gostaria de saber se existe um algoritmo estabelecido para classificar as unidades em grupos , onde cada grupo seria definido por todas as unidades que estão "conectadas" umas às outras (mesmo através de outras).
Um exemplo pode ajudar a entender melhor a pergunta (E = inimigo, O = unidade própria). Primeiro os dados que eu obteria do mecanismo de jogo:
E1 can see E2, E3, O5
E2 can see E1
E3 can see E1
E4 can see O5
E5 can see O2
E6 can see E7, O9, O1
E7 can see E6
O1 can see E6
O2 can see O5, E5
O5 can see E1, E4, O2
O9 can see E6
Então devo calcular os grupos da seguinte maneira:
G1 = E1, E2, E3, E4, E5, O2, O5
G2 = O1, O9, E6, E7
Pode-se supor com segurança que existe uma propriedade comutativa para o campo de visão: [se A vê B, então B vê A].
Só para esclarecer: eu já escrevi uma implementação ingênua que circula em cada linha das informações do mecanismo de jogo, mas, pelo que parece, parece um problema geral o suficiente para ser estudado em profundidade e ter vários algoritmos estabelecidos (talvez passando através de alguma estrutura em forma de árvore?). Meu problema é que não consegui encontrar uma maneira de descrever meu problema que retornou hits úteis do Google.
Agradeço antecipadamente por sua ajuda!
Respostas:
Se a sua relação "pode ver" é simétrica, de modo que "A pode ver B" implica "B pode ver A", os grupos que você deseja calcular são os componentes conectados do gráfico definido pela relação "pode ver". Como outros observaram, existem algoritmos simples para calcular estes, como:
(Uma fila ou qualquer outra coleção que implemente com eficiência as operações "adicione novo elemento" e "remova e retorne algum elemento" pode ser usada no lugar da pilha
s
acima.)Se a sua relação "pode ver" não é simétrica, você precisa decidir se deseja que seus grupos sejam os componentes conectados forte ou fracamente . Para componentes fracamente conectados, o algoritmo acima funcionará como está, exceto que a linha
for each unit w that v can see
deve ser substituída porfor each unit w that can see v, or that v can see
. Para componentes fortemente conectados , você pode usar um dos algoritmos ( Kosaraju , Tarjan ou Gabow ) mencionados na página vinculada da Wikipedia.Para relações não simétricas, você também pode calcular o fechamento transitivo da relação ou de seus componentes fortemente conectados. Para isso, você pode usar o algoritmo Floyd – Warshall ; veja esta resposta no SO para (um pouco) mais informações.
Ps. Como o artigo da Wikipedia que vinculei às notas acima, pode ser mais eficiente atualizar dinamicamente os grupos à medida que a relação de visibilidade muda. Não estou familiarizado com os algoritmos avançados (?) Mencionados na Wikipedia, mas não deve ser difícil reunir algo que pelo menos seja melhor do que recalcular os grupos do zero todas as vezes.
Metade disso é fácil: se duas unidades em grupos diferentes adquirirem uma linha de visão entre elas, mescle os grupos. Lidar com unidades que se perdem de vista é um pouco mais complicado; Uma solução simples, mas talvez não ótima, é executar novamente o algoritmo de agrupamento das unidades no grupo afetado sempre que isso acontecer. Existem algumas otimizações que você pode fazer para isso, se as alterações de visibilidade ocorrerem um par de unidades por vez:
fonte
O que você tem é um gráfico de conectividade. E geralmente, a melhor maneira de agrupar os nós conectados (ou seja: caracteres) é com um algoritmo de pesquisa de gráficos. Profundidade primeiro, largura primeiro, o que for. Tudo o que você está fazendo é criar uma lista de quais nós são acessíveis a partir de todos os outros. Desde que seu gráfico não seja direcionado (se A estiver visível para B, então B estiver visível para A), isso funcionará bem.
Pode haver alguns algoritmos para melhorar isso em casos específicos. Por exemplo, se às vezes os caracteres não se moverem (e o terreno também não se mover, para que caracteres imóveis permaneçam visíveis), você poderá optar por não testá-los novamente para atualizar seus gráficos de conectividade.
Mas, em geral, você terá que testar novamente a visibilidade a cada quadro. As probabilidades são de que isso será mais lento que o percurso do gráfico para encontrar os grupos de visibilidade.
fonte
Parece um problema de conectividade de gráfico padrão. Pode haver algum tipo de algoritmo para isso, e pode parecer com o seguinte:
Espero que seja possível implementar isso por meio de uma árvore, como cluster hierárquico, mas duvido que funcione mais rápido - as árvores tendem a ser O (log N), enquanto a maioria das verificações que dou acima pode ser implementada como O (1) .
fonte
Concordo com todos os outros que responderam em termos de problemas de conectividade gráfica, no entanto, deixe-me salientar que o que você precisa aqui é o gráfico da triangulação de Delaunay gerado a partir de todas as suas unidades relevantes. O que isso faz é garantir que apenas as unidades mais próximas sejam conectadas no gráfico que você gerar. Você achará muito desafiador fazer isso de qualquer outra maneira, porque os cruzamentos de gráfico (não planaridade) farão com que unidades muito distantes umas das outras sejam conectadas incorretamente no gráfico.
O descrito acima se aplica somente se você estiver usando um espaço contínuo (como na maioria dos FPSs de movimento livre); no entanto, se você já possui uma grade subjacente (um gráfico planar) na qual suas unidades se movem, basta usá-la para avaliar a conectividade.
fonte