DEV Community: Gabriel Zayas

Hexaflare: Exploring Data Structures

Gabriel Zayas — Sat, 15 Jun 2024 10:16:01 +0000

I initially got into programming because I wanted to make a game, and although I do web development now, I got the chance to create a game with vanilla JavaScript and CSS called Hexaflare which I made back in early 2020. It was one of the most fun programming projects I've ever worked on, and the main idea of it came to me when I was studying data structures and algorithms.

I don't consider myself a very good programmer, and there are a lot of problems with the code itself because it was more of an idea that I wanted to put on paper as a side project. I used a lot of global variables, I didn't use import/export statements to manage modules, and all around there's a lot that could be cleaned up. Either way writing the code was a lot of fun, but besides that, having a goal in mind, envisioning how to solve it from an abstract perspective first, and THEN applying those principles in code form was such a fun process that I wanted to write about it.

What is Hexaflare?
Hexagons in Nature
Hexagonal Tile Pattern (Data Structure?)
Flare Star UI: Writing the Tile Pattern dynamically
Embarking into the Unknown: Moving and Rotating Star Clusters
Simulating Gravity
Almost Giving Up
Flare: Clearing Rings when Filled
Timer, Levels, and Final Implementation
★ Code Blooper Compilation

1. What is Hexaflare?

Hexaflare is a Tetris-like puzzle game in which you move blocks (star clusters) around the game board (the flare star), and then drop them to create rings. Whenever you create a ring the blocks disappear (like when you make a line in Tetris), and the remaining pieces gravitate toward the center.

Play it here! https://hexaflare.fly.dev

I knew that I wanted to make a fast-paced puzzle game, but the initial idea wasn't to actually include a gravity mechanic or be anything similar to Tetris. I primarily wanted the player to move pieces freely across the board, but I thought that was too easy. That's when Tetris came to mind, and I thought it would be cool to add a gravity mechanic instead.

The idea came to me at night when I had the lights off right before I was about to go to bed. I took out my phone and started writing notes like crazy. It was a rush of inspiration, and I had so much momentum that I finished writing most of the logic in a few weeks. (There was a bug that almost made me give up on the project, but I'll get to that later in section 7). I took all my notes, and the next day I started working through what abstractions would be necessary to make the game a reality.

2. Hexagons in Nature

Before I actually get into the details of how I made the game, I just want to say that hexagons tend to show up a lot in nature, and they're pretty cool. Without getting too much into it, I suggest watching this video which talks about honeycombs, hexagonal rock formations, and hexagonal insect eyes. Honeycombs, for example, show that hexagons are the shape that provide bees with the most space for storing honey, shown by this video which also talks about the honeycomb conjecture, a mathematical expression of the same concept. I gained a new appreciation for hexagons in nature by working on this project, so I thought it was worth mentioning here before I started explaining how I made the game.

3. Hexagonal Tile Pattern (Data Structure?)

Before the idea to make this game came to me that one night, I had actually been studying heap data structures at the time using this app. Without showing any code, it had a visualization of how to populate and pop values off of max heaps.

In a max heap, the root is the biggest value in the set of data.

Let's see how values are handled when populating a max heap from a set of data. In the app's visualization, you can see that each value is added one by one.

You can see here that 2 is added underneath 5. It remains as a child node to 5 because 5 is a larger value. Let's see what happens when we append 7.

As a rule we append it as a child, but each time we add a new element, we sort the set of data by comparing the parent and child. We then switch them if the child is a larger value, thus ensuring that the root of the set of data is always the largest value. So, here we switch 7 and 5.

What I found so interesting about this is that it resembled gravity if you were to turn it on its head. In other words, the largest value would always "drop to the bottom" so to speak. That's when the idea sparked in my mind to create Hexaflare, and I wanted to create a data structure that would not just spread out two child nodes at a time, but that would fan out in a 360 degree fashion.

Before I get to the prototypes, here's what the structure looks like. I found that each ring should have its own array, so the final product turned out to be a two-dimensional array.

[
  [1] # The center (root) of the pattern.
  [1, 2, 3, 4, 5, 6], # Ring 1
  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], # Ring 2
  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] # Ring 3
]

