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 NodeComo 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 kilobytesetapa 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)
ENDWHILEA 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, ExitQuestã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?
fonte
Respostas:
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.
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.
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.
fonte