반응형
데바데 자동 구매는 어떤 방법일까? 해서 심심해서 비슷하게 구현해보았다.
데드바이 데이라이트를 플레이하던 중 게임에는 아래와 같이
아이템을 구매하는 시스템이 존재한다.
해당 페이지의 중앙 버튼은 아이템을 자동으로 구입해 주는 시스템인데 아무 생각 없이 보고 있다 문득
해당 페이지에서 사용하는 알고리즘이 무엇인지 궁금해졌다
처음 문득 생각했을 때는 다익스트라 또는 최소 스패닝트리를 사용했을 거 같았다.
당연하게도 전체적으로 가장 저렴한 루트를 제공할 것이라고 생각했기 때문이다.
알고리즘을 분석하기위해 자동 구매를 하며 영상녹화 한 뒤
분석하던 도중 이상한 순서로 구매하는 것을 확인하고 의문이 들어서 찾던 중 아래와 같은 사실을 확인해 버렸다.
깊이가 가까운 노드에서 가격이 저렴한 순서대로 샀다는 것이다.
그렇다는 건
가깝고 싼 순서부터 우선순위 더 싸더라도 한 칸이라도 멀리 있으면 비싼 걸 구매한다.
무서운 진실(최대한 싸게 구매하지 않는다는) 사실을 알아버렸지만 좌절하고 있을 수는 없다.
계속 분석해보자
배치는 어떤 식일까?
그렇다면 배치는 어떤 식으로 만들어지는지 자세히 보기 위해 좀 더 많은 배치가 있는 화면을 들고 와보았다.
자~세하게 본다면 미리 배치가 일정 정해져 있는 것을 볼 수 있다.
RootNode
Depth 1 노드수 6개
Depth 2 노드수 12개
Depth 3 노드수 12개
깊이에 비례해서 노드수가 커지지는 않는 것 같다.
간선은
RootNode = Depth 1 간선 6개
Depth 1 = Root Node + 같은 Depth 간선 최대 2개 + Depth +1 간선 2개
Depth 2 = Depth 1 간선 최대 2개 + 같은 Depth 간선 최대 2개 + Depth +1 간선 2개
Depth 3 = Depth 2 간선 최대 2개 + 같은 Depth 간선 최대 2개
정도로 보인다.
해당 시스템을 그대로 만든다면
미리 노드들과 위치 연결된 간선을 만들어둔 뒤
root 노드에서 BFS 나 DFS로 만 들것 같다.
하지만 아이템 등장 확률이나 간선 노드 생성 수식을 모르니
임시로 만들어보았다.
3개의 깊이로 2번 3번에서는 왼쪽과 아래 간선을 랜덤 하게 연결하는 식으로 만들었다.
깊이당 노드도 랜덤이기에
큰 기획 없이 랜덤 하게 스폰하게 만든 간단한 그래프기에
더 외부의 그래프의 노드가 적다면
간선끼리 겹치거나 이미지 뒤로 겹치는 경우도 존재한다.
생성 후 가까운 노드에 연결하는 방식도 생각해 보았지만
우선 대부분은 큰 문제가 없기 때문에 이후 수정하는 것으로 하자.
아래는 잘 나온 그래프.
간선이 겹치는 경우
이제 데바데의 형식으로 먹는 것을 계산해 보자
우선 아이템만 존재할 때 먹는 걸 만들었다.
더보기
using NUnit.Framework;
using System.Collections.Generic;
using UnityEngine;
using System.Linq;
using System;
using Unity.VisualScripting;
using UnityEngine.UI;
using System.Net;
using System.Collections;
public class BloodwebSystem : MonoBehaviour
{
private PriorityQueue<(int, ItemScriptableObject), (int, int)> queue;
private ItemScriptableObject RootItems;
private Dictionary<int, List<LineRenderer>> lineRenderers = new Dictionary<int, List<LineRenderer>>();
private Dictionary<(int, int), LineRenderer> EdgeDicrionaty = new Dictionary<(int, int), LineRenderer>();
private Queue<int> Deadny_Auto = new Queue<int>();
private List<bool> Deadny_ison;
//아이템리스트
public List<ItemScriptableObject> PabItems;
private List<ItemScriptableObject> ItemList = new List<ItemScriptableObject>();
// ui 생성위치
public GameObject MakeBloodwebPoint;
public GameObject MakeBloodwebLinePoint;
//깊이당 생성 저장
public List<List<ItemScriptableObject>> BloodwebDepth;
public GameObject BloodObjectPrefab;
public GameObject BloodObjectLinePrefab;
[SerializeField, UnityEngine.Range(1, 30)]
public int MaxPoint = 25;
public int MaxPath = 25;
[SerializeField, UnityEngine.Range(1, 100)]
public int CircleRadius = 25;
private List<(int, int)> DijkstraInts = new List<(int, int)>(), DBDSerchInts = new List<(int, int)>(), SmallSerchInts = new List<(int, int)>();
// 데이터 시트 구현
void Start()
{
Init();
//queue = new PriorityQueue<ItemScriptableObject, (int, int)>();
//queue.Enqueue(new ItemScriptableObject { price = 3 }, (0, 1000));
//queue.Enqueue(new ItemScriptableObject { price = 1 }, (-1, 2000));
//queue.Enqueue(new ItemScriptableObject { price = 2 }, (-1, 3000));
//queue.Enqueue(new ItemScriptableObject { price = 4 }, (1, -2000));
//queue.Enqueue(new ItemScriptableObject { price = 5 }, (2, 0));
//while (queue.Count > 0)
//{
// Debug.Log(queue.Dequeue().price);
//}
}
//가격순 정렬
int compareItem(ItemScriptableObject a, ItemScriptableObject b)
{
return a.price < b.price ? -1 : 1;
}
private void Init()
{
//3개의 뎁스
queue = new PriorityQueue<(int, ItemScriptableObject), (int, int)>();
BloodwebDepth = new List<List<ItemScriptableObject>>(3);
RootItems = new ItemScriptableObject { price = -1, edge = new List<ItemScriptableObject>() };
//PabItems 갑어치에 따른 정렬
PabItems.Sort(compareItem);
int min = 8;
int max = 12;
int number = 0;
for (int i = 0; i < 3; ++i)
{
BloodwebDepth.Add(new List<ItemScriptableObject>());
float randomValue = UnityEngine.Random.Range(0f, 1f);
float bias = 2f + i;
int selectedValue = Mathf.FloorToInt(min + Mathf.Pow(randomValue, bias) * (max - min + 1));
if (i == 0)
{
selectedValue = 6;
}
for (int j = 0; j < selectedValue; ++j)
{
int R_Number = UnityEngine.Random.Range(0, PabItems.Count);
//가치에 따른 낮은 확율 생성 필요
ItemScriptableObject tempI = new ItemScriptableObject
{
numbering = number,
price = PabItems[R_Number].price,
Sprite = PabItems[R_Number].Sprite,
depth = i,
edge = new List<ItemScriptableObject>()
};
lineRenderers.Add(number, new List<LineRenderer>());
number++;
BloodwebDepth[i].Add(tempI);
ItemList.Add(tempI);
}
}
(int, int)[] edges = { (-1, 0), (0, -1) };
DrawBloodWeb();
for (int i = 0; i < BloodwebDepth.Count; ++i)
{
for (int j = 0; j < BloodwebDepth[i].Count; ++j)
{
if (i == 0)
{
RootItems.edge.Add(BloodwebDepth[i][j]);
var d = DrawLine(MakeBloodwebLinePoint.transform.position, BloodwebDepth[i][j].g.transform.position);
EdgeDicrionaty.Add((-1, j), d);
//옆라인 연결 있든없든 상관없음
}
else
{
int numToSelect = UnityEngine.Random.Range(1, edges.Length + 1);
bool[] selectedFlags = new bool[edges.Length];
while (BloodwebDepth[i][j].edge.Count < numToSelect)
{
int randomIndex = UnityEngine.Random.Range(0, edges.Length);
// 이미 선택된 항목인지 확인
if (!selectedFlags[randomIndex])
{
int TDepth = i + (edges[randomIndex].Item1);
int whith = j + edges[randomIndex].Item2;
if (whith < 0) whith = BloodwebDepth[i].Count - 1;
if (BloodwebDepth[TDepth].Count - 1 < whith) whith = (BloodwebDepth[TDepth].Count - 1) % whith;
if (BloodwebDepth[TDepth][whith]) selectedFlags[randomIndex] = true;
BloodwebDepth[i][j].edge.Add(BloodwebDepth[TDepth][(whith)]);
BloodwebDepth[TDepth][whith].edge.Add(BloodwebDepth[i][j]);
var d = DrawLine(BloodwebDepth[i][j].g.transform.position, BloodwebDepth[TDepth][whith].g.transform.position);
lineRenderers[BloodwebDepth[i][j].numbering].Add(d);
lineRenderers[BloodwebDepth[TDepth][whith].numbering].Add(d);
EdgeDicrionaty.Add((BloodwebDepth[i][j].numbering, BloodwebDepth[TDepth][whith].numbering), d);
EdgeDicrionaty.Add((BloodwebDepth[TDepth][whith].numbering, BloodwebDepth[i][j].numbering), d);
}
}
}
}
}
Debug.Log("end");
//미리 계산하기
Deadny_Auto = Deadny_AutoChoiceAll();
Deadny_AutoDraw(Deadny_Auto);
//DBDSerchInts = DbdDirections();
//DijkstraInts = DijkstraAll();
SmallSerchInts = SmallerDirections();
//StartCoroutine(drawingColor(DBDSerchInts));
//StartCoroutine(drawingColor(DijkstraInts));
StartCoroutine(drawingColor(SmallSerchInts));
}
private LineRenderer DrawLine(Vector3 x, Vector3 y)
{
GameObject lineObject = Instantiate(BloodObjectLinePrefab, MakeBloodwebLinePoint.transform);
LineRenderer lr = lineObject.GetComponent<LineRenderer>();
lr.SetPosition(0, x);
lr.SetPosition(1, y);
lr.sortingOrder = -1;
return lr;
}
private void DrawBloodWeb()
{
Vector3 UITransformPosition = MakeBloodwebPoint.transform.position;
for (int i = 0; i < BloodwebDepth.Count; i++)
{
float CircleRate = (CircleRadius * 0.1f) * (i + 1);
int count = BloodwebDepth[i].Count;
for (int j = 0; j < BloodwebDepth[i].Count; j++)
{
float theta = (2 * MathF.PI / count) * j;
var data = BloodwebDepth[i][j];
data.position.x = UITransformPosition.x + CircleRate * MathF.Cos(theta);
data.position.y = UITransformPosition.y + CircleRate * MathF.Sin(theta);
Vector3 ObjectTransformPosition = new Vector3(data.position.x, data.position.y, 0);
GameObject G = Instantiate(BloodObjectPrefab, MakeBloodwebPoint.transform);
G.transform.position = ObjectTransformPosition;
G.GetComponent<Image>().sprite = BloodwebDepth[i][j].Sprite;
BloodwebDepth[i][j].g = G;
}
}
}
public Queue<int> Deadny_AutoChoiceAll()
{
Deadny_ison = new List<bool>(ItemList.Count + 1);
for (int i = 0; i < ItemList.Count + 1; ++i)
{
Deadny_ison.Add(false);
}
Queue<int> temp = new Queue<int>();
queue.Enqueue((0, RootItems), (0, 0));
while (queue.Count > 0)
{
(int, ItemScriptableObject) data = queue.Dequeue();
int num = data.Item1;
if (data.Item2.numbering != -1)
{
temp.Enqueue(data.Item2.numbering);
Deadny_ison[data.Item2.numbering] = true;
}
foreach (var edge in data.Item2.edge)
{
if (Deadny_ison[edge.numbering] == false)
{
queue.Enqueue((num + edge.price, edge), (edge.depth, num + edge.price));
}
}
}
return temp;
}
public void Deadny_AutoDraw(Queue<int> deadny_Auto)
{
while (deadny_Auto.Count > 0)
{
int num = deadny_Auto.Dequeue();
ItemList[num].g.GetComponent<Button>().image.color = new Color(144, 55, 55);
Debug.Log(ItemList[num].g.GetComponent<Image>().sprite);
}
}
public void NodeNtoChangeColor(int BaseNodeNumber, int ChangeNodeNumber, Color EdgeColor, Color ItemColor)
{
EdgeDicrionaty[(BaseNodeNumber, ChangeNodeNumber)].startColor = EdgeColor;
EdgeDicrionaty[(BaseNodeNumber, ChangeNodeNumber)].endColor = EdgeColor;
ItemList[ChangeNodeNumber].g.GetComponent<Button>().image.color = (ItemColor);
}
private IEnumerator drawingColor(List<(int,int)>Ints)
{
foreach ((int, int) d in Ints)
{
Debug.Log(d);
NodeNtoChangeColor(d.Item1, d.Item2, Color.green, Color.black);
yield return new WaitForSeconds(1f);
}
}
//이후 탐색클래스 분리
public List<(int, int)> DijkstraAll()
{
List<(int, int)> list = new List<(int, int)>();
PriorityQueue<(ItemScriptableObject, int, int), (int, int)> dijksqueue = new PriorityQueue<(ItemScriptableObject, int, int), (int, int)>();
dijksqueue.Enqueue((RootItems, -1, 0), (0, 0));
List<bool> complete = new List<bool>();
foreach (ItemScriptableObject item in ItemList)
{
complete.Add(false);
}
while (dijksqueue.Count != 0)
{
var data = dijksqueue.Dequeue();
Debug.Log(data.Item1.numbering);
if (data.Item1.numbering != -1)
{
if (complete[data.Item1.numbering] == true) continue;
list.Add((data.Item2, data.Item1.numbering));
complete[data.Item1.numbering] = true;
}
foreach (var edge in data.Item1.edge)
{
int dijkcost = edge.price + data.Item3;
if (complete[edge.numbering] == true) continue;
dijksqueue.Enqueue((edge, data.Item1.numbering, dijkcost), (dijkcost, 0));
}
}
return list;
}
public List<(int, int)> SmallerDirections()
{
List<(int, int)> list = new List<(int, int)>();
PriorityQueue<(ItemScriptableObject, int, int), (int, int)> dijksqueue = new PriorityQueue<(ItemScriptableObject, int, int), (int, int)>();
dijksqueue.Enqueue((RootItems, -1, 0), (0, 0));
List<bool> complete = new List<bool>();
foreach (ItemScriptableObject item in ItemList)
{
complete.Add(false);
}
while (dijksqueue.Count != 0)
{
var data = dijksqueue.Dequeue();
Debug.Log(data.Item1.numbering);
if (data.Item1.numbering != -1)
{
if (complete[data.Item1.numbering] == true) continue;
list.Add((data.Item2, data.Item1.numbering));
complete[data.Item1.numbering] = true;
}
foreach (var edge in data.Item1.edge)
{
int dijkcost = edge.price + data.Item3;
if (complete[edge.numbering] == true) continue;
dijksqueue.Enqueue((edge, data.Item1.numbering, dijkcost), (edge.price, 0));
}
}
return list;
}
public List<(int, int)> DbdDirections()
{
List<(int, int)> list = new List<(int, int)>();
PriorityQueue<(ItemScriptableObject, int, int), (int, int)> dijksqueue = new PriorityQueue<(ItemScriptableObject, int, int), (int, int)>();
dijksqueue.Enqueue((RootItems, -1, 0), (0, 0));
List<bool> complete = new List<bool>();
foreach (ItemScriptableObject item in ItemList)
{
complete.Add(false);
}
while (dijksqueue.Count != 0)
{
var data = dijksqueue.Dequeue();
Debug.Log(data.Item1.depth);
if (data.Item1.numbering != -1)
{
if (complete[data.Item1.numbering] == true) continue;
list.Add((data.Item2, data.Item1.numbering));
complete[data.Item1.numbering] = true;
}
foreach (var edge in data.Item1.edge)
{
int dijkcost = edge.price + data.Item3;
if (complete[edge.numbering] == true) continue;
dijksqueue.Enqueue((edge, data.Item1.numbering, dijkcost), (edge.depth, edge.price));
}
}
return list;
}
}
이후 추가 예정.
간선 겹침 해결
이후 아이템 노드 잠김
잠기는 노드에 따른 최적치 계산
'엔진 > 유니티' 카테고리의 다른 글
| unity shortcuts (0) | 2024.09.03 |
|---|---|
| 유니티 데칼 (decal) (0) | 2024.04.16 |
| 구글 gemini api 유니티에서 사용하기 (0) | 2023.12.21 |
| Unity Spline 기능 추가! (1) | 2023.06.01 |
| ChatGPT-Unity에서-사용하기 (5) | 2023.03.22 |