So, my journey to create this structure began. Since I had never seen anything like it before and I had no idea what it would actually look like at first, some of the prototypes were...interesting, to say the least.

The first idea I had was to make the structure look as close to a heap (or other data structures for that matter) as possible. That meant that the root would be at the top, and the child nodes would trickle downwards. You can see that in the screenshot above, and also in this one:

This was definitely getting closer to what I envisioned. It starts with a root, 1, and then fans out to 6 child nodes which represent one ring. As you go down each child, you start to see something peculiar about the rings. Whereas the first ring has six elements (1 through 6) the second ring has 12 elements. Then, the following ring has 18 elements. I had found a new abstraction in the pattern: Every successive ring increases by exactly 6.

Still, this structure really bothered me because it was mentally hard to grasp when trying to envision it as an actual, visual hexagonal tile pattern. It was at this point where I decided I needed to break out of the box of having a "top down" style data structure, and just let it be what it actually was; a pattern that extended in all directions two-dimensionally. That's when I came up with this pattern.

As you can see here, the first ring only has 6 elements, but when we get to the second ring, the following child nodes fan out to the side. Here is where I found a new abstraction the hexagon tile pattern. I found two abstractions that I called "Corner Hexagon" and "Side Hexagon." A corner hexagon is any hexagon that extends on a line directly from the root (In the screenshot above, you can see that the number 1 extends consistently to the right. This is the first Corner Hexagon in the ring, and each ring has a total of 6 Corner Hexagons). A Side Hexagon is anything else that is not a Corner Hexagon (Extends to the side away from the Corner Hexagon).

Without getting into the details of how to find parent nodes, etc., this two dimensional array was eventually what I came up with to implement the gravity mechanic which takes a leaf node and traces it all the way to the root, and it was just a lot of fun to think through the process and experiment. I can say that I genuinely enjoyed learning about data structures like heaps and then applying similar concepts to my own code.

4. Flare Star UI: Writing the Tile Pattern dynamically

Now that we have the structure, we can create it dynamically based on how many rings we want like this:

function generateFlareStar(number_of_rings) {
  // Generate Core (root)
  var core = 1

  // `flare_star` is the hexagonal tile pattern we'll be returning.
  var flare_star = [[core]]

  // The rings start from the second step
  // (In other words, the core itself isn't a ring)
  // `level` represents how many levels deep the structure is.
  var level = core + number_of_rings

  for(var i = 1; i < level; i++) {
    // Generate new ring
    var ring = []

    // Here we're just populating each array with numbers.
    // 1-6 for ring 1, 1-12 for ring 2, 1-18 for ring 3, etc.
    for(var value = 1; value <= i * 6; value++) {
      ring.push(value)
    }
    flare_star[i] = ring
  }
  return flare_star
}

The difficulty of mapping this out in CSS was that all of the pixels had to be determined dynamically when generating each hexagon. I eventually ended up with the following two functions:

// This generates the array
// 12 here determines how many rings the structure has
flare_star = generateFlareStar(12)

// This generates the CSS
generateFlareStarUI(numberOfRings(flare_star))

In the example below, the game board starts with 12 rings, then I change it to 7 and refresh the page to make the size change.

5. Embarking into the Unknown: Moving and Rotating Star Clusters

This was absolutely the most difficult part of the development process, and I had no idea how to even start envisioning it to make it a possibility. Basically, I wanted to take these blocks, move them around the outside of the game board, and rotate them like in Tetris. Here's what some of those blocks look like.

I sat at my desk for about half an hour just thinking. Then I felt overwhelmed so I laid down on the floor for about another half an hour staring at the ceiling trying to figure out how to pull this thing off. Then I got a wave of inspiration and got to work.

I ended up coming up with a Mapping abstraction that takes a map of the block and rotates the entire block of hexagons according to that map.

The map itself keeps track of every hexagon, and has data concerning where it's supposed to move next. For example, this is a portion from one of the block types called Pleiades, a straight line of four hexagons:

