Técnicas para cortar (literalmente) cantos em mapas de grade quadrada

Meu jogo envolve um nível com terrenos deformáveis ​​e unidades que podem viajar em qualquer direção, mas são desaceleradas por terrenos irregulares. A estrela A normal deve funcionar bem na maioria dos casos, exceto em terrenos planos, onde não importa como o descobridor de propósito geral funcionou, ele não enviaria unidades por um caminho direto. A estrela teta funcionaria se todo o nível fosse razoavelmente plano, mas seria muito mais lento se inicialmente tivesse que levar em consideração terrenos irregulares.

Eu acho que um algoritmo A-star de base à distância de Manhattan seria rápido e forneceria uma dica suficientemente boa para permitir que outros algoritmos de localização ou direção assumam o controle, mas não tenho certeza de que tipo de algoritmo usar para olhar em frente e decidir quando para abandonar o caminho, siga uma rota mais direta e para onde voltar mais tarde.

(A estrela-teta parece que seria muito ineficiente se fosse ajustada para levar em conta coisas como declives, obstáculos ou estradas. Veja a solução proposta para o comentário sobre como evitar campos minados em: http://aigamedev.com/open/ tutoriais / theta-star-any-angle-path / )

Edit: Eu não mencionei que já havia implementado e testado o A-star em uma grade semelhante. (Acho que excluí acidentalmente algo nesta pergunta.) Algumas das funções heurísticas / de custo mais óbvias que considerei não resultam em caminhos realísticos em uma grade quando um obstáculo bloqueia o caminho mais direto (basicamente quando a descoberta de caminhos é útil ) ( fotos de exemplo ). A mudança na função de custo usada pelo algoritmo Theta-star parece ser uma solução ideal (considerando a restrição de usar uma grade), mas assume-se que os ladrilhos têm os mesmos custos de viagem (e leva muito mais tempo).

Meu raciocínio original por trás do uso da distância de Manhattan foi terceirizar o algoritmo de "corte de canto" a partir do algoritmo de localização de caminhos, pois era mais importante ter um algoritmo rápido de localização de caminhos caso o layout ou o terreno dos obstáculos mudasse. Faz mais sentido executar o algoritmo "corner corner" uma vez quando a unidade chega do que em todas as permutações de todas as pesquisas do algoritmo de localização de caminhos (cujos resultados podem acabar sendo descartados de qualquer maneira). Uma pesquisa de quatro vizinhos com distância de Manhattan também é interessante porque você pode ver caixas de caminhos alternativos e identificar triângulos retos formados pelo caminho original e pelo caminho mais curto.

Uma pergunta melhor seria "Qual é a maneira mais rápida de identificar atalhos em um caminho com curvas de 90 graus?"

Você já deu uma chance a A *? Desde que você avalie adequadamente seus custos para diferentes tipos de terreno, ele encontrará o melhor caminho, considerando os nós disponíveis. No entanto, não encontrará uma linha reta sobre planícies abertas se você fornecer uma grade quadrada, o que parece ser o seu problema.

Se você quiser criar caminhos de linha reta através das planícies, poderá recolher as bordas do caminho em segmentos sempre que o novo caminho for de custo igual ou menor (ou seja, a mesma ou menor distância e não passar por terrenos mais irregulares). Apenas pegue cada dois pares de nós no caminho (AB e BC) e veja se AC é uma rota melhor. Se a CA for igual ou menor, remova B da lista. Repita a lista até a iteração em que a lista não muda mais e isso resolverá o problema da planície. Você precisa fazer algum processamento extra para garantir que a CA seja uma mudança legal e calcular o custo em uma distância arbitrária. Ou você pode fazer com que suas unidades usem o caminho como uma diretriz geral e se movam em direção ao nó em várias posições, usando ao mesmo tempo simples prevenção de obstáculos.

Você também pode melhorar significativamente sua qualidade de caminho fornecendo A * mais opções para os nós percorrerem. Por exemplo, apenas a adição de diagonais com custo ax√2 produzirá um caminho muito melhor do que o simples deslocamento de 4 direções.

Não tenho certeza de que tipo de algoritmo usar para olhar em frente e decidir quando abandonar o caminho, seguir uma rota mais direta e onde voltar mais tarde.

A * já lida com isso. Assim que o nó atualmente explorado não for mais o menor custo + heurístico, ele passa para o nó mais baixo + heurístico.