The Story of My First Significant Java Project - Path Finding Using Frameworks and Data Structures

Last month I went back to school, and now I'm officially on the books as a CompSci Master's student. This week, I tackled my first big assignment, and it was a bit of a doozy.

By way of context, I'm coming into this Master's program with some real-world work experience. I previously worked at a video game company, and have also made a few small PC games of my own (most notably a couple of 2D "bullet hell" shooters, for which I developed my own modest game designs, physics engines and AI routines). As such, I already have some of what is being taught in this curriculum in my repertoire. But the assignment I'm writing about today comes from an accelerated hybrid course on data structures, path finding, database administration and integration of custom frameworks. It is one of several courses that are famous within the program as having been added to the curriculum explicitly for the purpose of weeding out the poor kids who aren't cut out to be developers.

The assignment itself required us to write a program that satisfied the following requirements:

• generate a navigation mesh based on topographical map and geological/natural resource data provided in a text file
• read in mouse clicks to define starting and destination waypoints on the map
• include a "robot" (rudimentary AI) with limited traversal capabilities (stamina, resources, strength for handling inclines in 3-space, etc) that will try to find a path from start to destination
• utilize (and modify if necessary) a custom graphics and time (framerate) management framework provided by the professor and written in Java to display everything in a window

So, there was a lot to do, and a lot to learn along the way. Just as one example, my work experience has revolved mostly around UI engineering, and though I'd created rudimentary AI algorithms for my bullet hell games, this was my first time working with anything like nav meshes and pathfinding. This was also my first time using Java. I've made a few dumpy practice programs to learn some of the basics, but on day one, even something as simple as reading and parsing a text file, or working with an array was a non-trivial task. And of course, because I had to balance this with my work from other classes and didn't want to neglect my non-academic projects, I ended up with only three days to do everything.

At the time of this writing, I'm not actually done with the project (hah!). But it isn't due for another week and a half, and the remainder of the work is housekeeping (hiding print calls behind DEBUG flags and cleaning up documentation, for example). In any case, I'm happy with what I've produced, and I'd love to talk about everything I learned along the way. But there too much of it, so I'll fixate on my proudest achievement, the "simple path" pathfinding algorithm that I used in this iteration of the project, which will serve as a stepping stone to more complex iterations that will end up using the A* algorithm, remote database interactivity, and multiple simultaneous AI "players"!

In class, we have already learned about Dykstra's algorithm and the A* algorithm for path finding. These are both very good (much better, anyway) algorithms for path finding than the "simple path" algorithm I came up with. However, given the limited time to complete this task and the requirements set forth by the professor (he actually demanded a "simple path" solution for the first assignment as a stepping stone), I'm very happy with how quickly I generated a solution.

Simply put, I begin with a while loop. This loop will iterate until the robot runs out of stamina, the goal has been reached, or the robot has worked itself into a corner (backtracking is not allowed). Inside the loop, I first establish the current location of the robot (the nav mesh node it currently sits on). Then, I build an adjacency list for that node; in other words, a list of every node that the robot can navigate to from the current node. (A candidate node will only be added to the adjacency list if all of the conditions for travel between it and the current node are met; the candidate must not have been visited already, it must be close enough in 3D space (not too much of a slope), the robot must have enough stamina left to reach the candidate node, and there must actually be a node there.)

At this point, I can already kill the program if the adjacency list size is zero; if the bot has no means to reach any node adjacent to its current node, it is trapped and the traversal is a failure. However, if there is at least one candidate node available for travel, I compare the distance between the goal and each candidate node in the adjacency list. I choose the navigable candidate that is closest to the goal, and move the bot there (adjusting its stamina values along the way, based on terrain difficulty and discovered resources).

After each movement of the robot, I check if it has reached the goal. If so, that's a successful traversal! If not, I check if the robot's stamina has been exhausted. If so, that's a failed traversal, and if not, I can continue with another iteration of the while loop until and exit condition is met.

Not too shabby!

I would have loved to post some of my code, but due to my professor's concerns regarding plagiarism (which I find to be valid) I will have to refrain for now. But, as always...

Thanks for reading!
- Steven Kitzes

Understanding Java from a C++ Background

A short note of thanks before I begin. Some friends showed me a lot of shortcomings in the way I was thinking about this problem. That led to a huge, sweeping revision of this article. Hopefully it is more correct, coherrent and usable now.

I was born and raised in a world of C++, which treats class objects and primitives the same way. You can pass any variable around between functions either by value, or by reference. My dependency on this paradigm never became more apparent to me than when I finally made the switch to another language: Java.

C++

In C++, you can instantiate a class object, let's call it MrObject. You can then also create a pointer to it. Let's call that MrPointer. If you then decide you want access to MrObject's data in another function, there are a lot of ways you can do this. You can:

Pass a reference to MrObject into the function using the '&' operator, giving you direct access to the original instance of MrObject himself.

void MrFunction(MrObjectClass &MrObjectRef) {...}

Within MrFunction, you can use MrObjectRef just the same as if it were MrObject himself, because this is literally just creating another alias for the same exact object in memory.

You can also:

Pass by value, creating a new instance of a MrObjectClass inside MrFunction that is a duplicate of MrObject.

void MrFunction(MrObjectClass MrObjectDupe) {...}

When you pass MrObject into this function by value like this, a new class object called MrObjectDupe is created within the function. The original MrObject stays where he is, and is isolated from anything that is going on within MrFunction.

Things get a little more tricky when you create pointers to MrObject and try passing those into functions. For example, let's say you make a pointer to MrObject, like so:

MrObjectClass * MrPointer = &MrObject;