const PLEIADES_DATA = {
  ...
  "hexagon_2": {
    "center_of_gravity": true,
    "rotation_pattern": {
      "position_1": [["left", 1]],
      "position_2": [["up_left", 1]],
      "position_3": [["up_right", 1]],
      "position_4": [["left", 2]],
      "position_5": [["up_left", 2]],
      "position_6": [["up_right", 2]],
    }
  },
  "hexagon_3": {
    "center_of_gravity": false,
    "rotation_pattern": {
      "position_1": [["left", 2]],
      "position_2": [["up_left", 2]],
      "position_3": [["up_right", 2]],
      "position_4": [["left", 1]],
      "position_5": [["up_left", 1]],
      "position_6": [["up_right", 1]],
    }
  },
...
}

Each position_1 here for example represents the first position of each hexagon for the entire block. So, when rotating a block to position_2, we get the x and y values from the original div elements and pass the block data to the Mapper to calculate the new coordinates, thus rotating the entire block appropriately. If you're interested, you can check out the Mapper here.

There is a method in the code base called rotate which has some more logic to make this a reality. It calls a method named getCoordinatesByMap which can be found in the file linked to above, and this was by far the most brain-twisting part of the project. Still, I found it to be pretty fun even though it took a while to get it working properly.

6. Simulating Gravity

As I started to work on the gravity mechanic, I ran into a peculiar issue. I found that, when trying to move a block of four hexagons to the center, the hexagons started to fly in different directions. This was because, although all of the hexagons were moving toward the center, each hexagon didn't have the same parent, so whereas one hexagon might move downwards to the left diagonally, another might move downwards to the right diagonally. What I decided to do was determine the direction the entire block shifts in according to one hexagon, which I called the center of gravity. In doing so, the entire block would move in the same direction, solving the issue. You can see in the pleiades data above that there is a boolean value which designates if the hexagon is the center of gravity or not. If you're interested in how the logic works, you can see the source code here.

7. Almost Giving Up

There was one point where I ran into a bug that for the life of me I couldn't figure out. I implemented collision logic, so whenever you drop a block it gravitates toward the center, and if there is another block standing in its way, the block stops moving. The problem was that, very rarely, the block would move down one more ring, overlapping other blocks.

I looked at the collision logic over and over again and couldn't find any issues. Granted, not writing tests was totally my fault... To be 100% honest, I wasn't sure HOW to write tests for logic like this, and since I was doing this as a side project on my own, I figured it would be okay with out it. Lesson learned.

Anyways, I spent about a good two weeks (maybe even longer) trying to figure this bug out, and I made absolutely no progress during that time. I was so discouraged that I even started to remake the project in Unity. As I started from scratch, I realized it would take too long, so I sat down with the original code again.

I eventually found out that the problem was with the gravity logic, and that the while loop I had which pulled the block closer to the center with each call needed to be called as a do block instead, checking the while condition at the END of the loop.

do {
  // Gravitation logic...
  gravitation_direction = getGravitationDirection(center_of_gravity)
} while(gravitation_direction != null && starClusterCanGravitateToCore(star_cluster, gravitation_direction))

It was frustrating that the bug was being caused by just one conditional that should've been on a different line, but I'm so glad I was able to figure it out and get this project across the finish line.

8. Flare: Clearing Rings when Filled

Now that the gravity and collision mechanics were working, the last big step was to clear the rings and rack up the score. Similar to making a line in Tetris, first we check if any full rings exist, and if they do, we call the flare method (which simply removes the hexagons) and we add 1 to the total flare count which checks if we should level up or not.

while(fullRingExists(flare_star_rings)) {

  // Flare 💫🔥
  for (var i = 0; i < flare_star_rings.length; i++) {
    if(ringIsFull(flare_star_rings[i])){
      flare(flare_star_rings[i])

      current_flare_count += 1
      TOTAL_FLARE_COUNT += 1
      document.getElementById("flare_count").innerHTML = TOTAL_FLARE_COUNT

      // Level up here.
      if(TOTAL_FLARE_COUNT >= 12 && TOTAL_FLARE_COUNT % 12 == 0 && CURRENT_LEVEL < 24) {
        CURRENT_LEVEL = parseInt(CURRENT_LEVEL) + 1
        document.getElementById("level").innerHTML = CURRENT_LEVEL
      }

      if(parseInt(flare_star_rings[i].dataset["level"]) == 1) { flareTheCore() }
    }
  }

  ...
}

