SFML community forums

Help => General => Topic started by: Stauricus on September 23, 2019, 04:38:02 pm

Title: (almost) binary space partitioning example
Post by: Stauricus on September 23, 2019, 04:38:02 pm

hello everybody
I created this small example of BSP... its not done yet, and still a little buggy. but I wanted to share and ask for opinions
i'm planning to use it in some kind of random city creator. you press spacebar and it starts partitioning:

(https://i.postimg.cc/qtTmP9zC/Captura-de-tela-de-2019-09-23-11-15-35.png) (https://postimg.cc/qtTmP9zC)

and here goes the code:
(I know most people don't like globals, but its just for testing a prototype...)

(click to show/hide)

#include <SFML/System.hpp>
#include <SFML/Window.hpp>
#include <SFML/Graphics.hpp>

#include <vector>
#include <iostream>
#include <chrono>
#include <random>
#include <algorithm>

std::default_random_engine gen(std::chrono::system_clock::now().time_since_epoch().count());

class Block{
public:
    sf::Vector2i origin, end; //origin is the topleft corner, end is the bottom right
    sf::RectangleShape rect;

    Block();
    Block(int ox, int oy, int ex, int ey){
        update(ox, oy, ex, ey);
    }

    void update(int ox, int oy, int ex, int ey){
        origin.x = ox;
        origin.y = oy;
        end.x = ex;
        end.y = ey;

        rect.setPosition(sf::Vector2f(origin));
        rect.setSize(sf::Vector2f(end.x-origin.x, end.y-origin.y));
        std::uniform_int_distribution<int> dist(0, 255);
        rect.setFillColor(sf::Color(dist(gen), dist(gen), dist(gen)));
        rect.setOutlineColor(sf::Color::White);
        rect.setOutlineThickness(1);
    }

    std::vector<Block> subdivide(bool horizontal){
        std::vector<Block> blocks(2, Block(0, 0, 0, 0));
        if (horizontal == true){
            blocks[0].update(origin.x, origin.y, end.x, end.y-rect.getSize().y/2);
            blocks[1].update(origin.x, origin.y+rect.getSize().y/2, end.x, end.y);
        }
        else{
            blocks[0].update(origin.x, origin.y, end.x-rect.getSize().x/2, end.y);
            blocks[1].update(origin.x+rect.getSize().x/2, origin.y, end.x, end.y);
        }
        return blocks;
    }
};

int main(){
    sf::Vector2i max_block_size(20, 8);
    sf::RenderWindow window(sf::VideoMode(800, 600), "Binary Space Partitioning");
    window.setVerticalSyncEnabled(true);
    std::vector<Block> blocks{Block(0, 0, window.getSize().x, window.getSize().y)};

    while (window.isOpen()){
        sf::Event event;
        while (window.pollEvent(event)){
            if(event.type == sf::Event::Closed)
                window.close();
        }
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Space)){
            //identify the largest block
            std::vector<Block>::iterator it = std::max_element(blocks.begin(), blocks.end(), [] (Block a, Block b){return a.rect.getSize().x*a.rect.getSize().y < b.rect.getSize().x*b.rect.getSize().y;});
            //calculate its proportions based on the max size a block can have
            sf::Vector2f proportion(it->rect.getSize().x/max_block_size.x, it->rect.getSize().y/max_block_size.y);
            //if its horizontally big, but vertically small, divide vertically
            if (proportion.x > 1 && proportion.y < 1) {
                std::vector<Block> v = it->subdivide(false);
                blocks.erase(it);
                blocks.insert(blocks.end(), v.begin(), v.end());
            }
            //else, if its vertically big, but horizontally small, divide horizontally
            else if (proportion.x < 1 && proportion.y > 1){
                std::vector<Block> v = it->subdivide(true);
                blocks.erase(it);
                blocks.insert(blocks.end(), v.begin(), v.end());
            }
            //if its too large in both ways, make a random choice of how to divide, using a proportion based on how big it is compared to maximum block size
            //i.e.: if the max block size is 10, 10; and this block is 20, 30; it has 2/5 chances of subdividing horizontally, and 2/5 vertically
            else if (proportion.x > 1 && proportion.y > 1){
                std::discrete_distribution<int> dd ({it->rect.getSize().x/max_block_size.x, it->rect.getSize().y/max_block_size.y});
                std::vector<Block> v(2, Block(0, 0, 0, 0));
                if (dd(gen) == 0) v = it->subdivide(false);
                else v = it->subdivide(true);
                blocks.erase(it);
                blocks.insert(blocks.end(), v.begin(), v.end());
            }
        }
        window.clear();
        for (auto &i : blocks)
            window.draw(i.rect);
        window.display();
        sf::sleep(sf::milliseconds(10));
    }
    return 0;
}

=====EDIT=====

changed the code a bit
still produces some weirdness, but its much better. now it have streets  ;D
its kind of messy, tough. not intended for real life usage like it is, i guess.

