Considere A * pesquisando em um mapa baseado em blocos. Um código direto seria: Se houver uma unidade dentro dessa célula, ela estará inacessível, tudo bem.
Mas há um problema de resolução de mapa. Quando olho para o Warcraft 3, monstros e estruturas têm um raio diferente, e você pode caminhar muito perto, o que é mais parecido com o vetor, como isso foi implementado?
Além disso, qual é a solução padrão para incorporar a detecção de colisão de obstáculos em movimento com o algoritmo de localização de caminhos, como o Warcraft 3?
Respostas:
Não posso dizer com certeza que tipo de abordagem foi usada pelos desenvolvedores do WC3, mas parece muito com o Hierarchical Annotated A *. O raio da unidade definido no WC3Editor foi usado como está na escala do modelo 3D, mas o tamanho real da unidade para a busca de caminhos era discreto, talvez algo como unitSize = (int) (unitRadius / 10). Não era baseado em vetores, isso é certo.
Digamos que existem muitos nós de caminho criando uma grade de nós de alta resolução. Uma unidade simples como um ghoul tem tamanho 2, portanto, para colocá-la em algum lugar da grade, precisamos de 4 nós de caminho livre próximos um do outro. Um herói do cavaleiro da morte é um pouco maior com um tamanho de 3, ocupando 9 nós no caminho. Agora, colocamos dois zigurates juntos, deixando um espaço de 2 nós no meio, e enviamos um ghoul e um cavaleiro da morte do outro lado. Ghoul será capaz de passar entre dois zigurates, enquanto o cavaleiro da morte terá que se mover. Como isso pode ser determinado?
Para verificar se um nó pode acomodar uma unidade de tamanho específico, vamos atribuir um valor de folga especial a cada nó que define um tamanho de unidade máximo permitido. Basicamente, isso significa que várias verificações limitadas foram feitas para um nó e os maiores limites possíveis foram lembrados como liberação do nó. Então, quando queremos colocar um cavaleiro da morte em algum nó, torna-se tão simples quanto comparar a folga do nó com o tamanho do cavaleiro da morte. Obviamente, as coisas se tornarão muito mais complexas quando houver várias unidades competindo por nós, mas isso é outra história.
Para mais detalhes, consulte este artigo:
http://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/
fonte
Usaria o mosaico para criar malhas de navegação AKA de regiões de caminhos. Este artigo explica o conceito com diagramas completos.
Você ainda pode manter A * como sua abordagem de busca de caminhos, no entanto, sua rede não é mais uma grade (gráfico conectado a 4), mas um gráfico que representa a conectividade arbitrária entre suas regiões poligonais. Então você terá que adaptar seu algoritmo para se adequar.
fonte