안녕하세요? 도적코볼트에요!
위의 그림은 이번에 제 소개로 스팀잇에 오게 된 친구인 @sms0402 이 제 부탁을 받아서 그려준 짤방이에요. ( ㅎㅎ! )
@gotoperson 을 보면 항상 글에 일정한 짤방이 있더라구요. 그게 너무 부러웠어요. 딱 보기만해도 누가 글을 썼는지 알 수 있잖아요. 약간 스팀잇의 아이돌처럼 말이에요! 그래서 앞으로 제 글은 이 짤방을 사용하려고 합니다.
요 며칠 간 작업이 도통 안됐어요. 정확히 말하면 하고 있는데 작업이 앞으로 나가지 않았다고 하는게 맞을 것 같아요.
문제가 잘 안풀리고 있었거든요. 그렇지만 약 2.5일이 걸려서 해결한 것 같아서 이렇게 또 글을 쓰고자 합니다.
저번 포스팅(@krdoko/6-indie-game-dev-6-find-the-area-of-random-map)에서는 랜덤하게 만들어진 방의 구역을 찾아냈어요. 그리고 그것을 색을 입혀서 표현했죠!
Good morning? It's a thief kobold!
The above picture is drawn by my friend who came to SteemIt by my introduction @ sms0402.
When I look at @gotoperson, there is always a constant picture in the article. It was so envious. Just look at it and you can see who wrote it. Slightly steemit idol! So, in the future, my article is going to use this information.
I have not been able to work for a few days. I'm telling you exactly, but I do not think it's right that the work did not come forward.
The problem was not working well. But it took about 2.5 days to solve it.
In the last posting (@krdoko/6-indie-game-dev-6-find-the-area-of-random-map) I found a section of a randomly made room. And I painted it in color!
[ 이전 글에서 가져온 사진 ]
[ Photos from previous posts]
하지만 이렇게 만들어진 방들은 전부 떨어져 있어서 문제가 됐어요. 왜냐하면 플레이어는 이렇게 만들어진 맵을 이동할 수 있어야 하는데 더 이상 움직일 곳이 없다면..? 플레이를 할 수 없잖아요!
But the rooms that were made like this were all in trouble. Because the player should be able to move this map, if there is no place to move ...? You can not play!
[ 눈 앞에는 갈 곳이 없다! ]
[There is no place to go ]
그렇기 때문에 방을 이어줘야만 했어요. 하지만 아무렇게나 이을 수는 없었습니다. 만약에 아무렇게나 이어버린다면 이어지는 통로가 다른 방을 뚫고 가는 현상이 발생할 것이 분명하기 때문이었죠.
제가 원하는 방의 연결은 이런 식의 연결이었어요.
- 모든 방은 연결이 되어야 한다.
- 각 방의 연결은 그 길이가 최단길이로 연결되어야 한다.
제일 큰 조건은 위의 두 개입니다. 그렇지만 작업을 할수록 조금 씩 살이 붙어서 여러 조건이 붙게 되었어요.
- 연결을 시도하는 방 ( A )가 가장 가까이 있는 방 ( B )를 연결을 시도하려고 할 때, 이미 A와 연결된 방 ( C )가 있다면, 그 연결된 방 ( C )와 찾아내어진 방 ( B )를 검사해서 최단 거리를 비교해( A - B 사이의 거리와 A - C 사이의 거리) 둘 중에서 더 가까운 방이 연결된다!
이런 몇 가지 조건이 더 붙게 되었습니다. 말로만 들어도 헷갈리죠?
That's why I had to keep in the room. But I could not be any more. If I had to go to sleep, it would be obvious that the passage would go through the other room.
The connection in the room that I wanted was a connection like this.
- All rooms must be connected.
- The connection of each room shall be connected by the shortest length.
The two biggest conditions are the above. However, the more you work, the more you get a little bit more and more.
- When you try to connect a room (B) that is closest to the room (A) you are trying to make a connection with, if there is a room (C) already connected to A, ) And compare the shortest distance (the distance between A and B and the distance between A and C).
Some of these conditions are getting worse. Are you confused by words?
[ 무슨 말이야! ]
[What do you mean!]
저는 꾸준히 개발하기 위해 트위치에서 방송을 하면서 개발을 하고 있어요. 다른 분들이 제 개발방송을 보러 와주시기 때문에 그 시간은 개발만 하도록 시간을 할당하는 것이죠. ( 물론 다른 이유도 있어요! 말하는 걸 좋아해서... 헤헤)
그런데 이렇게 복잡하게 진행이 되기 때문에 방송하면서 하기가 참 힘들더라구요. 그래서 정신통일을 위해서 또 이틀간 쉬었답니다...
그리고 첫 날에는 방송을 봐 주시는 여러 분들이 도움을 주셨는데... 또 제가... 고집이 있다보니.. 그 조언을 듣는다고 하면서도 일단 제 방식대로 한번 코딩을 했어요. 그러다보니 더 오래 걸린 것 같네요.
그래서! 그 때 당시에 저에게 사용하라고 말씀을 해주셨던 방법 중 하나인 프림 알고리즘에 대해서 간략하게 소개를 해볼게요!
컴퓨터 공학에서는 참 많이 사용되는 종류의 알고리즘이에요. 여기서 많이 쓴다고 하는 종류는 어떤 것이 '최소'의 비용이 되는 것을 말합니다.
비용이 최소가 되는 것, 최적화에 대해서 사람들은 참 관심이 많잖아요! 컴퓨터 공학에서도 어떤 목적이 있을 때 ( 여기서는 최소 비용을 찾는 것 ) 이미 알려진 많은 알고리즘이 있어요. 그 중에 하나가 바로 프림 알고리즘입니다.
I am constantly developing and broadcasting from twitch to develop. Because other people come to see my development program, it is time to allocate time for development. (Of course there is another reason! I like to say ... hehe)
However, since it is complicated, it is very difficult to broadcast. So I rested for another two days for spiritual unification ...
And on the first day, the people watching the broadcast helped me ... and I was ... stubborn ... I told him to listen to the advice, but once I did it in my way. It seems that it took longer.
so! I'll give you a brief introduction to the prim algorithm, one of the ways you told me to use it at the time!
In computer science, it is a very popular kind of algorithm. The kind of thing that I write a lot here is something that costs 'minimal'.
People are really interested in optimizing the cost to be minimal! There are many algorithms already known in computer science when there is a purpose (here to find the least cost). One of them is the prim algorithm.
[ 프림 알고리즘이 동작하는 방식 ]
[ How the prim algorithm works]
천천히 보신다면 모든 동그라미(노드)와 연결된 선(엣지)가 있는데 그 연결된 선에 값이 있어요. 이것은 바로 비용입니다.
그런데 모든 동그라미를 연결할 때 가장 값이 적은 것으로 연결을 하고 싶을 때 사용하는 방식이에요.
저 또한 모든 방이 '최단거리'로 연결되기를 원했고, 전부 다 연결하기를 원했어요. 어떤 부분에서는 프림알고리즘과 비슷한 느낌이죠? 그렇기 때문에 제 방송을 보셨던 분들이 이렇게 프림알고리즘에 대해서 말씀을 해주셨어요.
그런데 위에서 말한 것처럼... 고집을 피우면서 제 나름의 방식대로 해보고 싶었어요. 물론 완벽하게 프림 알고리즘에 제 경우를 대입하는 것이 일치한다고 볼 수 없었죠. 왜냐하면 몇 조건이 저는 더 붙게 되거든요.
그래서 2-3일 정도 작업을 한 결과... 원하는 형태의 결과가 나오게 알고리즘을 구현했습니다!
If you look slowly, there are lines (edges) connected to all the circles (nodes). This is the cost.
But when you want to connect all the circles with the least value, you can use it when you want to connect.
I also wanted every room to be 'shortest', and I wanted to connect everything. At some point, is it similar to the prim algorithm? That's why those of you who have seen my broadcast talk about Prim algorithm.
But as I said above ... I wanted to do my own way while sticking. Of course, I could not say that matching my case to the prim algorithm perfectly matched. Because I'm getting a few more conditions.
So I worked on it for 2-3 days ... I implemented the algorithm to get the result of the desired type!
[ 연결 해야하는 방을 직선으로 표시, 그리고 연결되어야 하는 타일을 검은 색으로 표시 ]
[Display the room to be connected as a straight line, and the tiles to be connected as black]
저렇게 떨어져 있는 두 개의 방을 연결시켜야 할 때 빨간 색 줄을 통해서 어떻게 통로를 만들어야 하나 표현을 했구요(빨간 선을 이용해서). 그리고 현재 타일을 기반으로 하기 때문에 어떤 타일을 이용해서 이제 통로를 만들어야 하는지에 대해서 표현했어요(검은색 타일).
When you have to connect two separate rooms like this, you have to make a way through the red line (using the red line). And because we are currently based on tiles, I have expressed what tiles should be used to create the aisle (black tile).
[ 연결 예시 1]
[Connection example 1]
잘 안보이실 수 있는데, 보시게 되면 연결되어야 하는 방들이 빨간 색 선으로 표현되고 있어요. 1시 쪽의 경우 색이 어두워서 잘 구분이 안되는데요. 검은색 타일이 2개가 붙어있답니다. 그래서 선이 표시가 안되고 있어요. ( 시작 점과 끝 점이 똑같아서.. 선의 길이가 0이 됩니다. )
모든 방이 연결이 되어서 통로만 잘 만든다면 ( 표시된 것처럼 ) 모든 맵을 다 이동할 수 있죠!
You can not see it well, but when you see it, the rooms that need to be connected are represented by red lines. The color of 1 o'clock side is dark, so it can not be distinguished. There are two black tiles. So the line is not showing. (The start and end points are the same, so the length of the line becomes 0.)
If all the rooms are connected and only the aisle is built (as shown), you can move all the maps!
[ 연결 예시 2 ]
[Connection example 2]
처음 것 보다는 깔끔하게 보이죠? 색 구분도 눈이 구분하기 편하게 되어있구요!
Looks cleaner than the first one? The color distinction also makes it easier to distinguish the eyes!
[ 연결 예시 3 ]
[Connection example 3]
방이 더 많아지더라도 정상적으로 작동되고 있는 것을 확인할 수 있습니다!
기존에 알려진 방법이 아니라, 제 생각으로 만들어진 알고리즘이 정상작동이 되어서 참 다행이에요.
Even if you have more room, you can see that it is working properly!
I am glad that the algorithms that I have created are working properly, not the methods I already know.
[ 히히! ]
[ haha! ]
다음으로 해야하는 것은 저렇게 찾아낸 방을 연결시키는 '통로'를 만드는 것이죠. 그렇다면 이제 랜덤 맵에 대해서 생성은 얼추 기본적인 것은 다 끝난 것 같아요!
그 다음으로 생각해야하는 것은 몬스터나 아이템 그리고 중요한 전투 시스템에 관련된 것이겠죠. 조금 걱정되는 부분은 전투 시스템이 약간 리듬적인 요소도 들어가고 그래서... 참 걱정이에요.
하지만 차근차근 만들어 보도록 할게요. 다음 포스팅은 이렇게 찾아낸 방에 '통로'를 생성시키는 것을 목표로 하겠습니다!
긴 글 읽어주셔서 감사합니다. 오늘은 토요일이네요. 다들 편히 쉬고 계신지 모르겠어요. 다들 행복한 하루 되세요!
The next thing you need to do is to create a 'passage' that connects the rooms you find. If so, now the creation for the random map is basically done!
The next thing to think about is monsters, items, and important combat systems. A little worried part is that the battle system has a bit of a rhythm factor too ... so I'm really worried.
But I'll try to make it easier. The next posting will aim to create a 'passage' in the room you find!
Thank you for reading the long article. Today is Saturday. I do not know if everyone is resting comfortably. Have a happy day!
---출처---
---source---
[프림 알고리즘이 동작하는 방식]
[How the prim algorithm works]
->http://leeyongjeon.tistory.com/entry/%EC%B5%9C%EC%86%8C%EC%8B%A0%EC%9E%A5%ED%8A%B8%EB%A6%ACMinimum-Spanning-Trees%ED%94%84%EB%A6%BCprim-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98