Making a simple little word guessing game

On the 17th, I was feeling sort of empty and didn't want to do anything, but also didn't want to do nothing while laying in bed trying to fall asleep. I ended up opening up the android game store looking for something free to pass the time and found a decently fun puzzle game. Playing it here and there the next few days, I found myself irritated by the amount of deceptive ads, false clicks, and other nonsense that the company pushing this out had included.

Wait, I'm a programmer. I can make things. Why don't I just make my own version of the game since it's basically just a variation on boggle. This could be a great subject for a blog post that bridges the beginner to intermediate gap that I'm often trying to seek out for the content on my website. So. Here it is! Let's make a fun game for us all to enjoy, ad free, and then polish it up to make it something really good feeling!

Rules and planning

So, I planned on starting this a lot earlier in the day (It's now past 9pm and I was thinking about this around 9am), and while I'm writing this I haven't actually decided which language I'm going to do this in. But let's talk through the rules and what our end goals are here and I think we'll end up with answers before this section's done.

First off, the game itself is like a scaled down Boggle. Except that instead of shaking a container of letters and then trying to make words from that, you're given just a few letters and then must guess the words which set of words you can make from those are hidden on the page in front of you. The game has a lot of it's own unique rules with additional items that do things like reveal letters or similar, but I never use them and so my version of this game won't either.

We can plan to work on a limited set of words at first while we prep, and while I was thinking about this, I think that the hardest part of all of this is going to be the button interactions to make a nice feeling drag to select type deal for letter to letter selection. The second hardest part will be game generation, but I think I have a plan for that already, so we'll get to that when I get to that section 1.

The itch to make the game was motivated by the annoying ads, but also by the fact that creating a draggable word select from a group of letters seems like an interesting problem to solve. If what I'm putting in words doesn't make sense, consider my crappy paint diagram here:

When tapped the button is active and a line is drawn to the press point as its dragged, letting you select other letters to create a word

Let's pretend that ABC is a word. To construct it, you tap the A button and hold your mouse/finger down. Then dragging your finger over has some variety of line to indicate the path you're making, and then as you touch the other buttons it connects them with a line and then starts a new one to your finger as you go. Once you release, the letters are combined (in order) and checked to see if they match the word(s) you're trying to guess. A pretty intuitive and straightforward interaction, but one which is interesting to me to think about.

After all, we didn't really have to deal with this sort of multi-button state when we created a match 3 game in the past, since all the buttons in that project were basic click and release, with the behavior primarily confined to just the button itself 2. So that should pose something interesting to figure out.

Lastly, we have to decide what to do this in. Do we make a desktop / mobile app using LibGDX and Java? Do we use loosey goosey Javascript and an HTML5 canvas or similar to make the game be on this site itself? Do we use TypeScript rather than Javascript? Do we throw out any hope of trying to get this done in a reasonable amount of time and use Rust?

Xenoblade Chronicles X says it all for me. Let me think about it in the shower for a minute

For the sake of making it easily accessible, and potentially playable by everyone reading this post, let's do it in a web first language. For the sake of my sanity, let's do it in sigh Javascript 3. And if we get a good prototype working and decide that we need to swap languages later we can do that then and there. But I think that working in HTML for our FE and Javascript for the actual game logic should actually make this experiment relatively quick to start working on.

So let's get started.

Our game's skeleton

Before we dive into those cool buttons, or how we're going to generate the words for the user to guess. Let's setup the HTML page. I initially was thinking I'd just use plain HTML and then use the CSS transform: skewY() rotate() features to place the button elements in a circle, so I setup a neopolitan icecream inspired looking page like so:

Messages and encouragements here

I was pretty happy with it until I realized that as far as drawing a line from button to button goes, I'd probably be out of luck. So, while this HTML felt simple enough to work with as a prototype, I should probably swap to using a canvas now. So, a basic canvas snippet and some tweaks later, I had a starting point:

Or almost. The code to display the boxes was simple enough, deciding to use a font size of 48px meant that I wanted some extra padding and such, so I went with boxes of 50px by 50px and then just looped to draw the boxes with a bit of padding:

const canvas = document.getElementById("game1");
const ctx = canvas.getContext("2d");
const padding = 10;
const width = 450;
const height = 800;
const letter_background_color =  'rgb(200 200 200 / 50%)';
const word_row_start = padding * 2;
const letter_box_height = 50;
const letter_box_width = 50;
const input_area_start = word_row_start + letter_box_height * 7 + padding * 7 + padding * 2;
for (let i = 0; i < words.length; i++) {
  const word = words[i];
  const y = word_row_start + letter_box_height * i + i * padding;

  for (let j = 0; j < word.length; j++) {
      const x_offset = word_x + letter_box_width * j + j * padding;
      
      ctx.fillRect(word_x + x_offset, y, letter_box_width, letter_box_height);
      // Just eyeballing and fiddling to show the letter nicely
      ctx.fillText(word[j], word_x + x_offset + 4, y + letter_box_height - 4);
  }
}

But displaying the letters in a circle was off. At first, I tried to do a bit of a hack with the math. Thinking that maybe I just needed to offset things when I was to the left of the origin point of the circle:

ctx.fillStyle = 'red';
const origin_y = input_area_start + letter_box_width * 3;
const origin_x = width / 2;
ctx.beginPath();
ctx.arc(origin_x, origin_y, letter_box_width * 3, 0, 2 * Math.PI);
ctx.stroke();
const number_of_letters = letters.length;
const radians_per_letter = (2 * Math.PI) / number_of_letters;
for (let i = 0; i < letters.length; i ++) {
    const letter = letters[i];
    const x = Math.cos(radians_per_letter * (i + 1)) * letter_box_width * 2;
    const y = Math.sin(radians_per_letter * (i + 1)) * letter_box_width * 2;
    const left_side = x < 0;
    ctx.fillText(letter, origin_x + x - (left_side ? letter_box_width / 2 : 0), origin_y + y);
}

But this still looked bad.

And then, I remembered that we were using CSS properties in other parts, like the definition of the font and colors. So... does the context support drawing the letters from a placement that isn't the left side of the x and y that I give it? Yes, textAlign works and so does textBaseline

And while it still feels a little bit funny, it looks a lot better. Here's the code rendering the canvas beneath this code block:

const canvas = document.getElementById("sample3-canvas");
const ctx = canvas.getContext('2d');

function drawLetterCircleAt(x, y, letters) {
  if (!ctx) {
    console.log('Cannot draw example, canvas not supported');
    return;
  }

  ctx.fillStyle = 'lightblue';
  ctx.beginPath();
  ctx.arc(x, y, 120, 0, 2 * Math.PI);
  ctx.stroke();
  ctx.fill();

  ctx.fillStyle = 'black';
  ctx.font = "48px serif";
  ctx.textAlign = "center";
  ctx.textBaseline = "middle";
  const number_of_letters = letters.length;
  const radians_per_letter = (2 * Math.PI) / number_of_letters;
  for (let i = 0; i < letters.length; i ++) {
      const letter = letters[i];
      const lx = x + Math.cos(radians_per_letter * i) * letter_box_width * 2;
      const ly = y + Math.sin(radians_per_letter * i) * letter_box_width * 2;
      ctx.fillText(letter, lx, ly);
  }
}
drawLetterCircleAt(150, 150, 'PIZZA');
drawLetterCircleAt(430, 150, 'CODING');
drawLetterCircleAt(720, 150, 'FLEXBOX');

And when, taken as a whole and put back into our game program, I think we're at the point where we can start thinking about the thing that got me interested in this in the first place.

So, let's move along and...

Let's make some buttons

So, we can place letters around the circle, but can we place a button with a letter? Well, luckily for you and me, MDN has some very good documentation and some helpful examples. Their "mouse following animation" in particular seems very handy since it gives us a pattern on how to track the mouse and use it when requesting an animation frame be drawn to the canvas.

const cursor = {
    x: 0,
    y: 0
};
        
addEventListener("mousemove", (e) => {
    cursor.x = e.clientX;
    cursor.y = e.clientY;
});
        
addEventListener("touchmove", (e) => {
    e.preventDefault();
    cursor.x = e.touches[0].clientX;
    cursor.y = e.touches[0].clientY;
    },
    { passive: false },
);

the only problem with this is that the x and y are not relative to the canvas, but rather to the entire window. And since my game area is centered on the screen, if I console log the values out as I move myself around and to the left edges of the window:

The values are offset by the canvas's position. So, this is an easily fixable problem, we'll just subtract those offsets away from the current mouse value and that should work out!

const canvas = document.getElementById("game");
const offsetLeft = canvas.offsetLeft;
const offsetTop = canvas.offsetTop;
const ctx = canvas.getContext("2d");
ctx.save();

addEventListener("mousemove", (e) => {
    cursor.x = e.clientX - offsetLeft;
    cursor.y = e.clientY - offsetTop;
});

addEventListener("touchmove", (e) => {
    e.preventDefault();
    cursor.x = e.touches[0].clientX - offsetLeft;
    cursor.y = e.touches[0].clientY - offsetTop;
    },
    { passive: false },
);

Alright, so if we've got the mouse coordinates, now we just need to track out buttons and their states to do any sort of highlight on hover type situation. I don't really love that we're basically doing an immediate mode gui where everything is all drawn in one big function. I'd like to try to separate things out a little bit so that I can reason about the smaller parts within their own confined space. Rather than draw_static_shapes I'd like to instead set up the static shapes, and then pass a context and call a draw method on each "shape" I've made. I think this will put us into the position where we can do an .update(timestamp) call for each, which will lend itself well later on to animating and gamefeel being separated from any sort of game logic.

Luckily for us, MDN's advanced animation tutorial shows us how they like to do it:

const ball = {
  x: 100,
  y: 100,
  radius: 25,
  color: "blue",
  draw() {
    ctx.beginPath();
    ctx.arc(this.x, this.y, this.radius, 0, Math.PI * 2, true);
    ctx.closePath();
    ctx.fillStyle = this.color;
    ctx.fill();
  },
};

And I am happy to re-use a good idea! I think we've got two basic objects then, the word and the letter button. So let's refactor our existing code to set those up. First up, we'll create a class since Javascript supports those nowadays:

class WordRow {
    constructor(x, y, word) {
        this.x = x;
        this.y = y;
        this.word = word;
    }
        
    draw(ctx) {
        ctx.save();
        ctx.fillStyle = letter_background_color;
        ctx.strokeStyle = letter_color;
        
        for (let j = 0; j < this.word.length; j++) {
            const x_offset = this.x + letter_box_width * j + j * padding;
            ctx.fillRect(this.x + x_offset, this.y, letter_box_width, letter_box_height);
        }
        ctx.restore();
    }
}

Which is basically the same code as before, just with word_x and y replaced by this.x and this.y. We're still using a heavy amount of globals, but we'll tweak those to be more obvious once we've refactored more. Something simple like making them all capitalized will probably be a pleasant visual cue. Anyway. The loop where we set these up within the draw_static_shapes method is easily updated:

for (let i = 0; i < words.length; i++) {
    const word = words[i];
    const y = word_row_start + letter_box_height * i + i * padding;
    const wordRow = new WordRow(word_x, y, word);
    wordRow.draw(ctx);
}

So let's do the other one now. And while we're at it, we'll make the letters have a background color behind them as well, in the shape of a circle for now, but maybe we'll mix it up to a nonagon or something fun later. Just like before, we basically replace the x and y we calculated previous with a this.foo

class LetterButton {
    constructor(x, y, letter) {
        this.x = x;
        this.y = y;
        this.letter = letter;
    }
        
    draw(ctx) {
        ctx.save();
        ctx.fillStyle = 'lightcyan';
        ctx.font = "48px serif";
        ctx.strokeStyle = 'lightyellow';
        ctx.beginPath();
        ctx.arc(this.x, this.y, (letter_box_width + 8) / 2, 0, Math.PI * 2);
        ctx.fill();
        ctx.stroke();
        
        ctx.fillStyle = 'black';
        ctx.textAlign = "center";
        ctx.textBaseline = "middle";
        ctx.fillText(this.letter, this.x, this.y);
        ctx.restore();
    }
}

And the replacement within the loop happens naturally:

for (let i = 0; i < letters.length; i++) {
    const letter = letters[i];
    const x = origin_x + Math.cos(radians_per_letter * i) * letter_box_width * 2;
    const y = origin_y + Math.sin(radians_per_letter * i) * letter_box_width * 2;
    const letterButton = new LetterButton(x, y, letter);
    letterButton.draw(ctx);
}

We haven't gained anything, yet. But it still renders:

And our use of ctx.save() and ctx.restore() means that we can fiddle with the properties within each draw command as much as we like without negatively impacting the others. In the previous version, we had a bit of a cascade going on where the fillStyle and the friends were set and used by other parts. This is all well and good, but also an easy way to accidently make something weird happen if we're not careful. The examples on MDN imply (to me at least) that these are relatively cheap operations. So I'm using them!

Let's advance our refactoring a bit more and lift up the creation of the big circle with the letter buttons inside of it into a class. The reason for this is simple: I want to think about and track the state of all of those buttons in a unified way. After all, drawing a line between each button will be easier if we're doing it from the context of an observer at that level, right?

class LetterSelect {
    constructor(x, y, letters) {
        this.x = x;
        this.y = y;
        this.letters = letters;
        this.buttons = [];
        const number_of_letters = letters.length;
        const radians_per_letter = (2 * Math.PI) / number_of_letters;
        for (let i = 0; i < letters.length; i++) {
            const letter = letters[i];
            const lx = x + Math.cos(radians_per_letter * i) * letter_box_width * 2;
            const ly = y + Math.sin(radians_per_letter * i) * letter_box_width * 2;
            const letterButton = new LetterButton(lx, ly, letter);
            this.buttons.push(letterButton);
        }
    }
        
    draw(ctx) {
        ctx.save();
        ctx.beginPath();
        ctx.fillStyle = 'lightblue';
        ctx.strokeStyle = 'lightyellow';
        ctx.arc(this.x, this.y, letter_box_width * 3, 0, 2 * Math.PI);
        ctx.fill();
        ctx.stroke();
        ctx.restore();
        for(let i = 0; i < this.buttons.length; i++) {
            this.buttons[i].draw(ctx);
        }
    }
}

And then update the call site:

function draw_static_shapes(ctx) {    
    const letters = letters_used();
    const words = game_words(letters);
    const word_x = padding;
        
    // Create boxes, one for each letter in a word, show one word per row
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        const y = word_row_start + letter_box_height * i + i * padding;
        const wordRow = new WordRow(word_x, y, word);
        wordRow.draw(ctx);
    }
        
    // Draw the input area, which should be big enough to hold 3 - 7 letters
    const origin_y = input_area_start + letter_box_width * 3;
    const origin_x = width / 2;
    const letterSelections = new LetterSelect(origin_x, origin_y, letters);
    letterSelections.draw(ctx);
}

