게임에서 길 찾기 알고리즘으로 많이 사용되는 A* 알고리즘을 직접 구현해 보았습니다.

A* 소개

 A*(에이스타) 알고리즘은 격자식 맵구조에서 시작 지점부터 도착 지점까지의 경로를 탐색하는 방법입니다. 

A* 구현

구현을 위해 필요한 용어를 간단하게 정리해보겠습니다.

노드 : 격자(타일) 한칸당 하나씩 가질수 있는 격자에 대한 탐색 정보 데이터 
열림 목록 : 탐색할 노드를 넣는 리스트 입니다.
닫힘 목록 : 탐색을 마친 노드를 넣는 리스트 입니다.

노드 데이터
G : 시작 지점부터 현재 지점까지의 소모 비용
H : 현재 지점부터 도착지점까지의 추정 비용
F : G 와 H의 합. 어떤 노드가 최적인지 판단하기 위한 점수
부모 노드 : 현재 지점으로 도달하기 바로 직전의 노드

A*의 순서를 표현하면 다음과 같습니다.

1. 시작지점의 노드 데이터를 계한하여 열림 목록에 넣음
-------------반복-------------
2. 열림 목록에서 F가 가장 낮은 노드를 꺼내서 탐색 노드로 설정함
3. 탐색 노드의 인근 지점 중 도착 지점이 있고 이동 가능한지 확인(도착 지점을 발견하면 6.으로 이동)
4. 인근 지점을 확인: 이동 가능한 지점이고, 열림 목록이나 
 닫힘 목록에 포함되어 있지 않으면 
   해당 지점의 노드 데이터를 계산하여 열림 목록에 추가
5. 탐색을 마친 노드는 닫힘 목록에 넣음
------------------------------
6. 부모노드를 따라 시작지점까지 이동한 경로의 역순이 검색된 최단 경로

구현한 코드 입니다.

function find() {

    if(startPos.x < 0 || startPos.y < 0 
        || destPos.x < 0 || destPos.y < 0) {
        alert('시작지점과 출발지점을 설정해주세요.')
        return;
    }

    const openList = [];
    const closeList = [];

    const sideList = [
        {x: 0, y: -1},
        {x: 1, y: 0},
        {x: 0, y: 1},
        {x: -1, y: 0},

        //대각선 이동
        {x: 1, y: -1},
        {x: 1, y: 1},
        {x: -1, y: 1},
        {x: -1, y: -1},
    ]

    let destNode = null;

	

	//시작지점의 노드 데이터를 계한하여 열림 목록에 넣음
    const startNode = calcF({
        ...startPos,
    }, null, destPos);
    openList.push(startNode);
    
    //열림 목록에 노드가 있으면 반복. 열림 목록에 노드가 없다면 경로 탐색 실패
    while(openList.length > 0) {
    	
    	//F가 가장 낮은 노드를 탐색노드로 설정
        openList.sort((a,b)=>a.f-b.f);
        const node = openList.shift();

		

		//인접 지점들을 탐색함
        for(let i = 0; i < sideList.length; i++) {
            const side = sideList[i];
            const sideNode = {
                x: node.x + side.x,
                y: node.y + side.y,
            };

            if(sideNode.x < 0 || sideNode.y < 0
                || sideNode.x >= mapWidth || sideNode.y >= mapHeight) {
            //맵의 범위를 초과하는지 확인
                    continue;
            }
            else if(map[sideNode.y][sideNode.x] === 1) {
            //이동할수 없는 지점이면 다음 노드 탐색
                continue;
            }
            
            //대각선 이동할때 옆 블록이 벽인지 확인
            if(i >= 4 && (map[sideNode.y][node.x] === 1 
                || map[node.y][sideNode.x] === 1 )) {
                continue;
            }


			//도착 지점 찾음   
            if(sideNode.x === destPos.x && sideNode.y === destPos.y) {
                sideNode.parentNode = node;
                destNode = sideNode;
                break;
            }


			//열림목록과 닫힘목록에 대상 노드가 포함되어 있는지 확인 후 열림목록에 추가
            if(!openList.find(n=>(n.x === sideNode.x && n.y === sideNode.y))
                && !closeList.find(n=>(n.x === sideNode.x && n.y === sideNode.y))) {
                calcF(sideNode, node, destPos);
                openList.push(sideNode);
            }            
        }       
        
        closeList.push(node);
        if(destNode) {
            break;
        }
    }
    

	//도착 지점 찾았을 때
    if(destNode) {
        pathList = [];
        let prevNode = destNode;
        //부모 노드가 없을때(시작지점)까지 경로 저장
        while(prevNode) {
            pathList.push(prevNode);
            prevNode = prevNode.parentNode;
        }
        //경로 역순
        pathList.reverse();
    }
}

