Thursday, July 13, 2017

Tower of Hanoi Variations

A long, long time ago (1993) I spent a few weeks at a summer residential governor’s school, hosted by the college of William and Mary.  I remember only fragments of that time:  Playing capture-the-flag across the campus.  Some kind of fancy asteroids game.  Recording professors' answering machine messages and editing them to make them say funny things.

During one programming class, I remember the professor describing a linear congruential generator for pseudorandom numbers.  I thought to myself, "That can't be the best way, I came up with that on my own at home."  Then, being young, I said that out loud.  I think the professor said something to the effect of "Yes, you're very smart, now shut up."

I also remember helping to solve a variation of the Tower of Hanoi, and getting my name in a published paper.

You should already know what the Tower of Hanoi puzzle is.  If not, you know how to use Google: I'm not going to describe it to you here.

You probably didn't need a diagram for how to swap something.
This variation was pretty simple: As in the classic puzzle you can move the smallest disk to any other peg.  But the other disks can only be moved by swapping them with the next-smallest disk (and only when the two swapped disks are at the tops of their stacks).  This variation was introduced in 1944, and as far as Professor Stockmeyer could determine no algorithmic solution had been published (and he has looked around pretty thoroughly).  You can try it out at this demo site I made, by choosing the variation called "Swapping".

I hadn't thought about this for years, and then I go and watch two 3blue1brown videos about the Tower (part 1 and part 2) and the whole thing comes trickling back.

We were given a challenge: if we could produce a correct algorithm to solve this variation, then the professor would put our names on the paper he was going to publish.  It wasn't easy, but after some days we managed to find the solution.  The rest, as they say, is in the International Journal of Computer Mathematics.

Classic Tower of Hanoi solution
The classic Tower has a simple recursive solution:  Consider the biggest disk.  You want to get it from peg A to peg C, so first move everything else off of it and onto peg B.  Now you can move the big one to C, then move everything else from B to C.  The "move everything else" steps are where the recursion comes in, because doing that is just solving the puzzle again but with a slightly smaller tower.

Here's a notation that will help:  We'll list the positions of the disks from biggest to smallest, in a single string.  So we start out at "AAAA..." and we want to end up at "CCCC...".  The classic solution is to first go from AAAA... to ABBB... (by recursion), then to CBBB..., then to CCCC....

There's another variation, mentioned in the 3blue1brown videos, where you can only move disks to the right, except that you can also move a disk from the last peg to the first.  This might be called the Cyclic Tower of Hanoi, and it has a solution that's different from, but similar to, the classic Tower.  The difference is that here you can't just move the big disk from A to C.  It has to go to B first.  So you move everything else to C, move the big disk to B, move everything else to A, move the big disk to C, then move everything else to C.  This involves "move everything else" three times, so overall it takes more moves.  Using our notation, this means we go from AAAA... to ACCC... to BCCC... to BAAA... to CAAA... to CCCC....

Our variation involved swapping, and was a little more complicated.  Suppose we're going to implement a function "solve", which moves a tower from A to C.  To move the big disk to C you can't just get "everything else" out of the way.  You need the second-biggest disk to be on C, for the swap to work.  That is, we need to get from AAAA... to ACBB....  Let's ignore how to do that for a moment, and just say we have a function that does that, called "unfold".  Basically the function "unfold" takes a stack "AAAA..." and moves to "CBBB...", where the biggest disk of that stack is on one peg, and the rest of that stack is on another.  Suppose we also have the reverse function, "fold".

So the overall solution function, "solve", can work by first calling "unfold" to set up the big-disk swap (ACBB...), then doing that swap (CABB...), then calling "fold" to tidy everything up (CCCC...).  This is a good start, but unlike with the classic and cyclic variations, our "unfold" function isn't just a smaller version of the overall solution.  We still need to define it.

To implement "unfold", how do we get from AAAA... to CBBB...?  As before we've got to move the big disk from A to C.  So we start by going from AAAA... to ACBB..., then swap to CABB..., then somehow get from CABB... to CBBB....  The first part is easy, we call "unfold" on the sub-tower.  This last part is new, though.  Now we need some algorithm that can insert a disk underneath a stack.  That is, it needs to get from something like ABBB... to BBBB.... This requires another function, let's call that "insert".  We'll also need "extract", the inverse of this function (so we can implement "fold").

To implement "insert", how do we get from ABBB... to BBBB...?  The big disk needs to get from A to B, so we need to set things up for that swap.  This means we need to go from ABBB... to ABCC..., swap to BACC..., and then go from BACC... to BBBB....  Finally we have all the tools we need:  The first step there is just moving a whole tower (BB... to CC...), which is the "solve" function we're ultimately building.  The last step is "fold" (ACC... to BBB...).

