Death Star Wayfinding

2 minute read

You can see the relevant pull request on GitHub.

Background

In my senior year of my Bachelor’s degree, I took ECS 193AB (Senior Design Project) with Professor Xin Liu. This two-quarter class sequence was the capstone design project for that degree.

My team’s choice of project was to improve the Division of Social Services Wayfinding application. The program was designed to help people navigate UC Davis’ Social Sciences and Humanities Building, designed by Antoine Predock. Students call it the “Death Star” as it’s well-known for being confusing to navigate.

Project

Our team divided ourselves into pairs of two to work on separate portions of the program. My partner and I worked on designing a linter to clean up the SVGs that mapped out the Death Star.

Scalable Vector Graphics (SVGs)

Scalable Vector Graphics (SVGs) form the basis of the wayfinding application. You can see an example SVG in the gallery below. The base layer defines the layout of a building’s floor and its associated rooms. Lines between the rooms are valid paths that someone can travel on. There are lines that appear to go nowhere; these are “portals” to connect different floors and thus different SVGs.

Wayfinding Algorithm

The wayfinding itself is done via Dijkstra’s algorithm. To facilitate this, the set of SVGs defines a graph via the following:

rooms form nodes in the graph and are the starting and ending nodes for pathfinding
paths form the edges in the graph
points where paths in a SVG meet are intermediary nodes to connect rooms
portals are edges between nodes defined in different SVG files

Finding and Correcting SVG Errors

Due to impreciseness in SVG editors such as Adobe Illustrator, subtle errors can pop up and affect the correctness of the pathfinding:

rooms or nodes can be unreachable
two nodes can unintentionally be “close” to each other instead of being the same node, causing pathfinding errors
portals can be ill-defined and thus not connect to other portals properly

To solve these issues, my partner and I wrote a linter in C++ to analyze the SVGs. The linter uses a breadth-first-search to determine connectivity and to determine if portals are defined correctly. For “close” nodes, the linter calculates Euclidian distances between all points on a floor and displays point pairs that are within a certain threshold distance.