미로 효율성 🌸시각화🌸해서 판단하기 (C++, openFrameworks)

Siwon Yoo·2022년 6월 25일

🎈프로젝트 소개

학교에서 openFrameworks를 자유롭게 활용해 개발하는 프로젝트 과제가 나왔다. 나는 미로 생성 알고리즘의 경향성과 효율성을 직관적으로 판단할 수 있도록 시각화하는 그래픽 작업을 만드는 것을 주제로 프로젝트를 수행했다. 아래에서 내가 진행한 프로젝트를 소개한다.

프로젝트 환경
- Visual Studio 2017
- openFrameworks version 0.11.2
적용 알고리즘: C 기반으로 직접 구현
- Eller's algorithm(미로 생성)
- BFS(미로 탐색)
- Heap Sort(탐색 결과 정렬)
개발 기간
- 총 4일간
몇명이서?
- 나 혼자

🎈구현

📌미로 생성

Eller's algorithm을 적용해 미로를 생성했다.
Eller's algorithm은 완전 미로를 생성하는 알고리즘으로, 미로 내 폐쇄된 공간이나 순환 경로가 없도록 한다. Eller's algorithm은 (0, 0)의 행-열부터 마지막 행-열까지 진행하며 임의로 칸 사이 경계벽을 없애는 과정을 거쳐 생성된다. 상세 로직은 다음과 같은 흐름을 따른다.

첫 번째 행을 모두 다른 영역으로 초기화하고, 옆 칸과 자신의 칸 사이 경계벽을 임의로 없애거나, 없애지 않는다.
{한 행에서 아래 행으로의 경계벽을 임의로 없애거나, 없애지 않는다. 단, 현재 칸이 행 내 동일 영역의 마지막 칸인데 아직 현재 행에서 한 번도 아래 행으로 영역을 확장하지 않았다면, 필수적으로 아래 행으로 영역을 확장한다.
윗 행에서 확장한 칸은 해당 칸과 동일한 영역으로, 확장되지 않은 칸은 새로운 영역으로 취급한다. 새로운 행의 가장 왼쪽부터 오른쪽으로 한 칸씩 진행하며 임의로 영역을 확장한다.}
마지막 행에 도달할 때까지 {위 과정}을 반복한다. 마지막 행에서는, 첫 칸부터 진행하며 오른쪽 칸과 같은 영역에 해당하면 경계벽을 그대로 두고, 다른 영역에 해당하면 필수적으로 경계벽을 없앤다.

설명한 대로의 알고리즘을 그대로 적용해서, 미로의 너비와 높이를 N, M으로 입력받았을 때 N*M 크기의 완전 미로를 생성하는 프로그램을 작성했다. 아래는 작성한 프로그램으로 10*10 크기의 미로를 생성한 결과이다.

📌미로 탐색

미로 탐색은 너비 우선 탐색(BFS) 알고리즘을 그대로 적용했다. 나에게 익숙한 방식대로 BFS를 구현하기 위해 위와 같이 생성한 미로에서 이동할 수 있으면 0, 이동할 수 없으면 1 형식(Bit-form)으로 미로를 한 번 바꿔 주고, BFS 탐색을 수행했다.
인접한 미로의 칸 중 방문하지 않은 칸을 Queue에 넣고, 하나씩 pop하며 탐색했다. 탐색하는 과정에서 출발점으로부터 미로의 각 칸까지 도달하는 데 걸린 거리를 계산하기 위해서, Queue에서 pop할 때 마다 현재 탐색 중인 좌표까지 걸린 BFS distance를 따로 저장했다. 미로의 네 꼭짓점으로부터 각각 탐색을 수행했고, 총 BFS를 네 번 수행했다.

📌정렬

