Random or Not?

Here's a not-quite-hypothetical problem: you have a fixed size graph and want to arrange N points on that graph in a random manner. You could use such a thing for lots of different stuff not limited to distributing player positions on a map, etc.

So how do you do it? Feel free to code along at home.


First try: completely random. We'll just use our good friend rand() with some "proper" seed to choose X and Y values and mod them into the map space. Smashing. If you do that, it looks something like those on the left.

I saw the results and wondered where my bug was cause that sure as crap doesn't look random. Hint: there was no bug.


Hokay. Welp, I don't want those points to be within N distance of one another where N is something I can calculate easily because, er, I want it to run fast (not because I'm lazy--no not that at all).

Closer...

If you were looking for a point, you may have just found it: when I say random in this particular context, really mean evenly distributed rather than really random. In fact, truly random is not what I want at all.


On the left here are my final results after a mess of hacky heuristics. It's not the prettiest code but it seems to give good results on every map I've generated and it has a calculable upper bound on computation time. As a final step not shown here, I jitter each position inside the grid line so even points that are on the same row or column on the grid appear a little less regular (left as an exercise for the reader).

Now, I freely admit that I'm one to run off and code something because a) I figure I might learn something, b) I need the practice, and c) I reall like coding. Try as I might I was unable to find a better solution than the hackery I came up with. Apparently my google-fu is not as righteous as I thought. I'm pretty convinced that there's some crazy technique to do this in like 3.47 instructions on a 68020 or whatever but I sure as crap can't find it. If anyone knows of one, let me know.

(If anyone wants the code, just ask.)