Hexaflare: Exploring Data Structures
Tags: javascript, css, datastructures, algorithms
Published: 2024-06-15 10:16:01

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.

# Table of Contents
1. What is Hexaflare?
2. Hexagons in Nature
3. Hexagonal Tile Pattern (Data Structure?)
4. Flare Star UI: Writing the Tile Pattern dynamically
5. Embarking into the Unknown: Moving and Rotating Star Clusters
6. Simulating Gravity
7. Almost Giving Up
8. Flare: Clearing Rings when Filled
9. Timer, Levels, and Final Implementation<br/>
10. ★ 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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5iup5oj58l0y8wr1nejk.gif)

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](https://www.youtube.com/watch?v=Pypd_yKGYpA) 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](https://www.youtube.com/watch?v=kxDEcODUEP0) which also talks about the [honeycomb conjecture](https://en.wikipedia.org/wiki/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](http://algorithm.wiki/ja/app/?fbclid=IwAR07YaXmx7kTjaJ-RgoPEO1RF8w4qfnC_I30Ub0BATvFx4sR-cfzwx8TwrQ#0). 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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yxjft67vjzzcbdy7vx3h.png)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nlqckjjussab3flfyar6.jpg)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r8b7yr0jt5btlqvoju0g.jpg)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y2ab3luwepwl7swxda6b.jpg)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ws01yewo023ma2nicqat.jpg)

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.

```ruby
[
  [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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/an5fkas4847oriblyfih.jpg)

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: 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4wtqdzocub9l317fsa0r.jpg)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rc6ac7q50m3gd0c0kpqy.jpg)

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 <bold>side</bold>. 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:
```JavaScript
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:

```JavaScript
// 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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vdcctz52jlprvgsxqs4a.gif)

# 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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ti5k0pqlc3gtsk0pfji6.jpg)

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:

```js
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](https://github.com/gazayas/hexaflare/blob/main/javascript/mapping.js).

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](https://github.com/gazayas/hexaflare/blob/main/javascript/gravity.js).

# 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.

```js
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.

```js
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:

```js
// 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...

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

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cemwb61x52grcb8c71db.png)


This one's similar.
```js
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 😅

```js
// 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!