Recreating “Yoshi’s Island”

I was browsing reddit the other day, when I came across this post on /r/gaming:

Yoshi’s island was one of my favorite games as a kid, so naturally I immediately went and dusted off the old SNES and plugged it in to relive the glory days!

Well… not quite. I actually don’t own a SNES, and the one from my childhood is probably buried someplace in the bowels of my parents basement.

No matter though! I decided that if I couldn’t play the game, I’d do the next best thing and recreate the title sequence by hand. In this post I’ll describe the trials and tribulations of going through the process of reproducing old game art.

Yoshi’s Island Old to New:

Super Mario World 2: Yoshi’s Island came out just over 20 years ago in 1995. It was an instant classic. For it’s time, Yoshi’s Island was one of the most advanced games out there. It featured rich artwork and game-play dynamics that went way beyond the industry standard at the time. Since the game was in development for 4 years, lots of love went into adding cool little features.

One of these cool features was that, since the game used the new Super FX2 microchip, it had the ability to do advanced transformations on the artwork with rotation and scaling that was hard to achieve previously. That brings us to our title screen. The developers wanted to have a 3D island featured on the title screen, but (even with the cool new FX2 chip) the hardware at the time just couldn’t support implementing 3D graphics, at least not without some major elbow grease.

Instead, the developers elected to use an interesting trick to make the island seem as if it was 3D, by implementing a psuedo-3D or 2.5D mapping. In 2.5D your y and z coordinates are combined along with some trigonometry to make a parallel projection of the scene. Of course, you’re still dealing with 2D art assets, but as long as you order them correctly on the scene you can produce the optical illusion that the scene is in 3D.

In code this is actually fairly simple to produce. We can see from the original, that the island is angled at about a 30 degree angle from the ocean floor. This can be accomplished by taking an image, rotating about it’s center, and squishing it down by the proper ratio. Here I chose to shrink it by about 60%. This produces the illusion that you are looking down at a plane from an angle:

example1.gif
Left: original. Right: scaled by .4 in the y axis

Now we have the famous rotating island!

Putting some Clouds in the sky:

Now that the island is looking pretty good, the next step is to do the “skybox” and get some clouds put in it. In the original game, the clouds are just a big strip that keeps repeating like the background in an old film. Not only is that not very interesting to look at, but I’d have to manually un-stitch the background from the gif, and I don’t really want to do that. Instead, I elected to just have the several different cloud “shapes” move independently across the screen.

bgclouds
different cloud “shapes”

By giving each cloud a random X value and speed, I can produce an effect similar to the original skybox, but a little nicer to look at. I found that a random speed of around 3 pixels per draw and having about 20 clouds in the sky felt the best:

example2.gif
Cool! Now we have clouds!

Getting the Art Assets:

The island is pretty empty looking right now. To fill it out I need to get the rest of the art assets for the hills and decorations. I’d also like to get the music for the game as midi file.

I lucked out with the music! I was able to find a midi file for the title screen here: https://www.khinsider.com/midi/snes/super-mario-world-2-yoshi-s-island. I just threw it into Fruity Loops Studio and let it do it’s thing to render a pretty nice version of the song.

I wasn’t so lucky with the pixel art. You might notice that I already have the clouds and the island, but that’s because I was lucky and was able to find those files elsewhere on the web.

For the rest of the pixel art, I had to go through by hand and recreate them from the gif above. This was a time consuming process and took forever to get right. The static animations were the easiest, but I had to pick out key frames from the gif to get some of the animations right.

Then there’s that stupid bird! I hate that bird… The smoke animation? 6 frames. Yoshi himself only has 5 frames. The bird has 8 frames! And it’s white, so half the time it blends into the mountain. Why the f*$% does the bird have such a complex animation!?

Anyway, after cursing at my computer for hours, I finally managed to extract all the assets from the gif:

spritesheet

Placing in the Pieces:

The way the coordinates worked for the original Title Scene is that each object had an x, y, z, and id value. The x and y values corresponded directly to it’s coordinates on the island, and the z coordinate was the height. The id value told you what type of asset it was (e.g. id 5 is the crazy red tower).

So for every single object I had to go work out what I thought the proper x, y, and z coordinate are. I mostly did this by looking at different key frames from the gif, and cross referencing them with the island image. The island has a dimension of 256×256 pixels, so each coordinate should be relative to the center of the island at (128, 128). I think I was able to do this fairly accurately.

There’s a problem though – some of the objects have a curved bottom to make them appear more 3d. That messes up the position because you have to subtract off the bottom part of the image to get the “real” x and y:

example
“real” y is a few pixels up from the bottom of the object

