🔒 Locked

random filling algorithm

Started by GameDev.net Oct 10, 2006 at 4:02 PM 1 replies 850+ views

Original Post

Oct 10, 2006 at 4:02 PM

How can I eficiently do a "random" fill on a surface? I need this for some random map generation process. That is I don't wanna fill the surface from left to right, top to bottom, but by placing points randomly on the surface. This could be simple, but I need some optimization cause I don't want to start skipping more and more already written pixels when the surface starts to fill... Now I'm simply place random points with the condition that if I fail to find an empty position for, let's say, 1000 times, then it's enough; after that I make a liniar search over the surface for lost gaps and that's all... This is ok for 100 x 100 sizes, but for larger dimensions the time increseas exponentially [sad] I've also tried to fill the surface left-right, top-bottom with a step of various odd numbers, but the result doesn't look random anymore...

Fruny

Oct 10, 2006 at 4:50 PM

Create a vector of pixel indices, shuffle it with std::random_shuffle. Then you can fill the map in the order of those randomized indices.

For example:

std::vector<double> map(2500); // 50x50size_t size = map.size();std::vector<unsigned int> indices(size);for(int i=0; i<size; ++i)   indices = i;std::random_shuffle(indices.begin(), indices.end());for(int i=0; i<size; ++i)   map[indices] = 42.0;

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.