Pathfinding –
Abordagens para
Pathfinding
Bruno Campagnolo de Paula
Definição do Problema

Path planning (pathfinding, motion
planning, etc):
 Como
chegar de um ponto a outro em um
ambiente com obstáculos.
 Problema típicos das áreas de:
Jogos;
 Robôs Móveis.

Classificação de Path finding
Passos para a execução do path
finding

Parte 1 - Pré-processamento:
 Captura
do espaço contínuo em uma
representação sob a forma de grafo.
 Tranformação em representação discreta.

Parte 2 - Processamento da consulta:
 Busca,
no grafo usando algoritmo de busca
(A*, D*, etc).
Parte 1 – Préprocessamento
Abordagens adotadas quanto à
representação do espaço

Roadmap:
 A conectividade
do espaço livre é
representado por uma rede de curvas
unidimensionais.

Cell decomposition:
O
espaço livre é decomposto em células. A
conectividade do espaço livre é representada
por um grafo de adjacência entre estas
células.
Abordagens adotadas quanto à
representação do espaço

Campos Potenciais: consiste em definir
uma função sobre o espaço livre que
possua um mínimo global no local
objetivo. Assim, o objetivo emite um
campo atrativo e os obstáculos emitem
um campo repulsivo
Roadmap

4 técnicas:
 Grafo
de visibilidade;
 Diagramas de Voronoi;
 Silhouette;
 Roadmap probabilístico.
Grafo de Visibilidade
Objetivo
Início
Grafo de Visibilidade
Objetivo
Início
Grafo de Visibilidade
Objetivo
Início
Grafo de Visibilidade
Objetivo
Ínício
Grafo de Visibilidade
Objetivo
Início
Caminho
Grafo de Visibilidade considerando
unidades não puntuais


Assume-se que a unidade não tenha rotação.
Transformando em navegação em relação a
pontos.
Grafo de Visibilidade considerando
unidades não puntuais
Complexidade e características
O (n^2*log (n)) => tempo
 O(n^2) => espaço
 Melhorias:

 Pré-cálculo

do grafo de visibilidade;
Importante: grafo de visibilidade é um
método completo, ou seja, sempre que
existir um caminho este caminho é
retornado.
Diagrama de Voronoi




Originalmente da área de
geometria computacional;
Construção de um grafo
que possua arestas
distantes de um
obstáculo.
Diagrama de Voronoi
gera caminhos que
tendem a ser distantes
dos obstáculos e longe
do caminho ótimo.
Ou seja, a técnica
maximiza a segurança.
Geração do Diagrama de
Voronoi
 Tome sua distribuição de dados e encontre todos os
triângulos definidos por três pontos da distribuição, de tal
forma que um círculo passando por estes três pontos não
inclua nenhum outro ponto.
Geração do Diagrama de
Voronoi

Para cada conjunto de três pontos satisfazendo a
condição de Delaunay encontrado, gere um
triângulo.
Geração do Diagrama de
Voronoi
Determine o ponto
médio de cada
uma das arestas
do conjunto de
triângulos gerado
anteriormente.
Considere cada
aresta apenas uma
vez.
 Gere uma linha
perpendicular a
cada uma das



Determine as duas
intersecções mais próximas
de cada aresta com duas
outras arestas. Um
intersecção para cada lado.
Ignore os segmentos de reta
que seguem para além das
intersecções.
Forme as células do
diagrama com os polgonos
formados por segmentos
adjacentes. Ciclos geram
células internas, polígonos
Complexidade e características
O(n log n) => tempo
 O (n) => espaço
 Inserção de novo ponto: O (n/2)
 Importante: Voronoi não funciona bem em
ambientes muito abertos.

Probabilistic Roadmap
A técnica de Probabilistic Roadmap é
composta por duas fases: préprocessamento e consulta.
 Na primeira, são acrescentados pontos
aleatórios distribuídos no espaço livre e
tais pontos são conectados utilizando um
planejador local. Na segunda fase, devese conectar o ponto de início e o destino e
encontrar um caminho no roadmap.

Probabilistic Roadmap
Características
Rápido;
 Probabilisticamente completo;
 A construção do roadmap depende da
cena, pode levar de minutos a horas;
 A construção é computacionalmente cara,
mas a busca é bem rápida.

Decomposição em Células (Cell
Decomposition)

2 métodos distintos:
 Decomposição