This also had the negative side affect that when I placed an object at where I thought it should go, it looked like it was floating above the surface of the island. To counteract this, I gave each object a negative z value equal to the offset.

There’s another problem, which is that the island, has been rotated and scaled, so to get the actual position on the island, we also need to rotate and scale our x and y values by the same amount. after doing this we get this:

example3.gif
That’s no good!

So what’s going on here? Well we’re drawing the objects in the order that we created them, but that’s not the order they should appear on the screen. Instead we have to order them by the rotated and scaled y value so that we can make sure to draw the ones in the back first (similar to how z-indexing works). In JavaScript you can do this by defining the behavior for an Array.sort() function. In this case we will sort by the ‘y’ values from low to high:

example4.gif
Eureka!

Final product:

I hope you all enjoyed this breakdown of recreating the Yoshi’s Island title screen. There are definitely some things I could have improved, and there are definitely definitely better ways I could have obtained the images.

Let me know what you think, and if you have any questions, feel free to post them in the comments below!

Thanks for reading!

— Ben

 

 

Playing with Space Partitioning

In this post, I’ll talk about how I came up with the idea for a short project I did over the weekend called Shards:


Inspiration:

A couple of days ago I stumbled upon this great piece of work by user /u/woodrail on the subreddit /r/generative:

What really stood out to me about this piece was how it is structured. There are several main areas which are reflected about each other, and inside of each of those are smaller sub-sections which also contain reflections. It’s a fascinating piece to look at, and I wanted to understand more on how it was made.

In his post, Woodrail links to a github post which talks about the process of creating these pieces of artwork. The basic premise is a particular type of tiling known as the Kisrhombille Tessellation:

The idea behind this is that the tiling can be used, along with a (admittedly complicated) coordinate system to create small shapes that can then be built up like Legos into larger shapes.

The math behind it is still a bit fuzzy to me, so I wasn’t able to write an implementation, but it did get me thinking about this particular type of geometric space partitioning.


Space Partitioning:

I’ve worked a little bit before with other types of space partitioning before, such as voronoi diagrams (pictured below), which split space using a nearest point algorithm.

The trouble with these types of space partitioning algorithms is that they are too predictable. I want something a little bit more organic looking.

So I started thinking about other ways you could divide up space. One approach is to use the “broken glass” model of recursive subdivision, where you take a shape and split it into two shapes by drawing a line randomly through it. Then you repeat this process over and over until you have a lot of small subsections.

In the fractal world, this is one way you can generate shapes line the Sierpinski Triangle or the Pinwheel Fractal:

The trouble with this type of recursive subdivision is that you have to keep track of every new shape that you create, and that involves a lot of bookkeeping and math in figuring out how to split polygons into sub-polygons. I’m too lazy for all of that, I just want a quick solution.


Implementation:

What if, rather than splitting the shapes, I focus on the lines and sort of “grow” them outward from a central source. Each line or “branch” could have a certain chance of splitting and crating two branches. Then whenever a branch collides with another branch, it stops growing.

This isn’t a new idea per-se. Jared Tarbell has a really great implementation of this concept in one of his pieces called Substrate:

Jared uses a slightly different algorithm than mine though. In Substrate, branches can occur anywhere along the length of an existing branch, and again that means a lot of bookkeeping (keeping track of branches and such) that I don’t really want to do.

So for my algorithm I decided that the best approach would be to do everything on a pixel by pixel basis. If your branches can only travel one pixel each step, then you’ll never have any gaps in the branches. This means that each step of the algorithm all you have to do to test for collisions is check to see if the pixel you just moved into has already been turned on.

Similarly, if each split can happen only at the head of a branch, then it doesn’t matter where the rest of the branch is, so you can ignore the bookkeeping for keeping track of lines.

By doing it this way, you don’t have to think about all of the branches anymore, all you have to do is look at the head of each branch, which is more or less just a random walk particle, and the canvas holds all of the information that you need for collisions.

The end result of implementing this algorithm looks something like this:

You can get some really interesting variations by playing around with the parameters, such as how much the “walkers” can change their angle by, how often they split off, and how much they can change their angle by

In the end though, I decided that the straight lines where more aesthetically pleasing.

As a final touch I added a couple of visual effects, I made it so the lines fade over time, and after all of the walkers stop moving or run off of the screen, I fill most of the subsection using a flood-fill algorithm and color them based on a randomly selected color palette from a 60 degree section of the color wheel.

I’m quite pleased with the final effect:

As a bonus, I also wrote a variation of this algorithm which I nicknamed “Frost” which combines the fade effect with brightness threshold for when the walkers will die. The resulting animation is somewhat mesmerizing:

