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.

Sunday, December 18, 2016

Kendall Stories

Lala and Sing acting out an argument.
Here are some web animations I made for my daughter.  One day she asked me to cut a hole out of a cardboard box so she could use it as a TV.  She then made three "shows", and for each one she drew scenes on several sheets of paper.  To present the shows, she would hold the paper up to the hole in the box while the rest of us sat on the other side and watched.

I thought it would be cute to turn her drawings into SVG images and animate them, and to record her voice and sync it up with the animation.  She really got into it, giving me very strict directorial instructions.  Part of the challenge for me was to try not to "improve" on her work with my own ideas.  I tried to stay as true to her vision for the shows as possible, and I included all of her mistakes (that she didn't catch in post-production and demand that I fix).

Not gonna what?

I used GreenSock GSAP's TweenMax library for the animations, and howler.js for audio.  Both are overpowered for this kind of project, but they saved time that I would have spent dealing with little headaches.  For instance you can't trigger HTML5 audio directly on mobile browsers.  I should have found a library for preloading and sizing images, because I ended up with some frustrating work making sure image sizes were loaded properly for IE.

Sunday, November 27, 2016

Word Search Generator

Here's a quickly-slapped-together little project that generates word search puzzles.

I've been kicking around an idea for a kind of "evil" word search, in which there are tons of letter combinations that almost spell words, but don't.  The trick would be to see how distracting the almost-words are, and whether that makes the correctly-spelled words harder to find.  That's not what this one is, though.  This one is just a regular, non-evil word search generator.

The core generator code is at this githib repo, or on npm as @sbj42/word-search-generator.

Sunday, November 20, 2016

Mr. Floppypants

Here's Mr. Floppypants.  A simple ragdoll-physics game.  Maybe it's about a very lazy person who needs to be forced to go explore and have fun.

It's based loosely on a "Chrome experiment" called Boingy, which the kids really got a kick out of.  I think they mostly liked dropping stuff on the poor protagonist, or forcing it to fall down stairs, or getting it twisted up into painful-looking poses.  After I played a bunch of MANYGOLF and through that learned about the p2.js javascript physics engine, I thought I'd make a more complicated version of my own.

It seems to work in Chome, Firefox, and Edge.  It does not work in IE.

Basically you click and drag to toss the guy around.  For more advanced play, if you click on his hand and drag it to something then he'll "grab" the thing.  You can use this to carry an item with you to some other part of the world, and to operate the car.

This game isn't nearly finished yet.  I was hoping to make the world a lot larger, and to add other characters to meet and also toss around.  If you get any ideas for things I could add to the game, let me know in the comments below.

Tuesday, October 18, 2016

Song: Coming Up for Air

I was trying to make some background music for It's EELectric!, but I failed.  I had various ideas, mostly working around an undersea theme.  I originally wanted something like the "Evan's Room" song from Legend of Zelda: Majora's Mask.  (digression: I always associated that song with being underwater because that's the context in which you hear it in the game, but I just learned from Zeldapedia that it's also the "Game Over" music from the original Legend of Zelda.)

Anyway after various ideas didn't seem to work, I settled on a sequence of 9th chords.  I expanded that into a more complete piece with a solemn, contemplative verse and a hopeful chorus.  Then I realized that it didn't at all fit the whimsical theme of the game for which I was writing it, and completely gave up on using it in that context.

Now I don't have anything to attach it to, so here it is by itself:

Friday, October 14, 2016

Maze generators

I'm working on another game for the kids, called "Mr. Floppypants", of which I'll say no more in this article, except that I'm using node.js, and that for it I required some code to generate a maze.  For once not wanting to write my own code for that particular subfeature, I searched around npm for "maze generator" packages.  There were a few.

Watch out for bull-men!
I set about looking into each one in turn to see if it would suffice, but I discovered for each one a reason not to use it.  One of them simply didn't run, another used Ecmascript 6 (and so wouldn't work in some browsers without being transpiled), one only worked for square mazes, and some (and I admit I was a bit picky) just weren't written to my taste.  Maze generation is a fun little project, and it's natural that many people have made their own generators, in varying degrees of quality.  Yes, I gave up and wrote my own.

Here's what I learned about mazes... wait, no.  Instead let me point you at some much better sources of information:

Jamis Buck writes a mostly-programming blog, and wrote a great series on maze generators in 2010 and 2011.  This in-browser presentation sums up the whole maze generation concept very nicely, and this recap of the blog series is a great place to get more details.  He describes how to implement a handful of algorithms, and provides in-browser demos so you can watch the algorithm run.

Walter Pullen has such a variety of interests that I refuse to summarize his site, in one part of it you can find a very thorough maze generator program he wrote, and he has written extensively about maze generation.  Aalso I just can't keep myself from mentioning his extensive files about the movie Labyrinth.

Now you know everything about mazes.  But just in case you didn't spend hours reading through all that stuff, here are some highlights:

A maze is basically equivalent to a spanning tree of a graph based on a rectangular grid.  Consequently, algorithms that compute spanning trees can be adapted to make mazes.  Kruskal's algorithm is like this, and builds mazes in an seemingly magical way:  It connects random adjacent cells, taking care not to create a loop, until a maze basically appears out of the noise.