Cool. Let's invert this now and instead of creating and calculating every time, let's setup them up once, and then add them to a list of things that we need to have drawn on the screen. For lack of a better word, let's just call these entities.

const entities = [];

This list is useless unless we're using it for something of course, so we can do just that like so

function draw_entities(ctx) {    
    entities.forEach((e) => e.draw(ctx));
}

And then rename our method draw_static_shapes to setup_entities and replace any call to .draw with a push onto the list of things to be drawn.

function setup_entities() {    
    const letters = letters_used();
    const words = game_words(letters);
    const word_x = padding;
        
    // Create boxes, one for each letter in a word, show one word per row
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        const y = word_row_start + letter_box_height * i + i * padding;
        const wordRow = new WordRow(word_x, y, word);
        entities.push(wordRow);
    }
        
    // Draw the input area, which should be big enough to hold 3 - 7 letters
    const origin_y = input_area_start + letter_box_width * 3;
    const origin_x = width / 2;
    const letterSelections = new LetterSelect(origin_x, origin_y, letters);
    entities.push(letterSelections);
}

Now all we have to do is only call the draw method from the function being called by the requestAnimationFrame and call our setup method once before we do any of that! Easy.

function draw() {
    if (!ctx) {
        console.log('No canvas found?')
        return;
    }
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    ctx.save();
    draw_entities(ctx);
    ctx.restore();
    requestAnimationFrame(draw);
}

setup_entities();
window.addEventListener("load", draw);

Okay. Refactoring done, let's take advantage of this finally to start adding some logical state into the buttons to make them react to the mouse. Let's say that if the mouse hovers over the button and it's not already selected, we'll put it into a hover state and change its color. We can probably think ahead here and think of this as a finite state machine:

StateActionNext State
IdleMouse within boundaryHover
HoverMouse not in boundaryIdle
HoverMouse clicked / touch downActivated
ActivatedMouse released (within or not)Idle
ActivatedDragging (within or not)Activated

How should we propagate the mouse events? Well. Javascript in your browser is single threaded as far as I know. So, let's just enjoy global state while we can! Let's update our cursor object from before to track whether or not the mouse is clicked or not.