This part wasn't so bad when compared to writing the Mapping and gravity mechanics, but it was the next necessary step in the road map to finishing the game, and it was a fun portion to work on.

9. Timer, Levels, and Final Implementation

You can see in the previous section how a player levels up, and I also used the level to determine how fast the timer moves. I was in the final stages of development and things were getting pretty buggy here, but it was also very satisfying to see it all come together. Here's a snippet from the progress bar (timer) code:

// Just `if(UPDATE_TIMER){...}` below should be fine...
// Don't mind the messy code!
function processTimerEvents() {
  if(GAME_OVER == false && !GAME_PAUSED) {
    var timer_speed = 0.2 + (0.08 * CURRENT_LEVEL)
    if(UPDATE_TIMER == true) { current_prog -= timer_speed }
  }
  ...
}

current_prog represents a percentage value which starts at 1 and counts backwards. Once it reaches 0, the block is dropped automatically, and if the player drops the block quicker, they get a higher score by factoring in the current progress of the timer.

And that's about it! Part of me wants to talk about the rotate method that I mentioned before in detail, but this article is already pretty long enough, so I'll just wrap things up here. Thanks for reading!

10. ★ Code Blooper Compilation

The first thing I want to say is, the way I wrote this is NOT a conventional way of writing JavaScript. I actually didn't write any classes (I just organized all of the functions into their own files like gravity.js, flare.js, mapping.js, etc.). I also have a lot of global variables 😬. There's no way I'd take this approach when working with a team, but this was a personal project that I just wanted to "get on paper" so to speak, and I think if I were to make it again, I would do it on Unity with a lot better programming principles.

With that being said, here's some pretty bad code I wrote...

function togglePauseMenu() {
  if(GAME_PAUSED) {
    GAME_PAUSED = false
  } else {
    GAME_PAUSED = true
  }
  ...
}

Seriously? Maybe I should consider writing with this syntax instead:

This one's similar.

if(level_to_adjust > 12) {
  return 0
} else if (level_to_adjust < 1) {
  return 0
}

This next one is a UI bug that was happening when trying to move the entire block to a corner of the game board, and I still technically haven't fixed it...but it works?? So I'm not going to touch it for the time being. SUPER brittle 😅

// Redraw!
// Again, this is really hacky, but it works.
// ¯\_(ツ)_/¯
var reverse_direction = direction == "clockwise" ? "counter-clockwise" : "clockwise"
rotate(direction, star_cluster, star_cluster_type)
moveAlongCorona(direction, star_cluster, star_cluster_type)
moveAlongCorona(reverse_direction, star_cluster, star_cluster_type)
rotate(reverse_direction, star_cluster, star_cluster_type)

So there's that! I learned a lot and there's still a lot more for me to learn, but this was a very fun project, and I got to make a game! I'm not sure if I'll ever remake it in Unity one day, but it was a fun experience, and I'm glad I got to make it.

Thank you for reading!

Analyzing and Editing Ruby Source Code in Bullet Train

Gabriel Zayas — Thu, 29 Jun 2023 11:55:22 +0000

Hello, this is Gabe from the Bullet Train Core team. I’ve been on the team since December 2020, and it’s been a blast facing a lot of different challenges that don’t show up in traditional Rails application development. I say that because, if you’re familiar with our service, Bullet Train provides powerful tooling like Super Scaffolding to develop Rails applications quickly (please read this article in the Bullet Train blog to find out more about Super Scaffolding). This means that there are a lot of moving parts under the hood like transforming and copying templates for Tailwind-powered views, nested models, controllers, and more. For example, say you want to create a new model called Project.

> rails generate model Project team:references title:string
> bin/super-scaffold crud Project Team title:text_field

By just running these two commands, Bullet Train will add a new controller, a model, and views with Tailwind styling which all belong to a Team and can perform CRUD actions. Super Scaffolding will also update your tests with new attributes to ensure everything is working properly, and it will even update your routes files so you can start using new your endpoints right away.