Speaking of Kruskal's, the hardest part is quickly deciding whether two adjacent cells are already connected.  It can be done with a disjoint-set forest, and the tricks they use to make that fast (union by rank and path compression) are neat.

One of the simplest algorithms, recursive-backtracking, is my pick for making the best-looking mazes.  While generators like Kruskal's tend to make lots of clustered dead-ends, recursive-backtracking prefers meandering passages.  It works as basically a randomized depth-first-search of the grid.

Eller's algorithm can generate the maze one entire row at a time.  It works by keeping track of which cells connected to the previous row have already been connected (possibly by an earlier, now forgotten row).  On the very last row, it patches up any not-yet-connected regions of the maze.  In doing so, it may end up with a long straight passage along the bottom.

The Aldous-Broder algorithm generates all possible mazes with equal probibility, but you probably don't want to use it because it's very slow.  It's interesting to think about though: Start in a random cell and perform the well-named  "drunkard's walk", digging a passage when (and only when) you walk into a cell you've never visited before.  Assuming you have enough patience, you'll eventually visit every cell and oh hey, there's a maze!

It's not a generator, but "dead end filler" is an amusing way to solve some mazes without ever visiting cells in the solution path.  Find all the dead ends in the maze and fill them in.  Then find any new dead ends you created, and fill those in too.  Repeat until there are no more dead ends.  The remaining unfilled spaces are the solution.

Back to my project:  I implemented three algorithms (recursive-backtracking, modified Prim's, and Kruskal's).  I also used this as an opportunity to learn about node and npm, so the algorithm packages also have unit tests, benchmarks, and demos, and I spent some time trying to optimize them for speed and also make them easy to plug in to another project without needing to bring a lot of dependencies along.

@sbj42/maze-generator npm package

Update (10/15): I added a maze "puzzle" to Probably Puzzles.

Saturday, August 27, 2016

Generating Shikaku-like puzzles

A very small
in progress.
In my last post, I talked about adding Nonograms to Probably Puzzles.  Now let's talk Shikaku.

In Shikaku your task is to divide a grid into rectangular regions, such that every cell is assigned to a region, every region has exactly one number in it, and that number is the area of the region.

This one turned out to be harder to generate than Hidato, though maybe I haven't found the right algorithm.  The first step was to generate a random division of the grid into rectangles (i.e. to generate the solution).  I didn't find a good algorithm for that, so I made up a mediocre one:
  1. Choose a random cell that isn't yet in a rectangle
  2. Randomly decide on a major axis (horizontal or vertical)
  3. See how far we can stretch from that cell along the major axis (e.g. for horizontal we see how many empty cells there are to the left and right)
  4. Choose a random range from that span, with length no greater than 8
  5. See how far a rectangle of that width can go along the minor axis
  6. Choose a random range from that span, no longer than 8, where the rectangle's area is no bigger than 16
  7. If we were able to pick a rectangle bigger than 1x1, then go back to 1 and repeat until all cells are consumed.
  8. If not, then pick a random rectangle adjacent to the cell and remove it, then go back to 1.
That last step was the key to speed.  At first I had it just give up and start over if it hit an isolated cell, but it had to do a lot of resetting before it randomly ended up perfectly dividing the grid.  The last step allows it to make a small adjustment and try from there, rather than losing all the work it put into the earlier rectangles.

A grid, divided.
 This gives us a divided grid.  A solution in search of a problem.  So now we choose a random cell from each rectangle to use as the hint.  Here things get a little tricky.  To make sure there is only one unique solution for a given puzzle, we need to go ahead and solve it.

I wrote a brute force solver, but it was taking far too much time for puzzles of moderately-large size.  One trick I used to speed it up was to do a first pass on each hint, seeing how many possible rectangles could go there at the beginning of the puzzle.  Then we sort the hints from fewest to most possible rectangles, ensuring that we try all the "forced" ones first.

I suspect I can make the solver even faster if I resort at each decision in the solver tree, because placing one rectangle frequently reduces the number of options for another, and I find that for most of the Shikaku I'm generating, every rectangle is forced at some point or another, leaving the best kind of brute-force tree ever: a straight line to the solution.

There was another problem.  Too often the generator would put two 2x1 rectangles next to each other, and too often the hint-picker would select kitty-corner hints from those rectangles, giving the puzzle multiple solutions.
An ambiguous Shikaku.
When this happens, the solver takes longer to run, and in the end we have to throw all that work away because we won't accept a puzzle with multiple solutions.  So I threw in a pass to detect when this was happening and auto-correct it (by moving one of the hints).

That left me with a fast-enough generator and a not-so-fast-but-maybe-ok solver to verify the puzzles.

A generated Shikoku-like puzzle.
For the other puzzle types, I have a feature that allows you to adjust the "difficulty" of the puzzle, but so far I don't have that for Shikaku.  I could go by the number of choices made in the solver (which is what I did for Numbrix and Hidato), or I might even be able to use "number of initially-forced regions".  However I would need to speed up the solver before I attempted that.  At the highest grid-size setting, 15x15, it currently takes a while just to generate one puzzle, and if it started getting picky about difficulty it might take way too long.

Solving in progress.
The UI is pretty straightforward.  You click and drag to make rectangles.  It colors a rectangle red if it's invalid (i.e. if it contains no number, or more than one number, or doesn't have the right area for the number it contains).