The visual effect of this variation reminds me a lot of a (much more complicated) animation by Felix Woitzel called Traveling Wavefronts

wavefronts.gif


Conclusion and Next Steps:

Overall, I’m pretty happy with how Shards and Frost turned out. If I come back to this project in the future, I would like to add some gradients to the fill process in Shards to give it some more color depth, maybe I could also work on stitching the edges of the particles together in Frost to make something similar to traveling wavefronts.

I didn’t really get a chance to play around with reflections, but I suppose one way I could accomplish that would be to reproduce each particle movement about some reflection line. I’d really like to dig into the the nested geometry of the Kisrhombille Tessellation as well.

Of course, to do that I’ll have to stop being so lazy about the math and start actually keeping track of my polygons and lines. Oh well.

For an easy to implement, light-weight space partitioning algorithm, I think this works quite nicely. I haven’t decided what I’ll use it for yet, but maybe I can generate some textures or landscapes with it.

As always, thanks for reading! If you have any comments or questions, feel free to leave them below.

— Ben

Making Conway’s Fireworks

I’m reposting this old post from my other blog, Aaauueegh, since I think it belongs here


 

To celebrate the upcoming 4th of July holiday I made a project called Conway’s Fireworks:

If the above embed isn’t working, you can also check it out here

In this post, I’d like to take you through some of my thinking when creating this project, and also some of the technical details of how it was coded. I’ll be talking about the following parts of the project:


Conceptualizing the Project

I wanted to make an animation to celebrate the 4th of July. Of course the first thing anyone thinks of when they think of the 4th of July is fireworks. There’s a large volume of great fireworks canvas animations out there already. I wanted to do something special to make mine stand out.

gospel gliders from Conway’s Game of Life

Now, If you’re not familiar with the famous automaton algorithm “Conway’s Game of Life”, (pictured above) definitely go check it out here: https://bitstorm.org/gameoflife/. The game of life is part of a class of algorithms called cellular automatons, and it has some pretty interesting behavior. The basic rules for the algorithm are fairly simple:

A great illustration of the rules of the Game of Life from

Although the simulation works off of just these 4 rules, lots of really interesting and complex behavior comes out of these simple rules. Conway’s game of life is a textbook example of emergence.

Even though John Conway himself is not too fond of the algorithm, It has always captured my imagination. So when I sat down to work on this project, the Game of Life was one of the first things that popped into my head as something different I could try out. The way the shapes tend to sort of explode outwards seemed like the perfect fit for how a firework behaves.


Ideas into Reality:

So I had my basic idea down. I would make each individual firework its own tiny Game of Life simulation. The trick now was to turn this idea into code. As with many of my projects, I used the P5 processing library and the html5 canvas. I like to work in this library because it speeds up development and makes drawing to the canvas easy. I like to work in JavaScript because then I can share my projects on the web.

The first step was to make on object prototype for my fireworks. I appropriately named this object “Conway” and filled it out with some basic fields to control the color, position, size, and so on. The grid variable simply contains a 2d array of values, true/false, for if a cell is on or off.

function Conway(){
  this.x = floor(random()*width);
  this.y = floor(random()*height*.7);
  this.type = floor(random()*3);
  this.size = random()*2;
  this.baseHue = random()*360;
  this.hueSwap = random()*30 + 60;
  this.gridSize = 61;
  if (this.gridSize%2 == 0) this.gridSize;
  this.center = floor(this.gridSize/2);
  this.numTicks = 0;
  this.finished = false;
  this.grid = [];
}

Here I’m hardcoding a lot of values, which is generally bad practice. I think in the future I will come back and make some global variables for things like the grid size or how much hue variance there should be.

Now that we have the skeleton of a Game of Life simulation we need to add two more components – a way to update it, and a way to display it to the screen. For me, I usually add these as functions in the object prototype in the form of a tick and render function. This is nice because it pushes the responsibility for updating and drawing the object to the object itself. When it comes time to run the project, all we have to do is call tick and render for each object currently in a list of drawables like so:

function draw(){
  for (var i = 0; i < drawables.length; i++){
    drawables[i].tick();
    drawables[i].render();
  }
}

The render function for our game is fairly simple to write. we simply draw a rectangle for each cell in our 2d array that has a value of true. The update function took a little bit more thought. To properly update the simulation, we need to apply the rules of the Game of life to each cell in the grid. One mistake I made early on was only having a single 2d array to store the values. In actuality we need 2 separate grids, because we can’t be overwriting the data from our first array with the new values until we have looked through the entire array. The final update function looked something like this:

