Software / Program Structure

Interrupts

The general structure of the program is to force a timer0 overflow interrupt at a certain time interval for the purpose of executing four tasks. By setting the prescalar to 64 with an 8 MHz clock and preloading TCNT0 on the MCU to 256-125, we force TCNT0 to overflow every 125 clock ticks, which corresponds to 1 millisecond. Every millisecond, the timer0 ISR is executed and checks if any of the tasks need to be performed. Each task has a given timer associated with it that is decremented every interrupt, except for task 3, whose timer acts as a flag, which is set to zero when the task needs to be executed. Once a timer for the task reaches 0, the task is performed and the timer is reset. There is also a timer1 interrupt routine that increments the system time by one second every interrupt. The interrupt is executed every time TCNT1 matches the value in the OCR1A register. By setting the prescalar to 256 with an 8 MHz clock and setting the clear on match bit, we force TCNT1 to increment every 256/8 = 32 microseconds and to reset back to 0 when it matches OCR1A. We initialize OCR1A to 1000000/(256/8) which is the number of times TCNT1 needs to increment to correspond to a match every second. Inside the TIM1_COMPA interrupt, the system time is updated by one second, and adjusting any overflow values (such as changing 60 seconds to 0 seconds and 1 minute). A third interrupt routine is need for the serial communication between a GPS receiver and the system. When the UART_RXC interrupt is enabled, it executes every time a character is received in the UDR. The interrupt stays enabled until the system receives a return character, at which point, the system packages the NMEA sentence and disables the interrupt. Until the system interprets the command/data, the interrupt will remain disabled. Once the system processes this input, the interrupt will be re-enabled and will proceed to package the next NMEA sentence.

Tasks

Task1:
This task is executed every 30 milliseconds and processes keypad button pushes. Each time the task executes, it reads the keypad to see which button is being pushed. This state machine also debounces button pushes. Each time a button is pushed, the program calls update_menu( ). This function is responsible for setting state variables, based on the current state and the button pushed. This function then calls display_menu( ), which changes the LCD screen based on current state variables. One feature of the LCD was a wrap around scrolling feature used to scroll through the menu options. We implemented this by storing two state variables, scroll_number and select_number. Scroll_number kept track of which menu option appears on the top line, and select_number indicates which line is currently selected. See source code for a detailed explanation of implementation.

Task2:
This task is executed every 250 milliseconds and implements a blinking cursor. A blinking cursor is used when the user is entering his/her current coordinates or entering a new date or time. This task also refreshes the LCD screen if the current menu screen is the Nearest City screen or Display Coordinates screen, but only if the input mode is NMEA. The reason for this is that the user may be in transit, in which case his/her coordinates will be constantly changing. Thus, the distance/direction to the nearest city would be changing, or the nearest city itself.

Task3:
This task is only executed when the date needs to be changed due to an overflow of the time incrementing. When the day reaches the last day of the month, and the time transitions from 23:59:59 to 00:00:00, the timer3 flag is set to 0, indicating that task3 needs to be executed. This task then proceeds to update the day, month, and year as necessary.

Task4:
This task is executed every 250 milliseconds and checks to see if a NMEA sentence is waiting to be processed. If there is a NMEA sentence is waiting to be processed, then the task extracts the current latitude and longitude coordinates and sets the appropriate state variables.

Database

In order to compute the shortest path and directions between cities, we needed to construct a small database of cities and interstate connections. This database consisted of 32 predetermined cities, each of which had at least one interstate connection to another city. Each city was assigned a number 0 through 31. Each time a computation involving a city was made, this number was used to identify the city. Whenever the city needed to be printed, we would use the city number as an index to an array that contained city names. We mapped out each of the connections and stored the information in a one-dimensional character array. The format of the array was as follows:

The array consisted of a set of connections for each city. Each city has one or more connections, which were stacked one next to the other in the array. And each city’s set of connections were stacked one next to the other to form one large array. To access a given city’s set of connections, we stored an array of integers, which stored the starting position for each city in the connection array.

The connection array is structured as follows:

city00

city01

city02

city03

city04

.....

city27

city28

city29

city30

city31

Each city (a multiple of 6 bytes) in the connection array is structured as follows:

connection00

connection01

connection02

connection03

.....

Each connection was represented as a set of 6 characters (bytes):

connecting city

interstate

direction

distance

The connecting city field corresponds to the city number of an adjacent city.
The interstate field is the interstate that connects the city to the connecting city.
The direction field is the direction to the connecting city.
The three distance fields sum up to the total distance between the two cities on the interstate.

The other arrays used in the program were indexed and referenced via city number. These arrays include the latitude and longitude coordinates of each city. For example, the latitude for city00 is stored in latitude[0]. For a complete listing of all city database data, see Appendix.

Algorithm

To compute the directions between cities, we implemented a shortest path algorithm that used our city connection graph. The algorithm that we used was Dijkstra’s Algorithm. This algorithm is an O(n2) algorithm which steps through all the connecting cities and proceeds to compute the shortest path from a departure city to all other cities, including the arrival city. See Appendix for a detailed explanation of Dijkstra’s Algorithm.

To compute the geographical distance between two cities, we used a formula that computes the distance based on the latitude and longitude coordinates of each city. See Appendix for details.