[JS] a star algorithm

Graph ( node - edge ) 구조에서 PathFinding 의 해결 방법인 "A star" 의 구현입니다.

 

A* 알고리즘의 구현 예로 2 차원 배열을 자주 사용하는데, wiki 의 pseudocode 를 참고하여 작성했습니다.

wiki 에서는 없는 "Visited" 를 두어 탐색을 마친 node 를 재방문하지 않도록 했습니다.

heuristic func ( H ) 는 func 로 두어 자유롭게 작성할 수 있습니다.

 

먼저, Edge 를 두어 노드 사이의 간선의 이동 비용 ( Cost ) 를 두었습니다.
이는 Path 의 재구성 ( 탐색 종료 이후 ) 에도 재사용됩니다.

// relation of graph node
class Edge {
    // src, des is Node
    constructor(src, des, cost) { 
        this.Cost = cost; // cost of "src" to "des".
        this.Parent = src; 
        this.Next = des; 
    } 
}

Node 의 구현은 식별자 ( Id ) 와 H 계산을 위한 func 입력 받으며,
이동 불가를 표현하는 Blocked 을 포함합니다.

CameFrom 은 Path 재구성에서 사용됩니다.

MakeNodeMap 은 2 차원 배열로부터 Node 연결을 구성하는 Helper 이며,
개별 데이터로부터 노드를 구성하는 로직을 자유롭게 작성하면 됩니다.

class Node { 
    constructor(id, funcHeuristicCost) { 
        this.Id = id; 
        this.Edge = new Array(); 

        this.FuncHeuristicCost = funcHeuristicCost; 
    } 

    getId() { 
        return this.Id; 
    } 

    setBlock() { 
        this.Blocked = true; 
    } 

    addNeigbor(edge) { 
        this.Edge.push(edge); 
    } 

    setCameFrom(parent) { 
        // cost is not used. 
        this.CameFrom = new Edge(this, parent, undefined); 
    } 

    setVisit() { 
        this.Visit = true; 
    } 

    getEdge() { 
        return this.Edge; 
    } 

    heuristic(goal) { 
        return this.FuncHeuristicCost(this, goal); 
    } 

    // helper of generate node from "arr data".
    static makeNodeMap(arr) { 
        // NOTE: cost about current to goal. 
        function heuristic(current, goal) { 
            const currentId = current.getId(); 
            const currentCol = parseInt(currentId / n); 
            const currentRow = currentId % n; 

            const goalId = goal.getId(); 
            const goalCol = parseInt(goalId / n); 
            const goalRow = goalId % n; 

            return Math.max(goalCol - currentCol, goalRow - currentRow) 
        } 

        function getNode(idx) { 
            if (nodeMap[idx] === undefined) { 
                const col = parseInt(idx / n); 
                const row = idx % n; 

                const current = new Node(idx, heuristic); 

                const block = arr[col][row] === 1; 
                if (block) { 
                    current.setBlock(); 
                } 

                nodeMap[idx] = current; 
            } 

            return nodeMap[idx]; 
        } 

        const n = arr.length; 

        const nodeMap = new Object(); 

        const directionMap = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]; 
        // ready for node and binding edge. 
        for (let i = 0; i < n ** 2; i++) { 
            const current = getNode(i); 
            // 8 direction 
            for (const direction of directionMap) { 
                const col = parseInt(i / n); 
                const row = i % n; 

                const neighborCol = col + direction[0]; 
                const neighborRow = row + direction[1]; 
                // validation 
                if (-1 < neighborCol && neighborCol < n && -1 < neighborRow && neighborRow < n) { 
                    const neighbor = getNode(neighborCol * n + neighborRow); 
                    if (!neighbor.Blocked) { 
                        current.addNeigbor(new Edge(current, neighbor, 1)); 
                    } 
                } 
            } 
        } 

        return nodeMap; 
    } 
}

 

 A* 에서는 Heap 으로 OpenSet 을 구성했습니다.

( 탐색 시간 비용을 logN 으로 사용합니다 )

Path 를 생성하는 함수 이외에 Run 에서 알고리즘을 확인할 수 있습니다.

// NOTE: npm install --save @datastructures-js/heap 
const { Heap } = require('@datastructures-js/heap'); 

class Astar { 
    // 'cameFrom' is replaced by 'edge'. 
    static reconstruct_path(current) { 
        const path = new Array(); 
        path.push(current); // current is des. 
        while (current.CameFrom) { 
            current = current.CameFrom.Next; 
            path.push(current); 
        } 

        return path; 
    } 

    static run(src, des) { 
        if(src == des) return [src]; 
        else if(src.Blocked || des.Blocked) return []; 

        function getScore(target, index) { 
            return target[index] === undefined ? Infinity : target[index]; 
        } 

        const gScore = new Array(); 
        const fScore = new Array(); 

        gScore[src.getId()] = 0; 
        fScore[src.getId()] = src.heuristic(des); 

        const openSet = new Heap((a, b) => { 
            return getScore(fScore, a.getId()) < getScore(fScore, b.getId()); 
        }); 

        src.setVisit(); 
        openSet.push(src); 

        while (!openSet.isEmpty()) { 
            const current = openSet.pop(); 

            if (current == des) { 
                return Astar.reconstruct_path(current); 
            } 

            for (const edge of current.getEdge()) { 
                const neighbor = edge.Next; 
                // total cost about 'current' + 'next'. 
                const tentative_gScore = getScore(gScore, current.getId()) + edge.Cost; 
                if (tentative_gScore < getScore(gScore, neighbor.getId())) { 
                    neighbor.setCameFrom(current); 
                    gScore[neighbor.getId()] = tentative_gScore; 
                    fScore[neighbor.getId()] = tentative_gScore + neighbor.heuristic(des); 

                    if (!neighbor.Visit) { 
                        neighbor.setVisit(); 
                        openSet.push(neighbor); 
                    } 
                } 
            } 
        } 

        return []; 
    } 
}

마지막으로 예시는 아래와 같습니다.

// example. 
const nodeMap = Node.makeNodeMap([[0, 0, 0], [1, 1, 1], [1, 1, 0]]); 
const src = nodeMap[0]; 
const des = nodeMap[8]; 

const path = Astar.run(src, des); 

console.log(path);