The maze book for programmers!
Algorithms, circle mazes, hex grids, masking, weaving, braiding, 3D and 4D grids, spheres, and more!
Once upon a time, I wrote a fantasy trading simulator. You played a humble merchant, buying goods in one town and selling them in another. The goal was to make a profit, eventually upgrading your donkey to a caravan of wagons, with guards and magic wards to protect from brigands and dragons.
It was a fun project, but one of the weakest parts of it was generating the network of towns. I made it work, but imperfectly. It wasn’t until years later that I learned a technique–called Poisson disk sampling–that does the job much more neatly. It generates a spread of points, none of which are within some specified distance of each other, and with a pleasingly even distribution.
This week, we’re going to play with Bridson’s algorithm for Poisson disk sampling. But first, let’s recap week #12.
For the 12th weekly programming challenge, we fiddled with family trees and pedigree charts. Sadly, it must have been a busy week (or a boring topic!), as no one submitted a solution.
My own answer this week was again minimal. (Moving house, it turns out, is not a trivial thing, nor is it quickly over. I have hope that the end is in sight, though!) Once again, I went with a minimal Ruby implementation. I drew the pedgree as a PDF via Prawn, and supported pedigree charts of aribtrary size. (Though the charts are only legible at 7 or fewer generations, unless you increase the page size.) That’s two points for me! You can see what I’ve got here: https://github.com/jamis/weekly-challenges/tree/master/012-family-trees.
Before you read any further, you really must check out Mike Bostock’s hypnotizing demonstrations of Bridson’s algorithm for Poisson disk sampling. The first one shows the points growing outward from the starting point, and the second one gives a more detailed explanation of how the algorithm works.
The algorithm itself is detailed in this PDF–a remarkably brief paper by Robert Bridson. It’s actually quite straight forward to read and understand.
The general idea, though is this:
For normal mode (and one point), here’s all you’ve got to do:
For hard mode, you should be ready to stretch yourself a bit. Each of these will add one point to your score.
Feel free to shoot for “surprise me” mode, too! It doesn’t have to be any harder than normal mode, but it ought to implement the challenge (either normal mode or hard mode) in some surprising, clever, or otherwise delightful way. See what you can come up with!
This challenge will run until Saturday, October 29th, at 12:00pm MDT (18:00 UTC).
Post a link to your submission in the comments, but please: only link to your solution. Do not post source code in the comments. Comments that post source code directly will be removed. If you have any questions about this challenge, post them in the comments as well and I’ll try to clarify.
If you’d prefer not to post your solution as a comment, please feel free to email your solution to me directly, at firstname.lastname@example.org.