Atividade de implementação do algorítmo A* Search

Atividade acadêmica [IABV 2016]

Marcelo Barbosa @github/marcelobns

Implementação do Algoritmo A_Estrela (A Search*). A solução foi escrita em JavaScript por motivo de facilidade na distribuição e utiliza uma estrutura de dados semi-estruturada JSON como fonte de dados. E por fim o mapa é desenhado com HTML Canvas.

Todas as tecnologia utilizadas são livres e padrões da industria. [Live Demo]

JavaScript

O JavaScript vem ganhando força de mercado por sua capacidade de resolver problemas de diversos tamanhos e complexidades. Padrão da indústria como linguagem Front-end para a web, também vem se consolidando como tecnologia Back-end e Desktop. [Saiba mais]

JSON

JSON (JavaScript Object Notation) é uma estrutura de dados do tipo semi-estruturada, caracterizada por ser menos verbosa que o XML. É escrita em formato texto e completamente independente de linguagem, pois usa convenções que são familiares às linguagens C, Java, Perl, Python e muitas outras. Estas propriedades fazem com que JSON seja um formato ideal de troca de dados. [Saiba mais]

Canvas

É um elemento HTML que pode ser utilizado para desenhar utilizando linguagem de "script". Pode ser usado, por exemplo para desenhar gráficos, fazer composições de imagens ou simples animações. [Saiba mais]

Estrutura do Projeto

• search-a-star
  • css
  • fonts
  • img
  • js
    • a-star.js
    • assets.js
    • canvas.js
    • main.js
  • model
    • map.json
  • index.html

O Algoritmo está implementado no arquivo js/a-star.js. O algoritmo foi implementado de forma recursiva para respeitar o princípio DRY (don't repeat yourself).

// Antes de montar o caminho é necessário calcular o h_cost(heuristic) baseado no destino
// utilizando a fórmula √((ax - bx)² + (ay - by)²)
map = set_h_cost(map, destiny);

// Chamada da função, último parametro deve ir um array vazio para indicar que é a primeira chamada.
path_builder(map, node, []);

function path_builder(map, node, path){
    path.push(node);
    // Se o h_cost do nó for 0 então o caminho chegou ao destino
    if(node.h_cost == 0){
        node.g_cost = 0;
        paths[get_cost(path)] = path.slice();
        return paths;
    }
    // ordena os filhos pelo menor g_cost    
    node.roads = json_sort_values(node.roads);
    // percorre os filhos do nó atual
    for (var i = 0; i < node.roads.length; i++) {
        // ajuste de f_cost para o caminho não abrir nós na direção oposta ao destino
        var node_f_cost = Math.round(node.f_cost*2);

        // pega os dados do nó filho para calcular o f_cost
        var road = json_find(map, "name", get_pin(node.roads[i]));
            road.g_cost = get_value(node.roads[i]);
            road.f_cost = road.g_cost + road.h_cost;

        // verifica se o caminho está na direção correta e se o nó filho não foi aberto
        if(road.f_cost < node_f_cost && !json_find(path, "name", road.name)){
            node.g_cost = road.g_cost;
            path_builder(map, road, path);
            path.pop(node);
        }
    }
}

Os dados são lidos do arquivo model/map.json. O arquivo armazena um array de objetos com a seguinte estrutura, que pode ser facilmente replicável.

{
    "name" : "Arad",
    "longitude" : 49,
    "latitude" : 136,    
    "roads" : [
        {"Timisoara": 118},
        {"Sibiu": 140},
        {"Zerind": 75}
    ]
},

longitude e latitude são utilizados para a representação gráfica(x,y), e o atributo roads lista os nós adjacentes e custo para alcançar cada um deles.

DEMO

Você pode conferir a demo em: marcelobns.github.io

Licença de Uso

GNU GENERAL PUBLIC LICENSE
Version 3, 29 June 2007