const CLICK_STATE = {
    UP: 0,
    DOWN: 1
};
const cursor = {
    x: 0,
    y: 0,
    click: CLICK_STATE.UP
};
addEventListener("mousedown", (e) => {
    cursor.click = CLICK_STATE.DOWN;
});
addEventListener("mouseup", (e) => {
    cursor.click = CLICK_STATE.UP;
})

And then we can add an update method to our two classes that care about buttons. First the simpler of the two:

class LetterSelect {
  ...
  update(mx, my, click) {
      for (let i = 0; i < this.buttons.length; i++) {
          this.buttons[i].update(mx, my, click);
      }
  }
}

And then we can translate our state machine table from before into code for the actual button. We can use a switch or a bunch of if else clauses. I wish we had pattern matching, but anyway, today's mood was avoiding writing break three times:

class LetterButton {
  ...
  update(mx, my, click) {
      if (this.state === BUTTON_STATE.IDLE) {
          if (this.within(mx, my)) {
              this.state = BUTTON_STATE.HOVER;
          }
      } else if (this.state === BUTTON_STATE.HOVER) {
          if (!this.within(mx, my)) {
              this.state = BUTTON_STATE.IDLE;
          } else if (click === CLICK_STATE.DOWN) {
              this.state = BUTTON_STATE.ACTIVATED;
          }
      } else if (this.state === BUTTON_STATE.ACTIVATED) {
          if (click == CLICK_STATE.UP) {
              // TODO: emit an event.
              this.state = BUTTON_STATE.IDLE;
          }
      }
  }

  within(mx, my) {
      if (this.x - this.radius <= mx && mx <= this.x + this.radius) {
          if (this.y - this.radius <= my && my <= this.y + this.radius) {
              return true;
          }
      }
      return false;
  }

Of course, this won't do anything until we do two things. One, actually call the update method.

function update_entities() {
    entities.forEach((e) => {
        if (e.update) {
            e.update(cursor.x, cursor.y, cursor.click);
        }
    })
}

function draw() {
    ...
    update_entities();
    draw_entities(ctx);
    ...
}

And two, make something actually change depending on the state! In this case, let's start simple and tweak the button background color. We can setup a map to not have to repeat our else if from before and make things a bit easier to read and configure. Then in the draw method, just do a quick lookup:

class LetterButton {
    constructor(x, y, letter) {
        ...
        this.state = BUTTON_STATE.IDLE;
        this.state_color = {};
        this.state_color[BUTTON_STATE.IDLE] = 'lightcyan';
        this.state_color[BUTTON_STATE.HOVER] = 'cyan';
        this.state_color[BUTTON_STATE.ACTIVATED] = 'blue';
    }

    draw(ctx) {
        ...
        ctx.fillStyle = this.state_color[this.state];
        ctx.font = "48px serif";
        ...
    }
}

With both of these in place if I move my mouse over a letter while not clicking it will turn cyan, and if I'm clicking then it will transition quickly over to the activated blue.

Is it pretty? No. But it doesn't have to be to prove a concept is working. So let's do the next thing! Let's draw a line from the last activated button to the mouse cursor, as well as draw a line between each button that's been activated so far. In order to do this, we'll need to keep track of which buttons were activated when, and in case my TODO from before wasn't obvious, we're going to do this with an application of an observer style pattern.

Javascripts loosey goosey type system makes this pretty painless, and since the scope of our game is small, I don't really have any contentions about tying our two implementations very closely together:

class LetterButton {
  constructor(...) {
    this.subscribers = [];
  }

  subscribe(caller) {
      this.subscribers.push(caller);
  }
  ...
  update(mx, my, click) {
    if (this.state === BUTTON_STATE.IDLE) {
        if (this.within(mx, my)) {
            this.state = BUTTON_STATE.HOVER;
        }
    } else if (this.state === BUTTON_STATE.HOVER) {
        if (!this.within(mx, my)) {
            this.state = BUTTON_STATE.IDLE;
        } else if (click === CLICK_STATE.DOWN) {
            this.notify('activated', this);
            this.state = BUTTON_STATE.ACTIVATED;
        }
    } else if (this.state === BUTTON_STATE.ACTIVATED) {
        if (click == CLICK_STATE.UP) {
            this.state = BUTTON_STATE.IDLE;
            this.notify('released', this);
        }
    }
  }

  notify(event) {
    for (let i = 0; i < this.subscribers.length; i++) {
        this.subscribers[i].on_button(event, this);
    }
  }
}
...
class LetterSelect {
  ...
  constructor(...) {
    ...
    const letterButton = new LetterButton(lx, ly, letter);
    letterButton.subscribe(this);
    ...
  }
  on_button(name, button) {
      console.log(name, button);
  }
}

For now we'll just log and confirm it works as expected. Once we're sure, we can go ahead and build up a stack, as well as put some more meat on the LetterSelect's update method itself. Since we can see when things are activated, we should be able to build up a list of points to draw using the x and y of each button. So, updating the on_button method for LetterSelect

...
constructor(...) {
  ...
  this.active_buttons = [];
  this.check_words = false;
}

on_button(name, button) {
  if (name === 'activated') {
      this.active_buttons.push(button);
  }
  if (name === 'released') {
      this.check_words = true;
  } else {
      this.check_words = false;
  }
}
...

We can start to track the buttons that are pushed down so far. That second if statement we could rewrite as this.check_words = name === 'released'; but personally I like the explicit branches more than saving space here. If you find it more readable the other way, go for it though.

Now, we're not clearing out the active buttons yet, so we need to make sure we actually do that too or else we'll end up with a huge list after we match more than a few words. The right place to do this is within the update method:

update(mx, my, click) {
    for (let i = 0; i < this.buttons.length; i++) {
        this.buttons[i].update(mx, my, click);
    }
    if (this.check_words) {
        // TODO Emit the word!
        console.log(this.active_buttons.map((b) => b.letter));
        this.active_buttons.length = 0;
        this.check_words = false;
    }
}

For now, we can just console.log the list of letters to see that things are working as expected.

And since we reset the length of the array to 0 and our check_words to false, we're able to do this only once per release of the mouse button. Using our list of active buttons, we can update the draw method now and get what I wanted all along:

                draw(ctx) {
                    ctx.save();
                    ctx.beginPath();
                    ctx.fillStyle = 'lightblue';
                    ctx.strokeStyle = 'lightyellow';
                    ctx.arc(this.x, this.y, letter_box_width * 3, 0, 2 * Math.PI);
                    ctx.fill();
                    ctx.stroke();                
                    for(let i = 0; i < this.buttons.length; i++) {
                        this.buttons[i].draw(ctx);
                    }
                    ctx.beginPath();
                    for (let i = 0; i < this.active_buttons.length; i++) {
                        const btn = this.active_buttons[i];
                        if (i === 0) {
                            ctx.moveTo(btn.x, btn.y);
                        }
                        ctx.lineTo(btn.x, btn.y);
                    }
                    ctx.lineTo(cursor.x, cursor.y);
                    ctx.stroke();
                    ctx.restore();
                }
            

Luckily, the context for the canvas has the handy lineTo method and the moveTo method for us to start the path at the first button, then finish it at whatever our current cursor location is.

The last thing we need to do is actually do something with the result of the selection.

Matching words

Now that a user can select the letters for a word, we just need to check it against the list of possible options and then display a match if so. If there isn't a match, we can probably emit an event for some future polishing. We just want the basics of the game working first, then we can add in better visuals, animations, and things to enhance the game feel after.

For now, let's replace our TODO from before with a notification to the row of words entity. We can notify each of the rows, and if there's a match they can do decide to do something about it. If we were to break this out in a similar way to the buttons. We could say that there's a really simple state machine here.

StateActionNext State
IdleNo MatchIdle
IdleMatchMatched
MatchedAnyMatched

I think that even though the system is so simple, it's worth thinking about it this way. Primarily because when we do get around to adding polish, if we need a transitory state to be in while doing any sort of animation or similar effect, then it'll make that just that much easier. Anyway, let's implement this shall we? First off, wire up a new method to pass the information along and add in a stub for the landing place for those events:

class WordRow {
  ...
  on_select(name, word) {
      console.log(name, word === this.word);
  }
}
...
class LetterSelect {
  constructor(...) {
    ...
    this.subscribers = [];
  }

  subscribe(caller) {
    this.subscribers.push(caller);
  }

