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

Squeakers' M5 Case Study

Milestone 5: Help People Find Their Way

Task:
Allow users to find routes between two addressable buildings and show the route.

Why Is This Important to Get Right:
We will need this to work so we can make up tours for the 3D implementation. Also, we want something very general to work with an imaginary campus.

Design Ideas:
Use MapQuest to find a route using the real address of the buildings. Parse the resulting HTML and then draw the route from there.
This is problematic for a few reasons.
1. Parsing in Squeak seems somewhat confusing. We have never done it before. Learning is not always a good thing.
2. If we use MapQuest and we want a really portable system, our imaginary map won't be so imaginary. Pretty much, we will have to use real roads that are in existence.
3. Sometimes MapQuest does just plain out weird things. Like give us a road that is not on our map. That would so totally not work.

Make a graph and search it to find the route. Seeing that the whole group was familiar with the Breath First Searching algorithm, this made sense. We could make a really basic algorithm (that was pretty much taught in previous CS courses) to find the path. This seemed like a good idea and it would be nice and portable.

How We Implemented Our Design:
So, we knew we needed some way to make a graph. Fortunately, our design already had some graph-like properties. Each street knows how it can be entered (from a building) and how it can be exited (onto another street). So, we already have an internal representation that is very graph like.

Now, we needed a few more things to make the graphing algorithm work. Like, a queue. So, we made a queue and a node that would hold the information we needed. So far, not too bad. Now, all we had to do was write the algorithm.

This is where the problems began. We had been storing different things as dictionaries and ordered lists and all sorts of things. Make these different collection act in the way which we desired, took a long time to figure out. (Good thing Bill is patient.)

How the Algorithm Works:
Pretty much, what happens is the algorithm takes the two buildings. After checking to see if they are on the same street, it begins to do the actual graph searching. Starting on the first street, all of the possible exit streets are added to the queue. Now, the queue undergoes extensive looping. Pretty much what happen is a street is dequeued. If it is the actual street the second building is on, the path is found. Otherwise, you get all of its exit streets, make new nodes for them, and update their internal path (ie how you actually got to that street). Then you enqueue these nodes. Streets are not allowed to be repeated. Pretty much, what we find is the path with the least number of turns. This is great for buses.

The Algorithm:
This may have formatting issues...I tried...




findPathFrom: aBuildingName1 to: aBuildingName2

  "Finds a path between the buildings and stores it into route"



  | queue nodeToAdd currNode pointsCol pC building1 building2  sn1 sn2 s1 currStreet streetsSeenCol sNames |



  queue _ Queue new.

	

  building1 _ map buildingWithName: aBuildingName1.

  Building2 _ map buildingWithName: aBuildingName2.

	 

  sn1 _ building1 streetName.

  sn2 _ building2 streetName.



  s1 _ map streetWithName: sn1.



  pointsCol _ OrderedCollection new.

  streetsSeenCol _ OrderedCollection new.



  pointsCol add: (building1 streetLocation).			



  "If both buildings are on the same street, return"

  (building1 streetName = building2 streetName) ifTrue: 

    [ pointsCol add: building2 streetLocation.  

      route _ pointsCol.					

      ^self 

    ].



  sNames _ (((s1 exit) keys) asOrderedCollection).



  "Add the exit points of the first street to the queue"

  1 to: ((sNames) size) do: 

    [:number |  nodeToAdd _ StreetNode new. 

      nodeToAdd name: (sNames at: number).		

      pC _ (pointsCol copy).				

      pC add: ((s1 exit) at: (nodeToAdd name)). 	 

      nodeToAdd pointList: pC.			   

      queue enqueue: nodeToAdd.			  

      streetsSeenCol add: (nodeToAdd name).		

    ].



  streetsSeenCol add: sn1.

	

	"(true) whileTrue:" 

  50 timesRepeat: 

    [ | seen cN |

      seen _ false.

      currNode _ queue dequeue.

      currStreet _ map streetWithName: (currNode name).

      ((currNode name) = sn2) ifTrue: 

        [ currNode addPoint: building2 streetLocation.

          route _ (currNode pointList).

          Transcript show: 'About to return'; cr.

          Transcript show: (route printString).

          ^self 

        ].



      sNames _ (((currStreet exit) keys) asOrderedCollection).



      1 to: ((sNames) size) do: 

      [:number | seen _ false. 

        streetsSeenCol do: 

          [:aName | ((sNames at: number) = aName) ifTrue: 

             [ seen _ true.]. 

          ].   

        (seen = false) ifTrue: 

          [  nodeToAdd _ StreetNode new.

             nodeToAdd name: (sNames at: number).

             cN _ (currNode deepCopy).  

             cN addPoint: ((currStreet exit) at: (nodeToAddname)).

             nodeToAdd pointList: (cN pointList). 

             queue enqueue: nodeToAdd.

             streetsSeenCol add: (nodeToAdd name). 

          ].

        ].

   ].



Milestone5.zip

Link to this Page