A busca de caminho pré-computada ainda é relevante?

12

Contexto

Os antigos jogos da Lucas Arts (era ScummVM) apontam e clicam em aventuras gráficas usadas como busca pré-computada. Aqui está um esboço da técnica.

Passo 1

O piso de cada quarto era dividido no que eles chamavam de "caixas de passagem", que eram praticamente equivalentes a nós em uma malha de navegação, mas limitados a formas trapezoidais. Por exemplo:

 ______ _____ _________ _____
\   A  |  B  |    C    |  D   \
 \_____|     |         |_______\
       |_____|         |
             |_________|

Passo 2

Um algoritmo offline (por exemplo, Dijkstra ou A *) calcularia o caminho mais curto entre cada par de nós e armazenaria a primeira etapa do caminho em uma matriz 2D, indexada em cada dimensão pelo nó inicial e final usado. Por exemplo, usando as caixas de passagem acima:

      ___ ___ ___ ___
     | A | B | C | D | <- Start Node
  ___|___|___|___|___|
 | A | A | A | B | C |  ---
 |___|___|___|___|___|     |
 | B | B | B | B | C |     |
 |___|___|___|___|___|     |-- Next node in shortest path
 | C | B | C | C | C |     |   from Start to End
 |___|___|___|___|___|     | 
 | D | B | C | D | D |  ---
 |___|___|___|___|___| 
   ^
   |
End Node

Como você pode imaginar, os requisitos de memória aumentam rapidamente à medida que o número de nós aumenta (N ^ 2). Como um pequeno normalmente seria grande o suficiente para armazenar cada entrada na matriz, com um mapa complexo de 300 nós que resultaria no armazenamento de um extra:

300^2 * sizeof(short) = 176 kilobytes

etapa 3

Por outro lado, calcular o caminho mais curto entre dois nós foi extremamente rápido e trivial, apenas uma série de pesquisas na matriz. Algo como:

// Find shortest path from Start to End
Path = {Start}
Current = Start
WHILE Current != End
    Current = LookUp[Current, End]
    Path.Add(Current)
ENDWHILE

A aplicação desse algoritmo simples para encontrar o caminho mais curto de C a A retorna:

1) Path = { C }, Current = C
2) Path = { C, B }, Current = B
3) Path = { C, B, A }, Current = A, Exit

Questão

Suspeito que, com o hardware poderoso de hoje, juntamente com os requisitos de memória para fazer isso em todos os níveis, quaisquer benefícios que essa técnica tenha tido agora sejam superados com a simples realização de um A * em tempo de execução.

Também ouvi dizer que hoje em dia as pesquisas de memória podem até ser mais lentas que a computação geral, e é por isso que criar tabelas de pesquisa de seno e cosseno não é mais tão popular.

Mas devo admitir que ainda não conheço muito bem esses assuntos de eficiência de hardware de baixo nível; portanto, estou aproveitando a oportunidade para pedir a opinião daqueles mais familiarizados com o assunto.

No meu mecanismo, eu também precisava da capacidade de adicionar e remover nós dinamicamente ao gráfico em tempo de execução ( veja isso ), para que a rota pré-computada só tornasse as coisas mais complicadas, então eu a desfiz (sem mencionar que minha solução A * em tempo de execução já estava funcionando perfeitamente) ) Ainda assim, fiquei me perguntando ...

Bottom line, esta técnica ainda é relevante hoje em dia em qualquer cenário?

David Gouveia
fonte
2
Eu acho que ainda é relevante se você estiver com um orçamento apertado de CPU. Mas uma vez que você deseja caminhos dinâmicos, não é mais útil. Btw, olhei de onde você tirou o algoritmo A * e você pode otimizá-lo ainda mais usando um minheap e alguns outros truques. Fiz algumas iterações para melhorar o A * em C #, que você pode ver aqui: roy-t.nl/index.php/2011/09/24/… pode ser útil.
Roy T.
1
Obrigado, eu o marquei como favorito e analisarei quando começar a otimizar meu aplicativo. Eu praticamente usei a solução de Eric Lippert com algumas pequenas modificações, porque era muito limpa e fácil de seguir ... E para todos os meus casos de teste, ela foi executada "instantaneamente", de maneira que nem me preocupei em otimizá-la.
David Gouveia
1
BTW, se você decidir prosseguir com a pré-computação, convém examinar o algoritmo de Floyd-Warshall . Ele cria a matriz do "próximo passo" com mais eficiência do que repetidamente usando o Dijkstra / A *.
Amitp
@amitp Obrigado pela dica, é sempre bom saber sobre essas alternativas! Embora, na maioria dos casos, a pré-computação seja feita offline, não haveria muito a ganhar ao torná-la mais eficiente. A menos que você seja realmente impaciente. :-)
David Gouveia
Concordou, embora Floyd-Warshall também é muito mais simples de implementar do que o algoritmo de Dijkstra, então se você não tiver implementado, no valor de Dijkstra É um olhar :)
amitp