If you're not fluent in C++, what we are doing here is not creating a new MrObject. The asterisk (*) tells us that we are creating a pointer to an object of type MrObjectClass. The name of the pointer is MrPointer. The assignment here (=), combined with the ampersand (&), tells us that the specific object in memory that MrPointer points to is the one named MrObject (which must be declared elsewhere, but can, if you wanna be fancy, be defined through MrPointer via the new keyword, for example).

Now, if you want to pass MrPointer into a function, C++ also allows you to pass that either by value, or by reference. In other words, you can:

Pass a pointer by value; create a new pointer with the same value as the pointer you passed into the function. In other words, a new pointer, but one that points to the same address as the pointer that was passed into the function.

void MrFunction(MrObjectClass * MrPointerDupe) {...}

The asterisk must still be included so that C++ knows MrPointerDupe is a pointer. The side effect of this is that we can access MrObject through this duplicated pointer, but if we point MrPointerDupe at a new address (to a different object of MrObjectClass, or a new one, or to null), then the original MrPointer will remain unaffected, still pointing at (and modifying, if dereferenced) our original MrObject.

Alternatively, you can:

Pass a pointer by reference; in other words, we are not creating a new pointer to MrObject, we are using the same original MrPointer; we are just creating a new alias for MrPointer to be used within MrFunction.

void MrFunction(MrObjectClass * &MrPointerAlias) {...}

The asterisk in this case tells us that we are declaring a pointer to an object of type MrObjectClass, and the ampersand tells us that the pointer we are creating is not a new pointer, but just an alias (another name) for the existing pointer that is getting passed in to MrFunction.

Java

