Objective

This homework attempted to find the global shortest path in an obstacle course from any arbitrary start and any arbitrary end goal. If has been shown that the globally shortest path lies along the global tangent graph. This graph is made up of all of the lines that connect the all of the vertices of all of the obstacles in the environment. Obviously with even a few obstacles this graph can be rather large. Most tangents can be eliminated because there is no line of sight between them.

The method I used is very straight forward

1. Extract the set of vertices of the obstacles in the environment.
2. Traverse the tangents, which consist of lines between the vertices (nodes) Eliminate all tangents which not pass through obstacles (no line of sight) and all tangents which are duplicated.
3. Search the vertices for the shortest path.
4. Display the results.

Implementation

The code, which I wrote to perform these functions, was written in Lisp of course. I was able to reuse a few of my functions from previous homeworks. The full code is available on the web page. I wanted to highlight some of the core functions used.

1. If the top node has a straight view to the goal then this node is removed from the list and the distance from the start to the goal is calculated in the found-goal function.
2. If the top node has children nodes as determined by get-visible-nodes then the top node is removed and the children are put in its place. Magic, the expansion is done.
3. In the case were there are no children nodes then the branch is removed.

(defun expand-node (nlist)

(if nlist

(let ((node (car nlist))

(children-node (get-visible-nodes (car nlist) nlist world-objects)))

(cond

((if (line-of-sight? node goal)

(found-goal

(add-node-lineage goal node))))

((if children-node

(expand-node (append children-node (cdr nlist)))))))))

This recursive function determines the list of other nodes that are visible from the current parent node. It does this in the following steps.

1. The list-of-objects is simply a list of all of the objects in the world. This list includes obstacles, goal, starting position, and all of the vertices of all obstacles. This list is searched for all of the vertices by comparing the name of the object to ‘node.
2. If the object detected is a node then it is tested to see if it is in the line of sight of the parent node AND it is not already duplicated by searching the list-of-nodes (this is a list of traversed nodes)
3. If step two passes then the node is added to the result and the recursion starts.
4. If step two fails then the recursion continues with the next object in the list of world objects.

defun get-visible-nodes (parent-node list-of-nodes list-of-objects)

;;node is the vertex that we want to expand

;;list-of-nodes is a list of already traversed nodes

;;list-of-objects is a list of world objects -- the recursion

;; will stop when there are no more objects in the list-of-objects

(if list-of-objects

(if (eq 'node (get-value 'name (car list-of-objects)))

(let ((child-node (car list-of-objects)))

(if (and (line-of-sight? child-node parent-node)

(not (duplicated? child-node list-of-nodes)))

(cons (add-node-lineage child-node parent-node)

(get-visible-nodes parent-node list-of-nodes

(cdr list-of-objects)))

(get-visible-nodes parent-node list-of-nodes

(cdr list-of-objects)))))))

It was this function which gave me much grief. With more time I probably would have fixed it. Ther goal here was to determine if two objects could see each other unobstructed. A temorary object called a ping-object was created that would traverse the path from object A to object Z. The detect colision would search the world-object list and determine if an object collision was eminent.

(defun line-of-sight? (objectA objectZ)

;;Determine if the two objects can see each other

;;if a ping-object moves from objectA to objectZ without

;;hitting anything else then the two objects can see each other

(progn

(setq ping-object (copy-alist ping-proto))

(set-value 'xpos ping-object (get-value 'xpos objectA))

(set-value 'ypos ping-object (get-value 'ypos objectA))

(set-value 'orientation ping-object

(get-orientation-towards-object objectA objectZ))

;;This "if" statement is a very big kludge. The get-first-object-in-direction

;;function will not detect objects which are on the same x or y

;;values. There is a hard check placed here to capture these

(if

(or (= (get-value 'xpos objectZ) (get-value 'xpos objectA))

(= (get-value 'ypos objectZ) (get-value 'ypos objectA)))

(if t t)

(let ((collided-object (get-first-object-in-direction ping-object)))

(progn

(describe collided-object)

(if (and

(= (get-value 'xpos collided-object)

(get-value 'xpos objectZ))

(= (get-value 'ypos collided-object)

(get-value 'ypos objectZ))) t Nil))))))

(defun add-node-lineage (child-node parent-node)

(progn

(gp:draw-line display-pane

(get-value 'xpos child-node)

(get-value 'ypos child-node)

(get-value 'xpos parent-node)

(get-value 'ypos parent-node))

(set-value

'lineage

child-node

(append parent-node (get-value 'lineage parent-node)))

))

Found-Goal and Get-Trip-Distance

These utility functions are used to determine the length of path once a path from start to goal has been found. The minimum distance is recorded and reported and the end of the search. The path traversed by the shorted route is also saved in the "best-trip" list. This list is drawn at the end of the simulation.

(defun found-goal (node)

(let

((distance (get-trip-distance (get-value 'lineage node))))

(if (< distance shortest-distance)

(progn

(setq shortest-distance distance)

(describe distance)

(setq best-trip (get-value 'lineage node))))))

(defun get-trip-distance (list-of-nodes)

(if (and (car list-of-nodes) (cadr list-of-nodes))

(+ (distance-obj (car list-of-nodes) (cadr list-of-nodes))

(get-trip-distance (car list-of-nodes)))

0))