Это БСП дерево? Я что-то пропустила?


Я тренировался, используя БСП деревья, как я слышал, они являются хорошим началом для создания процедурных помещений, таких как дома.

Для облегчения развертывания целей, я проверил этот код в LUA, и это, кажется, работает. Однако, я хочу подтвердить, если я сделал то, что мне нужно делать, а не что-то другое. Когда я уверен, что это работает, я правильно их выполнять в C.

Это будет код:

MAX_RECURSION = 3
TL = 1
BL = 2
BR = 3
TR = 4


grid = {}
grid.w = 60;
grid.h = 12;
grid.max = grid.w * grid.h
grid.pos = function (self, x, y) return (x * self.w + y)+1 end
grid.get = function (self, x, y) return self.data[self:pos(x, y)] end
grid.set = function (self, x, y, d) self.data[self:pos(x,y)] = d end
grid.data = {}
for i = 1, grid.max do grid.data[i] = " " end

rooms = 1

function node_c(parent, rect)
    n = {}
    n.child1 = nil
    n.child2 = nil
    n.parent = parent
    n.rect = rect
    n.w = rect[TR].x-rect[TL].x
    n.h = rect[BL].y-rect[TL].y if n.h < 0 then n.h = 0 end
    n.level = parent.level + 1
    n.id = 0
    n.vertical = direction_get(n)
    node_draw(n)
    return n
end

function rootnode(rect)
    n = {}
    n.child1 = nil
    n.child2 = nil
    n.rect = rect
    n.parent = nil
    n.w = rect[TR].x-rect[TL].x
    n.h = rect[BL].y-rect[TL].y
    n.level = 0
    n.id = 0
    n.vertical = direction_get(n)
    node_draw(n)
    return n
end

function node_draw(node)
    local x, y
    local rect = node.rect
    for y = rect[TL].y, rect[BL].y do
        for x = rect[TL].x, rect[TR].x do
            if x==rect[TL].x or x==rect[TR].x or y==rect[TL].y or y==rect[BR].y then
                grid:set(x, y, "#")
            else
                grid:set(x, y, ".")
            end
        end
    end
end

function node_split(node)
    if not node or not (node.level < MAX_RECURSION) then
        node.id = rooms
        rooms = rooms + 1
        return
    else
        local p
        if node.vertical then p = "X" else p = "Y" end
        local split = node_splitfrom(node)
        if split == nil then return end
        local c1, c2, r1, r2
        r1,r2 = node_rects(node, split)
        node.child1 = node_c(node, r1)
        node.child2 = node_c(node, r2)
        --draw_it(grid)
        node_split(node.child1)
        node_split(node.child2)
    end
end

function direction_get(node)
    if math.random(0, 1) == 0 then return true else return false end
end

function node_splitfrom(node)
    local result
    if node.vertical then
        local r = math.floor(((math.random(20, 80)/100) * node.w))
        if r < 2 or r > node.w - 2 then return nil else return node.rect[TL].x + r end
    else
        local r = math.floor(((math.random(20, 80)/100) * node.h))
        if r < 2 or r > node.h - 2 then return nil else return node.rect[TL].y + r end
    end
end

function print_rect(rect)
    return "TL:"..rect[TL].x..","..rect[TL].y.." BL:"..rect[BL].x..","..rect[BL].y.." BR:"..rect[BR].x..","..rect[BR].y.." TR:"..rect[TR].x..","..rect[TR].y
end

function node_rects(node, split)
    local rect1, rect2
    local t
    t = node.rect
    if node.vertical then
        rect1 = {[TL] = t[TL], [BL] = t[BL], [TR] = {x=split,y=t[TR].y}, [BR] = {x=split,y=t[BR].y}}
        rect2 = {[TL] = {x=split,y=t[TL].y}, [BL] = {x=split,y=t[BL].y}, [TR] = t[TR], [BR] = t[BR]}
        return rect1,rect2
    else
        rect1 = {[TL]=t[TL],[TR] = t[TR],[BL]={x=t[BL].x,y=split}, [BR]={x=t[BR].x,y=split}}
        rect2 = {[TL]={x=t[TL].x,y=split},[TR]={x=t[TR].x,y=split},[BL]=t[BL],[BR] = t[BR]}
        return rect1,rect2
    end
end

function bsp_it(g)
    local rect = { --Counter clockwise
        [TL] = {x=0,y=0},
        [BL] = {x=0,y=g.h},
        [BR] = {x=g.w,y=g.h},
        [TR] = {x=g.w,y=0}
    }
    local root = rootnode(rect)
    node_split(root)
    return root
end

function print_it(t)
    if(t) then
        local spaces = (t.level * 2)
        local i
        local space = ""
        for i = 0, spaces do space = space.." " end
        if not t.parent then print(space.."#"..("%X"):format(t.id)) else print(space.."\\"..("%X"):format(t.id)) end
        print_it(t.child1) print_it(t.child2)
    end
end

function draw_it(grid)
    local line = ""
    local x,y
    for y = 0, grid.h do
        for x = 0, grid.w do
            line = ""..line..(grid.data[grid:pos(x,y)] or 0)
        end
        print(line)
        line = ""
    end
end

math.randomseed(os.time())

test = bsp_it(grid, 3)
print_it(test)
draw_it(grid)

Это очень наивный подход. Я не проверять размер или что-нибудь, чтобы она выглядела хорошо и я не соединяющий комнаты еще (я разберусь с этим позже. Таблица рекурсивно собирает узлы, следует выполнять работу).

Так вот вопрос, если это на самом деле БСП дерево, и если я пропускаю что-то важное здесь.

Кроме того, имея эти данные, как я должен проверить связь между отдельными комнатами? Выбор узла, проверить родителей и соединить все узлы внутри родителя, наверное?



Комментарии
1 ответ

Основной алгоритм-это правильно реализовано в БСП, так что да. Вы создаете двоичного дерева разделов.

Кроме того, чистки рядов: вам нужно всего лишь две точки на противоположных углах, чтобы определить ось которого совмещена прямоугольник, который вы, кажется, используете здесь. Это можно упростить.

Редактировать: только что заметил ваш вопрос про подключение:

Просто проверяю его непосредственного родителя дадут вам подмножество возможных сведений о соединении. Так как ваша БСП, ось которого совмещена и 2 мерных каждый узел может иметь от 1 до 4 соседних узлов (в зависимости от того, если он расположен по краям или нет) или 0 для корня, но если не обращать внимание на корень, потому что это не интересно.

Если вы заинтересованы в полное подключение можно либо обход дерева сверху вниз и следить за всеми краями и таким образом узнать, какие номера являются соседними. Или вы можете отслеживать север,запад,восток,юг Ближнего узла в процессе генерации дерева и использовать эту информацию для определения возможности подключения.

Если вы только посмотрите на непосредственного родителя, вы получите только один соединительный узел (из возможных 4). Я не знаю, как вы намерены использовать эту информацию, что это может быть достаточно для вас.

6
ответ дан 19 марта 2014 в 07:03 Источник Поделиться