앞서 탐색 과정에서 모든 좌표에 대한 BFS distance를 계산했다. 시각화를 위해 산출된 모든 거리 값을 {도달하기 가장 어려웠던 좌표 ~ 쉬웠던 좌표} 순으로 정렬하기 위해 Heap을 구현했다. First에는 BFS distance를, second에는 좌표를 담고 있는 pair<int, pair<int, int>> 형태로 이루어진 배열을 만들어 활용했다. Max Heap을 구현하기 위해서, 이진 트리의 root 노드부터 자식 노드 중 더 큰 노드로 진행하며 탐색해 Max heap에서의 적절한 위치에 원소를 삽입했다. 이후 root의 원소를 빼고, 마지막 index의 노드를 root자리로부터 자식 노드로 비교하며 적절한 자리를 찾아 주며 원소를 delete했다.
사실 Heap은 priority queue를 구현하기 위한 자료구조인 만큼, 본 프로젝트에서처럼 단순 정렬의 목적으로 사용하기에는 좀 과하다. 굳이 Heap sort를 하지 않아도 더 단순하게 정렬할 수 있는 방법이 많이 있지만(예컨대 Quick sort 등), 학교 과제인만큼 다소 퍼포먼스를 보이고자 Heap으로 구현했다.

📌시각화 및 애니메이션

BFS distance에 따라 예쁘게 정렬된 좌표의 위치에, 10가지 색상으로 분기해 조화로운 색상의 원들을 배치했다. 색 조합은 여기를 참고했다.

색을 배치해 놓고 보니, 너무 단조로웠다. 뭔가 각 원들이 살아 움직이면서, 자신들의 존재감을 외칠 생동감이 필요해 애니메이션을 구상했다. 심장 박동처럼 각 점들이 두근두근대면서 몇 번 움직이다, 꽃 피는 것처럼 확 퍼지도록 만들면 멋있을 것 같았다. ofApp 클래스의 멤버 함수인 update() 함수안에서 아래와 같이 작성해 애니메이션을 구현했다. update() 함수는 지속적으로 반복 호출되기 때문에, 호출 시마다 startCnt와 dotScale을 미세하게 증가시켜 부드러운 애니메이션을 구현했다. 두근두근 효과를 만들기 위해서 dotScale의 크기에 따라 dotDwindleFlag와 같은 Flag를 사용해 커지는 속도보다 빠르게 점을 감소시키고, 꽃 피는 Bloom효과를 위해 growRapid Flag를 활용했다.

startCnt++;
if (10 < startCnt) {		//점들이 반짝일 시간 간격
if (bounceCnt > 2) {
	growRapid = true;
}
// Bloom 효과
if (growRapid) dotScale += 3;
if (dotScale > 70) dotScale += 6;
if (dotScale > 130) {
	mazeRegen();
}
//숨쉬기(Bounce) 효과
dotScale += 0.4;       // always
if (dotDwindleFlag) {  // if flag
	dotScale -= 0.81;
}
if (dotScale >= 18.2) {  //한번 반짝일 때 얼마만큼 커지는지
	dotDwindleFlag = 1;
}
if (dotScale < 15) {
	dotDwindleFlag = 0;
	bounceCnt++;
	startCnt = 0;
	cout << "Bounce count is: " << bounceCnt << endl;
}
}

이전에 웹 페이지나 앱을 만들 때에도, ~~누군가 만들어 놓은 라이브러리는 얼마든지 있었기에~~ 애니메이션을 직접 구현해 본 적은 없었다. 간단한 애니메이션이더라도 생각하던 것을 직접 구현하는 것은 새로운 경험이었고, 꽤 의미 있었다.

예쁘죠?

🎈프로그램 동작 플로우

지금까지 설명한 과정이 동작하는 플로우를 나타낸 플로우차트이다.

Eller's algorithm을 적용한 미로를 생성하고, 사용하기 위해 적절한 자료구조로 저장하고, BFS 탐색을 수행하고, Heap에 넣어 정렬하고, 각 좌표에 BFS Distance를 배치하고, 이 과정이 완료되면 isGem 플래그를 true로 만들어 draw()와 update() 함수에서 시각화 및 애니메이션이 동작하도록 한다. 애니메이션이 동작하면서 Bloom 효과 동작 중 dotScale의 크기가 커지면 mazeRegen() 함수가 동작해 새 미로를 생성하고, 프로그램 종료 시까지 이 과정이 반복된다.

🎈결론