  update(mx, my, click) {
    for (let i = 0; i < this.buttons.length; i++) {
        this.buttons[i].update(mx, my, click);
    }
    if (this.check_words) {
        const word = this.active_buttons.map((b) => b.letter).join('');
        for (let i = 0; i < this.subscribers.length; i++) {
            this.subscribers[i].on_select('selected', word);
        }
        
        this.active_buttons.length = 0;
        this.check_words = false;
    }
  }
}
...

Then, let's update our setup method to construct the LetterSelect first, so that we can refer to it when setting up the row objects:

function setup_entities() {    
    const letters = letters_used();
    const words = game_words(letters);
    const word_x = padding;
        
    // Input area
    const origin_y = input_area_start + letter_box_width * 3;
    const origin_x = width / 2;
    const letterSelections = new LetterSelect(origin_x, origin_y, letters);
    entities.push(letterSelections);
        
    // Create word rows
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        const y = word_row_start + letter_box_height * i + i * padding;
        const wordRow = new WordRow(word_x, y, word);
        letterSelections.subscribe(wordRow);
        entities.push(wordRow);
    }
}

This is enough to see we're on the right track:

So next, let's implement that state machine we outlined before:

const ROW_STATE = {
    IDLE: 0,
    MATCHED: 1
};

class WordRow {
    constructor(x, y, word) {
        ...
        this.state = ROW_STATE.IDLE;
    }
        
    on_select(name, word) {
        if (name !== 'selected') {
            return;
        }
        const isMatch = word === this.word;
        if (this.state === ROW_STATE.IDLE) {
            if (isMatch) {
                this.state = ROW_STATE.MATCHED;
            }
        } else if (this.state === ROW_STATE.MATCHED) {
            // Do nothing for now.
        }
    }
}

And just like with the buttons, we can now use the state of our object to modify the way the draw method behaves. In the case of the row, we want to show people the actual word if they've managed to find it:

draw(ctx) {
    ...
    const shouldDisplayLetters = this.state === ROW_STATE.MATCHED;
    for (let j = 0; j < this.word.length; j++) {
        const x_offset = this.x + letter_box_width * j + j * padding;
        ctx.fillRect(this.x + x_offset, this.y, letter_box_width, letter_box_height);
        const half_width = letter_box_width / 2;
        const half_height = letter_box_height / 2;
        if (shouldDisplayLetters) {
            const letter = this.word[j];
            ctx.save();
            ctx.fillStyle = 'black';
            ctx.font = "48px serif";
            ctx.textAlign = 'center';
            ctx.textBaseline = 'middle';
            const x = this.x + x_offset + half_width;
            const y = this.y + half_height;
            ctx.fillText(letter, x, y, letter_box_width);
            ctx.restore();
        }
    }
    ctx.restore();
}

And doing a few more matchs we can see it's working:

Note that there aren't any six or seven letter words that you can make with five selectable letters. I just have 7 slots in the listing because I was making sure the UI looked ok like that. This is good, but how do we know when the game is over?

Well, the game would be over once we've found all possible words we've selected from a potential list. We'll save the generation of the initial game state to the next section, but we can wrap up this section with the method we'll use to track if every word has been found or not. If you guessed observe it, then you'd be right.

class WordRow {
    constructor(x, y, word) {
        ...
        this.subscribers = [];
    }
    ...
    subscribe(caller) {
        this.subscribers.push(caller);
    }

    on_select(name, word) {
        ...
        if (this.state === ROW_STATE.IDLE) {
            if (isMatch) {
                this.state = ROW_STATE.MATCHED;
                for (let i = 0; i < this.subscribers.length; i++) {
                    this.subscribers[i].on_match('matched', this.word);
                }
            }
        }
        ...
    }
}
            

But, what's going to actually listen to this? We're out of objects! Well, let's make a new one to keep trackof which words we started with and which ones we have so far. Once those two lists are the same size, then we should be able to indicate to the game loop that the game is over. I don't have any particularly creative names for this object, so let's just call it GameState:

class GameState {
    constructor(words) {
        this.words_to_find = words;
        this.found_words = new Set();
    }

    is_game_done() {
        return this.words_to_find.length === this.found_words.size;
    }

    on_match(name, word) {
        if (name !== 'matched') {
            return;
        }

        if (this.words_to_find.includes(word)) {
            this.found_words.add(word);
        }
    }
}
            

Then wiring it up to where we create the word rows:

function setup_entities() {    
    const letters = letters_used();
    const words = game_words(letters);
    gameState = new GameState(words);
    ...
    for (let i = 0; i < words.length; i++) {
        ...
        const wordRow = new WordRow(word_x, y, word);
        wordRow.subscribe(gameState);
        letterSelections.subscribe(wordRow);
        entities.push(wordRow);
    }
    ...
}

And this gameState needs to be used in our main game loop that requestAnimationFrame is calling, so we declared it near the top with the rest of the global level variables.

    // Lets' rename draw to game_loop
    function game_loop() {
        if (!ctx) {
            console.log('No canvas found?')
            return;
        }
        ctx.clearRect(0, 0, canvas.width, canvas.height);
        update_entities();
        if (gameState.is_game_done()) {
            console.log('Game complete');
            // TODO: New game and whatnot
            ctx.font = '48px Impact';
            ctx.fillText('You win', canvas.width / 2, canvas.height / 2);
            return;
        }
        draw_entities(ctx);
        requestAnimationFrame(game_loop);
    }

And if I remove my extra rows we can't actually clear and play the game:

Like I said before. We'll polish this later. Giving some sort of user feedback when they enter a word that's correct, but not one of the words they should be guessing is a big one. Some sort of animation for when we get a successful match and the words appear in the word row. Sound effects, maybe some background imagery or similar? There's plenty. But the most important thing we need to deal with right now is the fact that you can only play one round.

The forest and the Tries

So, obviously, we could wrack our brains and think of a bunch of words, play the "game" ourselves and see which words exist within the ones we picked and put those together...

But why do manual work when we can get the computer to do it for us? I've got a great idea 4. Let's trie using a Trie for this! 5. If you're unfamiliar, a trie is a pretty neat data structure one can use to efficiently query if a string of characters make up a word or not.

Sounds pretty perfect right? Even better, they're extremely easy to implement. As far as building a Trie goes, the code is extremely minimal:

class TrieNode {
    constructor() {
        this.isTerminal = false;
        this.children = {};
    }

    // returns true or false if word has been inserted (and is new)
    insert(prefix) {
        if (!prefix || prefix.length === 0) {
            // Don't think need to call this a terminal either.
            return false;
        }
        
        let tmp = this;
        for (let i = 0; i < prefix.length; i++) {
            const char = prefix[i];
            if (!tmp.children[char]) {
                tmp.children[char] = new TrieNode();
            }
            tmp = tmp.children[char];
        }

        if (tmp.isTerminal) {
            // No insert.
            return false;
        } else {
            tmp.isTerminal = true;
            return true;
        }
    }
  }

That's it. Really. I'll explain in a sec, but a picture is worth a thousand words:

a picture of a TrieNode in the debugger showing the full path of hello

As you can see, we've got a tree structure. Each letter in a word acts as the edge between two nodes, with a marker to indicate whether or not a given node terminates a word. This is maybe easier to see with a different set of insertions:

trie node expanded to show branching paths for words with the same prefix

As you can see, the tree is the same for t and h, but then we have two children for h, both e and y. You can see that y is a terminal, and so is e since we had the words "thy" and "the" in our list. Even though the e is a terminal node for a word, it still has children because each of those share the prefix up to that point.

Code-wise, the only thing of interest at all in the insert method is the walking of the tree using the tmp variable.

let tmp = this;
for (let i = 0; i < prefix.length; i++) {
    const char = prefix[i];
    if (!tmp.children[char]) {
        tmp.children[char] = new TrieNode();
    }
    tmp = tmp.children[char];
}

Rather than recursively insert, it's a little bit easier (in my mind) to iterate instead. If we didn't, we'd be slicing up a string by one character every single time we recursed. Which is fine but getting the terminal at the end is sort of awkward in recursion. If you were to exhaust the string as you go, then return a true/false, you'd be updating the terminal field on the second to last call. You could check for a length of 1 character left, but I don't know. Something about it just doesn't feel as reasonable to me as approaching this not by the nodes of a tree being recursed, but rather, iterating over the word we care about and following and creating the path as we go with tmp.

Maybe next week I'll change my mind.

thinking deeply about computers

Anyway. So, we can create a Trie. And assumedly it shouldn't be too difficult to find an online dictionary of some kind with a bunch of words and load it up. But how do we use it to generate rounds for the game? Let's consider what a tree looks like if we've put in a few words that share letters:

a Trie with f for terminal and t for terminal nodes with each edge marked with a letter.

