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.
Tuesday, July 28, 2009
Sunday, July 26, 2009
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.
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).
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).
Thursday, July 23, 2009
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.
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.
Sunday, July 19, 2009
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.
Tuesday, July 14, 2009
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
-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.
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.
Subscribe to:
Posts (Atom)