Because there’s so much automated generation that takes place, it comes with its own set of challenges. In this article, I’d like to talk specifically about…

A really difficult bug that I faced when working with the routes file scaffolding logic.
A new gem I’ve been making to increase the quality of our source code analyzation and replacement logic related to issues with that bug.

Brain Twister

This bug was one of the most challenging programming problems I’ve faced, yet it was also one of the most fun ones to work on. If I remember correctly, I had to sit for about an hour and just take notes before I looked at any code again just to organize my thoughts before attacking the problem. The problem might not be too difficult for some, but it sure was for me. Here's the original pull request for reference.

Basically, there was an issue where we were encountering namespace collisions when the same namespace existed within another part of the routes file. Take for instance the following model names.

> rails g model Insight team:references name:string
> rails g model Personality::CharacterTrait insight:references name:string
> rails g model Personality::Disposition team:references name:string

Personality::CharacterTrait belongs to Insight, so it should be namespaced under Insight. However, Personality::Disposition belongs to Team, so we should be creating a new namespace block entirely like so:

resources :teams
  resources :insights do
    namespace :personality do
      resources :character_traits
    end
  end

  namespace :personality do
    resources :disposition
  end
end

You can probably already see how messy this can get. When Super Scaffolding these models, we were getting something like this:

resources :teams
  resources :insights do
    namespace :personality do
      resources :character_traits
      resources :disposition
    end
  end

Just imagine trying to run integration tests on a whole set of these models with duplicated namespaces. My head was spinning!

To make a long story short, I ended up fixing this by taking each namespace and scoping it to its proper parent before actually trying to scaffold the proper routing.

Granted, the code works fine now, but it’s bugs like this that made me reconsider how we should be analyzing and editing our Ruby source code. For example, in the pull request I mentioned earlier, you can find this in the namespace_blocks_directly_under_parent method:

