June 2011 Archives

Display your data - Random::PoissonDisc

I read this nice article on map generation and naturally want to write something like it, but in Perl. For the first step, I want to distribute points nicely across the plane, by using the Poisson Disk Sampling method outlined in the article. Implementing the algorithm was straightforward, but how would I know that the output data was correct in the sense of reaching my goal of uniform but randomly distributed points across the plane?

The test program of Random::PoissonDisc conveniently outputs the generated points to STDOUT. For visually inspecting the data, I can then pipe it into App::ffeedflotr which displays a nice point cloud. The first output of Random::PoissonDisc looked like this:

perl -w bin/random-poissondisc.pl -r 10 | ffeedflotr.pl --type=scatter

Image of wrong distribution

Clearly, this picture shows that something was wrong with the first attempt of creating the random data. The grid is 20x20 units, and with a minimum distance of 10 between points, there should be at most 2 points per grid. My error was in the code for sample rejection. The code only checked the immediate cache, and not the neighbouring cache positions. After fixing that part of the code, I'm not certain whether the code is correct. But its output looks quite satisfying:

Better distribution

The module itself will soonish hit CPAN. I see a lot of improvement opportunities for the module. It could support incremental point generation. It could actually use a vector library like PDL instead of hand-rolling most of the vector manipulation code. It could use some tests beyond basic functionality tests.

But for the moment, I'm very happy with the fact that the code produces results I can use in creating random maps. And also I'm very happy with the fact that I have nice visualisation tools that enable me to visually verify the quality of datasets.

About Max Maischein

user-pic I'm the Treasurer for the Frankfurt Perlmongers e.V. . I have organized Perl events including 9 German Perl Workshops and one YAPC::Europe.