O espaço livre é representado por uma coleção de
células que não se interceptam, cuja união é
exatamente igual ao espaço livre.
 Decomposição

exata:
aproximada:
O espaço é representado por uma coleção de
células que não se interceptam. A diferença em
relação ao caso anterior é que a união de todas as
células está contida no espaço livre e não é
exatamente o espaço livre.
Decomposição exata
Objetivo
6
2
10
12
7
4
1
9
13
3
11
Início
5
8
1) Decomponha a região em células
Decomposição exata
Objetivo
6
2
10
12
7
4
1
9
13
3
11
Início
5
8
2) Construa um grafo de adjacência
Decomposição exata
2
Objetivo
6
10
12
7
1
9
Início
3)
Construa caminho a partir das células mais próximas do objetivo.
Decomposição exata
GOAL
START
3)
Construa caminho a partir dos centros de cada linha .
Decomposição aproximada
Space Representation
Equivalent quadtree
Decomposição aproximada
Space Representation
Equivalent quadtree
NW child
Gray node
NE
SW
SE
Free node
Decomposição aproximada
Space Representation
Equivalent quadtree
G
S(G)
Obstacle Node
Decomposição aproximada
Space Representation
Equivalent quadtree
Each of these steps are examples of
pruned quadtrees, or the space at
different resolutions
Decomposição aproximada
Space Representation
Equivalent quadtree
Complete quadtree
Aplicação em Star Trek Armada
(mista com grafo de visibilidade)
Otimização 1
Decomposição aproximada usando
framed-quadtrees
Inexatidão

O uso de grids ou decomposição
aproximada não garante que iremos
conseguir gerar o caminho sempre.
Vizinhos
r
Campos Potenciais
Definir uma função sobre o espaço livre
que possua um mínimo global no local
objetivo.
 Objetivo: campo atrativo
 Obstáculos: campo repulsivo.
 Perseguir os menores valores contidos no
campo potencial, ou seja, ele é tratado
como um ponto sobre a influência de um
campo.

Campo atrativo e repulsivo

Analogia com bola descendo a colina.
Campo atrativo e repulsivo
Alvo
Obstáculo
Cálculo da
resultante
Problema dos mínimos locais

Unidade fica presa
em pontos de mínimo
valor gerados pelos
obstáculos.
Problema dos mínimos locais

Soluções:
 Utilizar
o best-first
search, provavelmente
associado com
alguma técnica de
decomposição
aproximada de célula.
 Alternar “descidas” e
percursos aleatórios.
Outras técnicas (RRT)

Random Rapid Trees
Outras técnicas (FFM)
Outras técnicas

FMM (Fast Marching Methods) permite a
geração de múltiplas rotas.
Parte 2 – Métodos
de Busca
A* - A estrela dos métodos de
busca...



Vamos fazer alguns exemplos
usando representação sob a
forma de grid.
Algoritmos anteriores ao A*:
Dijkstra:





Algoritmo visita os vértices no
grafo começando no início.
Examina o vértice mais
próximo ainda não visitado e
adicionando este ao conjunto
a ser visitado.
Vai expandindo até encontrar
o objetivo.
Sempre encontra um menor
caminho.
A cor mais clara indica a
menor distância em relação
ao ponto inicial.
A* - A estrela dos métodos de
busca...

BFS:
 Utiliza
uma
heurística: Seleciona
o vértice mais próximo
do vértice objetivo
para expandir.
 Não é garantido que
obtenha o melhor
caminho.
 A cor mais escura
representa os locais
mais próximos do
objetivo.
A*

A* = Dijkstra + BFS:
 Favorece
vértices que
estão mais próximos
do início (g (n) ) e
favorece vértices que
estão mais próximos
do final ( h(n) ).
 f(n)=g(n) + h( n)
Pseudo código do A*


1) OPEN.add (nó inicial)
2) Repita:



Procure pelo menor valor de F em OPEN. Este valor será o
quadrado atual.
OPEN.remove (quadrado atual); CLOSE.add(quadrado atual)
Para cada um dos 8 quadrados adjacentes, quadrado:

Se não for caminhável ou estiver em CLOSE não faz nada, caso
contrário:




Se não estiver em OPEN então OPEN.add(quadrado);
quadrado.parent=quadrado atual
Se já estiver em OPEN, verifique se o caminho até este é melhor, se
for, quadrado.parent=quadrado atual, recalcular F e G de quadrado.
Pare quando: encontrar o fim ou OPEN vazio.
3) Salve o caminho: percorrer o parent desde o nó final
até achar o início.
Melhorias no A*
Pathfinding hierárquico;
 Caminhos suaves;
 Pathfinding pré-calculado;
 Curvas realistas;
 Otimizações sugeridas no Game
