[🐣질문] 아이템조합 알고리즘 질문

[익명(39.113)]

아이템 A를 만들기 위한 조합식은 아래와 같음

A = B + C + D

아이템을 조합하려면 게임 화면에 보이는 항아리에 재료들을 다 부어야함

만약 항아리에 B,C,D만 들어가 있다면 A를 만드는데 아무 문제 없고 구현되어있음

문제는 항아리에 다른 아이템들도 들어갈 경우임

예를들어서 B,C,D 그리고 E 까지 들어갈경우, B+C+D+E 조합식으로 생성되는 아이템은 없음

그래도 유저 편의성을 위해서 컴퓨터가 알아서 B+C+D를 조합하면 A를 만들수 있다는 사실을 유저에게 알리도록 만들고 싶음

상황이 복잡해지면 생성 가능한 경우의 수가 2개이상 나올수도 있긴한데, 이때는 아이템 이름 순서로 정렬하던가 해서 무조건 1개의 완성품만 나오게 하고싶음

결론은... 템이 이것저것 복잡하게 주어진 상황에서 생성할수 있는템이 무엇인지 자동으로 판단하게 만들고싶음

현재로선 완전탐색 돌리는거 말고는 다른 아이디어가 안떠오름

도와주십쇼 행님들

[dryrain(dryrain1025)]

이건 기획적으로 확실하게 정해져야할 부분 같은데, B+C+D+E를 넣으면 A와 E가 나오는거임? 아니면 생성 자체가 안되는거임? 전자라면 결과물을 미리 보여줄 때 플레이어가 오해할 여지가 있을거같고 후자라면 결과물을 안보여주는 게 맞지 않나

[글쓴 ㅇㅇ(39.113)]

B+C+D+E를 넣으면 조합은 불가능함. 대신 UI를 통해서 A = B+C+D 라는 정보를 유저한테 알려줌. 유저는 그걸보고 불필요한 아이템이 뭔지 뺄 수 있고

[글쓴 ㅇㅇ(39.113)]

F = B+C+E 라는 조합식이 있을경우에, 항아리에 B와 C를 넣으면 나머지 재료 한개가 무엇인지에 따라 A와 F를 생성 가능하자나. 그때는 일단 결과물 이름이 사전순으로 앞에 있는 조합식을 우선으로 출력할거임. 기획레벨에서 햇갈릴수 있는 조합식은 안넣도록 할려고. 즉 A = B+C+D와 F = B+C+E 처럼 재료가 2개이상 같은 조합식은 안넣을 예정임

[dryrain(dryrain1025)]

[바가로기(dd5ew96x9pyr)]

현재 들어간 재료로 조합할 수 있는 결과물 리스트를 따로 표시해주면 될듯 A = a + b + c B = a + b + d 일때, a + b + c +d를 넣었으면 A, B의 조합법을 리스트에 보여주면 되지않을까?

[글쓴 ㅇㅇ(39.113)]

ㅇㅇ 하나만 보여주든 둘다 보여주든, 어쨌든 a,b,c,d, 재료를 통해서 A와 B를 만들수 있다는거를 효율적으로 판별할 방법을 모르겠음. 완전탐색 말고 아이디어가 안떠오르네

[바가로기(dd5ew96x9pyr)]

조합식에 대한 정보를 가진 구조체를 List 형태로 만들고 이 List를 순회하면서 현재 재료를 인자로 넘겨서 매칭되는 조합식을 List로 반환하는 함수하나 만들어서 쓰셈

[ㅇㅇ 1(183.96)]

걍 완전탐색 써도 될 것 같은데. 재료 바꾸는게 프레임마다 몇십 번씩 불리지는 않을 거 아냐

[글쓴 ㅇㅇ(39.113)]

ㅇㅇ 아이템이 새로 들어오거나 나올때만 판별함. 조합식은 100개 가량 될 예정이고, 테스트 해보니까 재료 50개 넘게 쏟아넣어도 완탐 돌리면 시간 얼마 안되긴 하네. 정안되면 그낭 비동기로 연산하고

[익명(119.70)]

아니면 비트마스크로 하는건 어떰?

[ㅇㅇ 2(210.206)]

문자열끼리 편집 거리를 계산하는 Levenshtein 거리라는 체계가 있는데 재료와 레시피를 특정할 문자열로 치환한 뒤 합쳐서 편집거리가 작은 순으로 플레이어에게 노출하는 방법도 있을 것 같습니다. 편집거리가 동률인 레시피가 많은 경우 포함되어 있는 문자열끼리 판별할 우선순위를 만들어서 그에 따라 정렬할 수도 있을 거구요. 이건 어떤 접근법이던 어렵지 않게 가능한 것 같아서 상상하는 대로 구현하면 될 것 같습니다.

[글쓴 ㅇㅇ(39.113)]

오 감사해요 덕분에 좋은거 알아갑니다