궤텔님 혹시 미로문제 도움이 될까 해서...

마침 저번학기에 숙제로 나온 Plegde Algorithm이라.

백트래킹은 전혀 안쓰니 재귀비용 걱정은 안하셔도 되고 빠릅니다. 다만 길 최적화는 좀 곤란합니다.

알고리즘 개요는 http://en.wikipedia.org/wiki/Maze_solving_algorithm#Pledge_algorithm에서 찾으시면 되겠습니다.

간단히 설명하면 벽타기 알고리즘류인데 자신이 벽타면서 꺾은 횟수를 기록하다 갈림길에서 스프링처럼 반동효과로 돌아가려는 성질을 유지해주면 됩니다.

이 알고리즘의 Precondition이 "입구가 중앙" "출구가 벽"이라는건데, 이 경우는 정 반대시니 길찾는 알고리즘에서만 입출구를 반대로 적용해주시면 될거 같습니다.

코드는 파이썬으로 되어있는데 중간 신상정보 주석 아래쪽 코드가 중요한 부분이라 이해는 쉽게 가실겁니다.

(Robot 개체가 World의 중앙에 생성되고, beeper가 출구역할을 한다 보시면 됩니다.)

숙제용으로 준 라이브러리의 보충설명은 볼드체로 =.=

#*******************************

#CS101 Introduction to Programming

#Homework #1

#*********************

#*******************************

from cs1robots import *

#load_world("**")

load_world("world3.wld") #숙제할때 테스트용으로 주어진맵 -,.-

hubo = Robot(orientation = "N", avenue = 8, street = 8 )

#미로안에 들어간 놈. 실제로 맵에 구현할때 x, y, orientation 저장해두세요.

hubo.set_trace("blue")

angular_sum = 0

#이 스프링 역할을 해주는 변수가 중요합니다. 이 알고리즘의 핵심임.

def turn_left():

    hubo.turn_left() #orientation 변수를 왼쪽으로 꺾는 단순 메소드

    global angular_sum

    angular_sum += 1 # 왼쪽으로 꺾으면 스프링 1증가.

def turn_right():

    for i in range(3):

        hubo.turn_left() #구현할땐 그냥 orientation을 오른쪽으로 꺾으세요. =,.=

    global angular_sum

    angular_sum -= 1 # 오른쪽으로 꺾으면 스프링 1감소.

    

    

##### From here, your code should be.

##### ID: ********, Name: *****************, Lab: *

def tryforward(): #직진용 매크로 함수. 성공시 True, 실패시 False 리턴

    if hubo.front_is_clear():

        hubo.move() //앞으로 한칸 전진 메소드입니다. orientation에 따라 x/y 조절하세요.

        return True

    return False

def wf(): #wall following #넵 벽타기

    if angular_sum < 0: #오른쪽으로 과하게 꺾었으면 왼쪽으로 꺾기 우선 시도

        if hubo.left_is_clear():

            turn_left()

            hubo.move()

        elif not tryforward(): #그냥 벽타세욬

            turn_right()

    elif angular_sum > 0: #왼쪽으로 과하게 꺾었으면 오른쪽으로 꺾기 우선 시도

        if hubo.right_is_clear():

            turn_right()

            hubo.move()

        elif not tryforward(): #그냥 벽타세욬

            turn_left()

    else: #사실 여기 분기까지 오는 경우가 꺾인횟수가 밸런스인 채로 직진하다 막힌경우.

            turn_left()

    

while not hubo.on_beeper(): #출구를 찾을때까지 반복

    if angular_sum != 0 or not tryforward():

        wf()

   #꺾는횟수가 0이면 벽이고 개뿔이고 일단 직진시도해보고 안되면 벽타긔

   #꺾는횟수가 언밸런스면 닥치고 벽타긔

hubo.pick_beeper()

(주의 : 여기서 보시면 미로 찾는 중 자신이 꺾는 방향 횟수를 저장해야함 - angular_sum 변수

혹시 미로가 입출구가 절대 못만나는 망한 구조면 무한루프 걸릴텐데, angular_sum에 최대/최소값 - ex +1만번 - 같은걸 제한해 break 걸으셔도 될것같습니다)

참고로 난이도조절에 쓰시려면 길 길이를 move() 횟수로 기록하면 약간 곤란합니다. 이 알고리즘으로 길을 찾을 경우 똑같은 길을 중복해서 갈 수도 있습니다. (똑같은 길이라도 angular_sum 값이 다른채로 다시 도는 경우가 자주 발생함)

제가 생각한 트릭이 있는데, 미로 크기만한 int 이중배열 maze_reach[][]을 선언하고, maze_reach의 각 요소를 매우 큰 값으로 채워줍니다. 그리고 입구위치만 0으로 설정해주고, move()를 할때마다:

temp = maze_reach[이전x][이전y]

move()

maze_reach[새x][새y] = min(maze_reach[새x][새y], temp + 1)

이런뒤 마지막 출구위치의 maze_reach 배열값을 확인해보시면 지나온 길의 길이가 나올것 같습니다.

이런식으로 해주시면 아마 최적화까지는 어려워도(꺾는방향이 최적화가 안됨;)

똑같은 길 중복 길이는 컴팩트하게 없앨 수 있을겁니다.

최적화 하시려면 진짜 BFS 쓰셔야함 -,.-

머리가 핑글핑글..~;

외계언어닥;;;;;;

저게 한글로 되있으면 그냥 이런 거구나 하는데
영어라서 겁내 복잡해 보이네 ㅡㅡ

역시 백트래킹의 기본은 BFS부터 ㅜㅜ

어제도 적었듯이... 마치 갤디터 처음열어봤는데 와우 레이드같은맵 만들고 싶거든요 차근차근알려주세요 뭐 이런느낌이예요..
프로그래밍을 배운것도 아니라 아예 기본개념부터가 잘 이해가 안되고 프로그래밍 언어도 뭐가뭔지 잘 모르겠고.. ;ㅅ;
백트래킹이 개념은 이해가 되서 트리거로 어떻게 해야할지 고민을 많이 해봤는데 제 어줍잖은 지식으로는 아무래도 힘드네요;ㅅ;

으잌 백트래킹 전혀 안쓴다고 위에 적었는데 -,.-

좀더 쉽게 설명드리면

"항상 터닝하면 어디쪽으로 많이 턴했는지 기록하기"
(변수 하나 두고 좌로 턴하면 +1, 우로 턴하면 -1 ex. 가면서 좌로 360도 돌면 +4겠죠)
"왼쪽으로 많이 턴했으면(변수>0) 오른손 따라 벽타기"
"오른쪽으로 많이 턴했으면(변수<0) 왼손 따라 벽타기"
"이것도 아니고 저것도 아니면(변수=0) 일단 벽 안타고 직진, 앞이 막혔으면 왼쪽으로 턴"

이것만 반복하다보면 언젠간 안에서 밖으로 빠져나올수가 있다는게 Pledge Algorithm입니다.

def라.. 이거 RPGXP 루비언어 한참쓸때 본 함수이름이네요 ㅋㅋ
아.. 그때가 그립다;