알고리즘 (30) 썸네일형 리스트형 [유니티] BSP 알고리즘을 이용해서 랜덤한 게임 맵 생성하기 [구현(2)] https://sharp2studio.tistory.com/45 [유니티] BSP 알고리즘을 이용해서 랜덤한 게임 맵 생성하기 [구현(1)] https://sharp2studio.tistory.com/44 [유니티] BSP 알고리즘을 이용해서 랜덤한 게임 맵 생성하기 [이론] BSP 알고리즘 (Binary Space Partitioning)은 한국어로 이진 공간 분할법이라는 뜻이다. 말 그대로 한 공.. sharp2studio.tistory.com 이전 포스팅으로 BSP알고리즘을 통해서 맵을 나누고, 그 안에서 방을 생성하며 각 방끼리 연결을 어떤식으로 할 지에 대해서 알아봤다. 이번에는, 이전에 나눴던 영역에 타일을 깔고 collider를 넣는 작업을 해볼것이다. 우선, 적당한 타일 이미지를 받아온다... [유니티] BSP 알고리즘을 이용해서 랜덤한 게임 맵 생성하기 [구현(1)] https://sharp2studio.tistory.com/44 [유니티] BSP 알고리즘을 이용해서 랜덤한 게임 맵 생성하기 [이론] BSP 알고리즘 (Binary Space Partitioning)은 한국어로 이진 공간 분할법이라는 뜻이다. 말 그대로 한 공간을 계속해서 2개로 나눠주면서 맵을 만들어 주는건데, 특히나 다회차 진행을 반복하게 되는 로 sharp2studio.tistory.com 저번 포스팅으로, BSP알고리즘이 어떤 것인지 알아보았다. 이번에는 , 유니티 내에서 BSP알고리즘을 통해서 공간을 나눠보고, 시각적으로 확인을 해보도록 할것인다. 먼저, 각 노드의 정보를 담을 클래스를 생성해준다. public class Node { public Node leftNode; public Node.. [유니티] BSP 알고리즘을 이용해서 랜덤한 게임 맵 생성하기 [이론] BSP 알고리즘 (Binary Space Partitioning)은 한국어로 이진 공간 분할법이라는 뜻이다. 말 그대로 한 공간을 계속해서 2개로 나눠주면서 맵을 만들어 주는건데, 특히나 다회차 진행을 반복하게 되는 로그라이크 류 게임에서 플레이어에게 다양한 경험을 주기 위해서 자주 사용되곤 한다. 예시를 보이자면, 위와 같은 그림의 전체적인 맵이 주어졌다고 가정을 할 때, 이 공간을 둘로 나눠준다. 전반적으로 맵의 크기가 균형있게 되려면, 가로와 세로 중 더 긴 방향을 둘로 나눠주는게 좋은 결과가 나오게 된다. 위의 사각형은 가로가 더 기므로 가로로 나눠주면 되는데, 정확히 반반으로 나누기 보다는 랜덤한 좌표에서 잘라준다면 이런식으로 2개의 공간으로 나눠지는걸 볼 수 있다. 또한, 처음 공간을 root.. [유니티]A* 알고리즘(에이스타 알고리즘)을 통해서 길찾기[구현] https://sharp2studio.tistory.com/42 A* 알고리즘(에이스타 알고리즘)을 통해서 길찾기 구현(이론) A* 알고리즘이란? 길찾기 알고리즘에 여러 종류가 있다. DFS,BFS를 통해서 길찾기를 할 수도 있고, 다익스트라 알고리즘을 통해서 가중치가 포함된 경로의 길찾기를 할 수 있을 것이다. 게임에서 sharp2studio.tistory.com 앞선 포스팅에서 A* 알고리즘이 어떤건지에 대해서 알아보았다. 이어서 실제 게임에서 적용되는 모습을 보이도록 하겠다. 우선 클릭한 위치로 이동해주는 간단한 함수를 만들어 준다. using System.Collections; using System.Collections.Generic; using UnityEngine; public class P.. A* 알고리즘(에이스타 알고리즘)을 통해서 길찾기 구현[이론] A* 알고리즘이란? 길찾기 알고리즘에 여러 종류가 있다. DFS,BFS를 통해서 길찾기를 할 수도 있고, 다익스트라 알고리즘을 통해서 가중치가 포함된 경로의 길찾기를 할 수 있을 것이다. 게임에서 보통 길찾기를 할 때에는 다익스트라 알고리즘의 변형인 A* 알고리즘을 사용한다. A* 알고리즘은 휴리스틱 이론을 사용하는데, 이는 중간 지점에서부터 목적지까지의 가중치를 예상하는 기법을 말하며, 이 기법의 계산 방식에 따라서 수행시간의 차이가 매우 달라진다. A* 알고리즘은 다익스트라와 다르게 출발지와 목적지의 입력을 받는다. 출발지부터 갈 수 있는 선택지를 모두 openlist에 넣고, 이 openlist에 들어간 노드들의 비용 순서대로 탐색을 진행하는데, 비용은 출발지로부터 현재 노드까지의 최단거리를 gco.. [백준] 1987번 알파벳 [C++] https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 접근 방식 백 트래킹을 이용해서 문제를 해결하였다. 먼저 특정 알파벳이 포함 되었는지, 안 되었는지 구분할 bool형 배열을 만들어준다. (1,1)지점은 무조건 지나가게 되므로 (1,1)지점에 있던 알파벳은 지나갔다고 표시를 해주고, (1,1) 지점부터 4 방향으로 탐색을 해준다. 탐색이 가능한 조건(배열 내에 해당, 이미 지나가지 않은 알파벳)을 만날 경우에 다시 그 지점으로부터 탐색을 .. [백준] 13549번 숨바꼭질3 [C++] https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 접근 방식 0초의 시간을 사용하는 순간이동이 있기때문에, BFS보다 다익스트라가 적합한 문제이다. 출발점에서 부터 +1,-1,*2씩 해서 큐에 넣어주는데, *2를 하는 순간이동은 시간이 걸리지 않기 때문에 순간이동부터 연산을 진행시켜주면 된다. 시간 순서적으로 방문하기 때문에 이미 방문한 지점은 더 탐색할 필요가 없다. 코드 #include #include #in.. [백준] 2931번 가스관 [C++] https://www.acmicpc.net/problem/2931 2931번: 가스관 www.acmicpc.net 접근 방식 일단 모스크바에서 부터 가스관의 방향을 따라서 BFS를 통해서 탐색을 해준다. 탐색을 하다보면, 이어져 있지만 빈칸으로 뚫려있는 곳이 있게 되는데, 이 위치를 저장하고 어느 방향으로 탐색을 했는지도 저장해준다. 다시 자그레브에서 같은 방법으로 탐색을 해준다. 같은 지점에서 뚫려있게 되는데 여기서도 어느 방향으로 탐색했는지 저장해준다. 예를 들어 이러한 형태로 입력이 주어졌다고 가정해보자. 모스크바에서는 아래로 탐색을 하다보니 아래 방향이 비어있는 공간이 발견된다. 자그레브에서 가스관을 따라 탐색을 하다보니 오른쪽이 비어있는 공간이 발견될 것이다. 그렇다면, 비어있는 곳에 있어야 할.. 이전 1 2 3 4 다음
