Skip to content

Instantly share code, notes, and snippets.

/randomfloodfill.cpp
Created Aug 24, 2017

Embed
What would you like to do?
Random Floodfill
#include <fstream>
#include <vector>
#include <random>
#include <algorithm>
struct Point
{
int x;
int y;
bool water;
int water_neighbors;
bool valid;
Point(int X, int Y, bool Water, int Water_neighbors)
{
x = X;
y = Y;
water = Water;
water_neighbors = Water_neighbors;
valid = true;
}
Point()
{
x = y = water_neighbors = -1;
water = valid = false;
}
//necessary for std::sort
bool operator<(Point& rhs)
{
return water_neighbors < rhs.water_neighbors;
}
};
class Map
{
int _width;
int _height;
int* _data;
public:
Map(int width, int height)
{
_width = width;
_height = height;
_data = new int[width * height];
for (int i = 0; i < width * height; ++i)
_data[i] = 0;
}
~Map()
{
delete[] _data;
}
Point get(int x, int y)
{
if (x < 0 || x >= _width || y < 0 || y >= _height)
return Point();
int num_neighbors = (x == 0 ? 0 : _data[x - 1 + y * _width]) +
(x == _width - 1 ? 0 : _data[x + 1 + y * _width]) +
(y == 0 ? 0 : _data[x + (y - 1) * _width]) +
(y == _height - 1 ? 0 : _data[x + (y + 1) * _width]);
return Point(x, y, _data[x + y * _width], num_neighbors);
}
void set(int x, int y, int value)
{
if (x >= 0 && x < _width && y >= 0 && y < _height)
_data[x + y * _width] = value;
}
};
void make_lake(Map&, int, int, int, std::default_random_engine&);
void print_points(Map&);
int main()
{
//set up the basic data structure. 0 == land, 1 == water
Map points(100, 100);
//set up the RNG
std::default_random_engine rng;
rng.seed(std::random_device()());
make_lake(points, 50, 50, 600, rng);
print_points(points);
return 0;
}
void make_lake(Map& points, int start_x, int start_y, int desired_area, std::default_random_engine& rng)
{
//set up the pile of points
std::vector<Point> pile;
int covered_area = 0;
//push on the starting point
pile.push_back(points.get(start_x, start_y));
while (pile.size() > 0 && covered_area < desired_area)
{
//if there are any points with three or four neighbors, we should prioritize those by skipping this step
if (pile.back().water_neighbors < 3)
{
//pick a point in the pile based on some distribution
//int position = pile.size() - 1 - std::binomial_distribution<int>(pile.size() - 1, 0.5)(rng);
std::uniform_int_distribution<> distribution(0, pile.size() - 1);
int position = distribution(rng);
//swap that point with the back
std::iter_swap(pile.begin() + position, pile.rbegin());
}
//now pull off the top of the pile
Point p = pile.back();
pile.pop_back();
//set it to water, update the area variable
points.set(p.x, p.y, 1);
++covered_area;
//now go through the list and remove any points that neighbor this cell (we'll re-add them below with updated neighbor counts)
for (int i = 0; i < (int)pile.size(); ++i)
{
//if the manhattan distance bewteen the two points is 1...
if (std::abs(pile[i].x - p.x) + std::abs(pile[i].y - p.y) == 1)
{
//remove the element
pile[i] = pile.back();//the most efficient way to do this in a vector (where order doesn't matter) is by swapping with the back and then popping
pile.pop_back();
--i;
}
}
//now add in this cell's land neighbors
Point pw = points.get(p.x - 1, p.y);
Point pn = points.get(p.x, p.y - 1);
Point pe = points.get(p.x + 1, p.y);
Point ps = points.get(p.x, p.y + 1);
if (pw.valid && !pw.water)
pile.push_back(pw);
if (pn.valid && !pn.water)
pile.push_back(pn);
if (pe.valid && !pe.water)
pile.push_back(pe);
if (ps.valid && !ps.water)
pile.push_back(ps);
//then sort the pile by water-neighbor count (so the highest are at the end)
//std::shuffle(pile.begin(), pile.end(), rng); //if using a non-uniform distribution, shuffle first to reduce blockiness
std::sort(pile.begin(), pile.end());
points.set(start_x, start_y, 1);
}
}
void print_points(Map& points)
{
std::ofstream outfile("output.txt");
for (int x = 0; x < 100; ++x)
{
for (int y = 0; y < 100; ++y)
{
if (points.get(x, y).water)
outfile << "~";
else
outfile << "#";
}
outfile << std::endl;
}
outfile.close();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.