samedi 14 janvier 2023

Binary tree children not being stored into variable reference

So I'm creating this binary tree and here is what I've gotten to:

#include <cmath>
#include <random>
#include <queue>
 
 
const int MIN_CONTAINER_SIZE = 5;
 
 
struct Point {
    int x, y;
 
    inline bool operator==(const Point pnt) const {
        return x == pnt.x && y == pnt.y;
    }
 
    inline bool operator!=(const Point pnt) const {
        return x != pnt.x && y != pnt.y;
    }
 
    Point() = default;
 
    Point(int x_val, int y_val) {
        x = x_val;
        y = y_val;
    }
 
    inline std::pair<int, int> sum(Point &other) const {
        return std::make_pair(x + other.x, y + other.y);
    }
 
    inline std::pair<int, int> abs_diff(Point &other) const {
        return std::make_pair(abs(x - other.x), abs(y - other.y));
    }
};
 
 
struct Rect {
    Point top_left, bottom_right;
    Point center;
    int width, height;
 
    Rect() = default;
 
    Rect(Point top_left_val, Point bottom_right_val) {
        std::pair<int, int> sum = top_left_val.sum(bottom_right_val);
        std::pair<int, int> diff = top_left_val.abs_diff(bottom_right_val);
        top_left = top_left_val;
        bottom_right = bottom_right_val;
        center = Point((int) round(((double) sum.first) / 2.0), (int) round(((double) sum.second) / 2.0));
        width = diff.first;
        height = diff.second;
    }
};
 
 
struct Leaf {
    Rect container;
    Leaf *left, *right;
    Rect *room;
 
    Leaf(Rect container_val) {
        container = container_val;
        left = nullptr;
        right = nullptr;
        room = nullptr;
    }
 
    bool split(std::mt19937 &random_generator) {
        if (left && right) {
            return false;
        }
 
        std::uniform_int_distribution<> split_vertical_distribution(0, 1);
        bool split_vertical_val = split_vertical_distribution(random_generator);
        if ((container.width > container.height) && (((double) container.width / container.height) >= 1.25)) {
            split_vertical_val = true;
        } else if ((container.height > container.width) && (((double) container.height / container.width) >= 1.25)) {
            split_vertical_val = false;
        }
 
        int max_size = (split_vertical_val) ? container.width - MIN_CONTAINER_SIZE : container.height - MIN_CONTAINER_SIZE;
        if (max_size <= MIN_CONTAINER_SIZE) {
            return false;
        }
 
        std::uniform_int_distribution<> pos_distribution(MIN_CONTAINER_SIZE, max_size);
        int pos = pos_distribution(random_generator);
 
        if (split_vertical_val) {
            pos += container.top_left.x;
            left = new Leaf{
                Rect{
                    Point{
                        container.top_left.x, container.top_left.y
                    },
                    Point{
                        pos - 1, container.bottom_right.y,
                    }
                }
            };
            right = new Leaf{
                Rect{
                    Point{
                        pos + 1, container.top_left.y,
                    },
                    Point{
                        container.bottom_right.x, container.bottom_right.y
                    }
                }
            };
        } else {
            pos += container.top_left.y;
            left = new Leaf{
                Rect{
                    Point{
                        container.top_left.x, container.top_left.y
                    },
                    Point{
                        container.bottom_right.x, pos - 1,
                    }
                }
            };
            right = new Leaf{
                Rect{
                    Point{
                        container.top_left.x, pos + 1,
                    },
                    Point{
                        container.bottom_right.x, container.bottom_right.y
                    }
                }
            };
        }
 
        return true;
    }
};
 
void split_bsp(Leaf &bsp, std::mt19937 &random_generator, int split_iteration) {
    std::queue<Leaf> queue;
    queue.push(bsp);
    while (split_iteration > 0 && !queue.empty()) {
        Leaf current = queue.front();
        queue.pop();
 
        if (current.split(random_generator) && current.left && current.right) {
            queue.push(*current.left);
            queue.push(*current.right);
            split_iteration -= 1;
        }
    }
}
 
void create_map(unsigned int seed) {
    int grid_width = 50;
    int grid_height = 100;
    std::mt19937 random_generator(seed);
    Leaf bsp = Leaf{
        Rect{
            Point{0, 0},
            Point{grid_width - 1, grid_height - 1}
        }
    };
    split_bsp(bsp, random_generator, 5);
}
 
int main() {
    for (int i = 0; i < 1000; i++) {
        create_map(i);
    }
}

However, during the while loop in split_bsp, the binary tree is able to split and successfully creates and stores the children. But on the next iteration, it resets the current variable deleting any progress. The program should store the children onto the bsp parameter. How can I fix this?

Aucun commentaire:

Enregistrer un commentaire