A* Algorithm -3

앞에 포스트에서 기초 세팅이 끝났으니, Update를 해야한다.(아직 그려진거 없음)

 

virtual bool OnUserUpdate(float fElaspedTime) {
        // 노드의 사이즈와 두께를 정해준다.
        int nNodeSize = 9;
        int nNodeBorder = 2;

        // 마우스 위치를 기반으로, 노드 단위의 위치 식별
        int nSelectedNodeX = m_mousePosX / nNodeSize;
        int nSelectedNodeY = m_mousePosY / nNodeSize;

        // 마우스를 놓으면
        if (m_mouse[0].bReleased) {
            // 맵의 노드 범위 안에서
            if (nSelectedNodeX >= 0 && nSelectedNodeX < nMapWidth) {
                if (nSelectedNodeY >= 0 && nSelectedNodeY < nMapHeight) {
                    // Shift 키 누르고 있으면 -> 시작점 세팅
                    if (m_keys[VK_SHIFT].bHeld) {
                        nodeStart = & nodes[nSelectedNodeY * nMapWidth + nSelectedNodeX];
                    }
                    // Ctrl 키 누르고 있으면 -> 끝점 세팅
                    else if (m_keys[VK_CONTROL].bHeld) {
                        nodeEnd = & nodes[nSelectedNodeY * nMapWidth + nSelectedNodeX];
                    }
                    // 그냥 키는 ->장애물 세팅
                    else {
                        nodes[nSelectedNodeY * nMapWidth + nSelectedNodeX].bObstacle = !nodes[nSelectedNodeY * nMapWidth + nSelectedNodeX].bObstacle;
                    }
                    // 이해를 위해서 AStar 알고리즘은 뒤에서 설명
                    Solve_AStar();
                }
            }
        }

        ...

 

 

길을 생성하는 코드를 제외하고 노드와, 시작점, 끝점만 그렸을때

 

...
// Fill은 특정 길이에서 특정 높이까지 색깔을 채움.
// Path Update ( 노드보다 늦게 만들면 노드 가려짐, draw 순서 중요)

// 먼저 화면을 전부 clear 하게 만듦.
Fill(0, 0, ScreenWidth(), ScreenHeight(), L ' ');

// 전체 노드를 훑으면서 
for (int x = 0; x < nMapWidth; x++) {
    for (int y = 0; y < nMapHeight; y++) {
        // 초기설정때 넣어주었던 vecNeighbours 들 에다가 
        for (auto n: nodes[y * nMapWidth + x].vecNeighbours) {
            // 라인을 그려줌( 노드 사이의 길) 
            //NodeSize = 한 픽셀의 단위
            // NodeSize /2 = 노드의 시작 위치를 노드의 중앙으로 설정 
            // DrawLine파라미터( x시작점,y시작점,x도착점,y도착점,선 스타일, 선 색상)
            DrawLine(x * nNodeSize + nNodeSize / 2, y * nNodeSize + nNodeSize / 2, n - > _x * nNodeSize + nNodeSize / 2, n - > _y * nNodeSize + nNodeSize / 2, PIXEL_HALF, FG_DARK_BLUE);
        }
    }
}

//draw Node
// 노드 전체 훑어주면서
for (int x = 0; x < nMapWidth; x++) {
    for (int y = 0; y < nMapHeight; y++) {
        // if obstacle -> color is white.
        // 장애물로 체크 된 곳 있으면 white. 아니면 기본 블루
        Fill(x * nNodeSize + nNodeBorder, y * nNodeSize + nNodeBorder, (x + 1) * nNodeSize - nNodeBorder, (y + 1) * nNodeSize - nNodeBorder, PIXEL_SOLID, nodes[y * nMapWidth + x].bObstacle ? FG_WHITE : FG_BLUE);

        // 방문한 곳은 소라색
        if (nodes[y * nMapWidth + x].bVisited) {
            Fill(x * nNodeSize + nNodeBorder, y * nNodeSize + nNodeBorder, (x + 1) * nNodeSize - nNodeBorder, (y + 1) * nNodeSize - nNodeBorder, PIXEL_SOLID, FG_CYAN);
        }
        // 노드 시작점은 초록색
        if ( & nodes[y * nMapWidth + x] == nodeStart) {
            Fill(x * nNodeSize + nNodeBorder, y * nNodeSize + nNodeBorder, (x + 1) * nNodeSize - nNodeBorder, (y + 1) * nNodeSize - nNodeBorder, PIXEL_SOLID, FG_GREEN);
        }
        // 노드 도착점은 빨간색
        if ( & nodes[y * nMapWidth + x] == nodeEnd) {
            Fill(x * nNodeSize + nNodeBorder, y * nNodeSize + nNodeBorder, (x + 1) * nNodeSize - nNodeBorder, (y + 1) * nNodeSize - nNodeBorder, PIXEL_SOLID, FG_RED);
        }

    }
}

// 노드 역추적해서 경로를 시각화 ( A Star까지 구현하면 코드 적용) 
// 노드의 도착점 설정이 되었다면
if (nodeEnd != nullptr) {
    // 역추적을 할 노드 p
    Node * p = nodeEnd;
    // p의 parent가 nullptr이 될때까지
    while (p - > parent != nullptr) {
        // 라인을 그림 (노란색)
        DrawLine(p - > _x * nNodeSize + nNodeSize / 2, p - > _y * nNodeSize + nNodeSize / 2, p - > parent - > _x * nNodeSize + nNodeSize / 2, p - > parent - > _y * nNodeSize + nNodeSize / 2, PIXEL_SOLID, FG_YELLOW);
        p = p - > parent;
    }
}

return true;
}

 

 

이렇게 해 놓으면, 일단

 

콘솔 화면에 노드와, 길 , 노드의 시작점, 노드의 끝점이 일단 화면에 나온다.

 

길까지 다 연결된 모습.

정리하자면, 각 노드에는 방문한곳, 장애물, 시작점, 끝점, 주변 노드 의 데이터가 있고, 

 

update에서 초기화를 먼저 하고, 길, 노드 순으로 그려나가면서 현재 화면이 송출되고 있다.

 

컨트롤, 쉬프트로 시작점과 끝점을 설정할 수 있고, 기본 클릭으로는 장애물 설정을 할 수 있다.