Respostas:

3

No meu mecanismo, eu também precisava da capacidade de adicionar e remover nós dinamicamente ao gráfico em tempo de execução (veja isso), para que a rota pré-computada só tornasse as coisas mais complicadas, então eu a desfiz (sem mencionar que minha solução A * em tempo de execução já estava funcionando perfeitamente) ) Ainda assim, fiquei me perguntando ...

Bottom line, esta técnica ainda é relevante hoje em dia em qualquer cenário?

Não vejo nenhum benefício em usar essa técnica.

Não tenho a flexibilidade de um gráfico (você pode ter diferentes LODs, eles não precisam ter nenhuma forma específica, etc.). Além disso, qualquer usuário do seu mecanismo saberá o que é um gráfico e como usá-lo. Portanto, se eles quiserem adicionar funcionalidade extra, terão que aprender a implementar sua extensão usando uma situação completamente nova para eles.

Como você mencionou, parece que a escala seria horrível. Também vale a pena notar que, se um gráfico couber no dinheiro e você executar todas as descobertas do caminho de volta para trás, isso reduzirá o tempo de IO. Parece que sua implementação aumentaria muito em breve para caber em qualquer cache.

Também ouvi dizer que hoje em dia as pesquisas de memória podem até ser mais lentas que a computação geral, e é por isso que criar tabelas de pesquisa de seno e cosseno não é mais tão popular.

A menos que você possa caber em todo o seu programa e precisar de memória no cache, você vai engarrafar o pescoço para puxar as coisas para dentro e para fora da memória antes de engolir o pescoço do processador.

Suspeito que, com o hardware poderoso de hoje, juntamente com os requisitos de memória para fazer isso em todos os níveis, qualquer benefício que essa técnica tenha tido agora seja superado pela simples realização de um A * em tempo de execução

Perceba também que muitos jogos têm loops separados para atualizar a IA. Acredito que a maneira como meu projeto é configurado é que existe um loop de atualização para a entrada do usuário em 60hz, a IA é de apenas 20hz e os jogos são desenhados o mais rápido possível.

Também como nota lateral, fiz algumas programações de GBA apenas por diversão e nada foi transferido para o uso de um dispositivo moderno. Para o GBA, tratava-se de minimizar a carga de trabalho do processador (porque era patético). Você também deve perceber que a maioria das linguagens de alto nível C # e Java (não muito C ++ ou C) faz muitas otimizações para você. Quanto à otimização do código, não há muito o que fazer além de acessar o mínimo possível de memória e quando você executa o maior número possível de cálculos antes de trazer uma nova memória que a expulsa do cache e garante que você esteja apenas fazendo as coisas uma vez.

Edit: Também para responder ao seu título, sim, é. A pré-computação de caminhos usados ​​com frequência é uma excelente idéia e pode ser feita com o A * em qualquer lugar fora do loop do jogo. Por exemplo, da base para um recurso em um RTS, para que as pessoas não precisem recalcular toda vez que quiserem sair ou retornar.

ClassicThunder
fonte
Sobre sua edição, eu realmente não estava falando sobre pré-computar caminhos usados ​​com freqüência, mas estritamente sobre a técnica descrita para pré - computar todos os caminhos possíveis . Também estou um pouco confuso sobre como a maioria de sua resposta foi contra o uso de busca de caminho pré-computada, mas no final você disse que seria uma excelente idéia. Então, seria útil em um ambiente restrito de CPU, como o GBA?
David Gouveia
1
Pena que eu estava tentando apontar que a resposta para o seu título tirada de contexto é sim. Embora a resposta relacionada ao algoritmo específico descrito em sua pergunta seja não. Portanto, em suma, pré-computar todo caminho possível é uma má ideia, mas pré-computar alguns caminhos usados ​​com muita frequência pode ser uma boa idéia.
ClassicThunder
2
@ClassicThunder: Essa técnica de pré-calcular todos os caminhos de alguns pontos de referência é frequentemente chamada de ALT : Uma estrela com desigualdade de pontos de
Pieter Geerkens