Last active
March 6, 2020 15:43
-
-
Save G4rryS1ngh/d6834f3e9977c7f196293a6720dc94eb to your computer and use it in GitHub Desktop.
Procedural tree generation using space colonization algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # include <Siv3D.hpp> // OpenSiv3D v0.4.2 | |
| struct Leaf | |
| { | |
| Vec2 pos; | |
| bool reached = false; | |
| Leaf(Vec2 _pos) | |
| : pos(_pos) | |
| {} | |
| void draw() const | |
| { | |
| Circle(pos, 2).draw(); | |
| } | |
| }; | |
| struct Branch | |
| { | |
| Vec2 pos; | |
| Vec2 dir; | |
| Vec2 orig_dir; | |
| Optional<size_t> parent; | |
| int count; | |
| Branch(Vec2 _pos, Vec2 _dir, Optional<size_t> _parent = Optional<size_t>()) | |
| : pos(_pos) | |
| , dir(_dir) | |
| , orig_dir(_dir) | |
| , parent(_parent) | |
| {} | |
| void reset() | |
| { | |
| dir = orig_dir; | |
| count = 0; | |
| } | |
| void draw(const Array<Branch>& branches) const | |
| { | |
| if(parent) | |
| Line(branches[*parent].pos, pos).drawArrow(); | |
| } | |
| }; | |
| struct TreeParam | |
| { | |
| double max_dist = 100; | |
| double min_dist = 40; | |
| double branch_length = 20; | |
| Vec2 start = Scene::Rect().bottomCenter(); | |
| Vec2 dir = Vec2::Up(); | |
| size_t num_of_leaves = 500; | |
| Polygon shape = Ellipse(Scene::Rect().stretched(0, 0, -100, 0)).asPolygon(); | |
| }; | |
| struct Tree | |
| { | |
| Array<Leaf> leaves; | |
| Array<Branch> branches; | |
| TreeParam param; | |
| Tree() | |
| { | |
| initialize(); | |
| } | |
| void initialize() | |
| { | |
| // 葉(終点)をランダムに生成 | |
| Array<Vec2> points(param.num_of_leaves, Arg::generator = [&]() { return RandomVec2(param.shape.boundingRect()); }); | |
| points.keep_if([&](const Vec2 v) { return param.shape.contains(v); }); | |
| leaves = points.map([&](const Vec2 v) { return Leaf(v); }); | |
| // 始点 | |
| branches << Branch(param.start, param.dir); | |
| // いずれかの葉に近接するまで枝をまっすぐ伸ばす | |
| int id = 0; | |
| bool found = false; | |
| while (!found) | |
| { | |
| const Branch& current = branches[id]; | |
| for (const Leaf& leaf : leaves) | |
| { | |
| if (current.pos.distanceFrom(leaf.pos) < param.max_dist) | |
| found = true; | |
| } | |
| if (!found) | |
| { | |
| Vec2 new_dir = current.dir.normalized(); | |
| Vec2 new_pos = current.pos + new_dir * param.branch_length; | |
| branches << Branch(new_pos, new_dir, id); | |
| id++; | |
| } | |
| } | |
| } | |
| void reset() | |
| { | |
| leaves.clear(); | |
| branches.clear(); | |
| initialize(); | |
| } | |
| void update() | |
| { | |
| for (Leaf& leaf : leaves) | |
| { | |
| // 葉に一番近い枝 | |
| Optional<size_t> closest; | |
| double record = param.max_dist; | |
| for (auto [i, branch] : Indexed(branches)) | |
| { | |
| double d = branch.pos.distanceFrom(leaf.pos); | |
| // 枝に十分近い葉は削除 | |
| if (d < param.min_dist) | |
| { | |
| leaf.reached = true; | |
| closest.reset(); | |
| break; | |
| } | |
| else if (d < record) | |
| { | |
| closest = i; | |
| record = d; | |
| } | |
| } | |
| // 葉に一番近い枝を伸ばす | |
| if (closest) | |
| { | |
| Branch& branch = branches[*closest]; | |
| branch.dir += (leaf.pos - branch.pos).normalized(); | |
| branch.count++; | |
| } | |
| } | |
| // 枝に十分近い葉は削除 | |
| leaves.remove_if([](const Leaf& leaf) { return leaf.reached; }); | |
| // 葉が近くにある枝を伸ばす | |
| Array<Branch> new_branches; | |
| for (auto [i, branch] : Indexed(branches)) | |
| { | |
| if (branch.count > 0) | |
| { | |
| Vec2 new_dir = branch.dir.normalized(); | |
| Vec2 new_pos = branch.pos + new_dir * param.branch_length; | |
| new_branches << Branch(new_pos, new_dir, i); | |
| } | |
| } | |
| branches.append(new_branches); | |
| branches.each([](Branch& b) { b.reset(); }); | |
| } | |
| void draw() const | |
| { | |
| param.shape.draw(AlphaF(0.1)); | |
| leaves.each([](const Leaf& l) { l.draw(); }); | |
| branches.each([&](const Branch& b) { b.draw(branches); }); | |
| } | |
| }; | |
| void Main() | |
| { | |
| Tree tree; | |
| while (System::Update()) | |
| { | |
| if (KeyEnter.down()) | |
| tree.reset(); | |
| tree.update(); | |
| tree.draw(); | |
| Vec2 pos(10, Scene::Height() - 10); | |
| double numf = tree.param.num_of_leaves; | |
| SimpleGUI::Slider(U"num = {}"_fmt(tree.param.num_of_leaves), numf, 100, 1000, pos.moveBy(0, -40), 120); | |
| tree.param.num_of_leaves = (size_t)Round(numf); | |
| SimpleGUI::Slider(U"len = {:.0f}"_fmt(tree.param.branch_length), tree.param.branch_length, 10, 100, pos.moveBy(0, -40), 120); | |
| SimpleGUI::Slider(U"min = {:.0f}"_fmt(tree.param.min_dist), tree.param.min_dist, 10, tree.param.max_dist, pos.moveBy(0, -40), 120); | |
| SimpleGUI::Slider(U"max = {:.0f}"_fmt(tree.param.max_dist), tree.param.max_dist, tree.param.min_dist, 100, pos.moveBy(0, -40), 120); | |
| } | |
| } |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
無駄なループが多いのでブラッシュアップが必要φ(..)メモメモ