Livre não é desconhecido.
Num mapa real, “não observei nada aqui” pode significar que a zona ainda não foi vista. É diferente de confirmar que está livre. Esta grelha começa com todas as zonas não bloqueadas conhecidas como livres.
MAPAS / ESPAÇO LIVRE · OBSTÁCULOS · CAMINHOS
Há um obstáculo.
Por onde podes passar?
Um mapa ajuda a transformar o que os sensores observam em escolhas de movimento. Experimenta bloquear passagens e vê como o caminho muda.
PARA COMEÇARFecha uma passagem.
Seleciona quadrados para acrescentar obstáculos. O caminho verde atualiza-se. Depois constrói uma parede completa: o sistema deve dizer que não encontra uma passagem.
Construir um mapa simples
Cada quadrado é uma zona do espaço. Preto significa livre, castanho significa ocupado e verde mostra um caminho. O início e o destino estão fixos; o modelo permite movimentos para cima, baixo e lados.
Usamos procura em largura para encontrar o menor número de passos numa grelha com custos iguais. Não modelamos altura, tamanho do drone, curvas, vento ou travagem. Encontrar este caminho não prova que um drone real o consiga seguir.
O veículo tem tamanho.
Um caminho para um ponto pode ser estreito demais para hélices ou rodas. Alargar os obstáculos no mapa pela dimensão do veículo e por uma margem é uma forma de representar essa limitação.
O mundo muda.
Uma porta pode fechar e uma pessoa pode entrar no percurso. O mapa precisa de novas observações, e o plano tem de ser revisto sem ignorar a idade dos dados.
Mapa, caminho e trajetória são coisas diferentes
O que existe no espaço.
Pode ser uma grelha, uma nuvem de pontos ou uma lista de referências. Inclui o que sabemos e, idealmente, o que ainda não sabemos.
Por onde passar.
Liga uma origem a um destino. O caminho pode ter curvas demasiado apertadas para o veículo, mesmo que evite obstáculos.
Como e quando passar.
Acrescenta velocidade e tempo. Precisa de respeitar capacidade de aceleração, travagem, margens e outros veículos.
Procurar um caminho na grelha
fila = [início]
visitados = {início}
enquanto fila não estiver vazia:
atual = retirar_primeiro(fila)
se atual == destino:
devolver_caminho_pelos_antecessores()
para cada vizinho livre de atual:
se vizinho não estiver em visitados:
guardar_antecessor(vizinho, atual)
adicionar_a_visitados(vizinho)
adicionar_ao_fim(fila, vizinho)
devolver("Não foi encontrado caminho")