BSP 던전 생성의 간단한 예제

Question

나는 원래 C#에서 약간 간단한 roguelike 던전을 만들기 위해 this algorithm을 따르려고했다. 하지만 내 결과가 항상 뒤죽박죽 된 엉망진창으로 나왔기 때문에 나는 너무 어리 석다.

그런 다음 내 자신의 알고리즘으로 전환했는데,이 알고리즘은 감옥에있는 것처럼 보이지는 않지만 반쯤은 알아볼 수있는 결과를 만들어냅니다.

누구나 링크 된 기사에서 설명한대로 BSP 방식으로 수행하는 예가 있습니까? 그것은 게임 세부 정보/라이브러리 호출의 잔뜩에 의해 방해하지 않는 것이 가장 좋을 것입니다, 왜냐하면 (다시) 나는 바보입니다.

(당신이 특히 자학이고 싶다면 나에게 내가 할 수있는, 내가 가진 코드를 게시하는,하지만 난 그것이 SO 질문에 대한 너무 많은 것 생각.)

Answer 1

이 객실을 연결하지 않습니다 하지만, 설명 된 알고리즘을 사용하여 정상적인 던전을 생성합니다. (불행히도 자바에 있지만 나는 수행되고 있는지 명확히하기 위해 몇 가지 주석을 추가했습니다.)

public static class Rectangle { 

    private static int MIN_SIZE = 5; 
    private static Random rnd = new Random(); 

    private int top, left, width, height; 
    private Rectangle leftChild; 
    private Rectangle rightChild; 
    private Rectangle dungeon; 

    public Rectangle(int top, int left, int height, int width) { 
     this.top = top; 
     this.left = left; 
     this.width = width; 
     this.height = height; 
    } 

    public boolean split() { 
     if(leftChild != null) //if already split, bail out 
      return false; 
     boolean horizontal = rnd.nextBoolean(); //direction of split 
     int max = (horizontal ? height : width) - MIN_SIZE; //maximum height/width we can split off 
     if(max <= MIN_SIZE) // area too small to split, bail out 
      return false; 
     int split = rnd.nextInt(max); // generate split point 
     if(split < MIN_SIZE) // adjust split point so there's at least MIN_SIZE in both partitions 
      split = MIN_SIZE; 
     if(horizontal) { //populate child areas 
      leftChild = new Rectangle(top, left, split, width); 
      rightChild = new Rectangle(top+split, left, height-split, width); 
     } else { 
      leftChild = new Rectangle(top, left, height, split); 
      rightChild = new Rectangle(top, left+split, height, width-split); 
     } 
     return true; //split successful 
    } 

    public void generateDungeon() { 
     if(leftChild != null) { //if current are has child areas, propagate the call 
      leftChild.generateDungeon(); 
      rightChild.generateDungeon(); 
     } else { // if leaf node, create a dungeon within the minimum size constraints 
      int dungeonTop = (height - MIN_SIZE <= 0) ? 0 : rnd.nextInt(height - MIN_SIZE); 
      int dungeonLeft = (width - MIN_SIZE <= 0) ? 0 : rnd.nextInt(width - MIN_SIZE); 
      int dungeonHeight = Math.max(rnd.nextInt(height - dungeonTop), MIN_SIZE);; 
      int dungeonWidth = Math.max(rnd.nextInt(width - dungeonLeft), MIN_SIZE);; 
      dungeon = new Rectangle(top + dungeonTop, left+dungeonLeft, dungeonHeight, dungeonWidth); 
     } 
    } 

} 

그리고 여기의 사용 입증하는 테스트 클래스입니다 :

import java.util.ArrayList; 
import java.util.Random; 


public class GenerateDungeon { 

    private static Random rnd = new Random(); 



    public static void main(String[] args) { 
     ArrayList<Rectangle> rectangles = new ArrayList<Rectangle>(); // flat rectangle store to help pick a random one 
     Rectangle root = new Rectangle(0, 0, 60, 120); // 
     rectangles.add(root ); //populate rectangle store with root area 
     while(rectangles.size() < 19) { // this will give us 10 leaf areas 
      int splitIdx = rnd.nextInt(rectangles.size()); // choose a random element 
      Rectangle toSplit = rectangles.get(splitIdx); 
      if(toSplit.split()) { //attempt to split 
       rectangles.add(toSplit.leftChild); 
       rectangles.add(toSplit.rightChild); 
      } 

     } 
     root.generateDungeon(); //generate dungeons 

     printDungeons(rectangles); //this is just to test the output 

    } 



    private static void printDungeons(ArrayList<Rectangle> rectangles) { 
     byte [][] lines = new byte[60][]; 
     for(int i = 0; i < 60; i++) { 
      lines[ i ] = new byte[120]; 
      for(int j = 0; j < 120; j++) 
       lines[ i ][ j ] = -1; 
     } 
     byte dungeonCount = -1; 
     for(Rectangle r : rectangles) { 
      if(r.dungeon == null) 
       continue; 
      Rectangle d = r.dungeon; 
      dungeonCount++; 
      for(int i = 0; i < d.height; i++) { 
       for(int j = 0; j < d.width; j++) 

        lines[ d.top + i ][ d.left+ j ] = dungeonCount; 
      } 
     } 
     for(int i = 0; i < 60; i++) { 
      for(int j = 0; j < 120; j++) { 
       if(lines[ i ][ j ] == -1) 
        System.out.print('.'); 
       else 
        System.out.print(lines[ i ][ j ]); 
      } 
      System.out.println(); 
     } 
    } 

}