완성한 프로젝트를 쳐다보고 있으면, 정말 중독성 있어서 시간 가는 줄 모르고 쳐다보게 된다. 유명해지게만 한다면 현대인의 휴식 문화로 자리잡은 불멍, 물멍, 산멍을 이은 Blooming maze flower멍이 될지도..

넋 놓고 열심히 쳐다본 결과, Eller's algorithm의 경향성 및 효율성을 판단할 수 있었다. 일반적으로, Eller's algorithm으로 생성된 미로는

네 꼭짓점에서 출발할 때, 미로의 중심에 고립된 공간일수록 도달하기가 힘들었다.
미로의 하단부보다, 상단부에 도달하기가 힘들었다.

1번은 사실 당연한 얘기이고, 2번은 타당한 근거가 있는 이야기이다. Eller's algorithm은 미로의 가장 윗 행부터 임의로 벽을 없애고, 아랫 행으로 내려오면서 막혀 있던 벽을 없애 간다. 그러다 마지막 행에 도달해서는 막혀 있다면 다 뚫는 과정을 거치기 때문에, 아래 행으로 갈수록 윗쪽 행과 비교해 상대적으로 접근성이 좋아진다. 짐작한 가설을 드러나는 결론으로, 눈으로 확인할 수 있어 뿌듯하고 즐거웠다.

🎈후기

처음으로 C/C++로 의미 있는 프로젝트를 수행해본 것 같다. 하나의 크게 사용자 Interaction이 있진 않지만, 처음으로 PC에서 동작하는 애플리케이션을 만들어 본 경험이 즐거웠다. C/C++로 모바일 앱을 만들어 봐도 재미있지 않을까..?

한 학기동안 한 과목에서만 과제를 50건 제출받을 수 있다니.. 꽤 악랄하다고 생각한다. 채점하신 조교님도 정말 고생이 많으셨을 것 같다. 이 글을 이번 학기를 성공적으로 마무리한 모든 대학생과 대학원생 분들께 바칩니다. 고생 많으셨습니다 :)

Siwon Yoo

세상은 넓고 배울 건 언제나 많다😃

이전 포스트

🔥패기🔥로 무장한 컴공 2학년의 인턴 도전기🚀

다음 포스트

[회고] 간단한 LG Aimers 수료 후기🏃‍♂️

24개의 댓글

준환

2022년 6월 25일

너무잘봤어요!!! 최고에요 시원님

1개의 답글

sonam singh

2022년 9월 3일

Glad to see this astounding article, You are giving motivation, inspiration to us.
http://www.pujaescort.in/
https://www.bangalore-escort.in/
http://www.anshikabangaloreescorts.in/
http://www.bangalorehotescorts.co.in/
http://www.bangalore-escorts.in/

답글 달기

pooja sharma

2022년 9월 22일

Hi am pooja sharma accompanies relative which gives you best to best assistance with accompanies. Administration is constantly given on our site, at whatever point you need, you can get it on our site.
https://www.sapnadelhi.com/escorts-aerocity/
https://www.sapnadelhi.com/dwarka-escort-girls/
https://www.sapnadelhi.com/escorts-mahipalpur/
https://www.sapnadelhi.com/escorts-south-delhi/

답글 달기

Nidhi sani

2022년 11월 25일

I read your article and find you article is brimming with data. Continue to post that is exceptionally useful for those individuals who is searching for these sort of data.
https://www.gurgaonescortsservice.co.in/delhi-escorts.html 4
http://www.mumbaimodels-escorts.com/delhi-escorts.html
http://www.mumbai-escort.com/delhi-escorts.html
http://www.kingescorts.in/delhi-escorts.html
https://www.aashigupta.co.in/delhi-escorts.html

답글 달기

anju sharma

2023년 3월 17일

This is really a nice site post. There really won't be many people, the way you did. I am really impressed that such a huge amount of data has come out regarding this topic and with the class you have written in your blog. that's clan praise
https://www.thedelhicallgirls.com/

답글 달기

Akriti Verma

2023년 3월 23일

With our Russian Escorts in Bangalore, you can enjoy a nice time with your partner. We love to serve you and we want you to have a good time. Are you looking for some Indian girls? Then, contact us and come to our Ladies Escorts.
https://www.thebangaloreescorts.in/russian-call-girls.html

