#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;
}