How the five functions call each other.
So our solution involves five functions: "solve", "unfold", "fold", "insert", and "extract".  The paper rigorously describes why this solution is optimal, but I prefer to simply note that there aren't really any other options.  For the implementation of each function, the biggest disk really does need to move to the right place, and it can only get there if every other disk is set up just right.  It seems to me that it's optimal because it only makes necessary moves.

I made a site that demonstrates this and a few other variations of the Tower of Hanoi, at the link below.

Wednesday, June 21, 2017

Musical Notes and the Hilbert Curve

3blue1brown logo
seriously go watch the videos
Grant Sanderson makes a great series of YouTube videos, called 3blue1brown, that explore math concepts with animations.  This video talks about Hilbert curves, which are continuous fractal curves that completely fill a two-dimensional area.  The video uses them for a hypothetical system of encoding a two-dimensional image (as a grid of pixels) into a one-dimensional sound (as a range of frequencies).  I'm not sure such a system would work very well as described (to me, this system called "vOICe" seems a bit more practical) but that's not really the point of the video.  It's just a setting for talking about the curves, and how a concept like "approaching infinity" can have practical applications.

Fourth order Hilbert curve
would not make a good maze
Here, the Hilbert curve is used as a mapping from a 1D space into a 2D space.  A useful property of these curves is that when you increase the resolution (or the number of iterations) the mapped 2D location of a given 1D value is not drastically changed.  So someone can get used to 0.083 being at the top-center of the image, and it doesn't much matter what resolution is chosen for the curve - it's still basically at the top-center.

After watching the video, I wondered about the reverse procedure.  That is, what kind of images would it take to produce a given sound.  In particular, where would the standard musical pitches lie on the curve, and what would chords look like?

So I made a little web experiment to find out.  I call it Hilbert Chords.  Here's how it works:  I mapped the 1D space onto a single octave, the range of frequencies between middle-C and high-C.  It's a logarithmic scale, so the 12 pitches in the chromatic scale (plus one for the repeated C) are spaced evenly apart.  You can move your mouse over either the 2D or 1D regions to hear the corresponding pitch and also see where each point maps to in the other space.  Also you can click a handful of buttons that play preselected chords and see what the chord would look like.

