View this PageEdit this PageAttachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

Case Study Milestone 5

Edit Case Study Milestone 5 here.
Uploaded Image: demo.jpg

Introduction

In this milestone, we were required to draw a route between a start and an end building. Frankly, we found this project more challenging than making the whole thing 3D. This was because we had to write code that would navigate curved roads, yet still be able to find almost the shortest path. This could have been a lot easier if we had chosen straight roads in the beginning.

The Obstacles and the Solutions

First and foremost, our problem was to develop some way to navigate around a curved road. After some discussions amongst our group, we decided the best solution to the problem was to make intermediate nodes. These nodes would help to break up a long curved roads into smaller linear segments. So a road might be made up of, for example 5 nodes. These 5 nodes connect to each other. This does not form a perfect curve, but it comes reasonably close. We created a text file which held all the coordinates of the nodes. Each node is also assigned a number which makes it unique (this allows us to identify where we are on the map). Once the curve problem was solved, we had to overcome another obstacle. Find the path from one point to another. The solution for this was not as simple. We thought of using Djkhra's algorithm, but it turned out to be rather difficult to code. So we decided on an easier approach. We developed our own algorithm which formed a tree out of the map. Then it did a breadth first traversal on the tree until it found the ending node (This is very similar to what we learned in CS1322). Using this algorithm, we could find the path from one building to another and return it in an array.

The File Loader



The first order of business was to load a text file which held all the coordinates of our nodes. We made a class Loader which opened a text file and read in all the coordinates. It stored all of these into an array. This array was then fed into a function called interlink. The job of this interlink function was to find which node was adjacent to which other node. The reason we need to do this is to develop the tree on which we will do a breadth first search. So the interlink function takes in the array and returns another array which has the information of which node is linked to which other node. Once we are armed with this information, we can actually do some serious work.

The Tree


In order to build the tree we have to use the array we receive from the Loader file. We traverse through that array and enqueue each node if it has not been visited before. If it has been visited we ignore it. This visited list is another array that we maintain. Obviously, when we enqueue a node we add it to the visited list so we don't enqueue it again. When we dequeue a node, we try to figure out which other nodes to enqueue. This is where we use the array from the Loader file. Since we know that node X links to node Y and Z, when we dequeue X, we enqueue Y and Z. This is basically a breadth first search of a map. We repeat this process until there are no nodes remaining. You may ask how we remember the path even if we do find the ending node. Well, the solution was to make each node remember what path it has taken. So whenever a node is dequeued, the paths of the node are updated. Once the final node is reached, we just pull the path out and that's the answer.

Conclusion


There were a couple of important lessons to be learned from our experience. First of all, START EARLY. We stayed up the whole night since we started barely one day before. Second of all, when you want to make a text file to store data, please look for the easiest way to do it. We spent 7 hours writing the text file with all the nodes (and it still had a lot of typos in it, which caused our program to crash more times than we can remember). The easiest way is to write a small program (perhaps in VB or Java) which allows you to pull our coordinates etc and writes them to a text file in the format you want. This may take an hour, but it'll save you a lot of frustration and time in the long run. Finally, we highly recommend using text files to store data. Don't HARD CODE anything. The reason we were able to pull off our next few projects easily was because we didn't hard code anything. Just changing the text file changes everything. It's really convenient.

CS2340.st

Uploaded Image: UMLDiagram.gif

Link to this Page