Quais são as desvantagens e / ou limitações das malhas de navegação? [fechadas]

8

Eu tenho muitos materiais sobre malhas de navegação, o que são, suas vantagens sobre gráficos compostos por pontos de referência etc. No entanto, não vi muitas informações sobre as limitações e as desvantagens do uso de malhas de navegação, além da hora óbvia. eles precisam ser criados manualmente (o que é relativamente resolvido pela reformulação).

Certamente, essa não é uma técnica completamente "mágica" que se apresente sem inconvenientes? Alguém poderia explicar quais são as limitações e desvantagens do uso de uma malha de navegação sobre, digamos, um gráfico composto de pontos de referência? Ou me aponte na direção certa?

Ray Dey
fonte

Respostas:

8

As malhas de navegação são uma melhoria qualitativa em relação aos gráficos de waypoints, da mesma forma que A * é uma progressão natural sobre o algoritmo de Dijkstra. Em cada caso, o primeiro evoluiu devido às deficiências do último e é um algoritmo inteiramente mais útil para a maioria das aplicações. A deficiência é, obviamente, a complexidade (tempo e / ou espaço). Mas eu teria que dizer que a troca é pequena para malhas de navegação versus gráficos de waypoints (ou seja, a complexidade computacional pode aumentar, mas não por uma ordem de magnitude).

O único benefício prático do uso de gráficos de waypoint é onde você realmente deseja restringir o movimento às linhas exatas, e não às áreas. Gráficos de waypoint = pontos e linhas infinitesimais, enquanto malhas de navegação são praticamente a mesma coisa apenas com áreas poligonais (convexas) anexadas que descrevem um espaço válido considerado "o território desta célula". De qualquer maneira, você está interpolando a posição de uma entidade de IA de um nó para outro; a única diferença com navmeshes é que você está fazendo isso de um local de pontos para outro, enquanto que com gráficos de waypoints você está fazendo isso de um ponto para outro, e potencialmente dando a devida consideração à borda que separa os nós A e B. E é claro da perspectiva da complexidade, é fácil ver que os gráficos de waypoints são moderadamente mais baratos de operar.

Com o passar do tempo, as melhorias vêm aparentemente "de graça" (da perspectiva individual). É por isso que um computador que você compra hoje por US $ X é muitas vezes mais rápido que um computador que você poderia comprar há dez anos pelo mesmo preço. O ponto é que não é realmente gratuito - alguém, em algum lugar, investiu em pesquisa e desenvolvimento nisso. Mesmo com algoritmos. E é por isso que a tecnologia mais antiga cai na esquina.

Engenheiro
fonte
3
Sua resposta é boa, mas eu realmente gostaria de ver uma citação de "mesmo no nível dos neurônios animais, [pathfinding] é representado como uma espécie de gráfico que liga a idéia de um lugar à idéia de outro por meio de associação, e em breve." É uma afirmação muito forte que eu nunca ouvi antes.
11
"São representáveis" e "são representados" não são a mesma coisa. A relação entre pensamento e estrutura dos neurônios não é um mapeamento direto (obviamente - os neurônios que sinalizam vermelho não são eles mesmos vermelhos). De qualquer forma, sua edição é uma reivindicação muito mais direta.
Obrigado pela resposta informativa. Percebo que todos os exemplos práticos de busca de caminhos usam gráficos e acho que pode haver um problema de complexidade de tempo / memória. No entanto, eu estava imaginando se havia um caso extremo em que você não poderia usar uma malha de forma eficaz - em retrospectiva, acho que talvez tenha pensado demais nisso. É provável que perguntar sobre as limitações das malhas de navegação seja perguntar sobre as limitações de um gráfico como uma forma de representação mundial. Só mais uma coisa, se você puder vincular a um exemplo de Difusão Colaborativa, eu realmente aprecio isso! Obrigado novamente.
quer
-1, porque você realmente não respondeu à pergunta. Você disse que navmeshes são uma melhoria qualitativa, mas o pôster original queria saber quais eram essas qualidades.
Kylotan
@Kylotan: Não, de fato, a pergunta diz: "Eu tenho muitos materiais sobre malhas de navegação [e] suas vantagens".
0

As malhas de navegação são restritas às superfícies, enquanto os waypoints podem ser colocados em qualquer lugar e podem ser executados qualquer número de conexões (arestas) em qualquer direção. Assim, os waypoints podem fornecer uma solução mais generalizada e flexível para, por exemplo, jogos com unidades ou ambientes abstratos ou extraordinários.

Acey
fonte