답글 달기

Akriti Verma

2023년 3월 23일

You can hire any girl you want. These girls work in an organization where we can have a chance to meet them and enjoy it. We have many types of services you can choose from; a good time with your girl is waiting for you. ||
https://russianbangaloreescorts.blogspot.com/2023/02/russian-escorts-in-bangalore.html ||
https://telegra.ph/VIP-Russian-Escorts-in-Bangalore-Available-For-Sexual-Fun-02-21 ||
https://www.atoallinks.com/2023/bangalore-russian-escorts/ ||
https://russianescortsinbangalore.samexhibit.com/blog ||
https://educatorpages.com/site/akriti69 ||
https://bangalorehotescorts.hashnode.dev/russian-escorts-in-bangalore ||
https://thebangaloreescorts.bcz.com/2023/02/22/russian-escorts-in-bangalore-hub-of-sexual-joy/ ||
https://akriti69.blogrip.com/2023/02/22/russian-escorts-in-bangalore/ ||
http://iamakritiverma654321.populr.me/bangalore-russian-escorts ||
https://www.polyeyes.com/Article/Get-The-Real-Sensual-Satisfaction-with-Bangalore-Russian-Escorts ||
https://justpaste.it/cafxo ||
https://akriti01.skyrock.com/3354783792-Hire-Russian-Escort-Service-in-Bangalore-to-Enjoy-Your-Time-with.html ||
https://www.gamerlaunch.com/community/users/blog/6223159/2189240/get-high-profile-russian-escorts-in-bangalore-for-/?gid=535 ||
https://russianescortinbangalore.bloggersdelight.dk/2023/03/02/our-vip-russian-escorts-service-in-bangalore-make-your-night-memorable/

답글 달기

anju sharma

2023년 4월 13일

I imagine that it is ideal to shape extra on this issue, it won't be a distant point in any occasion considered individuals are adequately not to visit on such subjects.

https://www.jaipurbeauties.in/jaipur-call-girls ||
https://www.soniyachauhan.net/jaipur-call-girls.html ||
http://www.peehu4u.com/jaipur-call-girls.html ||
http://www.escortsinjaipurcity.com/jaipur-call-girls.html ||
http://www.pinkcityjaipur.in/jaipur-call-girls.html ||

답글 달기

anju sharma

2023년 4월 13일

I never defend myself from saying something concerning it. You're working thoroughly. It's dumbfounding to disengage other's assessment and the manner by which it connects with them or their clients, as their point of view would help you later on.

http://www.escortsserviceinjaipur.in/jaipur-call-girls.html ||
http://www.jaipurqueen.net.in/jaipur-call-girls.html ||
http://www.suhaniescorts.in/jaipur-call-girls.html ||
http://www.jaipurescortsgirl.com/jaipur-call-girls.html ||
http://www.escort-jaipur.in/jaipur-call-girls.html ||

답글 달기

anju sharma

2023년 4월 13일

I like to see and visit any data on this posting. I figure I will return in the future to see another remarkable one here. If you have any desire to find a couple of plans concerning me, carefully don't stop quickly to reach me here.

http://www.jaipurescortsservices.in/jaipur-call-girls.html ||
http://www.lalita.co.in/jaipur-call-girls.html ||
http://www.jaipurescortservice.co.in/jaipur-call-girls.html ||
http://www.raimaoberoi.in/jaipur-call-girls.html ||
http://www.adna.in/jaipur-call-girls.html ||

답글 달기

anju sharma

2023년 4월 13일

What other spot might anyone at some point have the choice to get such data in a particularly ideal framework for making? I have a show a piece of a month from now, and I'm on a post for such data.

http://www.sotcjaipur.com/jaipur-call-girls.html ||
http://www.jaipurescortservices.net/jaipur-call-girls.html ||
http://www.sanjanaescorts.com/jaipur-call-girls.html ||
http://www.jaipurescortscity.in/jaipur-call-girls.html ||
http://www.escortjaipur.co.in/jaipur-call-girls.html ||

답글 달기

anju sharma

2023년 4월 13일