There's quite a few words here just from five letters. If you were to walk this Trie and collect all the letters you'd see that we've got a, b, e, k, and r. Simply walking the nodes isn't enough, we need to collect when the node indicates that we're at a terminal. Obviously, as a product of the Trie's construction, every leaf node is a terminal, but what about when we see one along the path?

If we were to flip a coin, then we could construct a simple method to get a random word out like this:

randomWord() {
    const chooseChild = (child) => {
        let letters = Object.keys(child.children);
        let randomKey = letters[Math.floor(Math.random() * letters.length)]; 
        let tmp = child.children[randomKey];
        return { child: tmp, character: randomKey };
    }
    
    let { child, character }  = chooseChild(this);
    if (!child) {
        return '';
    }

    if (child.isTerminal && child.children.length == 0) {
        return character;
    }


    if (child.isTerminal) {
        const coinFlip = Math.random() < 0.5;
        if (coinFlip) {
            return character;
        }   
    }

    return character + child.randomWord();
}

For the sake of making our conditional logic simpler, we've got a helper method to randomly select a letter from the current node we're on, and then return it and the node associated with it to the primary method. If we're at a leaf, then obviously we should finish up. But if we're in the middle somewhere, then we can go with a 50 50 shot on if we'll stop early or not.

This works well enough for selecting a random word, though I have some ideas about how we could improve it. Running it a few times shows that it works at least:

But selecting a bunch of words at random isn't going to work very well to build a list of words that share the same characters is it. I mean, sure, some vowels will probably show up twice and make our list of letters shorter, but if I ask you for two three letter words to guess and give you six letters, that's going to be more bothersome than if I handed you three or four letters. i,p,t,a as the letters would give you words like pit, tip, tap, pat simply enough. While abceit is going to give you a ton of options and lead to a lot of rejections if I'm only asking you to guess ace and bit. I think that generally speaking, to have an enjoyable round of our game, we want to keep the letters minimal to make it easy to guess some words, while occasionally mixing in something more intriguing.

So. How do we get words that share the same letters out of the Trie? Well, the simplest thing of course would be to walk down, then collect up. Right? Go to a leaf. Then as we undo our recursive descent, check for terminals along the way and snag them. Or. Given that we've been doing an iterative approach to walking the list so far, we could collect them as we go like this if we know which word to start with:

collectWordsOnPath(word, max) {
    if (!word) {
        return [];
    }

    let collected = [];
    let tmp = this;
    let wordInProgress = [];
    for (let i = 0; i < word.length && collected.length < max; i++) {
        const char = word[i];
        if (!tmp.children[char]) {
            return collected;   
        }

        wordInProgress.push(char);
        tmp = tmp.children[char]; 
        if (tmp.isTerminal && collected.length < max) {
            collected.push(wordInProgress.join(''));
        }
    }
    return collected;                        
}

But while this works, I don't think it's quite as good as us poking around like a mouse in a maze sniffing out cheese. Which is to say, I feel like we should flip coins and combine both this, and the random work collection, to take random paths as we walk downwards, and collect things from more than one path at a team. I'm thinking something like this in pseudo code:

For min and max length of desired words
Walk tree down and collect prefixes until we reach a terminal that satisfies our constraints.
Select the current prefix as a word, and flip a coin on its children to follow.
Repeat the process of walking down and selecting until we reach the max depth
Or end the process if we only wanted a certain number of words.

The hard part of this, to me at least, is that the letters of the trie are stored in the edge. Not in the node itself, which means that keeping track of each prefix as we go down seems like bookkeeping that the caller sort of needs to be ready for. It's not that much complexity, but it is unfamiliar in comparison to an N-ary tree. So it took a bit longer to puzzle out the code to do this. But, I did:

collectRandomSimilarWords(minLength, maxLength, maxCount) {
    const stack = [[this, '']];
    let collected = [];

    const coinFlip = () => (Math.random() < 0.5);

    while(stack.length && collected.length < maxCount) {
        const [node, prefix] = stack.pop();
        // If this is a terminal and within constraints, consider adding it.
        if (node.isTerminal && minLength <= prefix.length && prefix.length < maxLength) {
            if (coinFlip() || collected.length === 0) {
                collected.push(prefix);
            }
        }
        // Regardless, continue the traversal.
        const letters = Object.keys(node.children);
        for (let i = 0; i < letters.length; i++) {
            const newPrefix = prefix + letters[i];
            // If we're not even at the min length yet, follow all paths
            if (prefix.length < minLength) {
                stack.push([node.children[letters[i]], newPrefix]);
            // otherwise flip a coin if we'll follow the path or not.
            } else if (coinFlip()) {
                stack.push([node.children[letters[i]], newPrefix]);
            }
        }
    }
    return collected;
}

Javascript lacks tuples 6, so I'm just using a simple array to compensate. The destructuring syntax const [a,b] = c is nice to use. Though if it's your first time seeing it, it can feel a bit odd. Especially if one renames the variable or assigns a default in a nested way. But anyway. The code is pretty small, so not too hard to understand I think. We're doing an iterative search in order to easily maintain a list of collected words, and rather than doing breadth first search (via a Queue) we're using a stack to do depth first search. This way, we'll bias ourselves towards filling up the collection list with deeper words in the Trie rather than shorter shallower words sharing less letters.

This works well enough to ensure that we've always got at least one word collected (assuming min length is met). But given that Object.keys is going to return the list of letters to us in ascending order each time, I feel like this biases us towards words at the start of the list. So to compensate, let's add randomness to each of the iterations of the children:

const letters = Object.keys(node.children);
letters.sort((a, b) => {
    coinFlip() ? 0 : coinFlip() ? -1 : 1;
});

I'm normally not a huge fan of ternary statements, let alone nested ones. But in a blog post I do value some degree of brevity. So I hope you'll excuse the mess. We simply flip a coin to decide if two keys are equal, if we land on tails, we flip another coin to see whether a is going to be considered less than b or not.

There are other ideas we could try, like making an A star search that weights towards or against paths based on the already collected prefixes. But, we can revisit that during the polishing section if we feel it needs work. For now, let's move along to generate the Trie with more than just a toy example to see how our current method works.

Loading a dictionary

Doing a quick search online for "dictionary list of words" found me a handy stackoverflow post here that then led me to this pretty handy website https://www.wordfrequency.info/. While is a paid dataset, luckily for us they have free samples! And their samples include 5000 words. That sounds like it should be pretty good for our purposes. So, checking out the sample pages I decided to grab the lemmas_60k_words sample because it included both the lemmas and the words associated with them.

You can read the page I linked, but a simple example is that the lemma do is the same for both does and doing because both of those are word forms derived from that lemma. Within the text file the first 8 rows can be skipped, and then it looks like the 6th column is the one I actually care about:

* Top 60,000 lemmas, with word forms for each lemma
* This sample data is taken from the one billion word Corpus of Contemporary American English (COCA)
(www.english-corpora.org/coca), which is the only corpus of English that is large, up-to-date, and is based on a wide range of genres.
* For complete word frequency data from COCA, please see https://www.wordfrequency.info
* For instructions on using this file in Excel, see https://www.wordfrequency.info/freqTxtToExcel.pdf
* For an explanation of the columns below, see https://www.wordfrequency.info/files.asp
----- Before converting file to Excel, remove the first eight lines, with the first line being the one starting with "rank"

lemRank	lemma	PoS	lemFreq	wordFreq	word
5	of	i	23159162	23159162	of
15	do	v	8186412	4501047	do
15	do	v	8186412	1889734	did
15	do	v	8186412	964997	does
15	do	v	8186412	461455	doing
15	do	v	8186412	356317	done
15	do	v	8186412	9657	doin            

Nothing a little bit of *nix tooling can't help. Luckily for me I've got git bash so it's easy enough to come up with the commands needed to quickly convert this into a list of just words:

cat lemmas_60k_words.txt | tail -n +10 | cut  -f 6 | sort > words.txt

Scrubbing through this listing, I noticed something:

a-lister
abandon
abandoned
abandoning
abandons
abashed
abatement
abatements
abbey
abbeys
abdicate
abdicated
abdicates

There's a lot of long words in this sample. So maybe this isn't the right sample set to use after all. I think if I were making a game that I wanted to charge money for, maybe I'd consider buying the full set and using it. But since this is just for fun, I'm not about to do that. Luckily, that stackoverflow post I mentioned linked more than one potential set!

Looking at the British set of words it seems we can get quite a few more potential options for our needs. So let's try loading one of these files up.

The format is: four fields, separated by spaces.
1: frequency
2: word
3: pos
4: number of files the word occurs in
For non-orthographic words, spaces are replaced by underscore, giving eg "in_spite_of".

