Minecraft edu - Sorting simulator 만들기

4학년에 졸업하려고 여러 과목을 듣다 보니 1학년... 과목을 듣게 되었다. 

문제해결과 프로그래밍이라는 과목이 마인크래프트 교육용 버전을 사용해서 정렬 알고리즘을 구현하는 과제가 있어서 만져보고 있다. 

에이전트를 사용하라고 하는데 생각보다 잘 안되서 이상하긴 하지만, 뭐 다 했으니 토이 프로젝트 느낌으로 블로그에 남긴다.

1. 정렬 알고리즘

본 프로젝트에서는 나만의 정렬 알고리즘을 마인크래프트에서 구현하는 것이다.
Divide and conquer 개념의 대표적인 quick sort 알고리즘을 부수기와 설치하기로 구현하고, 예시로 보여진 bubble sort를 성능을 확인하기 위한 기준으로 사용해 성능의 차이가 얼마나 나는지 확인한다.

1.1 성능의 비교 방법

알고리즘의 평균적인 성능을 알기 위해서는 동일한 배열을 상대로 해야 한다고 생각할 수 있으나 배열이 섞인 상태에 따라 알고리즘의 성능은 다를 수 있다. 또한, 사용하는 알고리즘들에 대한 시간 성능 비교를 해야 하기 때문에 각각 25 번의 무작위 배열을 대상으로 걸리는 시간의 평균으로 비교한다.

1.2 Bubble sort의 구현 - 성능 참조 용도

set 기능을 사용해 블록을 바로 설치할 수도 있다. 그러나 에이전트를 활용해야 하기에 에이전트의 다음 기능들(위치, 블록 측정, 움직임, 수집, 파괴, 버리기)을 활용한다.

• agent.get_position()
• agent.inspect(AgentInspection.BLOCK, FORWARD)
• agent.move(RIGHT, 1)
• agent.teleport(world(j,0,1), NORTH)
• agent.destroy(FORWARD)
• agent.collect_all()
• agent.place(FORWARD)
• agent.set_slot(1)
• agent.drop_all(LEFT)

def bubbleSort(self, A, n):
    for i in range(n):
        for j in range(0, n-i-1):
            init_pos()
            if self.arr[j] > self.arr[j + 1]:
                self.blockSwap_tp(j, j+1)

1.3 Quick sort의 구현

def quicksort(self, A_, low, high):
    A = []
    A = A_

    if len(A) == 1:
        return
    if low < high:
        pp = self.partition(A, low, high)  # pi Pivot position
        self.quicksort(A, low, pp - 1)
        self.quicksort(A, pp + 1, high)

def partition(self, A_, low, high):
    A = []
    A = A_
    pivot = A[low]
    j = low

    for i in range(low + 1, high + 1):
        if (A[i] < pivot):
            j += 1

            # swap A[j], A[i]
            self.blockSwap_tp(j, i)

    self.blockSwap_tp(j, low)

    return j

뭐 프로젝트가 통과될지는 모르겠지만, 각각 10번씩 돌려보니까 버블정렬 평균 161.1 초, 퀵정렬 평균 54.5 초가 걸렸다.

2. 블록의 setting

본 프로젝트에서는 523부터 542 사이의 정수들로 이뤄진 하나의 배열이 주어졌을 때 정렬을 수행하고 “clear” 명령으로 초기화를 할 때까지 다른 배열을 처리하지 않는다. 즉, 한 번에 하나의 배열만 정렬 업무를 수행한다. 이 점을 통해 블록들은 굳이 여러 곳에 설치되지 않고 한 곳에만 설치되어도 문제가 없음을 알 수 있다. 마인크래프트에는 상대 좌표 pos와 절대 좌표 world를 사용할 수 있고 앞서 설명한 점을 쉽게 구현할 수 있도록 절대 좌표 (0,0,0)부터 (11,0,0)까지 배열을 블록으로 구현할 수 있도록 한다.

def init_pos():
        # player.teleport(world(0, 0, 5))
        agent.teleport(world(0,0,1),NORTH)

def getArr(num):
    arr = []
    for i in range(num):
        temp = randint(523, 542)
        while temp in arr:
            temp = randint(523, 542)

        arr.append(temp)

    return arr

def set_blocks():
    init_pos()
    
    lst = getArr(11)
    for i in range(len(lst)):
        blocks.place(lst[i], world(i, 0, 0))

참고 : 마인크래프트의 좌표계

3. 블록의 clearing

본 프로젝트에 사용하는 원소 블록은 용암 등을 사용하여 쉽게 제거할 수 있다. 그러나 마인크래프트 에듀 버전에서 에이전트의 움직임을 응용하는 것에 익숙해지기 위해 에이전트가 바로 앞에 블록이 존재할 때에 앞의 블록을 부수고 오른쪽으로 한 칸 이동하도록 한다.

이 경우 바닥에 존재하는 아이템들이 다음 시연에 방해가 될 수 있다.

/kill @e[type=item]

이를 해결하기 위해 위 명령어를 사용해 지상에 있는 아이템들을 다 삭제하고, 에이전트의 월드 위치를 초기화한 뒤 clearing이 완료되었음을 알 수 있도록 간단한 메시지를 출력한다.

순서로 나타내면 다음과 같다.

1. 에이전트의 위치를 world (0,0,1)로 옮긴다
2. 앞에 블록이 존재하는지 확인한다
3. 있다면, 앞의 블록을 제거하고 오른쪽으로 1 칸 간다
4. 더 이상 블록이 없다면 지상에 뿌려진 아이템들을 명령어로 제거한다

def destroy_blocks():
    init_pos()
    while(agent.inspect(AgentInspection.BLOCK, FORWARD)):
        agent.destroy(FORWARD)
        agent.move(RIGHT,1)
    
    agent.drop_all(LEFT)
    player.execute("/kill @e[type=item]")
    player.say(":)")