(https://i.postimg.cc/c6SHpjkR/Captura-de-tela-de-2019-09-23-15-45-00.png) (https://postimg.cc/c6SHpjkR)

(click to show/hide)

#include <SFML/System.hpp>
#include <SFML/Window.hpp>
#include <SFML/Graphics.hpp>

#include <vector>
#include <iostream>
#include <chrono>
#include <random>
#include <algorithm>

sf::Vector2i tile_size, map_size;
std::default_random_engine gen(std::chrono::system_clock::now().time_since_epoch().count());

class Block{
public:
    sf::Vector2i origin, end;
    sf::RectangleShape rect;

    Block();
    Block(int ox, int oy, int ex, int ey){
        update(ox, oy, ex, ey);
    }

    void update(int ox, int oy, int ex, int ey){
        origin.x = ox;
        origin.y = oy;
        end.x = ex;
        end.y = ey;

        rect.setPosition(sf::Vector2f(origin.x*tile_size.x, origin.y*tile_size.y));
        rect.setSize(sf::Vector2f((end.x-origin.x)*tile_size.x, (end.y-origin.y)*tile_size.y));
        std::uniform_int_distribution<int> dist(55, 255);
        rect.setFillColor(sf::Color(dist(gen), dist(gen), dist(gen)));
        rect.setOutlineColor(sf::Color::White);
    }

    std::vector<Block> subdivide(bool horizontal, bool put_street){
        std::vector<Block> blocks(2, Block(0, 0, 0, 0));
        if (horizontal == true){
            blocks[0].update(origin.x, origin.y, end.x, end.y-rect.getSize().y/tile_size.y/2);
            if (put_street == true) blocks[1].update(origin.x, origin.y+rect.getSize().y/tile_size.y/2+1, end.x, end.y);
            else blocks[1].update(origin.x, origin.y+rect.getSize().y/tile_size.y/2, end.x, end.y);
        }
        else{
            blocks[0].update(origin.x, origin.y, end.x-rect.getSize().x/tile_size.x/2, end.y);
            if (put_street == true)blocks[1].update(origin.x+rect.getSize().x/tile_size.x/2+1, origin.y, end.x, end.y);
            else blocks[1].update(origin.x+rect.getSize().x/tile_size.x/2, origin.y, end.x, end.y);

        }
        return blocks;
    }
};

int main(){
    sf::Vector2i max_building_size(4, 4);
    sf::Vector2i max_block_size(10, 10);
    sf::RenderWindow window(sf::VideoMode(800, 600), "Binary Space Partitioning");
    window.setVerticalSyncEnabled(true);
    map_size = sf::Vector2i(50, 50);
    tile_size = sf::Vector2i (window.getSize().x/map_size.x, window.getSize().y/map_size.y);
    std::vector<Block> blocks{Block(0, 0, map_size.x, map_size.y)};

    while (window.isOpen()){
        sf::Event event;
        while (window.pollEvent(event)){
            if(event.type == sf::Event::Closed)
                window.close();
        }
        if (sf::Keyboard::isKeyPressed(sf::Keyboard::Space)){
            std::vector<Block>::iterator it = std::max_element(blocks.begin(), blocks.end(), [] (Block a, Block b){return a.rect.getSize().x*a.rect.getSize().y < b.rect.getSize().x*b.rect.getSize().y;});
            sf::Vector2f proportion(it->rect.getSize().x/tile_size.x/max_block_size.x, it->rect.getSize().y/tile_size.y/max_block_size.y);
            if (proportion.x > 3 && proportion.y < 1) {
                auto v = it->subdivide(false, true);
                blocks.erase(it);
                blocks.insert(blocks.end(), v.begin(), v.end());
            }
            else if (proportion.x < 1 && proportion.y > 3){
                auto v = it->subdivide(true, true);
                blocks.erase(it);
                blocks.insert(blocks.end(), v.begin(), v.end());
            }
            else if (proportion.x > 1 && proportion.y > 1){
                std::discrete_distribution<int> dd ({it->rect.getSize().x/max_block_size.x, it->rect.getSize().y/max_block_size.y});
                std::vector<Block> v(2, Block(0, 0, 0, 0));
                if (dd(gen) == 0) v = it->subdivide(false, true);
                else v = it->subdivide(true, true);
                blocks.erase(it);
                blocks.insert(blocks.end(), v.begin(), v.end());
            }
            else {
                sf::Vector2f proportion_b(it->rect.getSize().x/tile_size.x/max_building_size.x, it->rect.getSize().y/tile_size.y/max_building_size.y);
                if (proportion_b.x > 1 && proportion_b.y < 1) {
                    auto v = it->subdivide(false, false);
                    blocks.erase(it);
                    blocks.insert(blocks.end(), v.begin(), v.end());
                }
                else if (proportion_b.x < 1 && proportion_b.y > 1){
                    auto v = it->subdivide(true, false);
                    blocks.erase(it);
                    blocks.insert(blocks.end(), v.begin(), v.end());
                }
                else if (proportion_b.x > 1 && proportion_b.y > 1){
                    std::discrete_distribution<int> dd ({it->rect.getSize().x/max_building_size.x, it->rect.getSize().y/max_building_size.y});
                    std::vector<Block> v(2, Block(0, 0, 0, 0));
                    if (dd(gen) == 0) v = it->subdivide(false, false);
                    else v = it->subdivide(true, false);
                    blocks.erase(it);
                    blocks.insert(blocks.end(), v.begin(), v.end());
                }
            }
        }
        window.clear(sf::Color(100, 100, 100));
        for (auto &i : blocks)
            window.draw(i.rect);
        sf::VertexArray grid(sf::Lines, 2);
        grid[0].color = sf::Color(255, 255, 255, 100);
        grid[1].color = sf::Color(255, 255, 255, 100);
        for (int x=0; x<=map_size.x; x++){
            grid[0].position = sf::Vector2f(x*tile_size.x, 0);
            grid[1].position = sf::Vector2f(x*tile_size.x, map_size.y*tile_size.y);
            window.draw(grid);
        }
        for (int y=0; y<=map_size.y; y++){
            grid[0].position = sf::Vector2f(0, y*tile_size.y);
            grid[1].position = sf::Vector2f(map_size.x*tile_size.x, y*tile_size.y);
            window.draw(grid);
        }
        window.display();
        sf::sleep(sf::milliseconds(10));
    }
    return 0;
}