The nature of Java variables may not seem clear at first, coming from a C or C++ background. In Java, every variable you declare is a reference (except for primitives like int or boolean). Even primitive types such as int have Java class equivalents that give you reference type variables for handling primitive types (such as Java's Integer class).

Why is this so important? Just taking one important example, in C++, you might be used to creating a new instance of a class object, then being able to copy it into another second class object, like so:

// C++ code to create a new instance of MrObjectClass called MrObject.
MrObjectClass MrObject();

// C++ code to create a second, separate instance of MrObjectClass called
// MrDuplicate, by copying MrObject. Note that this results in two
// distinct class objects in memory.
MrObjectClass MrDuplicate = MrObject;

By contrast, in Java, when you instantiate a class object like so:

MrObjectClass MrObject = new MrObjectClass();

you are not creating a class object called MrObject. You are implicitly creating a reference to an object of type MrObjectClass, and that reference is called MrObject. In the following Java snippet, the two declarations result in only one distinct class object instance, which has two reference variables referring or "pointing" to it. (Though these variables are not pointers, I found it useful to think about them as such in the beginning, as a sort of "training wheels" approach to getting going in Java. However, of course you should try to build an understanding of Java's implicit referential nature as early as possible.)

// Java instantiation of a reference called MrObject to a nameless object
// of type MrObjectClass
MrObjectClass MrObject = new MrObjectClass();

// Java instantiation of a second reference called MrDuplicate, which
// actually refers or "points to" the same nameless object as MrObject
// refers to, resulting in only a single nameless MrObjectClass object
MrObjectClass MrDuplicate = MrObject;

It's very important to understand this so that you will understand what happens the first time you attempt to duplicate a class object, then modify your new variable only to see the changes reflected in your first variable as well! In other words, in Java, you cannot create a MrObject that you have "direct" C-style access to. Also, perhaps most importantly, it's critical to remember that reassigning MrObject or MrDuplicate does not overwrite any data! MrObject and MrDuplicate are references, and reassigning them simply points them to new memory locations. This can, in turn, potentially leave data unreferenced, in which case Java automatically cleans it up (but this unpredictable, sometimes seemingly sporadic process, often called garbage collection is another topic for another day).

Another reason this concept is so important to grasp early on in a programmer's exposure to Java, is because Java does not support pass-by-reference! In other words, even if you get used to the fact that everything in Java is a reference, you then have to accept that all functions in Java are pass-by-value! In other words, if I pass my MrObject reference from the example above into a function, the result is that within that function I cannot directly manipulate the original MrObject, ever!

What's happening within the function is we are creating a new reference variable whose value (referred or "pointed" address) is the same as MrObject's, because that is what's passed by value. Using the new reference inside the function, we can access our referred, nameless class object's public members. But if I try to reassign my reference variable from within my function, only the duplicated reference variable within the function will refer to the new destination address (nameless class object instance) I designate (including, possibly, null); the original MrObject reference outside the function will still point to (and protect from garbage collection) the original address (nameless class object) it originally referred to in the first place.

Are there ways to simulate pass-by-reference for those instances where you really want that behavior? Sort of (storing reference variables in an array or container class and passing the array or container itself into functions by value to preserve the original pointer-like variables within is the closest I can come up with so far, though these can feel like clumsy substitutes for true pass-by-reference). But when possible, it's better to just be aware of Java's idiosyncrasies and think in a Java-like way; its lack of pass-by-reference, and its requirement that all non-primitive class object variables are references; and to design around these features to the extent possible.

Thanks for reading!
-- Steven Kitzes

'const' vs 'final' - A Discussion

(For the tl;dr, click here.)

My latest forays into the realm of software development have taken me into Java country. I'm going to be taking my first classes toward my Master's in Computer Science in the coming months, and the bulk of the courses taught at my university are in Java. It will be my first time working with Java, so I thought it'd be a good idea to test the waters and get up to speed.

When I started writing my first entry level Java programs, one of the first features I instinctively tried to carry over from my C++ background was the const concept. After some research, I discovered that there is no const keyword in Java. Or, more accurately, const is a reserved word, that Java prohibits you from using in your code. It has no function in Java, but you may not use it as a variable or function name, either.

Instead, Java has a keyword called final, which seems on the surface to have a similar function to C++'s const. I wondered what the difference was between the two, and why Java's creators decided to block the const keyword from their language, I went on a quest to find out!

I came across a variety of myths along my search that I quickly busted via simple testing. For example, some folks believe that Java's final keyword can't be applied to primitive data types such as int, double, or char; but it can. Others believe that const C++ references are special, in that while they are immutable, the data they point to is mutable; however, this is also the case with a Java final.

As a side note, I found some information indicating that you do have the option in C++ of differentiating between a constant pointer to data, a pointer to constant data, and a pointer that is declared as constant to protect the otherwise non-constant data that can be dereferenced through it. If that sounds a bit confusing, it's much easier to understand when you see the code:


Cases 1 and 3 are simple enough, as far as syntax, though case 3 may be a little more confusing because of how we are protecting our data. Case 2, on the other hand, is a bit more confusing in terms of syntax; the const keyword appears after the pointer operator, even though the pointer itself is where we are applying the const functionality.

It would make more sense to me if the const keyword immediately preceded the item that it modified, in this case, the pointer operator. But sometimes you just have to accept that things are the way they are, and forge ahead!

So what is the difference between const and final? It turns out the primary difference is in initialization. In C++, a const must be defined in the same statement in which it is declared. In other words, you can't declare a C++ const and define it later in a separate statement.


On the other hand, a final in Java can be initialized in the same statement that it is declared; but you can also choose to declare it and then define it later in the program. This allows for each instance of a final to be defined by one of a variety of values (as you can see in the below example), but still ensures that once it is defined, it is constant forevermore.


As you can see in the above example, depending on whether 'someBool' is true, x might end up being defined as 10 or 20, but once it is set to one or the other, it can never be changed from there on out because it is final. Another important thing to note: when you are using a Java final without defining and declaring it in the same statement, you must be careful to define it before it is used, or you will have an error.

Hopefully this will help clear up some of the idiosyncrasies of and differences between C++'s const and Java's final!

Thanks for reading!
-- Steven Kitzes

Updating Environment Variables in Windows

This weekend I installed the Java Runtime Environment and the Java Development Kit onto my desktop and my laptop, both running identical Windows 7 environments. The installation onto the desktop went without a hitch. I ran both the JRE and JDK installers, got the JetBrains IntelliJ IDEA Java IDE up and running, and tried executing my first Java 'Hello World' program from the console. Shockingly, this worked on the very first try with no errors, and from the Git Bash, no less! This was such a pleasant surprise and unexpected result that it even prompted me to rename my dev blog to 'Unexpected Result'!

But for whatever reason, after going through all the same steps on my laptop, I couldn't seem to get Java to run from Git Bash. Upon checking my environment variable (typing env | grep PATH in Git Bash), I discovered that the JDK directory somehow didn't seem to have been added!

It turns out the solution was a simple matter of closing the Git Bash and reopening it! When a PATH variable change is registered, that change won't be visible to any running instances of Git Bash. It seems that Git Bash reads the PATH variable from Windows one time only, when the CLI is launched, and doesn't refresh it until the CLI is closed and launched again. This is true of other command line interfaces in Windows, as well (such as the Windows command prompt).

So if you've just added something new to a Windows environment variable, and it doesn't seem to be working from your CLI, make sure you have restarted your CLI after the environment variable was modified and it should be smooth sailing from there!

Thanks for reading!
-- Steven Kitzes

Parsing XML in ActionScript 3

I recently had a task handed down at work requiring me to parse XML data in ActionScript 3. It sounded simple, because AS3 includes documented libraries to handle XML content. But on my first pass trying to use them, I got unexpected results. After some investigation, I was able to understand what was happening. I was surprised the AS3 documentation didn't explain the behavior of the XML and XMLList classes in better detail, so I hope to fill some of the gaps with a quick write-up of my misadventure.

It was little trouble getting the XML file loaded into AS3, and I verified that the file was loading correctly by tracing the resultant XML object's contents in output. But when I tried to filter XML elements out of the XML object by tag name or attribute content, I would sporadically get unexpected results, or get no results returned at all (an empty set).

Just for some background, the XML files I was working with contained various lists of buttons for a video game UI. Each button had a button type denoted by its tag title, for example Slider, Toggle, or just plain Button. Each then had attributes, such as Name, ID, and DisplayText. So the XML would look something like this:


Note that none of the elements in the above example have any text content! My attributes have values, but the tags have no content between them. (This is legal in XML, but may have been unwise in retrospect, at least for debugging purposes.)

When I tried to filter based on button type (in other words, by tag name, e.g. Slider, Toggle, or Button) I would get strange results. When filtering MainMenu, I'd get a list of XML objects for Slider tagged elements and Button tagged elements, as desired; but would receive an empty string when filtering on Toggle tagged objects. Conversely, when filtering GfxMenu, I'd get the opposite; XML objects for Toggle tagged elements but empty strings for the others. What?!

At first, I didn't see why this would be happening, and I scoured the AS3 documentation to no avail. But after some experimentation I realized that when filtering, if only one element within the search range meets the requirements of a given search, AS3's XML class will return the text content of the element's tag automatically! And if multiple elements meet the search criteria, a list of XML elements will be returned.

I don't know if this was done to satisfy some language specifications or what, but that's what I was able to figure out!

Mystery solved.

Thanks for reading!
-- Steven Kitzes

Bitmask Basics

Working directly with bits is one of my favorite things to do as a programmer. I just find it fun! I haven't used these techniques recently in any of my projects, but I wanted to take some time to explain how bitmasks work, and some of their uses and advantages. Hopefully you'll agree they're very useful, and you'll see why I like them so much!

Higher level bitwise operations (also known as bit masking, bit flagging, etc) are great for a number of reasons. I find them quite fun, in addition to being useful and more efficient than other methods of Boolean comparisons and assignments. But before going into the methods and uses of bitmasking I should give a little bit of background on the topic. I'll be giving my examples in C++ because that's the language I'm most comfortable and familiar with, but bitmasking is possible in many languages.

First of all, what is a bitmask (or, what do I mean when I say bitmask)? In C++ (or any typed language), there are many data types that you are probably familiar with. These data types represent collections of bits, organized into bytes, stored in memory. We normally think about our variables and constants in terms of a given type (for example, int, double, or maybe even float), but behind the scenes an int or double still represents a contiguous set of bits.

Let's take the char data type in C++ as an easy example (it only represents a single byte, 8 bits). We can manipulate and compare data types such as chars in terms of their constituent bits. One way of terming such a collection of bits in this context is as a bitmask. This is often the case when using a char or int not to represent an actual character or integer, but rather to represent a condensed set of Boolean values.

At this point, you may be wondering: why is this useful? Isn't it simpler to just make a bunch of bool variables and compare those? Well, yes; that would be simpler, and easier for a human to read in the code. But it would necessitate long, convoluted argument lists if those bools ever needed to be passed around; not to mention that the bool type is very wasteful in languages like C++. Remember, the smallest size for a data type is one byte, 8 bits. So for C++ to store a bool in memory, it must allocate a full byte - 8 bits - even though only one bit is really needed to represent a Boolean value. Then, when making comparisons, an entire operation is wasted on each individual check against each individual bool. Holy smokes!

Alternatively, if we have a large number of Boolean variables that we need to track, instead of wasting an entire byte on a bool for each Boolean variable we want to track, we can track up to 8 Boolean values using a char's 8 individual bits, in the form of a bitmask! (Or, to expound on that idea, up to 16 values in a short int, 32 in a standard int, etc.) In addition to the efficiency achieved by storing several Boolean values' worth of information under a single primitive data type, this also means we can save a lot of time by comparing or manipulating several Boolean values in one go, as well! And of course, we can pass a bitmask as a single arg, which communicates a lot of Boolean data in a single variable, as opposed to needing to go through the hassle of passing multiple bools or encapsulating them in a container of some kind. So how does all this work...?

Example Time

Let's start by visualizing a C++ char's bits.

As an empty bitmask, with no bits turned on, our char would look like this:

00000000

If all the bits were flipped / turned on, it would look like this:

11111111

And with some bits on and some off, the bitmask would look like this:

00101101

Comparing two bitmasks against each other, or checking if a bitmask is either zero or non-zero works more or less as you would probably expect. Keep in mind, the following bitmasks are contained in char type variables. That's why they have 8 bits each.


C++ doesn't know or care that we're using our char as a bitmask. It just so happens that we are able to use bitwise operations and comparisons on our char. This means that while we may choose to perform bitwise operations and comparisons on our char, typical C++ comparisons like those on line 10 (comparing identical bitmasks) and line 14 (comparing differing bitmasks) return true and false results just as we would expect. Of course, zero / non-zero checks (such as on line 20) work as we are used to. And finally, assignment works as you would expect as well (such as on line 25).

The real value in bitmasks starts to become clear when we look at some of the special operators we can use to compare bitmasks against each other. These are the ampersand, the bar, and the carrot (& | ^). Let's take a look at what each of these operators does.

When using these operators with two bitmasks, the bit in each position of the first operand will be compared to the corresponding bit of the second operand. I call this vertical comparison, because it looks like this:

00101101
vvvvvvvv
10110110
vvvvvvvv
????????

The return value (the question marks) will be a new bitmask, whose bits will be flipped off or on (to 0 or 1 respectively) depending on the rules associated with the operator you are using. The ampersand (and, '&') checks to see if the corresponding bits in both bitmasks are both switched on, and flips the resultant bit on if so. The bar (or, '|') checks to see if the corresponding bits in either (or both) of the compared bitmasks are switched on, and flips the resultant bit on if so. Finally, the carrot (exclusive or, '^') checks specifically to see if one of the compared bitmasks has the bit in a given position switched on, while the corresponding bit in the other bitmask is switched off, and sets the resultant bit on if so.

This is a bit tricky to explain concisely, and a bit awkward to digest if you're not used to these concepts, so check out this Gist snippet for examples and visual representations. Here I show how each of these very useful operators works, and can be combined with a variety of comparisons and checks:

Real-World Example

Now that we have some idea of the mechanics of bitmask assignment and comparison, let's look at some real-world application. One challenge that lends itself particularly well to handling via bitmask is control input checking in video games. Video games, especially action-intensive games, must run at high frame rates, so performance is key and wasting a full bool data type's worth of data on each individual check is a monumental waste of space. As you'll see below, we can efficiently contain and check all the control input Boolean values we need in a single bitmask.

In this simple example, imagine a simple game with a perspective looking down onto the top of the player, who can move up, down, left or right, who can perform a regular attack and a special attack. Let's check out how we can manage the input for this control scheme using a bitmask! Note the use of constants here; having these constants available for use in assignment and checks is what makes bitmasks usable as arrays of Boolean values. Without the constants to check against, we wouldn't know what the individual bits in a bitmask represent! Also note the use of hexadecimal expressions to define the constants. I'll talk about this more in the example, but for now, just bear in mind that this is the easiest way (that I know of) to define a bitmask with a single bit flipped on in the position you want. (If you want to understand why I'm using hexadecimal the way I am, you need an understanding of how integers are represented in binary, which I won't explore in this post. An understanding of hexadecimal isn't required to understand this bitmask example, though!)
There is a lot of omitted error checking and pseudocode in this example, but it should give you an idea of how bitmasks can be useful in a real-world application.

Thanks for reading!
-- Steven Kitzes

Sum of Digits

While playing around and taking online classes in Python, I came across an exercise that I hadn't encountered before (in any language). The goal of the exercise was to write a function that took in an integer as an argument and returned the sum of the digits of the integer.

Because this exercise was nestled in a section of Codecademy that showcased looping strategies, for loops in particular, I starting trying to figure out a way to write a Python for loop to solve this problem. That maent I needed to figure out how to iterate over the digits of the int I received and add them up.

I had lots of wrong ideas. (Well, not "wrong," per se, but definitely "bad.") My first thought was to convert the int to a string, then iterate over the length of the string, taking each character and converting that back to an int to be added to a total (and then returned later). I didn't like this approach because it seemed clunky and inefficient. I have always felt that using strings to solve any arithmetic problem is probably among the worst ways to do it. It certainly didn't seem like the best approach here.

After a few moments of thought, I realized I could get the value of the last (rightmost) digit of any integer by taking the modulo (remainder) x % 10. Attempting to extrapolate this, I got caught up in my excitement and tried to add the values of x % 10^1, x % 10^2, ... x % 10^n, because this would translate somewhat easily to a for loop. This was sort of close to a good answer, and ultimately led me to a good answer.

I finally solved the problem by iterating through my integer x, adding x % 10 to my total and then dividing x by 10 with each iteration. This method gives each of x's original digits a turn in the ones' place, to be hit with % 10. I used a while loop instead of a for loop, and iterated through the integer dividing by 10 until my integer was 0 (rounded down). It worked like a charm ...

... until I tried a negative number! Python doesn't currently have native support for toward / away from infinity / negative infinity. When using modulo (%), Python always rounds down toward negative infinity. This meant that for any negative, single-digit number x % 10, Python would give me -1 as a result. So, my while loop would never equal 0 and would never exit!

My first thought was to write a needlessly complex snippet to catch negative numbers and use math.ceil() to ensure Python would round up in these cases. But that is more complex than it needs to be, since the remainder of any integer x / 10 will be the same (in real life) whether x is positive or negative. I fixed this by simply setting x = abs(x) (taking the absolute value of my integer) at the beginning of the function. Perfect!

Here is the code, in its beautiful simplicity (my first Python post!):


Thanks for reading!
-- Steven Kitzes

Using Recursion - Word Search

Amid efforts to broaden horizons and learn as much about different disciplines of development as possible, my C++ and heavy algorithms skills have gone somewhat untested lately. Although I have personal projects and work experience that I owe to a past rich in C++ and OOP, it's been a while since I revisited those realms. I decided it was time to test myself and see how I would do on an old challenge I'd tackled before, but not since almost four years ago when I first began seriously programming.

Long ago, a friend offered a challenge to help me learn. An aspiring developer himself, he'd taken several programming tests at job interviews. He forwarded one of them to me. The goals were as follows:

1. Goals:
2. generate a grid of random characters
3. display the grid to the screen
4. read in a dictionary file (more a word list, really)
5. iterate through the list, obeying a set of rules to search the grid for each word
1. Rules: using recursion:
2. when seeking the next letter in a word, navigate only one spot at a time
3. navigate only in the cardinal directions (up, down, left, right)
4. never use the character at a single grid location more than once on a given attempt
5. once a given word is discovered, don't search for more instances of it
6. display the number of words discovered
7. complete in 8 hours, 6 hours for bonus points

The first time I attempted this, years ago, it took me about a week's worth of evenings, totalling about 16 hours or so of total time. That's too long, and in the real world I would have failed that programmer test miserably. But it did give me an opportunity to learn about recursion.

I still need to sit down and plan out my recursive algorithms if I want them to be clean and efficient, but at least I have a firm grasp of the concept. This time around, I was able to solve the problem in under 5 hours. Here is how I tackled the task:

First thing being first, I generated a grid of chars using a two dimensional array to satisfy Goal #1, and slapped together a simple print function to cover Goal #2. Later, instead of simple characters, I came up with structs that contained both a char and a bool (for checking whether a given char had been used during any given check attempt). Then I had to (I admit) Google a way to read in a word list from a text file. Incidentally, Goals #3 and #4 were achieved with the same single while loop, but that part of the solution isn't relevant to the topic of recursion. (You can still see how I did it by viewing the project on my GitHub page, linked at the bottom of this post.)

It was finally time to sort through the grid to see if a given word was contained within it ... using recursion! First, how does recursion work? Recursion is a way of looping that's a little more confusing and involved than a simple for or while loop. These types of loops generally (if clearly and cleanly constructed) encapsulated chunks of code that run over and over again until a condition is met, then they stop looping and the program moves forward. Recursion, likewise, allows you to loop a chunk of code over and over again until a condition (usually called the "base case") is met. However, instead of a simple keyword call such as for or while, a recursive function is called. That is, a function that runs some code, and then calls itself, resulting in a looping effect.

• A recursive function runs some code and then calls itself to create a looping effect similar to a for or while loop.
• A recursive function iterates by receiving values from previous calls to itself as arguments, then checks those values to see if the "base case" has been met.
• (In some cases, a recursive function may modify and check a variable that is outside its scope and check that variable for the "base case".)
• When the "base case" is met, the ultimate result of the nested recursive function calls is returned down through the chain (or "stack") of calls to the original.

Take the following C++ snipped as an example. Notice how this simple function:
- accepts a value to get it started
- checks if the value has met the goal (or "base case") - modifies the value and passes it to another call of itself
- returns the result back down the chain



Here is a quick walkthrough of how this simple recursive function performs its duties on a call with the value 8 passed to it.

• First, recursiveExample( 8 ) is called. CompSci professors would describe this as placing a call to recursiveExample on the "call stack." In simpler terms, we're on the first layer of recursion and our value is currently 8.
• recursiveExample checks if the base case has been met; but value is less than 10.
• Since the base case was not met, we go to the else block. Here, value is incremented by 1, and recursiveExample calls itself, passing value (currently 9) as the argument.
• Now there are two instances of recursiveExample on the call stack; we are on the second layer of recursion.
• recursiveExample checks if value (currently 9) meets the base case, but it doesn't, so again we go to the else block.
• In the else block, value is iterated once more, now to 10 (can you predict what will happen next?). recursiveExample then calls itself again, passing value (currently 10) to itself as an argument.
• We now have three instances of recursiveExample on the call stack, and we're on the third level of recursion, and we have received 10 as the value for our value variable.
• recursiveExample checks the base case, and sees that it is met (value is greater or equal to 10)!
• Since the base case was met, recursiveExample returns value, which is 10. This removes one instance of recursiveExample from the call stack and returns us down to the previous call of recursiveExample.
• We are now back down on the second layer of recursion. Recall that the last thing we did on this layer was to call an instance of , the second layer of recursiveExample. We pick upu exactly where we left off, and the next thing to appear in code is another return! So that's exactly what we do; return the 10 on down the chain. The 10 is returned, and this second instance of recusiveExample is removed from the call stack.
• At last, we are back down at the bottom layer, to our original function call. Again, we pick up where we left off and the next piece of code is another return. So we pass the 10 on down, and since this is the final layer of recursion, the 10 is what ends up actually being returned to the program that originally called recursiveExample in the first place!

I used this idea of recursion in my word search program in checking the grid for successive letters of a given word. For example, taking the word "banana," I would search the grid for a 'b', then pass the word "banana" into my recursive function along with an iterator to represent the position of the next letter in "banana" that I was searching for. That function would check for the base case (in this case, if the letter position iterator had been incremented all the way up to the full length of the word I was searched for). If the base case was not met, the function would search the neighboring grid spots for the next letter in the word. If it found that letter, it would call itself, passing an incremented value as the iterator, with a reference to "banana" (or whatever word). This would continue until an instance of the letter-searching function met the base case (in which case it would return true all the way down the chain), or the function was unable to find the next letter while obeying all the rules of the WordSearch challenge (in which case it would return false all the way down the chain). Here, you can see what this recursive function looks like in my program:



You can see my WordSearch program in its entirety on my GitHub page! The recursive function itself is called checkNextLetter, and it can be found on line 76 of main.cpp, here. It's a bit more complicated than the simple example above, but you can spot some of the basic elements of a recursive function. For example, see lines 79 to 82, where checkNextLetter checks if the base case has been met and returns true if it has. Also check out lines 88, 95, 102, and 109 where checkNextLetter calls itself (and increments the spot value at the same time), creating the recursive equivalent of the looping effect.

Thanks for reading!
--
Steven Kitzes

Mounting Nexus 7 Using MTP

I'm sort of surprised no one else has come across this problem before, or posted this solution - at least, not that I could find - so I'm telling this story in the hopes it will help someone down the line. (If you want my solution to the problem, here's the Cliff's Notes at the bottom of this post.)

I ran into a problem today, trying to mount my Nexus 7 to my laptop, which is equipped with Ubuntu 12.10. When I plugged in the Nexus 7, I expected it to just work. I thought the device would appear on the desktop and in the Nautilus sidebar and just be accessible for file transfers over MTP. The device didn't show up.

I spent a good hour or so scouring the web for any help or hints I could find on how to mount a Nexus 7, running Jelly Bean, to Ubuntu. I found over a dozen convoluted work-arounds, updates, middleware installation guides, and other recommendations - all of which I tried (the free ones, anyway) and none of which made any difference at all. Using the work-arounds and various third-party software, I was able to determine that Ubuntu 12.10 could see the device, and obtain vendor and product ID information from it. But the device could not be mounted using MTP to transfer files. I got a variety of errors and warnings, which I followed up with Google searches that resulted in even more searches and fixes and updates and work-arounds, and another hour later, the device still wouldn't connect over MTP.

Scratching my head, I moved the Nexus 7 to my PC, a 64 bit Windows 7 machine. I plugged in the Nexus and it appeared in my Windows Explorer sidebar under the name I had given the device, but it was not expandable and the file system couldn't be accessed. I went into the Windows Control Panel and the device appeared there, under the correct name and in the right location, but again, couldn't be accessed. Flabbergasted, I started the whole search / update / word-around routine from scratch, this time on Win7. Again, to no avail.

I checked that the USB setting for the device itself was set to MTP, and it was. I tried restarting Ubuntu. I tried restarting Windows. I tried restarting the Nexus. I tried restarting them in varying orders. Nothing!

In desperation, I went into the USB connection setting on the Nexus 7 and switched it from MTP to PTP (the Camera protocol). I did this with the device plugged into the Windows PC, and this prompted the installation of new drivers for PTP. The device was now fully available as a media storage device, and gave me access to the part of the Jelly Bean file system where picture files are normally stored (DCIM, etc). Ah-hah! The device's file system capacity and available free space appeared, and were accurate. Ah-hah!

I switched back to MTP. No new installation of drivers, no pop-ups asking me what I wanted to do with the device, nothing changed on the surface. But when I accessed the device by name in Windows Explorer again, I now had access to the entire file system. Voila! I made some changes, moved things around, used the device some, and the file system disapparated from Windows yet again. Why?!

I repeated the steps again, did some testing (my QA experience played a role in this process), and ultimately came to the discovery that the Android device would only give Windows access to its file system when the device's "USB computer connection" settings menu was in focus, with MTP selected. Ugh!

Cliff's Notes:

To use an MTP connection between my Android 4.2 / Jelly Bean device and my computer, I must navigate to the "USB computer connection" menu on the Android device, make sure "Media device (MTP)" is selected, and leave that menu on-screen until I am done transferring files.

I want to note that I still can't get the device to mount on Ubuntu. I get a wholly new error, something about "Transport endpoint is not connected." But I have seen blog posts and articles about this error, as well. I'm sure I can spend another hour or two chasing wild geese around until I figure that one out, too. For now, I'm just glad I figured out how to knock some sense into the device itself!

Thanks for reading!
- Steven Kitzes

Value of an Ace

I made a Blackjack game to test myself on the JavaScript I have learned so far. (Link to it at the bottom of this post.) The greatest challenge I faced in getting the game to work was the variable value of an Ace. As you will know if you're familiar with the game of Blackjack, the objective is to get the player's hand as close as possible to a value of 21, without going over (which is an automatic loss). The player starts with two cards, and can continually ask for more cards until the player fears "busting" (going over 21), then the player may stop and pray that the dealer will do a worse job.

Aces behave in a special way in this game, as they are generally valued at 11, but their value changes if the player accidentally goes over 21. If the player is holding an Ace and goes over 21, the Ace will drop from a value of 11 to just 1. This value changes as the player draws new cards, and every Ace drawn will behave this way independently. So I needed to handle the scoring of a hand in a way that would allow the value of an Ace to be evaluated anew every time a new card was drawn.

When I started building the scoring function I ran into some problems. The first problem was timing. Because Aces change their value based on the non-Ace cards in the player's hand, I couldn't evaluate the player's hand in the order it was dealt.

Take the following example, in which the player is dealt (and the player hand is populated with) 5, 4, Ace, and 8, in that order. If I evaluate the cards in order, I would come to the Ace at a time when the cumulative value of the hand is still only 9 (first 5, then add the next card, 4). Since the 8 hasn't been added yet, the Ace seems like a great addition to the hand at this point, because even if I'm checking for bust (going over 21), 9 + Ace (11) would be 20, which is very close to 21. But then, when the 8 is added, the player would bust - I would want to evaluate the Ace as a 1, but it would be too late, the Ace was already evaluated!

One solution that came to mind early on was to reiterate through the hand any time a bust was detected, and check for Aces. I could subtract 10 from the total value of the hand for each Ace (if any) until the value of the hand came back to under 22 (leaving any remaining Ace valued at 11). But this struck me as a rather inelegant and scrappy solution. I wanted to evaluate the Aces on the fly so I wouldn't have to feel like I was "going back" and removing value that had already been added to the hand.

I got around this by adding the value of each non-Ace to the value of the hand and leaving out the values of any Aces, but counting the number of Aces. Only after the non-Ace value of the hand was evaluated, I began to evaluate and add in the value of each Ace. This is where things became complicated algorithmically. I needed to put together an algorithm to check not just whether an Ace would bust the hand, but whether an Ace would bust the hand in light of the fact that there is a variable quantity of Aces left to evaluate!

Here's what I came up with, I'll explain it below.

The good part is the for loop at line 24, where Ace values are evaluated. The for loop iterates through all the Aces. For each Ace, I check whether the hand would bust if the Ace was valued at 11, and all remaining Aces were valued at 1. If the hand would bust, the Ace is evaluated to 1; otherwise, it gets an 11 and the loop continues.

In retrospect, and as more experienced developers / mathematicians / Blackjack players will likely have noticed, this excessively elaborate Ace evaluation algorithm is entirely unnecessary! You only ever have to check whether the first Ace would bust the hand. If one Ace is valued at 11, you know all the rest must be valued at 1, because if two Aces evaluated to 11, you would already have busted with 22. Oops! If I continue to iterate this game with future editions, I will fix this inefficiency (because now it's bugging me).

If you want to try out the game, you're of course welcome! Be warned, it's fairly rudimentary as Blackjack games go, I was more concerned with getting JavaScript up and running on a website than with putting together a faithful representation of the game of Blackjack. (No betting, can't double down or split, no automatic win for Blackjack, but the basics are all there, single player versus a dealer.) Also, as a bare-bones first attempt at writing my own JS in the wild, the entire game exists in alert() and confirm() pop-ups, so apologies for all the clicking you'll have to do to play it! At any rate, here it is.

Thanks for reading!
- Steven Kitzes

State Based Menus

Recently I've been doing a lot of UI (user interface, or menu) work, specifically for console and mobile video games. This hasn't turned out to be nearly as easy as I originally thought it would be. To my relief, others have confided in me that even seasoned veterans of the gaming and mobile app industries find it difficult to engineer UI without things getting pretty kludgy. There are lots of problems to solve along the way, so I thought I'd share some of what I've learned along the way about designing and building game UI.

I want to concentrate on state-based menus. One of the easiest ways to navigate between screens, elements, and submenus of a user interface is using states. If you don't know what that means, my goal today is to try to explain it. I have seen it explained many times in terms that I, as a junior developer, did not understand, so I want to revisit the topic in a way that is as easy as possible to understand for beginners.

So, what is a state? Let's build an analogy using a very simple example. A light in your home has two states. One state, on, represents the light's status when it is (hopefully) powered and glowing. The other state, off, represents the light when it is unpowered and dark. The user can choose from these two states to tell the light how to behave. A simple, state-based interface! Of course, in computer programming terms, even this simple two-state interface can begin to look complicated. Obviously, if the light is off and the user attempts to turn it on, we apply power. If the light is on and the user tries to turn it off, we remove power. But what happens if the user tries to turn the light on when it's already on? What happens if the user tries to turn the light on, but there is no power? We have to account for these possibilities and more.

In the case of a menu system like one you might see in a video game, you might have a "Main Menu" state, a "Load Game" state, an "Options" state, and others. The "state" itself is stored somewhere as a variable. This can be conveniently handled with an enumerated index, which makes it easier for you (and other people working in your project) to read. Using enumeration at the lower level can be a bit intimidating for beginners, but think of it like this: you have a variable, an int called menuState, which is our state variable. Then you have a collection of words that represent constant values that menuState might represent. If your menuState integer matches one of the constant values you defined (an enumerated value), the menu is in a state that it recognizes! Consider the following snippet, defining (enumerating) some constant integer values that represent a menu's states, and setting up a menuState variable.

To connect this to our light bulb analogy, consider the menu system to be the light bulb itself - it can be switched from one state to another. For example, when your program is first loaded and the UI is initialized, the application might take the user to the Main Menu state automatically. But the user can then switch to another state, just as you can switch a light from "off" to "on." Just as you would use a switch to change a light's state from "off" to "on," you can use UI controls to change a menu's state from "Main Menu" to "Options Menu"! For a more concrete example of what I'm talking about, consider this next snippet. Read the comments if the code is a bit confusing right now.

For a more complex example, I'll take the case of a project I was recently assigned. One feature of a game we are making is an image gallery. One of the greatest challenges in building this gallery has been organizing the functions of the menu so that each element is only visible when I want it to be - in other words, when the menu is in the proper state! In organizing the gallery menu into states, the first step was to look at the features and functions the gallery needed to have.

According to the project specifications, the gallery needed to be separated into categories, with a set of buttons to select each category; a grid of selectable image thumbnails filling the rest of the screen; a popup window to display selected images full size; a dialog window for providing extra information to the user; a confirm window for making selections; and an alert pop-up to warn the user when trying to select an item that is not available. If that sounds like a lot of things to manage in one menu, I agree. I felt the same way the first time an assignment like this was handed to me. But using states, breaking these menu elements into manageable chunks was a breeze! I'll talk through my process to make it a little easier to see.

The first step I took was to break each function of the gallery apart into pieces, to be grouped into states based on when the functions would be available. For example, when the category buttons needed to be active, nothing else in the menu could be. The game needed to know that when the category buttons were active, arrow key and button presses would only affect the category buttons themselves. The solution is to tell the gallery menu that it is in the CategoryButtons state!

When the menu is in a given state, input should only effect the part of the menu that corresponds to the current state. For example, when the user presses the down arrow, if the menu is in the CategoryButtons state, the cursor should move down the list of category buttons. The cursor in the thumbnail grid should not move; in fact, it probably shouldn't be visible at all! Then, when the player finally presses a button to confirm a category selection, the state of the menu is changed from CategoryButtons to ThumbnailButtons. Now, the game sees the state change, makes the category button cursor disappear, and makes a cursor appear on the thumbnail grid. Now, control input makes the thumbnail cursor move, instead of the category button cursor! See the following snippet for an example of how this would look in code. Again, I've tried to add a lot of comments to make it clear what I'm doing in the code.

Obviously, there is a lot more to state-based UI development than just managing the states themselves. And of course, states can be used for a plethora of other tasks that I haven't begun to delve into, and there is a lot of other stuff to worry about when you are putting a UI together. States are just the beginning and help to organize your menu and control flow throughout the menu navigation process. But hopefully this will help you understand the fundamental state-based strategy for menu management!

Thanks for reading!
- Steven Kitzes

Motivation

I have struggled with the idea of motivation throughout my life. I was always told by family and friends that I was capable of great things. "You're so smart," they told me. "You'd be able to do such-and-such if only you'd get motivated." I could get in shape, I could find love, I could learn to program. All I needed was motivation.

That makes it sound so easy. You see people around you all the time who are motivated to do or attain things. They have reached, or are on the road to reaching those goals. You see the guy who is up and on his bicycle at 5am every morning to ride 60 miles. You see the guy who has his laptop out every morning at Starbucks monitoring the world financial markets. You see all kinds of people working hard to get what they want. Just do what they do: wake up in the morning and feel motivated.

I always wanted to be a computer programmer, to one end or another. And though I did genuinely desire to learn the trade, I never possessed the motivation. My friends and family told me to work at it, just keep plugging away, but I couldn't find the motivation. I used to beat myself up about it daily. It drove me mad, almost to tears. I truly wanted to be a programmer. So why, despite the desire, did I lack the motivation?

I tried telling myself I was motivated. I tried the infamous fake-it-till-you-make-it routine. I tried to feel motivated, to generate a sort of synthetic enthusiasm. I slipped in and out of periods of extraordinary effort - not effort toward learning programming, but effort toward getting motivated to learn programming. I even tried forcing myself to learn programming even without feeling motivated. This went on for no less than two decades.

But for some reason, no matter what I tried, I couldn't force it upon myself. It wasn't until after motivation finally struck me of its own accord that I realized desire and effort do not necessarily cultivate motivation.

One morning several months ago, I woke up, bleary-eyed, and gazed around the room, which was a shambles. The night, week, and month leading up to that morning had been a bit of a blur, part of a period of time I would define by its extraordinary lack of effort either to motivate myself or to learn programming. But as I came to my senses that fateful morning, I sensed that a new dawn had broken over the horizon of my life. I was going to get my ducks in a row. I was going to become a grown-up.

I redoubled my efforts as a Junior Programmer at work. I built my own libraries, not because I had to but because I wanted to know how it was done. I built very simple ones at first, of course. But I wanted to learn and grow and optimize and share and contribute. I was motivated. Not a single day has passed since then that I haven't learned something or improved upon something in my coding repertoire. Not a day has passed since that morning that I haven't spent an hour or so of my own free time learning. Sometimes more or less, but my free time is going into this on a daily basis. I am motivated.

Looking back on this motivational renaissance, I have attempted to identify the catalyst that led to the reignition of my passion as a budding programmer. I was somewhat dismayed to find that I couldn't. Perhaps to be more fair, I could speculate as to whether certain conditions in my life had performed a sort of slow-acting emotional catalysis. But I couldn't say in fairness that I did anything to motivate myself. Motivation came to me.

So if you are out there trying to figure out how to motivate yourself to learn programming, get in shape, or whatever it is you want to do, don't give up on the desire. It never hurts to practice or work toward your goals. But if the motivation doesn't come, don't be discouraged. When you are ready, life will let you know.