if lines[line_number].match?(/^#{" " * (parent_indentation_size + 2)}namespace/)

We use the standard gem for linting our Ruby code which takes away a lot of problems when trying to Super Scaffold new files, but you can probably already see why this code is problematic. In the regular expression here, we’re grabbing the indentation of the parent, and then just adding two spaces to it to find the namespace block that exists under it.

What if developers are using four spaces instead of two? What if for some reason they added an extra space? Even if they ran the correct command to Super Scaffold a new model, it would break and it would take too long to debug the problem for something that isn’t even their fault.

Also consider this line in the scope_to_namespace_parent method in the same pull request.

namespace_line_number if lines[namespace_line_number].match?(/ +namespace :#{namespace}/)

By the time we get to this line we’re already within the scope of the parent, so matching the namespace to this regular expression / +namespace :#{namespace}/ gets the job done for us. The problem is, using regular expressions on strings like this can grab so many other things. What if the namespace is :project and we had another namespace just called :project_sites already? The regular expression would match the wrong namespace and it would be a pain to debug.

Learning About Abstract Syntax Trees

And well, I hadn’t really been proactively looking for a solution to all of this, but it had been sitting in the back of my mind for a while because this isn’t the only place where we use match? or gsub to edit files like this. What actually led me to start working on this new gem was the book Ruby Under a Microscope. I learned about the abstract syntax tree data structure, Ruby’s LALR algorithm for parsing its source code, and some other cool things along the way. I talked to some Ruby commiters at Ruby Kaigi 2023 and they said Ripper is a semi-outdated library for looking at abstract syntax trees of your source code, and they suggested syntax_tree. Someone on the Bullet Train team also suggested looking into referral. They’re both awesome tools, but taking a quick look at them, I didn't quite find what I was looking for.

syntax_tree

For example, I really like this about syntax_tree. Imagine we have a file named add.rb with the following content.

2 + 2

Simple enough. By running the following CLI command, we get the following output about the nodes in the abstract syntax tree.

> stree expr add.rb
SyntaxTree::Binary[
  left: SyntaxTree::Int[value: "2"],
  operator: :+,
  right: SyntaxTree::Int[value: "2"]
]

Ripper doesn't provide this kind of information, and it can be really hard to read, so having this CLI command available is pretty great.

Also, the abstract syntax tree that Ripper.sexp generates looks like this:

irb(main):001:0> Ripper.sexp("2 + 2")
=> [:program, [[:binary, [:@int, "2", [1, 0]], :+, [:@int, "2", [1, 4]]]]]

syntax_tree’s AST output is much cleaner.

> stree ast add.rb
(program (statements ((binary (int "2") + (int "2")))))

This is great and all, and maybe I haven't delved deep enough into syntax_tree itself to find the tooling I was looking for, but I was finding that I wanted to analyze my Ruby source code in “real-time” so to speak and apply changes directly to the source code all within Bullet Train's code. Ripper also provided the line numbers I was looking for, which aren’t present in syntax_tree’s ast output. I wanted a library that I could require in Bullet Train to pinpoint each and every variable, symbol, or method invocation to transform on the spot and give back to the developers using Bullet Train.

Masamune

This led me to start making Masamune. Masamune takes the output from Ripper and translates it into a meaningful collection of nodes to pinpoint whatever data types or keywords we want to grab from our code. Take the following code snippet for example.

require "masamune"

code = <<CODE
java = "java"
javascript = java + "script"
puts java + " is not " + javascript
# java
CODE

msmn = Masamune::AbstractSyntaxTree.new(code)

msmn.variables
#=> [{:line_number=>1, :index_on_line=>0, :token=>"java"},
#=> {:line_number=>2, :index_on_line=>0, :token=>"javascript"},
#=> {:line_number=>2, :index_on_line=>13, :token=>"java"},
#=> {:line_number=>3, :index_on_line=>5, :token=>"java"},
#=> {:line_number=>3, :index_on_line=>25, :token=>"javascript"}]

msmn.strings
#=> [{:line_number=>1, :index_on_line=>8, :token=>"java"},
#=> {:line_number=>2, :index_on_line=>21, :token=>"script"},
#=> {:line_number=>3, :index_on_line=>13, :token=>" is not "}]

msmn.variables(name: "java")
#=> [{:line_number=>1, :index_on_line=>0, :token=>"java"},
#=> {:line_number=>2, :index_on_line=>13, :token=>"java"},
#=> {:line_number=>3, :index_on_line=>5, :token=>"java"}]

Knowing exactly what lines these tokens are on is extremely valuable information when trying to edit files in Bullet Train, and if we can isolate the tokens to the exact word we’re looking for, we won’t have to worry about regular expressions matching similar strings that we don’t want (like the :project and :project_sites example I mentioned above).

Since Bullet Train has been in development for a long time, I don’t foresee Masamune replacing all of this logic overnight. This also doesn’t account for the yaml and erb files which we also have to transform when using Super Scaffolding. However, I think this is a step in the right direction to replace code with more precision. I submitted a pull request to implement the new gem recently, and I’m excited to see how it will be used in the future. You can see here where Masamune pinpoints the lines each namespace its on by grabbing each namespace method call.

# `@msmn` here represents a Masamune::AbstractSyntaxTree
# object instantiated with the contents of config/routes.rb in a Rails app.
namespaces = @msmn.method_calls(name: "namespace")
namespace_line_numbers = namespaces.map { |namespace| namespace[:line_number] }

We then go through each line in the file, check if that line has a namespace invocation on it, and then retrieve the first symbol that comes right after the namespace.

if namespace_line_numbers.include?(line_index)
  namespace_name = @msmn.symbols.find { |sym| sym[:line_number] == line_index }[:token]
  # …
end

This puts my mind at ease when I think of trying to retrieve and edit tokens in our Bullet Train files. There’s still a lot of more work to do on Masamune and we’re only scratching the surface of how to use it in Bullet Train, but it’s challenges like this that make me enjoy programming, and I would be glad if this allows us to produce a better developer experience and help others by making our code generation tools more precise.

Give syntax_tree Another Chance

In Masamune, I’ve based all of my node classes off of the abstract syntax trees that Ripper.sexp generates. I think there’s a lot of good information that can be gleaned from the syntax_tree gem though, so I might give it another chance and base my node classes off of the output from there instead. Either way, there’s a lot of work that can be done here, and if you decide to check out Bullet Train, I hope you enjoy how helpful Super Scaffolding is!