Which sounds simple enough to parse with our tools again:

$ cat all.al.o5.txt | tail -n +1 | cut -d ' ' -f 2 | head
!!WHOLE_CORPUS
%
&aacute
&aacute;ngel
&aacute;ngel
&aacute;ngel
&aacute_la
&acirc
&aelig;lfgifu
&aelig;lfgifu

And we can see a new problem. We've got a whole bunch of stuff that is a "word" in the sense that it appears a bunch of times and is certainly a word that you'd read. But this doesn't really match with what I want. So instead, let's filter down the list to words that are just plain alphabetical words:

$ cat all.al.o5.txt | tail -n +1 | cut -d ' ' -f 2 | egrep "^[a-zA-Z]+$" | uniq > words.txt

And then I was left with a better list, but still one which had plenty of confusing things.

a
aa
aaa
aaaaa
aaaah
aaagh
aaah
aaas
aabida
aachen
aage
aagh
aagpc

I suppose the British lexacon does include the Wilhelm scream. But I wouldn't consider this a good word for our game at all. And as beautiful as Aachen is. It's also not something I'd consider game for our word finding fun. In general, I would say that most places and people should be ruled out. We could probably do some regex to remove words with repeated characters, but I have the feeling that it will take me as much time to look up the syntax to do lookahead/lookbehinds and craft an appropriate expression as it would for me to run it on this massive list.

So, rather than the full comprehensive list. Why don't we use the lemma list from this site instead? It seems a bit better than the other one as far as length of words goes:

5 2186369 a det
2107 4249 abandon v
5204 1110 abbey n
966 10468 ability n
321 30454 able a
6277 809 abnormal a
3862 1744 abolish v
5085 1154 abolition n
4341 1471 abortion n
179 52561 about adv
69 144554 about prep
3341 2139 above a
942 10719 above adv
786 12889 above prep

It's not perfect, but it feels better at least. And I was about to use it, before a thought struck me like a truck on a fine school day in the Japanese suburbs.

zombielandsaga clip of the main character before she becomes a zombie

Proper nouns out? Places out? Scrabble rules?! Scrabble! So I did a quick search and lo and behold someone had a nice gist of a bunch of words for use in scrabble. And just like that we've got a decent list of words to use. So now, all we have to do is load them up into the Trie! So, we'll need to tweak the calls to the setup_entities method, as well as remove the document load event and instead tie the startup of our game loop to the words being ready to be used:

const potentialWords = new TrieNode();
fetch("words.txt")
    .then((response) => response.text())
    .then((w) => { 
        window.words = w.split("\n");
        window.words.forEach((word) => {
            if (word.length >= 3) {
                potentialWords.insert(word)
            }
        })
        setup_entities();
        game_loop();
});

So once again, trying out our method to get random stuff to see if it feels like it'll work for our game generation:

strange z biased output that feels like a bug

While there is variety in some of the output, it seems very very biased towards Z words. Which is pretty strange. Looking through my code to get a random word, I became a bit suspect of the random ordering of the children for each level of the Trie. So, based on my hunch, I tried randomizing it further:

// Randomize the traversal order of the children to prevent ascension bias
const letters = Object.keys(node.children);
const randoSort = (a, b) => {
    return coinFlip() ? 0 : coinFlip() ? -1 : 1;
};
Array(10).fill(0).forEach(() => letters.sort(randoSort));

And this seemed to improve things a bit:

output after more randomization but still bug feeling

But it still felt like it wasn't enough. In fact, looking at the words returned by the method. They certainly shared an amount of similar letters. But it also felt like the total number of letters would always be more than I really wanted to have in the controls of the game. So maybe I was approaching my game generation wrong. So. I took a break to think.

The first idea that came to mind is to see if doing a breadth first search, rather than a depth first seach would provide better results. It's trivial to change stack.pop() to stack.shift() to do it.

results from random BFS traversals

But the results exhibit the behavior for why I picked DFS in the first place. We end up going too shallow, too often, and so we end up with a bunch of three letter words rather than a mix of one long word and a mix of words less than that. The reason I choose depth first search is because walking down to the depth that corresponds to the length of the word I want to be the maximum ensures that we get at least one of those. It's more interested when there's at least one 7 letter word I think.

My second idea was to weight the traversal of the tree and bias it in the direction of a given word. So rather than flipping a coin at each node to decide which key to follow next, we'd prefer selecting a key (still at random) from the list of letters in our given word. My intuition on this is that we'd end up constructing words with more shared pieces, but if we do this as we walk down the tree, perhaps BFS this time, then we'd end up with similar subsequences of the same letters within the same words.

For example, if we were biased towards the word lonely, then when we step down from l we'd be more likely to follow the path to end up at lone if we followed from l or alone if we started a walk from a. It wouldn't be guaranteed unless we wanted to try to force it. But it would be interesting to see if a sort of "reverse" walk specifically looking at letters we've already used could be useful for determining a good set of words for a round.

So, I was in the middle of implementing this, rather than whipping out the full A star algo, I realized I could just bias my randomized sort and probably achieve similar results:

// Randomize the traversal order of the children to prevent ascension bias from Object.keys
const letters = Object.keys(node.children);
const randoSort = (a, b) => {
    // Bias the front of the list to find more shared letter combinations
    if (biasWord.includes(a) || biasWord.includes(b)) {
        return -1;
    }
    return coinFlip() ? 0 : coinFlip() ? -1 : 1;
};
Array(10).fill(0).forEach(() => letters.sort(randoSort));

But then, looking at this code and how I would need to find a random word first. I asked myself another question. ”Why don't I just bias towards the current prefix?” and so I changed the sorting routine to be like this instead:

const randoSort = (a, b) => {
    // Bias the front of the list to find more shared letter combinations
    if (prefix && (prefix.includes(a) || prefix.includes(b))) {
        return -1;
    }
    return coinFlip() ? 0 : coinFlip() ? -1 : 1;
};

Running the method a few times felt like I was getting a healthier mix:

showing results of the biased walk

Though I was certainly not getting away from the similar prefixes, which makes sense given what we're doing. But if I wanted to be able to get our something like rake if I were finding break related words. Then I think we need to step up our game here (haha, pun) and do more than one method call when constructing our potential words. So, let's step up from our building blocks so far and compose them. Returning to some code we wrote a while ago:

function game_words(from_letters) {
    // TODO: we'll use a Trie.
    return [
        // 'MMMMMMM', // max of 7 letters seems good.
        // 'MMMMMM',
        'APPLE',
        'PALE',
        'LEAP',
        'APE',
        'ALE'
    ];
}
      
function letters_used() {
    return [
        'A','P', 'P', 'L', 'E', 
    ]
}

Let's actually do that TODO. game_words and letters_used are what the current setup code is using so it'd be nice to not break any of the contracts we established already, but it might be a bit awkward to not do that. After all, we have a bit of a chicken and egg situation if we try to solely restrict one... but then again. What if we did?

What if we add just one more helper method to our Trie and make it possible to fetch back terminals that match only a given set of letters? I'd been avoiding doing this becuase I was afraid of the combinatoric explosions, but how bad exactly is 7 factorially when you weight it against how many words actually exist with those possibilities? It's trivial to code to test...

restrictedWalk(minLength, maxLength, restrictedTo, maxCount) {
    const stack = [[this, '', restrictedTo]];
    const collected = [];

    while(stack.length && collected.length < maxCount) {
        const [node, prefix, lettersLeft] = stack.pop();
        // If this is a terminal and within constraints, consider adding it.
        if (
            node.isTerminal 
            && minLength <= prefix.length 
            && prefix.length < maxLength 
            && !collected.includes(prefix)
        ) {
            if (coinFlip() || collected.length === 0) {
                collected.push(prefix);
            }
        }

        // only allow traversing paths that include the letters left to us
        const letters = Object.keys(node.children).filter((k) => lettersLeft.includes(k));
        const randoSort = (a, b) => {
            return coinFlip() ? 0 : coinFlip() ? -1 : 1;
        };
        Array(10).fill(0).forEach(() => letters.sort(randoSort));

        // Regardless, continue the traversal.
        for (let i = 0; i < letters.length; i++) {
            const letter = letters[i];
            const newPrefix = prefix + letter;
            // If we're not even at the min length yet, follow all paths
            const tuple = [
              node.children[letter],
              newPrefix,
              lettersLeft.replace("letter", "", 1)
            ];
            if (prefix.length < minLength) {
                stack.push(tuple)
            // otherwise flip a coin if we'll follow the path or not.
            } else if (coinFlip()) {
                stack.push(tuple);
            }
        }
    }
    return collected;
}