I have begun making notes with the tips that you shared a short time back. This breezes up being a snappier way.

http://www.jaipurvipescorts.com/jaipur-call-girls.html ||
http://www.sonika.co.in/jaipur-call-girls.html ||
http://www.escortserviceinjaipur.in/jaipur-call-girls.html ||
http://www.jaipurgirls.co.in/jaipur-call-girls.html ||
http://www.bedpari.in/jaipur-call-girls.html ||

답글 달기

anju sharma

2023년 4월 13일

I feel genuinely about this and truly like ending up being more acquainted with extra on such a field. Do you mind restoring your blog district with extra course of action? It should be truly colossal for us by and large.

https://www.jaipurescortsclub.in/jaipur-call-girls.html ||
http://www.escortsserviceinjaipur.com/jaipur-call-girls.html ||
https://www.taini.in/jaipur-call-girls.html ||
https://www.escortsvilla.in/jaipur-call-girls.html ||
https://www.jaipurmidnight.com/call-girls-in-jaipur.html ||

답글 달기

Noor Ansari

2023년 8월 3일

You really want to check out at a test for likely the best web diaries on the web. I will propose this site.
https://www.escortsdeals.com/call-girls/hyderabad
https://www.escortsdeals.com/call-girls/lucknow
https://www.escortsdeals.com/call-girls/chennai
https://www.escortsdeals.com/call-girls/surat
https://www.escortsdeals.com/call-girls/kolkata

답글 달기

russian girl

2023년 11월 12일

답글 달기

natasha bajaj

2024년 2월 14일

Thank you for this wonderfull post! https://www.escortsgurgaon.co.in/ It has long been extremely helpful. I wish that you will carry on posting your knowledge with us thanks for sharing this post.

답글 달기

natasha bajaj

2024년 2월 14일

Thank you for this wonderfull post! https://www.escortsgurgaon.co.in/ It has long been extremely helpful. I wish that you will carry on posting your knowledge with us thanks for sharing this post.

답글 달기

natasha bajaj

2024년 2월 20일

It felt very good to me and it made a lot of difference to me and https://www.bookdelhiescorts.com/ it is true that I can believe it and it made me very happy and now I am very happy it really made me happy.

답글 달기

natasha bajaj

2024년 2월 23일

Thanks for sharing this information. I really like your blog post very much. You have really shared a informative and interesting blog post . I really enjoyed it and my heart became very happy and I can swear that I have a lot of confidence in it.
https://www.delhiescortsnumber.com/escorts-service-in-crowne-plaza-okhla-hotel-new-delhi.html
https://www.delhiescortsnumber.com/escorts-service-in-diplomat-hotel-new-delhi.html
https://www.delhiescortsnumber.com/escorts-service-in-eternity-hotel-new-delhi.html
https://www.delhiescortsnumber.com/escorts-service-in-fabhotel-prime-sage-new-delhi.html
https://www.delhiescortsnumber.com/escorts-service-in-galaxy-hotel-gurgaon.html

답글 달기

natasha bajaj

2024년 2월 28일

It felt very good to me and it made a lot of difference to me and it https://www.delhiescortsgirls.com/ is true that I can believe it and it made me very happy and now I am very happy it really made me happy.

답글 달기

natasha bajaj

2024년 3월 4일

It felt very good to me and it made a lot of difference to me and it is true that I can believe it and it made me very happy and now https://www.delhiescortsnumber.com/ I am very happy it really made me happy.

답글 달기

natasha bajaj

2024년 3월 23일

Appreciation for the unfathomable post you posted. https://www.alisachopra.in/ I like how you depict the momentous substance. That focuses you raise are attested and sensible.

답글 달기

natasha bajaj

2024년 3월 27일

Jaipur Escorts Service has an exemplary reputation for being intelligent, classy, and authentic. https://www.escortsservicesjaipur.in/call-girl-contact.html They are always eager to please. Whether you're celebrating a birthday, a special anniversary, or just want to, Independent Jaipur Escorts are the perfect way to make your night out in the city that much more special! With a touch of class, our city escorts are sure to make you feel like royalty. https://www.escortsservicesjaipur.in/call-girls-photos.html

답글 달기