Pré-requisitos:
- Um pouco de Java
- NetBeans com plugin Gradle Support instalado
- Conhecimento sobre grafos
Objetivos:
- Praticar o uso de algoritmos de planejamento de caminhos em grafos
- Implementar heurísticas para o algoritmo A*
- Perceber que o algoritmo de Dijkstra é o A* que não usa heurística
- Entender o que é uma heurística admissível e o impacto do uso de uma que não é
Você deve começar usando o código do professor como ponto de partida para a atividade. Você deve implementar 3 heurísticas para o algoritmo A*:
- Uma heurística "nula", que transforme o A* no Dijkstra
- A heurística de distância Euclidiana
- (Opcional) Uma outra heurística à sua escolha (e pesquisa ;)
- Boa referência para pesquisa: página do Amit
- (Opcional) Baixar o Tiled e modificar o arquivo do mapa
(
core/assets/greed-island.tmx
) de alguma forma, para ver como o editor de mapas funciona
Descrevemos um Agente (Agent.java
) por:
- Algoritmo de movimentação (steering)
- Algoritmo de planejamento
- Que, por sua vez, pode conter uma função heurística
A movimentação acontece em três passos. Assim que um clique é feito:
- Passo de Planejamento: Um algoritmo de planejamento (no caso, A*) encontra a melhor rota para o ponto desejado.
- Passo de Movimentação: Um algoritmo de movimentação (no caso, seek estático) determina para onde o agente deve ir. O objetivo (target) do algoritmo é definido sempre como o próximo nó do caminho retornado pelo passo de planejamento.
- Passo de Física: Usamos integração de Euler para atualizar a posição do agente.
Um algoritmo de controle identifica se o passo de movimentação cumpriu
seu objetivo e, em caso afirmativo, define o objetivo como o próximo nó do
caminho. Veja o trecho de código de Agent.java:58
:
public void update(float delta) {
boolean shouldMove = true;
// verifica se atingimos nosso objetivo imediato
if (position.coords.dst2(steeringTarget.coords) < MIN_DISTANCE_CONSIDERED_ZERO_SQUARED) {
// procurar se temos outra conexão na nossa rota
// e, caso afirmativo, definir o nó de chegada como novo target
if (shouldMove = pathIterator.hasNext()) {
TileConnection nextConnection = pathIterator.next();
TileNode nextNode = nextConnection.getToNode();
steeringTarget.coords = nextNode.getPosition();
// atualiza a velocidade do "seek" de acordo com o terreno (a conexão)
this.behavior.maxSpeed = fullSpeed - (fullSpeed / 2.0f) * (nextConnection.getCost() - 1) / (LevelManager.maxCost - 1);
}
}
// integra
if (shouldMove) {
Steering steering = behavior.steer(this.position);
position.integrate(steering, delta);
}
}
O Agente (Agent.java:95
) recebe um evento de clique quando o usuário clica em
uma parte do mapa. Nesse momento, acionamos o algoritmo de planejamento para
traçar a rota:
public void setGoal(int x, int y) {
TileNode startNode = LevelManager.graph.getNodeAtCoordinates((int) this.position.coords.x, (int) this.position.coords.y);
TileNode targetNode = LevelManager.graph.getNodeAtCoordinates(x, y);
path.clear();
pathFinder.searchConnectionPath(startNode, targetNode, new EuclideanDistanceHeuristic(), path);
pathIterator = path.iterator();
}
Ao abrir o código na IDE, você pode compilar e executar o código e deve aparecer o mapa, com o agente no canto esquerdo, assim como mostra a figura lá em cima.
Nesse momento, ao clicar com o botão do mouse em alguma posição válida (fora de um obstáculo), o agente deveria planejar o (melhor) caminho e ir até lá. Contudo, o programa (e talvez seu computador - cuidado) vão explodir porque a heurística não está implementada, mas apenas lançando uma bomba chamada exceção:
// AQUI ESTAMOS CHAMANDO O ALGORITMO A* (instância pathFinder)
pathFinder.searchConnectionPath(startNode, targetNode, new Heuristic<TileNode>() {
@Override
public float estimate(TileNode n, TileNode n1) {
throw new UnsupportedOperationException("MEIMPLEMENTEPORFAVOR");
}
}, path);
Além disso, a qualquer momento você pode pressionar a tecla d
do teclado
para ativar o modo debug e poder enxergar o grafo que foi construído
para representar o mapa:
O modo de debug mostra todos os nós e conexões do grafo de navegação, que é usado pelo algoritmo de planejamento (o A* neste caso).
- Nó vermelho: obstáculo
- Nó azul: "passável"
- Peso das arestas incidentes:
- Grama: 1
- Água: 9 (maior custo possível)
- Água com pedrinhas para pisar: 5
- Ponte: 1
- Peso das arestas incidentes:
O algoritmo de Dijkstra é (1) completo e (2) ótimo:
- Se há um caminho do ponto atual ao desejado, ele acha
- Esse caminho é o melhor possível (i.e., um que minimiza o peso das arestas)
Neste jogo, as arestas possuem pesos referentes ao tempo gasto para se percorrê-la. Por exemplo, andar na grama é mais rápido (peso menor) que andar na água (peso maior).
Como vimos em aula, o A* também é completo, mas para que ele seja ótimo também, a heurística deve ser admissível (volte nos slides e veja o quê isso significa :).
Ou seja, para saber se a sua heurística bacanuda está funcionando devidamente, o A* usando ela precisa dar a mesma rota que o Dijkstra (que é A* sem heurística, ou com a "herística nula").
Caso o agente esteja passando toda hora por cima da água, é provável que a função heurística que você implementou não está admissível. Neste caso, reveja o conceito de admissibilidade e conserte-a =). Uma ótima fonte de estudo é a explicação do Amit Patel sobre as heurísticas do A*.
Este trabalho deve ser entregue via Moodle. Entregue o link para seu fork do repositório do código seminal.
Os exercícios desta aula prática serão corrigidos ao final do nosso horário. Assim que estiver pronto, chame o professor para que possa ver seu trabalho.