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.)

A Year of BEER

Programming is pretty cool. It's one of the only disciplines where the tools are made of the same stuff the products are. In fact, the only other one I can name is blacksmithing and really, it's best that I don't try that one.


As of a couple weeks ago, the BEER engine is officially a year old. Sadly, I didn't notice until I went to update numbers for September. A good 35,000 lines and more than 200 hours later, I have to say that it's everything I wanted it to be and more. It's hard to say in objective terms how much I've learned in this endeavor and the (so far) three projects it's enabled, but I can say without hesitation that it's been a substantial amount.