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.

Linked List Assignment
-Could modify data in object. May not want setter for linkedlistnode

Dijkstra's Algorithm
-No clear instructions for set up using Windows and Eclipse
-Managed to get it to work with unorthodox methods
-Start on costFrom, didn't get far
-Wondered if I needed to build my own data structure or did something already exist
-Spent an hour on set up, hour and a half on looking at problem
-Got help on what useful structures I could use for this problem

Continued Problems with AI project
-Destinations can sometimes be empty on start up
-Tried to determine solution to destinations list

Dijkstra's Continued
-Discovered my inital method for creating my data structure was poor
-N search of graph each time I did CostFrom and DirectionAt
-Boss suggested grid or hash table
-Decided to take grid approach first and abandon the linked list
-Discovered graph is 20 x 20 and uses integers from 0 to 19.
-Used old code

Dijkstra's Continued 2
-Progress was slowed by small bugs and errors
-Found that guessing for certain functions to run before others to be irritating and caused bugs
-When program crashed from bad code, window lingered until killed with task manager
-Had troubles getting Eclipse's debugger working with program
-Got costs working, red points were not
-Changed my DNode such that pi was gridcord
-Modified DNode methods
-Program began to work properly
-Planning to start working on Hash Set version next until I get next assignment

Dijkstra's Continued 2

I finally have the 2d array method up and running more or less. Most of my problem revolved around silly mistakes and odd bugs that normally comes with programming. One of the problems with the assignment that I found agitating was the fact that I had to anticipate that there would be an iteration through this program in which destinations (the array of grid coordinates) might be null. Another problem I found was when my code caused a crash, the window for the game lingered and couldn't be killed unless I used the Task Manager. Another problem I was having with the program was that I couldn't properly debug with break points at the like. I had to resort to print statements to tell me what was happning.

I have it such that the correct costs are printing out however the direction the red pointers is still wrong. It stalls when it tries to put up the direction to the destination. I'll have to hammer out these bugs. After a little bit of tinkering around, I tweaked my DNode (which held information for pi and d) such that pi was a GridCord rather than another DNode. After I made those modifications, the program worked as expected. There were no performance issues to note (other than the tower didn't shoot anything, that would be fun if it did, maybe that's a later assignment).

With the Grid method done, I may return to my linked list method (which is awful) or move on to working with a hash set. I might do the hash set one since that may be more promising or interesting at least. The linked list verison would be more of a test in patience for debugging than learning about Dijkstra's or Java.

Dijkstra's Continued

I was thinking about this particular program all week. The way I had it set up was bad. Really bad. The short of the long for what I had, it would've done an N long search for the entire graph each time it called costFrom and directionAt. In other words, it was an awful idea. I hate it even though I thought it up. After a little chat with my boss, he imparted words of wisdom on how I could do better. I feel ashamed I didn't think of the first suggested he gave. That would be a 2d array that would store my data (d, pi) in each index corrisponding to the x and y cordinates on the GridCoordinate. The next suggestion was use of a hash table. This was slightly less obvious but still... I should hang my head in shame for not thinking of it. This will use the GridCoordinate as a key and the DNode (my class that will hold d and pi) is the value.

After poking at the x and y coordinates of the gridcor's I found that all the values are greater than or equal to 0 (in this case it was 0 to 19). For now I will set aside my awful (and probably not working) linked list version and do the grid version. It will probably lead me to a working solution faster than my first method. I'll go back to my first iteration later.

Fortuantely, most of the code is the same from my linked list attempt. So not much is truely lost. Time to just sit down and work on it.

Wrote down a majority of the code, but will test it more later. I'm having null pointer exceptions. Figures.

PS: Professor, Stephen has been trying to get in touch with you about the next assignment.

Continued problems with AI Project

Making progress on this assignment has been difficult. Other than tackling the part where concept meets code, I am having another issue which may or may not lie within my domain of fixing.

I can't very well make much progress without having a destination node to start from. Otherwise I have no place to start from. After a little bit of trial and error I found out the destination list being handed to me in cashe() is empty. I assume that is very much needed to perform even the first step of Dijkstra's algorithm. No method is coming to mind to start testing unless I can take the first step of the algorithm. Perhaps the relax method, but until I know what is wrong with destinations, I can't make much progress. I could try digging through the robot defense JAR but I don't think there would be much in there that I could understand.

Some of my guesses what the problem is:
- I have an older version that doesn't work.
- My configuration is wrong somehow.
- I need to be doing something with destination (even though its empty) inside of the cashe function. I doubt this possibility.

This program had to have worked at some point for someone else so I figure it must be one of the two likely possibilities. At the very least I'll start laying the ground work for the rest of the algorithm.

Dijkstra's Algorithm

This game is like a tower defense game but we are supposed to program the search algorithm to find the exit point.

The first thing I started with was setting up the program. The directions being only for linux machines didn't help me at all. So a great deal of time has been spent fumbling around with Eclipse just to make the program run. After finally picking the correct main to run, I found that only Stub was showing up as the method that was available. After must trial and error, mostly error, I managed to get the program to work without having to depend on the terminal instructions.

Here is what I did:
1. Put the Meta-Inf folder into my src folder.
2. Put my new routemap class into the src folder under the default pacakge.
3. Placed the robot defense jar folder in the src folder along with the metadata folder (don't know if that's necessary or not).
4. Renamed my class to LudwigSDRouteMap and modified it in the metadata folder.
5. Ran the game on the method PrjSingleDestinationRoutes.
6. It works!

Now that the set up is out of the way, on to the meat of the assignment, building my search using Dijkstra. For that I will start to look at the comments littering the class file. The first thing I set about doing was looking into building my graph necessary to do Dijkstra's Algorithm. While working on costFrom I was growing frustrated that I couldn't check and see if the node I was on was an end or start.

For the moment I'm giving up on the problem. I suppose one of the things I'm confused on at this point is do I need to create my own type of nodes to calculate the path and should I start on the cashe method first? I'll fiddle with it more later.

I spent about an hour setting up the program and about an hour and a half on looking at the problem and trying to figure out how to tackle it.