Programming Gems 1.
 Otimizações sugeridas no Game
Programming Gems 2.

Pathfinding hierárquico



Se os nós início e objetivo forem muito
longe um do outro, o Pathfinding vai
levar muito tempo.
Utilizar um máximo de 40 X 40 para a
distância máxima a ser pesquisada.
Alternativas:



Subdividir a linha até o objetivo em pontos
intermediários;
Dividir o mapa em regiões (pontes, colinas,
etc);
Usar mais de um nível hierárquico.
Obtendo Caminhos suaves

Algoritmo “Line of sight”:



checkPoint = início do caminho
currentPoint = próximo ponto no caminho
while (currentPoint->next != NULL)

if walkable(checkPoint, currentPoint->next)





//Faça uma linha entre os dois pontos
temp=current Point
currentPoint = currentPoint->next
Delete temp from the path
else


checkPoint = currentPoint
currentPoint=currentPoint->next
Pathfinding pré-calculado
A
B
Quero ir para:
A
D
C
A
E
F
B
C
D
E
F
G
- A-B A-C A-B A-C A-C A-C
B B-A - B-A B-D B-D B-D B-D
G
Estou em:
C C-A C-A - C-E C-E C-F C-E
D D-B D-B D-E - D-E D-E D-G
E E-C E-D E-C E-D - E-F E-G
F F-C F-E F-C F-E F-E - F-G
G G-E G-D G-E G-D G-E G-F -

O(n^3) espaço e difícil atualização!
De A até G:
+ A-C
+ C-E
+ E-G
Otimizações do GPGems 1




Para utilizar caminhos
suaves: spline;
Usar Pathfinding
hierárquico;
Limitar o tempo destinado
ao Pathfinding, quando
este tempo acabar,
utilizar a melhor
alternativa considerada;
Movimento de grupo:



Enfileiramento de ações;
Seguir o líder.
Discussão sobre melhor
abordagem para RTS:
usar grid retangular.
Otimizações do GPGems 1

Grid retangular:
 Enorme
espaço de busca;
 Fácil de colocar obstáculos;
 Movimento estilo “tabuleiro de xadrez”.

Grafo de visibilidade:
 Caminhos
perfeitos;
 Difícil fazer a manutenção quando um elemento é
eliminado.

Conclusão: para RTS, é melhor usar grid
retangular.
Otimizações do GPGems 2











1.Use event driven behavior rather than polling
2.Reduce redundant calculations
3.Centralize cooperation with managers
4.Run the AI less often
5.Distribute the processing over several frames
6.Employ level-of-detail AI
7.Solve only part of the problem
8.Do the hard work offline
9.Use emergent behavior to avoid scripting
10.Amortize query costs with continuous bookkeeping
11.Rethink the problem
Modelos de Movimento de
Grupo

Flocking: aplicar a cada unidade um
conjunto de regras simples de
movimentação.
Separação:
Evitar os vizinhos
que estão muito
próximos
Alinhamento:
acompanhar a
velocidade
média do grupo
Coesão:
acompanhar a
posição média
do grupo (centro
de gravidade)
Evitar
obstáculos:
procurar desviar
os obstáculos
pelo caminho.
Replanning
D*;
 LPA*;
 D* Lite.

Flocking em Pathfinding

Utilizar abordagem de Campos Potenciais:
 Cai

no problema de mínimos locais;
Simplificação de pathfinding:
 Fazer
o pathfinding para o grupo e não para a
unidade;

Fazer com que o grupo siga o elemento
que for mais bem sucedido.
Conclusões sobre flocking

Vantagens:
 Comportamentos
complexos a partir de
regras simples;
 Diversos tipos de comportamento podem ser
obtidos;

Desvantagens:
 Difícil
de acertar parâmetros para obter
comportamento bom.
Conclusões sobre Pathfinding
1) Utilizar abordagem hierárquica:
diferentes algoritmos para diferentes
níveis.
 2) Usar flocking para melhorar o
movimento das unidades;
 3) Distribuir o processamento em diversos
frames.
 4) Pré-calculo do Pathfinding é possível.
 4) Usar possível decomposição
aproximada do espaço.
