Parte 1. Algoritmo de pesquisa geral
1. Introdução
Encontrar um caminho é um desses tópicos que geralmente são os mais difíceis para os desenvolvedores de jogos. As pessoas especialmente pobres entendem o algoritmo
A * , e muitas pensam que isso é algum tipo de mágica incompreensível.
O objetivo deste artigo é explicar a busca pelo caminho em geral e
A * em particular de uma maneira muito compreensível e acessível, pondo fim ao equívoco generalizado de que este tópico é complexo. Com a explicação certa, tudo é bem simples.
Observe que, no artigo, consideraremos a busca de um caminho
para jogos ; ao contrário de mais artigos acadêmicos, omitiremos algoritmos de pesquisa como Profundidade-Primeiro ou Largura-Primeiro. Em vez disso, tentaremos passar de zero a
A * o mais rápido possível.
Na primeira parte, explicaremos os conceitos mais simples de encontrar um caminho. Ao entender esses conceitos básicos, você perceberá que
A * é surpreendentemente óbvio.
Circuito simples
Embora você possa aplicar esses conceitos a ambientes 3D complexos arbitrários, vamos começar com um esquema extremamente simples: uma grade quadrada 5 x 5. Por conveniência, marquei cada célula com uma letra maiúscula.
Malha simples.A primeira coisa que faremos é imaginar esse ambiente como um gráfico. Não explicarei em detalhes o que é um gráfico; Simplificando, este é um conjunto de círculos conectados por setas. Os círculos são chamados de
"nós" e as setas são
chamadas de "arestas" .
Cada nó representa um
"estado" no qual o personagem pode estar. No nosso caso, o estado do personagem é sua posição, por isso criamos um nó para cada célula da grade:
Nós representando células da grade.Agora adicione as costelas. Eles indicam os estados que podem ser
"alcançados" de cada estado; no nosso caso, podemos ir de qualquer célula para a próxima, com exceção das bloqueadas:
Arcos denotam movimentos permitidos entre células da grade.Se pudermos ir de
A a
B , dizemos que
B é um
"vizinho" de
um nó.
Vale a pena notar que as costelas têm uma
direção ; precisamos de arestas de
A a
B e de
B a
A. Isso pode parecer supérfluo, mas não quando "condições" mais complexas podem surgir. Por exemplo, um personagem pode cair do teto para o chão, mas não é capaz de saltar do chão para o teto. Você pode ir do estado "vivo" para o estado "morto", mas não vice-versa. E assim por diante
Exemplo
Suponha que queremos passar de
A para
T. Começamos com
A. Você pode executar exatamente duas ações: vá para
B ou vá para
F.Digamos que nos mudamos para
B. Agora podemos fazer duas coisas: retornar a
A ou ir a
C. Lembramos que já estávamos em
A e consideramos as opções lá, então não faz sentido fazê-lo novamente (caso contrário, podemos passar o dia inteiro movendo
A →
B →
A →
B ...). Portanto, iremos para
C.Sendo em
C , não temos para onde nos mover. Voltar a
B é inútil, ou seja, é um beco sem saída. Escolher a transição para
B quando estávamos em
A foi uma má idéia; talvez você devesse tentar
F em vez disso?
Continuamos repetindo esse processo até terminar em
T. Neste momento, simplesmente recriamos o caminho de
A , retornando em nossos passos. Nós estamos em
T ; como chegamos lá? De
o ? Ou seja, o final do caminho tem a forma
O →
T. Como chegamos a
O ? E assim por diante
Lembre-se de que não estamos realmente nos
movendo ; tudo isso foi apenas um processo de pensamento. Continuamos em
A , e não sairemos dela até encontrarmos todo o caminho. Quando digo "mudamos para
B ", quero dizer "imagine que mudamos para
B ".
Algoritmo geral
Esta seção é a parte mais importante de todo o artigo . Você absolutamente
deve entendê-lo para poder realizar a busca pelo caminho; o restante (incluindo
A * ) são apenas detalhes. Nesta seção, você entenderá até
entender o significado .
Além disso, esta seção é incrivelmente simples.
Vamos tentar formalizar nosso exemplo, transformando-o em um pseudo-código.
Precisamos rastrear os nós que sabemos alcançar desde o nó inicial. No início, este é apenas o nó inicial, mas no processo de "explorar" a grade, aprenderemos como chegar a outros nós. Vamos chamar esta lista de nós de
reachable :
reachable = [start_node]
Também precisamos rastrear os nós já revisados para não considerá-los novamente.
explored chamá-los de
explored :
explored = []
A seguir, descreverei o núcleo do algoritmo : em cada etapa da pesquisa, selecionamos um dos nós que sabemos como alcançar e observamos quais novos nós podemos obter dele. Se determinarmos como alcançar o nó final (alvo), o problema será resolvido! Caso contrário, continuamos a pesquisa.
Tão simples, o que até decepciona? E isso é verdade. Mas este é o algoritmo inteiro. Vamos anotá-lo passo a passo com pseudo-código.
Continuamos a pesquisar até chegarmos ao nó final (nesse caso, encontramos o caminho do nó inicial ao final) ou até ficarmos sem nós nos quais você pode pesquisar (nesse caso, não há como os nós inicial e final) .
while reachable is not empty:
Escolhemos um dos nós para o qual sabemos como chegar e que ainda não foi investigado:
node = choose_node(reachable)
Se aprendemos como chegar ao nó final, a tarefa estará concluída! Nós só precisamos construir o caminho seguindo os links
previous volta ao nó inicial:
if node == goal_node: path = [] while node != None: path.add(node) node = node.previous return path
Não faz sentido examinar o nó mais de uma vez; portanto, acompanharemos isso:
reachable.remove(node) explored.add(node)
Identificamos nós que não podemos alcançar daqui. Começamos com uma lista de nós adjacentes ao atual e excluímos os que já examinamos:
new_reachable = get_adjacent_nodes(node) - explored
Tomamos cada um deles:
for adjacent in new_reachable:
Se já sabemos como alcançar o nó, ignore-o. Caso contrário, adicione-o à lista
reachable , acompanhando como ele entrou:
if adjacent not in reachable: adjacent.previous = node
Encontrar o nó final é uma maneira de sair do loop. A segunda é quando o
reachable fica vazio: ficamos sem nós que podem ser explorados e não atingimos o nó final, ou seja, não há como o nó inicial para o nó final:
return None
E ... é isso. Este é o algoritmo inteiro e o código de construção do caminho é alocado em um método separado:
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty:
Aqui está a função que cria o caminho, seguindo os links
previous volta ao nó inicial:
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
Isso é tudo.
Esse é o pseudocódigo de
cada algoritmo de pesquisa de caminho, incluindo
A * .
Releia esta seção até entender como tudo funciona e, mais importante,
por que tudo funciona. Seria ideal desenhar um exemplo manualmente no papel, mas você também pode assistir a uma demonstração interativa:
Demonstração interativa
Aqui está uma demonstração e um exemplo da implementação do algoritmo mostrado acima (você pode executá-lo na
página do artigo original ).
choose_node apenas seleciona um nó aleatório. Você pode iniciar o algoritmo passo a passo e examinar a lista de
explored reachable e
explored , bem como para onde os links
previous apontam.
Observe que a pesquisa termina assim que um caminho é detectado; pode acontecer que alguns nós nem sejam considerados.
Conclusão
O algoritmo apresentado aqui é um algoritmo geral para
qualquer algoritmo de pesquisa de caminho.
Mas o que distingue cada algoritmo de outro, por que
A * é
A * ?
Aqui está uma dica: se você executar a pesquisa na demonstração várias vezes, verá que o algoritmo nem sempre encontra o mesmo caminho. Ele encontra
um caminho, e esse caminho não é necessariamente o
mais curto . Porque
Parte 2. Estratégias de Pesquisa
Se você não entender completamente o algoritmo descrito na seção anterior, retorne a ele e leia-o novamente, porque é necessário para entender mais informações. Quando você descobrir,
A * parecerá completamente natural e lógico para você.
Ingrediente secreto
No final da parte anterior, deixei duas perguntas em aberto: se cada algoritmo de pesquisa usa o mesmo código, por que
A * se comporta como
A * ? E por que a demo às vezes encontra caminhos diferentes?
As respostas para as duas perguntas estão relacionadas entre si. Embora o algoritmo esteja bem definido, deixei um aspecto sem solução e, como se vê, é a chave para explicar o comportamento dos algoritmos de pesquisa:
node = choose_node(reachable)
É essa string de aparência inocente que distingue todos os algoritmos de pesquisa um do outro.
choose_node depende do método de implementação de
choose_node .
Então, por que a demo encontra caminhos diferentes? Porque seu método
choose_node seleciona um nó aleatoriamente.
O comprimento importa
Antes de mergulhar nas diferenças no comportamento da função
choose_node , precisamos corrigir uma pequena supervisão no algoritmo descrito acima.
Quando consideramos os nós adjacentes à corrente, ignoramos aqueles que já sabem como:
if adjacent not in reachable: adjacent.previous = node
Isso é um erro: e se descobríssemos a
melhor maneira de chegar a isso? Nesse caso, é necessário alterar o link do nó
previous para refletir esse caminho mais curto.
Para fazer isso, precisamos saber o comprimento do caminho desde o nó inicial até qualquer nó acessível. Vamos chamar isso de custo do caminho. Por enquanto, assumimos que a mudança de um nó para um dos nós vizinhos tem um custo constante de
1 .
Antes de iniciar a pesquisa, atribuímos o valor do
cost de cada nó ao
infinity ; graças a isso,
qualquer caminho será mais curto que isso. Também definiremos o
cost nó
start_node como
0 .
Então é assim que o código ficará:
if adjacent not in reachable: reachable.add(adjacent)
Mesmo custo de pesquisa
Vamos agora dar uma olhada no método
choose_node . Se nos esforçarmos para encontrar o caminho mais curto possível, escolher um nó aleatoriamente não é uma boa ideia.
É melhor escolher um nó que possamos alcançar a partir do nó inicial ao longo do caminho mais curto; graças a isso, geralmente preferimos caminhos mais curtos a caminhos mais longos. Isso não significa que caminhos mais longos não serão considerados, significa que caminhos mais curtos serão considerados primeiro. Como o algoritmo termina imediatamente após encontrar um caminho adequado, isso deve nos permitir encontrar caminhos curtos.
Aqui está um exemplo possível da função
choose_node :
function choose_node (reachable): best_node = None for node in reachable: if best_node == None or best_node.cost > node.cost: best_node = node return best_node
Intuitivamente, a busca por esse algoritmo se expande “radialmente” do nó inicial até atingir o nó final. Aqui está
uma demonstração interativa desse comportamento:
Conclusão
Uma simples mudança no método de escolha do nó considerado a seguir nos permitiu obter um algoritmo bastante bom: ele encontra o caminho mais curto do início ao nó final.
Mas esse algoritmo, até certo ponto, permanece "estúpido". Ele continua a procurar em todos os lugares até encontrar um nó terminal. Por exemplo, qual é o ponto no exemplo mostrado acima para procurar na direção
A , se é óbvio que estamos nos afastando do nó final?
É possível tornar a
choose_node mais inteligente? Podemos
direcionar a pesquisa para o nó final , sem nem mesmo saber o caminho correto com antecedência?
Acontece que nós podemos - na próxima parte, finalmente
choose_node , o que nos permite transformar o algoritmo geral de busca de caminho em
A * .
Parte 3. Remova o véu de sigilo de A *
O algoritmo obtido na parte anterior é bastante bom: encontra o caminho mais curto entre o nó inicial e o final. No entanto, ele gasta sua energia: ele considera as maneiras que uma pessoa obviamente chama de errôneas - elas geralmente
se afastam da meta. Como isso pode ser evitado?
Algoritmo mágico
Imagine que executamos um algoritmo de busca em um computador especial com um chip que pode fazer
mágica . Graças a esse chip incrível, podemos expressar o
choose_node maneira muito simples, que garante o caminho mais curto sem perder tempo explorando caminhos parciais que não levam a lugar nenhum:
function choose_node (reachable): return magic(reachable, " , ")
Parece tentador, mas os chips mágicos ainda precisam de algum tipo de código de baixo nível. Aqui está uma boa aproximação:
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = magic(node, " ") total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Essa é uma ótima maneira de selecionar o próximo nó: você seleciona um nó que nos fornece o caminho mais curto do nó inicial ao final, que é o que precisamos.
Também minimizamos a quantidade de mágica usada: sabemos exatamente qual é o custo da mudança do nó inicial para cada nó (este é
node.cost ) e usamos a mágica apenas para prever o custo da mudança do nó para o nó final.
Não é mágico, mas é incrível *
Infelizmente, os chips mágicos são novos e precisamos de suporte de equipamentos desatualizados. A maior parte do código nos convém, com exceção desta linha:
Ou seja, não podemos usar a magia para descobrir o custo de um caminho inexplorado. Bem, então, vamos fazer uma previsão. Seremos otimistas e suporemos que não há nada entre os nós atuais e os finais, e podemos simplesmente mover diretamente:
cost_node_to_goal = distance(node, goal_node)
Observe que o
caminho mais curto e a
distância mínima são diferentes: a distância mínima implica que não há absolutamente nenhum obstáculo entre os nós atuais e finais.
Essa estimativa é bastante simples de obter. Nos exemplos de nossa grade, essa é a
distância dos blocos de cidade entre dois nós (ou seja,
abs(Ax - Bx) + abs(Ay - By) ). Se pudéssemos mover na diagonal, então o valor seria igual a
sqrt( (Ax - Bx)^2 + (Ay - By)^2 ) , e assim por diante. Mais importante, nunca obtemos uma estimativa de valor
muito alta.
Então, aqui está uma versão não
choose_node do
choose_node :
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Uma função que estima a distância do nó atual ao nó final é chamada
heurística , e esse algoritmo de busca, senhoras e senhores, é chamado ...
A * .
Demonstração interativa
Enquanto você está se recuperando do choque causado pela percepção de que o misterioso
A * é realmente
tão simples , você pode olhar para a demonstração (ou executá-la no
artigo original ). Você notará que, diferentemente do exemplo anterior, a pesquisa gasta muito pouco tempo na direção errada.
Conclusão
Finalmente, chegamos ao algoritmo
A * , que nada mais é do que o algoritmo de pesquisa geral descrito na primeira parte do artigo, com algumas melhorias descritas na segunda parte e usando a função
choose_node , que seleciona o nó que, em nossa opinião, nos aproxima de nó final. Isso é tudo.
Aqui está um pseudocódigo completo do método principal para sua referência:
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty:
Método
build_path :
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
E aqui está o método
choose_node , que o transforma em
A * :
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Isso é tudo.
Mas por que precisamos da
parte 4 ?
Agora que você entende como o
A * funciona, quero falar sobre algumas áreas surpreendentes de sua aplicação, que estão longe de se limitarem a encontrar caminhos em uma grade de células.
Parte 4. A * na prática
As três primeiras partes do artigo começam com os próprios fundamentos dos algoritmos de pesquisa de caminho e terminam com uma descrição clara do algoritmo
A * . Tudo isso é ótimo na teoria, mas entender como isso é aplicável na prática é um tópico completamente diferente.
Por exemplo, o que acontece se o nosso mundo não é uma grade?
E se um personagem não puder girar instantaneamente 90 graus?
Como construir um gráfico se o mundo não tem fim?
E se não nos importamos com o comprimento do caminho, mas dependemos da energia solar e precisamos estar sob a luz solar o máximo possível?
Como encontrar o caminho mais curto para qualquer um dos dois nós finais?
Função de custo
Nos primeiros exemplos, procuramos o caminho mais curto entre os nós inicial e final. No entanto, em vez de armazenar comprimentos de caminho parciais no comprimento variável, chamamos de
cost . Porque
Podemos fazer com que
A * procure não apenas o
caminho mais curto , mas também o
melhor , e a definição de "melhor" pode ser escolhida com base em nossos objetivos. Quando precisamos do caminho mais curto, o custo é o comprimento do caminho, mas se queremos minimizar, por exemplo, o consumo de combustível, precisamos usá-lo como custo. Se queremos maximizar o "tempo gasto sob o sol", então o custo é o tempo gasto sem o sol. E assim por diante
No caso geral, isso significa que os custos correspondentes estão associados a cada extremidade do gráfico. Nos exemplos mostrados acima, o valor foi definido implicitamente e sempre foi considerado igual a
1 , porque contamos as etapas ao longo do caminho. Mas podemos alterar o custo da costela de acordo com o que queremos minimizar.
Função de critério
Digamos que nosso objeto seja um carro e ele precise chegar ao posto de gasolina. Qualquer reabastecimento nos convém. Leva a rota mais curta até o posto de gasolina mais próximo.
A abordagem ingênua será calcular o caminho mais curto para cada reabastecimento e selecionar o caminho mais curto. Isso funcionará, mas será um processo bastante caro.
E se pudéssemos substituir um
goal_node por um método que, em um determinado nó, possa dizer se é finito ou não. Graças a isso, podemos procurar vários objetivos ao mesmo tempo. Também precisamos modificar a heurística para que ela retorne o custo mínimo estimado de todos os nós finais possíveis.
Dependendo das especificidades da situação, talvez não consigamos alcançar o objetivo com
perfeição , ou isso custará muito (se enviarmos o personagem por meio de um mapa enorme, a diferença é uma polegada importante?), Portanto o método
is_goal_node pode retornar
true quando Estamos "perto o suficiente".
Não é necessária certeza total.
Representar o mundo como uma grade discreta pode não ser suficiente para muitos jogos. Tome, por exemplo, um jogo de tiro ou corrida em primeira pessoa. O mundo é discreto, mas não pode ser representado como uma grade.
Mas há um problema mais sério: e se o mundo for infinito? Nesse caso, mesmo que possamos apresentá-lo na forma de uma grade, simplesmente não conseguiremos construir um gráfico correspondente à grade, porque deve ser infinito.
No entanto, nem tudo está perdido. Obviamente, para o algoritmo de pesquisa de gráficos, definitivamente precisamos de um gráfico. Mas ninguém disse que o gráfico deveria ser
abrangente !
Se você observar atentamente o algoritmo, notará que não estamos fazendo nada com o gráfico como um todo; examinamos o gráfico localmente, obtendo nós que podemos alcançar a partir do nó em questão. Como pode ser visto na demonstração
A * , alguns nós do gráfico não são investigados.
Então, por que não construímos o gráfico no processo de pesquisa?
Tornamos a posição atual do personagem o nó inicial. Ao chamar
get_adjacent_nodes ele pode determinar as possíveis maneiras pelas quais o caractere pode se mover de um determinado nó e criar nós vizinhos em tempo real.
Além das três dimensões
Mesmo que seu mundo seja
realmente uma malha 2D, há outros aspectos a serem considerados. Por exemplo, e se um personagem não puder girar instantaneamente 90 ou 180 graus, como geralmente é o caso?
O estado representado por cada nó de pesquisa não precisa ser apenas uma
posição ; pelo contrário, pode incluir um conjunto de valores arbitrariamente complexo. Por exemplo, se curvas de 90 graus levarem tanto tempo quanto a transição de uma célula para outra, o estado do personagem poderá ser definido como
[position, heading] . Cada nó pode representar não apenas a posição do personagem, mas também a direção do seu olhar; e as novas arestas do gráfico (explícitas ou indiretas) refletem isso.
Se você voltar para a grade 5x5 original, a posição de pesquisa inicial agora pode ser
[A, East] . Os nós vizinhos agora são
[B, East] e
[A, South] - se queremos chegar a
F , primeiro precisamos ajustar a direção para que o caminho assuma a forma
[A, East] ,
[A, South] ,
[F, South] .
Atirador em primeira pessoa? Pelo menos quatro dimensões:
[X, Y, Z, Heading] . Talvez até
[X, Y, Z, Heading, Health, Ammo] .
Observe que quanto mais complexo o estado, mais complexa deve ser a função heurística.
A * em si é simples; a arte geralmente surge de boas heurísticas.
Conclusão
O objetivo deste artigo é dissipar de uma vez por todas o mito de que
A * é um algoritmo místico que não pode ser decifrado. Pelo contrário, mostrei que não há nada de misterioso nele e, de fato, pode ser deduzido de maneira simples, começando do zero.
Leitura adicional
Amit Patel tem uma excelente
“Introdução ao algoritmo A *” [
tradução em Habré] (e seus outros artigos sobre vários tópicos também são excelentes!).