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