this.tick = function(){
  var ind = (this.numTicks%2);
  for (var i = 0; i < this.gridSize; i++){
    for (var j = 0; j < this.gridSize; j++){
      var neighbors = 0;
      for (var k = 0; k < dirs.length; k++){                           var dx = i+dirs[k][0];                           var dy = j+dirs[k][1];                           if (dx >= 0 && dy >= 0 && 
          dx < this.gridSize-1 && dy < this.gridSize-1){
          if (this.grid[ind][dx][dy]) neighbors++;
        }
      }
      if ((this.grid[ind][i][j] && 
          (neighbors == 2 || neighbors == 3)) ||
          (!this.grid[ind][i][j] && neighbors == 3)){
        this.grid[(ind+1)%2][i][j] = true;
      } else {
        this.grid[(ind+1)%2][i][j] = false;
      }
    }
  }
  this.numTicks++;
}

This looks pretty complicated, but really all its doing is going through each cell in the grid and applying our 4 basic rules of the Game of Life simulation to them. the “ind” variable (short for “index”) simply lets me switch between which of my 2d arrays I’m looking at when I check which cells are alive or dead. The “numTicks” variable updates by one each time the tick function is called.

To make checking the 8 neighbors of each cell easier, I created a global array called “dirs” (short for “directions”) which contains the dx, dy values for each of the 8 neighboring cells.

The final hurdle was to get the “fireworks” to behave like an actual firework. This means that the fireworks have to be symmetrical about the center point. I had to think a little bit on how to do this. The trick is to separate the grid into quadrants, then randomly speckle alive cells into one of the quadrants (I picked the upper left quadrant). To make it look symmetrical, I then “flip” or “rotate” this quadrant onto the other 3 quadrants to make the “seed” for the shape. To do this, I simply added a bit of code that generates these quadrants when the object is created:

for (var i = 0; i < 10; i++){
  for (var j = 0; j < 10; j++){               if (random() > .5){
      this.grid[0][this.center-i][this.center-j] = true;
      this.grid[0][this.center+i][this.center+j] = true;
      this.grid[0][this.center+i][this.center-j] = true;
      this.grid[0][this.center-i][this.center+j] = true;
    }
  }
}

The great thing about this is that because of the nature of the Game of Life, when you create a symmetrical seed, the rest of the game of life is naturally symmetrical about that center point!

Success!

That seemed to do the trick!


Touch-ups and Visuals:

Now that the core of the project is working, its time to start cleaning up the visuals. I find that this is always the most time consuming part of the project. I can spend hours making little tweaks to the look and feel of a canvas animation.

For starters, My fireworks felt really unrealistic. The Game of Life simulation naturally expands outwards, but it didn’t have that “pop and fade” feeling of a real firework.

To add that in, I added a couple of rules to my render function. I made the size and opacity values of the firework a function of how long it was on the screen for. A linear transition felt pretty unnatural, so I used the built in P5 pow function to create a quadratic curve for my size and opacity. By doing this, The fireworks expand outward really quickly in the beginning, and then have a slow fade out as their expansion slows down. Here’s what that looks like in code:

this.render = function(){
  this.numTicks++;
  var mod = pow(((48-this.numTicks)/40),2);
  this.size += mod*.5;
  var ind = this.numTicks%2;
  translate(this.x, this.y);
  scale(this.size);
  for (var i = 0; i < this.gridSize; i++){
    for (var j = 0; j < this.gridSize; j++){
      if (this.grid[ind][i][j]){
        fill(this.baseHue + random()*this.hueSwap, 
             100, 100, mod*100);
        rect(i-this.center, j-this.center, 1, 1);
      }
    }
  }
}

In this case the “mod” variable is doing the heavy lifting of offsetting the size and opacity

Once I had that down the fireworks felt pretty natural, but I didn’t like that they were just sort of free floating in a black void.

To add some decoration to the scene, I added in some stars and hills to sort of round out the visuals and give it some aesthetics. The hills are simple sine curves with some offset by distance. For the stars, I decided to make them little squares and to make them “sparkle” a little by randomly changing the intensity and hue of the color by a little bit.

Conclusion:

I hope you all enjoyed reading this post! Let me know in the comments if you liked this and you would like to see more of these types of posts. Also let me know if you found my explanations useful or if there is anything I can do to improve my code or writing.

Whenever you are doing creative work, there will always be some things that you aren’t completely happy with. I think if I come back to this project I will clean up the code a little and change some of those hard-coded values into global variables. Also, I think I would spend a little bit of time tweaking the visuals for the fireworks, maybe changing how the curves work for the expansion and fade out animations.

All in all though, I’m pretty happy with this project. I think it was a neat idea, and I’m really pleased with how it turned out!

Thanks for reading!

— Ben