Weekly Programming Challenge #6

Let’s make some noise…

One of the things I love most about these challenges is that it gives me an excuse to try things I’ve been wanting to try for a long time. For this week’s challenge, we’re going to take a look at something that’s intrigued me for a while: the Perlin noise function, a staple of the 80’s and 90’s demoscene.

But first, let’s recap week #5…

Week #5 Recap

Last week’s challenge was to implement a priority queue on top of a binary heap. This earned you one point. Additional points were earned for:

• making your heap’s sort function configurable
• allowing arbitrary data types
• allowing the priority of individual elements in the queue to change
• implementing a Huffman coder
• implementing Dijkstra’s algorithm

There were three brave souls who rose to the challenge:

1. Lasse Ebert came away with 5 points for his Elixir implementation. What is more, he went above and beyond by taking his Huffman coder and implementing a corresponding decoder, so he could compress and decompress files, which qualifies him for the coveted surprise me award! Check out his implementation here: https://github.com/lasseebert/jamis_challenge/tree/master/005_heap
2. Steve Desmond earned 4 points for his implementation is C#. He was the only contestant to implement the “update priority” feature, and his solution looks quite elegant! See for yourself: https://github.com/stevedesmond-ca/WeeklyChallenges/tree/master/05-BHPQ
3. Jérôme De Cuyper earned 1 point for his concise normal-mode submission, in vanilla Javascript — complete with QUnit tests! His solution fits in a gist: https://gist.github.com/jdecuyper/45b72028c8568de2a85e1c93022c6b05

Great work, all! I hope you all had as much fun with this challenge as I did.

My own solution, in Go (a first, for me!), can be seen here: https://github.com/jamis/weekly-challenges/tree/master/005-priority-queue. I implemented a custom sorting function, “arbitrary” data types (using interfaces), and a simple Huffman coder, which all added up to give me 5 points.

Weekly Programming Challenge #6

Perlin noise was developed by Ken Perlin back in the 80’s, and even if you’ve never heard of it before, you’ve almost certainly seen it used. It is ubiquitous, most notably in demos and video games, but more generally in any kind of computer graphics. It’s great for such things as randomly generated terrain, or clouds, or fire. The result of drawing Perlin noise in two dimensions, and then rescaling it and adding it to itself, looks something like this:

Perlin noise in two dimensions

Our challenge for this week is to produce an image of two-dimensional Perlin noise, at least 256 pixels square.

Now, as I’ve never implemented Perlin noise before, I can’t really give any significant guidance to this, but Wikipedia has a description of the algorithm, with pseudocode. Consider that a starting point and do your own research, but beware: some articles on the Internet are wrong (can you believe it?!) and call different (but related) algorithms “Perlin noise”. Let’s try to stay on point for this challenge!

Normal Mode

So, for normal mode (and one point), you must implement a 2D Perlin noise function, and use it to produce an image (at least 256 pixels square). You may use whatever image library you want (or even the one you created in challenge #3, “drawing lines”), and produce the image in whatever format you want (though a lossless format would be preferred).

Hard Mode

As I’ve never implemented this algorithm, it’s hard for me to say what’s worthy of extra points. Still, let’s grope around in the dark a bit and say that the following milestones will earn you additional glory, to the tune of 1 extra point each:

• 3D noise — in addition to being able to produce a 2D image of Perlin noise, implement 3D Perlin noise. Your output may be whatever you wish, but it should at least demonstrate that your noise has three-dimensions. You may want to emit multiple images, each representing a 2D slice of the 3D noise.
• Terrain — by mapping pixel intensity to altitude, you can treat the output as a terrain map. Color your noise according to altitude, treating lower altitudes as water and higher as mountains, and produce landscapes.
• Height map — these noise images can also be used as height maps. Using a tool of your choice, produce a 3D image that employs some noise you generated to produce a height effect (either displacing the surface of an object, or producing height-mapped terrain).

There’s lots of room for “surprise me” here, too, since this is all new to me. See what you can come up with! Hopefully, once you’re generating Perlin noise, you’ll have all kinds of fun ideas for how to play with it.

Feel free to share helpful resources in the comments! I’m hopeful that we’ll all learn a lot this week.

This challenge will run until Saturday, September 10th, at 12:00pm MDT (18:00 UTC).

The deadline for this challenge has passed, but feel free to try your hand at it anyway! Go ahead and submit a link to your solution in the comments, anytime. If you’re following along, the next week’s challenge is “B+ trees”. See you there!