locations of pitches on the chromatic scale
in color.. because, you know..
I was surprised, at first, to see that the notes all lie on corners of the four quadrants.  After thinking about it a bit, it makes sense.  Each quadrant connects to the next one at one of its corners.  The pair of corners connecting two quadrants are basically the same pitch.  So that leaves three distinctly-pitched corners per quadrant, for a total of twelve (and again there's the final corner for the repeated C).

When we increase the number of iterations, the curve gets denser, but the points representing the pitches move less and less.  As the number of iterations approach infinity, the pitch-points approach specific points on the square.  I don't have a complete understanding of the math, but it seems to me that four of them (E, G#, and the two Cs) approach the corners, six of them (C#, F, G, A, and B) approach the centers of the sides, and three of them (D, F#, and A#) approach the center.  At sufficiently high resolution, you wouldn't be able to see the difference between some very different chords, and the D augmented chord would look like a single point in the middle.

Ok, not a good visualization of the chromatic scale.  A plain circle is much better.  Or even just a keyboard.

Tuesday, June 13, 2017

Do not Discharge Stink Bombs in Andover

I'm not a lawyer.  Let's start with that.

(Los Angeles, not Andover)
credit: Steve Isaacs
But I was, you know, browsing through the code of bylaws of Andover, Massachusetts, and a few things jumped out at me.  First, the prohibition on certain items of amusement in Article XII §39(c):
The sale, distribution and discharge of stink bombs, smoke bombs and aerosol silly string products within the Town of Andover are prohibited.
This is apparently not an uncommon kind of ban.  Silly String is also banned in Middleborough, among other towns, and notably in Los Angeles, though only on Halloween.  Stink bombs are banned in Oklahoma City.  And there's New Hampshire 2017 House Bill 100, which would provide an exemption for "toy smoke devices" on the apparently more general prohibition of smoke bombs.  I guess serious smoke bombs would still be banned.

I don't know of any other town that has banned all three.  But I didn't do the most thorough of searches.  Nor did I, in ten minutes of googling, see any codes that provided an exception like that of §39(d):
This by-law shall not apply to public safety personnel in the conduct of their duties.
(Don't worry, this was photoshopped)
credit: What_No_Cookie
So it's fine for a police officer to use silly string, as long as it's part of their job.  I don't know how often that comes up.  Maybe if they're demonstrating things you're not allowed to do?  "Hey kids, see this stuff I'm spraying everywhere?  This is Silly String.  Looks like fun, huh?  Well, you can't do this!  Also, drugs."

§39 was enacted in 1998, after the town "experienced severe problems" with these sorts of devices.  It's hard for me to imagine how tough it must have been back then; I wasn't living in Andover at the time, so who am I to judge?  One thing's for sure though, I haven't had any severe silly string problems since I've moved in.  So I guess the ban is working!

The rest of Andover's bylaws are, for the most part, as interesting as you would expect bylaws to be.

Awww yeah, candlepin.
Article XI §4, which allows the Selectmen to "grant licenses for the operation of bowling alleys on the Lord's Day between the hours of 1:00 and 11:00 p.m.".  I think that bit refers to "[Massachusetts] General Laws, Chapter 136, Section 4B", which doesn't seem to exist at the moment.  But it's probably talking about something in the Common Day of Rest Law, which goes on and on about things you're not generally allowed to do on Sunday in Massachusetts, at least not without a license: such as dancing in exchange for money, offering to watch people dance in exchange for money, and just generally conducting business.  I'm not a lawyer, and that whole law seems ridiculous, so I'm probably not reading it right.  Anyway, it's good to know that if there were any bowling alleys in Andover (there aren't) then they could operate on Sunday if they got the appropriate license.

What you can't get a license for, according to Article XI §8(a), is an "automatic amusement device [kept at a business and operated for hire] which presents a risk of misuse as a gaming device".  I'm not sure about "misuse as a gaming device".  Is this indicating that gaming devices in general are bad, and we wouldn't want anyone using a non-gaming amusement device for gaming?  Maybe the misuse is bad, but only the kind of misuse that can happen with gaming devices.  MGL Chapter 140 Section 177A seems to indicate that pinball machines are "automatic amusement devices", but I would assume using it as a gaming device wouldn't be misuse.

Somehow I think they had slot machines in mind here, but they also helpfully list characteristics associated with risky amusement devices.  If it has any of those characteristics, then no license for you.  For instance, any device that "involves matching, random numbers, patterns or cards".  Or one that "accumulates more than 26 plays" (26 seems like a strange threshold).  Look out for any device that's "equipped with a "knock off" switch, button or similar device", those also carry a risk of misuse, somehow.

Probably needs a rabies shot, though.
There is the bit where it says one may keep or board pet cows (part of Article VII §, which I guess is cool, and let me to discover in the Board of Health regulations that the "Keeping of Goats Permit" is only $30.

So in summary, I'm not a lawyer, but I think you can ride your goat to the bowling alley on Sunday.  And you can bring your Stink Bombs but you can't use them.  And, please, play pinball only in moderation.

Thursday, June 1, 2017

BlockFractal: generator of blocky fractal-like shapes

The frabjous isle of North Osia
BlockFractal is an algorithm that generates blocky fractal-like shapes.  The idea is to make something that would be suitable for a continent, island, or lake, in a procedurally generated 2d tile-based game.  The demo page shows the generated shape with a Google-Maps-like interface, where you can zoom and pan around.

First it generates a random place name, like New Gharnia, Superior Iukauton, or Twuq'eros.  That name is used as a random seed to generate a random fractal.  You can enter your own place name, and you can control two properties of the fractal generation.

One is "iterations".  This sets how many times the BlockFractal algorithm is run on the initial seed shape.  The initial shape is a simple square, but each iteration adds finer and finer random detail to it.  Drag the iterations slider around to see how the shape was built.

The other is "variation".  This basically affects the craziness of the shape.  Low variation produces a simpler but blockier shape.  High variation produces a shape with many more twists and turns.  Somewhere in the middle seems to be pretty good for continent-looking shapes.

Seed square
Iteration in progress
New shape after first iteration

There's a thorough description of the algorithm at the Algorithm Overview page on the github site, but basically it goes like this:  Take the initial seed shape (a 2x2 square in the first of the three example images above), double it, and then for each unit edge make a random decision to leave it be or to move it "inward" or "outward".  That produces a new shape which is more complicated, and around twice as big, as the last one.

The frumious land of Yixonia
Repeat this algorithm as many times as you like, though it does take twice as much memory with each iteration, so to avoid memory issues I stopped the demo at 9 iterations.

There are a few edge cases to consider, for instance I don't want the path to intersect itself.  If you're curious the Algorithm Overview page has more details.

The resulting shapes make me think of Koch snowflakes and quadric fractals.  Also, check out Brainfilling Curves, for some similar and amazing shapes.

As you play with the demo, imagine if this were the high-level map of a top-down RPG or roguelike game.  I like the idea of scattering some different biomes and rivers around, randomly placing some cities and towns, and maybe using some Delaunay triangulation to connect them with roads.

Sunday, May 28, 2017

WarpField: portal-casting field-of-view algorithm

Here's WarpField, a "portal-casting" field-of-view algorithm.  This goes beyond the usual field-of-view mechanism by adding support for portals.  A portal basically connects an edge between tiles in one map with an edge in a (possibly different) map.  WarpField computes the field of view through the portal, and also returns what the player can see at each location.  This could be useful for:
Going up (or down) stairs.
  • Continuous overworld movement from zone to zone
  • Over/under pathways, such as bridges and tunnels
  • Smooth transitions of elevation changes, like stairs
  • Crazy magical effects, like portals to alternate dimensions.
In a previous post, I discussed WallyFOV, my implementation of a 2d grid-based field-of-view algorithm using shadow-casting.  For games that don't need portals, that algorithm is a better choice, since it's simpler and faster.  Unlike many field-of-view implementations, WallyFOV supports walls, which is a prerequisite for adding portal support.

"Portal-casting" is basically an extension of shadow-casting.  Shadow-casting tracks contiguous ranges of angles of rays that are visible from the player.  When a wall is encountered, we simply cut that range of angles out (causing a shadow).  For portals, instead of cutting that range out, we split it off into a new, separate range.  For each range we track which map the range "sees", and the relative tile offset into that map.

Entering a tunnel.
For each location that isn't completely in a shadow, we now have to decide which map we're seeing at that location, and which tile in that map goes there.  This can be tricky, because we might see the location more than one way at a time.  Maybe some rays reach the location after passing through a warp to map A, while others reach it after a warp to map B, and some reach it without passing through any warps at all.  In a 2D tile-based game we don't really want to show slices of a tile, we want to just pick one to show.  To resolve this ambiguity, WarpField has an order of preference: rays closest to the center are preferred, followed by rays that go through fewer warps, and finally ties are broken by the map with the lowest "id".

There are a lot of edge cases to consider, and most of them are touched upon in the algorithm overview.  I did a lot of testing and benchmarking, and I'm pretty sure it works according to spec, but there are some asymmetries that I'd like to remove (due to the order in which locations are visited).  I think I can clean that up by switching to fractional math instead of floating-point math.  Nevertheless, it's fairly robust, you can throw crazy cases at it like warps into the same map (such that the player can see themself through it), and rays that pass through many warps at once.

I think this could add a lot of potential to roguelike games.

Monday, May 15, 2017

WallyFOV: Shadow-casting field-of-view implementation with walls

I've been working on a field-of-view algorithm for 2d tile-based games (e.g. roguelikes).  There's a particular killer feature I mean to include in the algorithm, which I won't reveal in this post, but I decided to go ahead and release the slightly simpler version because I think it might be useful on its own.

It's called WallyFOV.  It's basically an implementation of recursive shadowcasting in TypeScript, but with support for walls.

Go ahead and check out the demo.  (and thanks to EasyStar.js for the pathfinding algorithm used in that demo, and from which I kindof copied the demo page style)

Recursive shadowcasting works by scanning outwards from the player looking for obstructions.  When something is found, a shadow (represented by two angles) is added to a shadow list.  Overlapping shadows are merged to keep the algorithm running quickly.

In this particular variant, a tile is considered visible if there exists any line from the center of the player's tile to any point within the target tile.  There are some complications around dealing with diagonally-adjacent bodies, which you can read about in the algorithm overview, but overall it's a pretty simple algorithm to understand.  It's a bit tricky to implement and optimize, however.

I spent a little extra time optimizing it to run in V8 (at least the version of V8 in node.js 7.9).  Along the way I learned how to use node's --trace-deopt, and discovered some very unexpected optimization tips, mainly having to do with newer ECMAScript features.

For instance, this version of V8 doesn't optimize "compound let/const assignment".  Meaning if you declare a variable with let or const, and then use something like X += Y, your function will be deoptimized.  Simply using X = X + Y instead avoids that trap.  The general lesson here is that JavaScript is apparently changing too rapidly to rely on the engine optimizing things according to your intuition.  This is probably true with any language, to a certain extent.  But, come on, X = X + Y?

Friday, January 27, 2017

Two Songs Arranged for Solo Piano

I've arranged two of my songs for solo piano, using MuseScore.  I had to make some changes in these arrangements compared to the originals, to remove or combine parts, and to make them physically possible to play.  I'm not a great pianist, but I made sure that I could play them through at a stop-and-think-about-the-next-part pace.  I think someone more skilled should be able to play them properly.

If you're that person I'd love to hear the result.  You can use the Download link at the MuseScore page for each piece to get printable versions of the scores.

The easier of the two, this one involves lots of many-fingered chords in both the right and left hands.  It's a mellow, ambient piece, and my most recent.

I made this one for Robot Quest.  At the time I called it "Plugged In", but I've renamed it because this name is much better.  A quick, boisterous, staccato piece, this one is very hard for me to play.