The end

Ran into a weird error that prevented me from saving....yes, saving. For future reference...if you copy and paste the "π" character into Eclipse, it will not let you save until you remove it, even if it's in a comment.

Well, I encountered many bugs, most of them were null pointer exceptions. I fixed most of my problems by providing null checks at the beginning of functions such as directionAt. The first time directionAt is called, my grid has nothing in it.

Constantly throughout this assignment I found myself wanting a little more explanation about each method. The headers themselves provide information for what they do, but not why/when they're called. This got me into a lot of trouble because the methods are called at times I didn't expect, causing null pointer exceptions. Something simple like..."This method assumes a non-null node, if null then return null" or something to that nature.

On the second map, I ran into a bug. Anytime the ants move to the left, they spin. I'm not sure what's causing that but I don't think it's in my code. The ants don't seem affected though, they still travel in the correct direction, just spinning.

Aside from the bug described above, the project seems to be in perfect working order, I played with it for about an hour. Overall, Dijkstra's Algorithm is fairly straight forward once you convert it to "English", but converting it to code is the real challenge of this assignment. The open-endedness of being able to choose your own data structure is kind of cool, gives you a little satisfaction when you complete it that you made a choice and made it work. I found the given algorithm using u,v,w,Q,S was extremely turse and hard to read. The first thing I did was find a guide that expanded those into words I could get my brain around.

NEXT!

Debugging begins

I have completed the first draft of code and have turned to debugging. I fixed a few minor array bounds errors but I kept getting a persistent error when I tried used destinations.get(0);

I found that destinations.isEmpty() returns true and I'm not sure if I am able to continue if I don't have a destination available.

Dijkstra's Algorithm - Linked List

I managed to get the Linked List version of the assignment completed. Now that all remains is the challenge of the Hash Set (if I can figure it out). I may need to look into Sets more to see if I can gain a little more understanding before attempting it.

One odd thing I encountered when testing the linked list version I have was that it seemed to clobber the results of other maps. Once I click to select anther map, the error results for the other maps pop up. This could be a serious problem when grading this assignment. Every map after the linked list map was wrong. It's as though I destroyed a resource. After a little poking around, I discovered that if I use the remove method on the destinations list, I permanently remove that coordinate from the destinations list. Apparently that list was passed by reference or something of the sort. Either way, this allows the programmer to clobber the destinations list. If a student, by accident uses the remove method, then the destination is removed from the list for the remainder of the time programmer is running the game. I'm not certain where cache for the route maps are called so I'm not certain if I can fix it. I tried using different search methods (like for SDRouteMap or Cache in the project) but I couldn't find it. Unless I can un-bury it, all I can do is leave a warning of what might happen if the destinations list is tampered with.

Note: Giving in to my mischievous side, I even tried to insert a different destination GridCoordinate into first element of the destinations list. As I predicted, it changed the destination node.

Dijkstra, first look

Initially the program is a little daunting, but I think I have a clear grasp on what Dijkstra's Algorithm is supposed to be doing....it will just be another story to convert it into code.

I decided that the best data structure I can think of to simply implement for this assignment is an array of arrays, or in this case a list of lists. I chose to make my own type of data container/node to hold all the information that was required for the grid. I found this a little easier since I'm not entirely familiar with the interface of the provided data structures. I was initially confused as to what some of these functions were for, especially in regards to the costFrom() function. But after talking to Dr. Wallace, it turns out that most of the hard work is done for us, this is simply a getter method for printing. I was also confused at first as to what the coordinates of the destination point were, I didn't find it very clear that the first argument of the destinations was the clear and definite choice. (Thanks Soren!)

I spent a fair bit of time exploring the methods provided for retrieving specific attributes from the GridCoordinate object and how I could use those to complete this assignment. I have to say, my Java skills have jumped quite a bit since I started this assignment, I really had to learn a lot to understand how each object knew how to access what. Our class has had very little Java experience, so all of this helps a great deal.

The custom container will store d, pi and a reference to the node it represents. This will make all my information readily available.

To create the grid, I need to know the size of the world we're dealing with. The only way I know of, and it's a hideous one...is to just iterate through the entire list of nodes and take the largest value of both x and y to determine the size. It is terribly inefficient but it does work for the time being until I find a more efficent method.

I decided to create my list of unvisited nodes at the same time as creating the grid to increase efficiency and reduce the chance of a bug implementing it later on another way.

http://renaud.waldura.com/doc/java/dijkstra/ Is a nifty little website I found with a nice rundown of the algorithm with a few examples, ones that I'm sure I'll be using to debug this beast when I get to it.

Dijkstra's Algorithm - Helping Stephen

After answering questions for Stephen I realized there were a few things that might be handy for future uses of the assignment.

Useful items that might be useful to add to the assignment:
- The EnumerableGraph could contain the dimensions of the graph.
- Provide a little more documentation on how to get the edges for the GridCoordinate.
- Potentially suggesting on how to store our own data type (though that might take too much away from the assignment).

Dijkstra's Algorithm - Hash Map

For the time being, I figured I should just attempt the Hast Table problem using a Hash Map. Doing the program again using the Hash Table was fairly easy. All I had to really change was how I handled the nodes in the "data structure" otherwise the rest of the code/algorithm was the same. It functions the same as the other implementation. This took roughly 30 minutes to do. I suppose I should focus on the Hash Set a bit more to see if I can make sense of it.

If I went back to the linked list version, I would have a fair amount of trouble considering the searching and overhead involved with that method. Plus the overall clutter and complexity I created by trying to do a "simple" method of storing my "DNodes."

I believe the most of my time was spent wondering how to store data regarding my Search Algorithm. That consumed the most effort and time. Dijkstra's itself was rather easy to understand after the small lecture by my supervisor, most of the problems I had relating to the assignment were purely design issues.

Dijkstra's Algorithm - Hash Set

Working on Dijkstra's again with the Hash Set. This time around its learning about Hash Sets rather than understanding the Dijkstra's algorithm. I'm not sure yet how its any different from a hash table, though the set usage idea is strange. I suppose I am wondering if each HashSet has only one key and value or you can hash to each element in the set? It will require more reading.