Building Walls with Digital Logic


A few months back, a friend and I set out to build a simple computer game in 1 month. My friend, Greg, is an artist. He created the art assets and I did the coding.
We built the game in Unity. We decided to build a 2D over-head game where the player navigates a maze and collects items from different stages of life. When all items are collected — from pacifier to coffin — the game is over. It’s all very deep and philosophical. I want to highlight one cool experience in the development of this game: building the walls.

It’s always fun to see knowledge that, at first, seems superfluous come into practical use. I took a course in digital logic last fall (as part of my ongoing education plan for a BS in computer science). I didn’t immediately see the use in knowing about binary conversion. I mean, doesn’t the computer just do that for me? In the end, this small bit of knowledge, practiced over and again for class, came in very handy.

A 2D overhead maze game showing walls, floor, player, and pacifier collectible


The Blueprint

I researched maze creation algorithms before beginning any other development. The one that seemed like the best option was Depth-First Search (DFS). Miguel Kano’s article on DFS is a big help. From his article:

“Depth-first search is an algorithm that can be used to generate a maze. The idea is really simple and easy to implement using recursive method or stack.

Basically, you start from a random point and keep digging paths in one of 4 directions(up, right, down, left) until you can’t go any further. Once you are stuck, you take a step back until you find an open path. You would continue digging from there. It’s just the repetition of these.”

I used DFS to build a 2D array which stores a 0 to represent a floor position and a 1 for a wall position. Since there was only one floor tile, it was easy to place the floor with some simple game logic like:

if (thisPos === 0) { drawFloor(thisPos); }

So far so good. Then comes the tricky part — wall placement.

Read more…

Project Euler – 012: Triangle Numbers


This was originally posted in May 2015. Updated on 25 May 2016 for clarity.

I’m working on Project Euler which challenges users to use, create, or creatively reinvent algorithms to solve math problems. Problem #12 reads:

Highly Divisible Triangular Number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Note: For any integer n, the triangle number is equal to (n * (n+1)) / 2.

A lot of scratch paper went into following formula for finding the number of divisors which make up a number (triangle or otherwise). The steps are as follows:

1. Create an array of the prime factors which make up that number; include all repeating digits.

Example: Using the 7th triangle number, 28, the prime factors array is [ 2 2 7 ].

2. Find the number of times each integer appears in a group of like integers.

Example: There are two 2’s and one 7. This gives {2:2, 7:1}.

3. Add 1 to the number count of each integer group.

Example: {2:2+1, 7:1+1} => {2:3, 7:2}. The reason for doing this is that, if you take just the 2’s in their own array [ 2 2 ], they make up [ 1 2 4 ] which are the 3 divisors of 2×2 (or 4). The number count n of an integer group always returns n + 1 unique divisors.

4. Multiply the repeating-integer divisor count values together.

Example: {2:3, 7:2} => 3 * 2 = 6.

5. The product of the multiplication of number count values provides the number of divisors in the original number.

Example: The number 28 divides evenly (meaning the division results in an integer) with the following numbers: [ 1 2 4 7 14 28 ]. Note that there are 6 divisors, as expected.

The previous steps account for all the math necessary to solve the problem. The rest of the work is just implementation.

Check out the simplified JavaScript implementation.

Read more…