2013-09-26

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

2 comments:

Clayton Paplaczyk said...

Would love to try to follow along with the algorithm that you have created, but I completely understand about the plagiarism concerns.

Steven Kitzes said...

Sorry for the (years) late reply, but there's not much to follow. It's a direct implementation of the A* algorithm. A glance at the Wikipedia article on A* pathfinding will give you pretty much exactly what I ended up putting into code.