And running it, fully expecting my browser to lock up from 5040 potential paths being searched (7!) and

the restricted walk shows impressive results

Hey that's not bad! In fact that's quite good. Let's use this instead of doing a bunch of extra work! Now we just need to go back and update that game setup code I mentioned. We'll replace game_words with two calls to our Trie:

function setup_entities() {
  const word = potentialWords.randomWord();
  const words = potentialWords.restrictedWalk(3, 8, word, 7);
  ...

And then let's update letters_used to take in this list of words and give us back the appropriate amount of letters. The only tricky part of this is that for a word like Apple, we need to make sure we include two ps for the buttons or else the user won't be able to solve the puzzle.

function letters_used(words) {
    const allLetters = Object.keys(words.join("").split("").reduce((accum, l) => {
        accum[l] = l;
        return accum;
    }, {}));
    const leftovers = words.map((word) => {
        let leftover = word;
        allLetters.forEach((l) => { 
            leftover = leftover.replace(l, '');
        });
        return leftover;
    }).filter(Boolean);
    if (leftovers.length) {
        allLetters.push(...letters_used(leftovers));
    }
    
    return allLetters;
}

There's probably a nicer way to do this, but this was the first idea that came to mind for me. We can take the unique letters from the list of words, then remove each of those letters once from each word. Any word that only used those letters will be gone, but any leftover pieces will contain letters that had duplicates. Of course, in those leftovers there might also be duplicative letters, and so we just treat the leftovers as another set of words to deduplicate! By combining those two+ results then we'll end up with the list of letters that are used without any extras.

The moment of truth, does it work?

function setup_entities() {
  const word = potentialWords.randomWord();
  const words = potentialWords.restrictedWalk(3, 8, word, 7);
  const letters = letters_used(words);
  gameState = new GameState(words);
  ...
newly generated game each time

The only problem that's left is our dictionary. In the above sreenshot the "words" are: ['ERR', 'ERE', 'SUSS', 'SUER', 'SUERS', 'SURE', 'SEE'] and while those are pretty good words. Memery aside, I don't know if archaic language like ere or suss are guessable in a way that wouldn't infuriate people. So we'll probably need to weed out words from the word list at some point. But I think that for now, we can move along and try to make the experience better in other ways.

Start screens and sound effects

With the ability to generate random words to puzzle out, we've made the game at least somewhat more interesting than guessing the same Apple based words all the time. But, given how many words exist that aren't in the 7 words we return that are real, it's going to be an unpleasant experience when someone guesses a word that is real but not in the list to guess.

So we'll fix that, but first, let's deal with the fact that you can only play once and then have to refresh. We can do an immediately obvious thing. Let's consider the game loop code:

function game_loop() {
    if (!ctx) {
        console.log('No canvas found?')
        return;
    }
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    update_entities();
    if (gameState.is_game_done()) {
        console.log('Game complete');
        // TODO: New game and whatnot
        ctx.font = '48px Impact';
        ctx.fillText('You win', canvas.width / 2, canvas.height / 2);
        return;
    }
    draw_entities(ctx);
    requestAnimationFrame(game_loop);
}

If we call the clear out the old entities, call the setup method, and request the animation frame to continue running the game loop, then we can instantly restart the game. Assuming we want to let the user bask in the glory of their completed game for a moment, we can use a timeout to schedule the reset a moment later:

function game_loop() {
    if (!ctx) {
        console.log('No canvas found?')
        return;
    }
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    update_entities();
    if (gameState.is_game_done()) {
        console.log('Game complete');
        ctx.font = '48px Impact';
        ctx.fillText('You win', canvas.width / 2, canvas.height / 2);
        entities.length = 0;
        setup_entities();
        setTimeout(game_loop, 1000);
        return;
    }
    draw_entities(ctx);
    requestAnimationFrame(game_loop);
}

This works, but it feels a bit funny. Reseting the entity list outside of the setup feels like we're leaking out some concerns here. So, we can move that into the setup entities function instead. But... this still nags at me a bit. Since we're now in the polishing stage, it feels like we'd want to transition to a new screen and let the user choose what to do, maybe play some victory music, those kinds of things. To make that happen, I think it's important we cut the ties that bind here and decouple the game_loop and the setup_entities functions from each other.

How are we going to do that, you ask? Simple. Events. 7

Let's de-couple the setup and teardown of our game in time so that we can slip things inbetween each to make it feel like an actual game. First up, we'll make the setup trigger off an event with no extra stuff yet. We can make an object to keep track of the events so we don't have to hardcode the names in the places where we call or catch them.

const SCENE_EVENTS = {
    WORDSLOADED: 'wordsloaded',
    NEWGAME: 'newgame',
    ROUNDOVER: 'roundover',
};

Then updating the game loop section of the code to not call the setup methods directly, but instead notify the document about the finished round.

if (gameState.is_game_done()) {
    ctx.font = '48px Impact';
    ctx.fillText('You win', canvas.width / 2, canvas.height / 2);
    document.dispatchEvent(new Event(SCENE_EVENTS.ROUNDOVER));
    return;
}

For this to do anything we need the document to listen for the event, and while we're at it, let's wire up the new game event to fire when we've loaded the words from the file.

fetch("words.txt")
    .then((response) => response.text())
    .then((w) => { 
        window.words = w.split("\n");
        window.words.forEach((word) => {
            if (word.length >= 3) {
                potentialWords.insert(word)
            }
        })
        document.dispatchEvent(new Event(SCENE_EVENTS.WORDSLOADED))
});

document.addEventListener(SCENE_EVENTS.WORDSLOADED, () => {
    document.dispatchEvent(new Event(SCENE_EVENTS.NEWGAME));
});

document.addEventListener(SCENE_EVENTS.NEWGAME, () => {
    setup_entities();
    game_loop();
})

document.addEventListener(SCENE_EVENTS.ROUNDOVER, () => {
    setup_entities();
    setTimeout(game_loop, 1000);
})

The game still works, and everything's still the same. But now... let's change things up. We can do two small pieces of polish. Let's make a landing page, and a victory page. We can re-use our handy buttons and the way they trigger to make the start button not a single clicked item, but rather have the user spell start just like they'd select other words during the game. So now our start button is our tutorial:

class StartSelect {
            
  constructor(x, y, letters) {
      this.letters = [];
      this.buttons = [];
    
      this.x = x;
      this.y = y;
      this.letters = letters;
      this.buttons = [];
      const number_of_letters = letters.length;
      for (let i = 0; i < letters.length; i++) {
          const letter = letters[i];
          const lx = x + letter_box_width * i * 1.5;
          const ly = y + letter_box_width * 2;
          const letterButton = new LetterButton(lx, ly, letter);
          letterButton.subscribe(this);
          this.buttons.push(letterButton);
      }
      this.active_buttons = [];
      this.check_words = false;
      this.subscribers = [];
  }
    
  draw(ctx) {
      ctx.save();
      ctx.beginPath();
      ctx.fillStyle = 'lightblue';
      ctx.strokeStyle = 'lightyellow';
      for(let i = 0; i < this.buttons.length; i++) {
          this.buttons[i].draw(ctx);
      }
      ctx.beginPath();
      for (let i = 0; i < this.active_buttons.length; i++) {
          const btn = this.active_buttons[i];
          if (i === 0) {
              ctx.moveTo(btn.x, btn.y);
          }
          ctx.lineTo(btn.x, btn.y);
      }
      ctx.lineTo(cursor.x, cursor.y);
      ctx.stroke();
      ctx.fillStyle = 'black';
      ctx.font = "36px serif";
      ctx.textAlign = "center";
      ctx.textBaseline = "middle";
      ctx.fillText("Click and drag to spell", width / 2, this.y - height / 2);
      ctx.restore();
  }
  ... update and subscriber related methods same as the LetterSelect class...
}

And if we create a setup_start method, similar to the setup_entities method we used before. We can position the start "button" and some simple instructions to the user on the page.

function setup_start() {
    const words = ['START'];
    const letters = letters_used(words);
    gameState = new GameState(words);
      
    const word_x = padding * 2;
    const origin_y = input_area_start + letter_box_width * 3;
    const origin_x = word_x + width / (letter_box_width * 6) + letter_box_width;
    const letterSelections = new StartSelect(origin_x, origin_y, letters);
    entities.length = 0;
    entities.push(letterSelections);
      
    // Create boxes, one for each letter in a word, show one word per row
    for (let i = 0; i < words.length; i++) {
        const word = words[i];
        const y = height / 3 + word_row_start + letter_box_height * i + i * padding;
        const wordRow = new WordRow(word_x, y, word);
        wordRow.subscribe(gameState);
        letterSelections.subscribe(wordRow);
        entities.push(wordRow);
    }
}

Of course, it still looks a little bit funny. And if you spell START then you see a "You Win" screen before you're taken to the first real round of the game. So let's work on fixing that. It's the WordRow that's listening and that will emit the event we care about, so we need think about that first. Its subscriber is the game state, which is always being checked inside of the game_loop method. Similar to how we decoupled things before, let's think about how the game loop checked for if the game loop is done or not causes a problem.

function game_loop() {
    if (!ctx) {
        console.log('No canvas found?')
        return;
    }
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    update_entities();
    if (gameState.is_game_done()) {
        ctx.font = '48px Impact';
        ctx.fillText('You win', canvas.width / 2, canvas.height / 2);
        document.dispatchEvent(new Event(SCENE_EVENTS.ROUNDOVER));
        return;
    }
    draw_entities(ctx);
    requestAnimationFrame(game_loop);
}

If we didn't have to have a game state check, then we wouldn't have to do any sort of messy conditionals here if we wanted to use it for both the "done" state of the start menu and the individual rounds of the game. That sounds like an easier situation to deal with to me, so let's refactor the actions the game takes when you finish a round.

First, lets added in an ALLMATCHED event to use:

const SCENE_EVENTS = {
    WORDSLOADED: 'wordsloaded',
    NEWGAME: 'newgame',
    ROUNDOVER: 'roundover',
    ALLMATCHED: 'allmatched',
};

Then, let's update GameState.on_match to actually emit the event we care about once everything is matched for the first time:

on_match(name, word) {
    if (name !== EVENT_NAME.MATCHED) {
        return;
    }

    if (this.words_to_find.includes(word)) {
        this.found_words.add(word);
    }

    if (this.is_game_done()) {
        document.dispatchEvent(new Event(SCENE_EVENTS.ALLMATCHED));
    }
}

This will let us remove the if statement from the game loop making it simple:

function game_loop() {
    if (!ctx) {
        console.log('No canvas found?')
        return;
    }
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    update_entities();
    draw_entities(ctx);
    requestAnimationFrame(game_loop);
}

But there was more than just the use of gameState.is_game_done() here before. We need to have something draw the "you win" text after all. So, let's make a new entity to represent the victory screen's needs:

class VictoryScreen {
    draw(ctx) {
        ctx.save();
        ctx.font = '48px Impact';
        ctx.fillText('You win', canvas.width / 2, canvas.height / 2);
        ctx.restore();
    }
}

And for us to render it, we obviously need to add it to the list of entities. So let's go ahead and setup an event listener for the new ALLMATCHED event. The only thing special about this, is that we want to not create a victory screen the first time get a match (the start screen). So we'll track a bit of global state in a flag:

let firstTime = true;
document.addEventListener(SCENE_EVENTS.ALLMATCHED, () => {
    if (firstTime) {
        document.dispatchEvent(new Event(SCENE_EVENTS.NEWGAME));
        firstTime = false;
    } else {
        const victory = new VictoryScreen();
        entities.length = 0;
        entities.push(victory);
        setTimeout(() => {
            document.dispatchEvent(new Event(SCENE_EVENTS.ROUNDOVER));
        }, 1000);
    }
});

This gets us back to where we started, but better. The game still loops and shows you a "You Win" screen at the end of each round, but the first match you ever do jumps you right into a new game.

So, we've now got the ability to make a nice victory screen for ourselves, and heck, we could do things like track points for matches, or count and show the number of rounds done... but the only thing that I really want to add before I call this blog post done is add a teensy bit of sound.

The last time I did anything with sound and the web, I used the webkitAudioContext to play a little melody. But rather than beeps and bops, this time I think I want to just make some simple bopping noises. Three to be precise. I want a noise for when you're activating a button, when you release, and when you make a match successfully. Well, maybe four actually, we probably want a little victory jingle for a round completion.

For this, we can use the Audio class. It's pretty simple to use, we just need to pass it the URL of the sound to load and then we can call .play(). So I popped over to itch.io and found myself a free asset pack with some noises and another one with some jingly samples to use for the victory sound.

While listening to the various sounds play, I noted that the audio element has to be loaded before you can play it, and the MDN documentation suggests listening for the canplaythrough event from the audio element to signal this. So let's encapsulate that need and make our life easier in the game with a helper class:

class Sound {
    constructor(path) {
        this.audio = new Audio(path); 
        this.canPlay = false;
        const ref = this;
        this.audio.addEventListener("canplaythrough", (event) => {
            ref.canPlay = true;
        });
    }
      
    play() {
        if (this.canPlay) {
            this.audio.play();
        }
    }
}

And then we can setup some global references to the sounds to be used wherever we need to, and then tie them to events so that it's easy to trigger them from elsewhere in the code. For sounds that should fire based off existing events, it's pretty easy to add them in:

const sound_victory = new Sound(...pathtovictorymusic.wav);
document.addEventListener(SCENE_EVENTS.ROUNDOVER, () => {
    sound_victory.play();
});

Since the location we decide if there was a match or not is in the GameState class, we can dispatch the event for the sound that matches there.

on_match(name, word) {
    if (name !== EVENT_NAME.MATCHED) {
        return;
    }

    if (this.words_to_find.includes(word)) {
        this.found_words.add(word);
        document.dispatchEvent(new Event(ROW_STATE.MATCHED));
    }

    if (this.is_game_done()) {
        document.dispatchEvent(new Event(SCENE_EVENTS.ALLMATCHED));
    }
}

And we can have the WordRow dispatch the unhappy sound for if something doesn't match.

on_select(name, word) {
    if (name !== EVENT_NAME.SELECTED) {
        return;
    }
    const isMatch = word === this.word;
    if (this.state === ROW_STATE.IDLE) {
        if (isMatch) {
            this.state = ROW_STATE.MATCHED;
            for (let i = 0; i < this.subscribers.length; i++) {
                this.subscribers[i].on_match(EVENT_NAME.MATCHED, this.word);
            }
        } else {
            document.dispatchEvent(new Event(SOUND_EVENTS.NO_MATCH));
        }
    } else if (this.state === ROW_STATE.MATCHED) {
        // Do nothing for now.
    }
}

But while this feels like it works. It's not quite right. Since the word that matches one row won't match any of the others, it's going to end up requesting to play the "no match" noise multiple times as well as the matching sound when we do have one. The sound effects that I've chosen so far don't actually sound too bad played over each other, and as far as feel goes, the game sounds okay since it's just an indicator of something happening and it's easy enough to hear that. But if we wanted to extend this idea out, of events on matches or not, then we'll need to solve this problem.

Unfortunately, it's going to take a bit more refactoring to get us out of this and I was really hoping to finish up this blog post today. So, since there's no crunch time on my head since this is just a side project for my own benefit. I'm going to go ahead and call it a day for now and publish this. But, you can probably expect to see a post in the future where we refactor this code and get it to a state where it's not just "playable", but enjoyable too.

To that end, here's what I think this game still needs (and you the reader are welcome to do this if you like!)

  1. Visual motion (negative). Like side to side "no" wiggles for when letters don't make a word, when words don't match a row
  2. Visual motion (positive). Pulses, like small growth or shrinkage to make visual interest in a row that has successfully matched. Things like the letters flying across, or spiraling towards, their destinations in the row would make for a fun "gamey" feel.
  3. Pleasant imagery. A nice background, or a rotating mix of backgrounds to show the user as they progress in rounds
  4. Background music. Preferably something easy on the ears. Maybe a little jukebox button to go to the next song and such.
  5. Controls such as a mute or a give up/new round button.
  6. A better dictionary. This might come sooner than later, there's a lot of garbage in the dictionary I found that claims to be words but definitely aren't. Like, Tres is not an english word, why is it showing up in this scrabble dictionary for english?
  7. A refactor of the event systems. The observer pattern is nice, but I should have thought to use the DOMs event system sooner, we could probably save ourselves some trouble if we used that instead of having to wire everything up ourselves!
  8. A scoring system. While it's just a time-passing game, it still wouldn't hurt to gamify things a bit more and have a score. Folks do love it when a number gets bigger after all.
  9. Probably some other stuff when I read this in the future. Heck, maybe I'll give TypeScript another go... probably not though.

Anyway, I hope you enjoyed this post! Feel free, as always, to let me know if you did or didn't, and if you want to play the game yourself. Then go ahead and click here. The answers are console logged if you want to open the inspector and see what inane words the dictionary has given you if you get stuck. Best of luck!