[💬] 몰랐는데 어제 기획떡밥 있었네

[ㅁㄴㅇㄹ(121.181)]

그래서 팀원들하고 기획 관련 논의하던거 몇개 긁어와 봄. 딴 사람들은 어캐 하는지 모르겠는데, 나는 이렇게 하니 다른 사람들에게 참고 될지는 모르겠다. 아까 얘기한 개념증명 프로그램도 전체는 못 올리지만 클래스 하나는 긁어 올려봄.

...

https://textbin.net/tkuhgqty81

....

In short, communication efficiency can be a generalized way of measuring distance from one central place to a set of other places, where the size of that set is usually far higher than just one. This generalized distance, or to be more precise 'the measure of difficulty and efforts required to get from point A to a set of points B' can be very useful for both political and economical gameplay. However, as I believe it'd require further discussion on the topic, I would refrain from getting into the details other than its abstract role, and immediately go into how it can be used to solve the 'Tile Aggregator' problem.

1. Assume that some method for measuring CE(Communication Efficiency) exists.

2. First, the world has only a set of COT(Center of Trade) and a set of tiles.

3. Each COT is located in a certain tile.

4. Then, use CE measurement to create a set for each COT where that set is a set of all the tiles whose closest COT in terms of CE is that COT.

5. When a new COT gets added, simply create a new set for that new COT out of tiles whose new closest COT in terms of CE is that new COT.

6. When a preexisting COT gets removed, create a temporary list of all neighboring COTs of that removed COT, and for all tiles within that removed COT's set of tiles, check which COT out of that list of neighbors is the closest.

....

One thing that I'm thinking about is how to properly update a graph when one of its node(a tile) is flagged as dirty. I think this algorithm can ensure that your assumption will hold afterwards.

1. There exists a set of dirty tiles.

2. While the dirty tiles set is not empty, find a dirty tile with a lowest distance value. Pop it off from the set.

3. Update its data from its neighbors.

4. If the new distance is equal to its previous distance, continue.

5. If the new distance is lower than its previous distance, find every neighbors whose distance can be improved, update their data, and add them to a temporary set.

5.1. While the temporary set is not empty, find a tile within it with a lowest distance value, pop it off from the dirty tiles set if present in that set, find all of its neighbors whose distance can be improved, update their data, and add them to a temporary set.

6. If the new distance is higher than its previous distance, flag all of its NEXT as dirty, and append them to the set of dirty tiles. 

[익명(218.157)]

현기증나요 ㅜㅜ

[거붓(ggp02217)]

오 무슨 여행 무역 게임 만드나봐?

[거붓(ggp02217)]

알고리즘이 대략 상상이 가는데 상세하게 뭐라하는지 잘 모르겠다

[ㅁㄴㅇㄹ(121.181)]

ㄴㄴ 대전략 게임임. 경제 + 정치 시뮬레이션이 핵심인 게임인데, 최근 작업하던게 그 둘 모두에서 사용 될 수 있는 일종의 거리측정 시스템이었거든. 도시 A에서 도시 B사이의 거리를 단순히 유클리드적으로 계산하면 노잼이니 그렇게 하는건 당연히 안 되고, 좀 더 상호작용 가능한 방식으로 기획 중이었음.

[ㅁㄴㅇㄹ(121.181)]

그래도 저 부분만 놓고 보면 여행 무역 생각한게 나름 맞는 생각 같기도 하네/

[거붓(ggp02217)]

아 그렇구나 그러면 더 이해가 되네 혹시 이 알고리즘이 가깝게 이웃된 상점가가 많을수록 상점의 효율이 증가하는 걸 뜻하는거야?

[ㅁㄴㅇㄹ(121.181)]

결국 길찾기 알고리즘을 사용하는데, 프로그래머는 A* 쓰자고 했거든. 근데 그건 두 지점 사이의 최소길이경로를 하나 찾는데는 그럭저럭 괜찮은 반면 여러 '시작점'으로부터 엄청 많은 '도착점'까지의 '모든' 최소길이경로와 그 경로의 길이를 찾는데는 불필요한 오버헤드가 많음. 그래서 나는 차라리 dijkstra's algorithm 을 쓰자고 제안해서 보여준게 저 개념증명 프로그램이었음. 이 알고리즘에 맞춰서 문제를 수정하면 이게 의외로 되게 효율적일수가 있거든. 구관이 명관인 면도 있음.

[ㅁㄴㅇㄹ(121.181)]

아, 그런건 아니고, 이렇게 설명해볼게.

[ㅁㄴㅇㄹ(121.181)]

음 생각해보니 길게 설명할게 없네. 걍 두 도시간에 거리가 멀어질수록 무역도 더 어려워지고 그러는데 쓰는거임. 문제는 이 게임에 타일이 백만개 있고, 그 중 바다가 아니라 땅인 타일이 16만개고, 그 중 도시인 타일이 1만개 정도라는 점 정도. 그래서 시스템 기획에서 극한의 효율을 쥐어짜낼 수 있도록 구상하는게 가장 큰 고비였음.

[ㅁㄴㅇㄹ(121.181)]

나는 중간에 끼어든거여서 이 세계구 기획과 구현은 이미 끝나 있는 상태니 그거에 맞춰서 내가 만들라고 스카웃 된 시스템들을 짤 수 밖에 없었음.

[ㅁㄴㅇㄹ(121.181)]

내 개인 의견을 물어본다면 백만개는 좀 많이 나아간 것 같다고 말할 수 밖에 없지만, 뭐 별 수 있나. 이미 만들어지기까지 한걸 다 갈아 엎을 수도 없는 노릇이고.

[거붓(ggp02217)]

너무 많다면 전체맵을 노드를 합쳐 크게 만들고 유닛 주위 그리드만 적게 만들어 처리하지

[ㅁㄴㅇㄹ(121.181)]

ㅇㅇ 그런 방향으로 기획을 잡긴 했음.

[거붓(ggp02217)]

근데 다익스트라를 추천하는 거 보면 만든게임이 뭐 방해물이 없나? 방해물이 있으면 에이스타가 나을텐데

[익명(usnned)]

걍 노드와 노드 사이의 거리만 있는 형태로 만들면 상관없을듯

[익명(222.111)]

씨발련아 왜영어쓰는데