function calcG(node, parentNode) {
    if(!parentNode) {
        node.g = 0;
        node.parentNode = null;
    }
    else if(node.x !== parentNode.x && node.y !== parentNode.y ) {
        node.g = parentNode.g + 14;
        node.parentNode = parentNode;
    }
    else {
        node.g = parentNode.g + 10;
        node.parentNode = parentNode;
    }
}

function clacH(node, destPos) {
    const width = Math.abs(node.x - destPos.x);
    const height = Math.abs(node.y - destPos.y);
    node.h = (width + height) * 10;
}

function calcF(node, parentNode, destPos) {
    calcG(node, parentNode);
    clacH(node, destPos);
    return node;
}

프로젝트 바로가기

https://diyplay.co.kr/project/view/5

성능 테스트 및 개선

구현한 코드의 동작 시간이 얼마나 걸리는지 테스트 해보았습니다.

맵 크기를 100*100으로 설정하고 도달할 수 없는 경로를 설정하여 시간 측정을 해보았습니다.

길찾기 실패 
총 탐색 노드 수: 9991 
정렬의 누적 시간: 21.900001049041748 
중복확인의 누적 시간: 519.9000015258789 
총 소요 시간:  
570.5

중복확인으로 표시된 노드가 닫힘목록이나 열림목록에 포함되어 있는지 확인하는 부분에서 대부분의 시간이 소요 되는것을 확인하였습니다.

해당 부분을 개선하기 위해 객체를 하나 두고 노드의 인덱스값을 키값으로 사용하여 닫힘목록이나 열림목록에 포함되었는지 여부를 확인할 수 있게 해보았습니다.

 class AddMap {
    constructor(width, height) {
        this.width = width;
        this.height = height;
        this.map = {};
    }

    add(node) {
        const idx = node.y * this.width + node.x;
        this.map[idx] = true;
    }

    isAdd(node) {
        const idx = node.y * this.width + node.x;
        return !!this.map[idx];
    }
}

실행 결과

길찾기 실패 
총 탐색 노드 수: 9991 
정렬의 누적 시간: 23.499996662139893 
중복확인의 누적 시간: 20.100004196166992 

총 소요 시간:  
69

메모리는 좀 더 쓰겠지만 이전에 비해 측정 시간은 많이 단축 되었습니다. 

추가 개선 방향

한 프레임에 너무 많은 노드를 탐색하게 되면 프레임 드랍이 일어날 수 있으니 한번 탐색할 때 최대 횟수 제한을 걸어 최대 횟수를 초과할 경우 다음 프레임에 이어서 탐색하는 방법으로 개선하는것도 괜찮아 보입니다. 

그밖에 개선 방향이나 최적화도 시간을 측정해보거나 테스트 해보면서 차근차근 탐구해 보겠습니다.

프로젝트 바로가기

https://diyplay.co.kr/project/view/6

캐릭터 이동 및 심화 작업

이전 작업들에 이어서 실제로 게임을 개발하는 것처럼 캐릭터를 이동시켜 보는 작업과 함께 몇 가지 추가 작업을 진행해 보았습니다.

진행 내용

1. 각 캐릭터는 별도의 길찾기 객체를 가집니다.
2. 한 프레임 당 탐색 수를 제한해서 일정 수를 넘기면 다음 프레임에 이어서 탐색합니다.
3. 캐릭터가 이동 중 다른 캐릭터와 만나 이동할 수 없으면 다른 경로를 다시 탐색합니다.
4. 캐릭터의 크기가 타일 보다(1 이상) 큰 경우의 길찾기를 지원합니다.( 크기가 짝수인 경우 홀수로 반올림)
5. 목적지에 도달할 수 없는 경우 목적지와 가장 가까운 타일로 이동합니다.

프로젝트 바로가기

https://diyplay.co.kr/project/view/7