Student-Faculty Projects

Many studios have adopted behavior trees as their standard AI development structure instead of the finite state machines prevalent in games of the early 2000s. Behavior tree logic follows a top-down approach starting from a root node at the top and following different branches based on certain conditions until finally reaching a leaf node in which actual behaviors of the AI reside and execute. This organization allows the designer to easily follow the control flow of the AI. It also provides excellent modularity as it is easy to insert new behaviors and sub-trees anywhere in the structure. However, one of the downsides to using standard behavior trees is they are less suited to creating reactive behaviors. Due to the simple top-down logic, the system can only respond to certain environmental stimuli at certain points in the tree, meaning it must finish the logic it was working through before reevaluating a conditional and changing its execution path. If an AI needs to be more responsive to a lot of external stimuli in the game world, another development model can be used called statecharts. In this project, we explore the use of statecharts to design a reactive AI that can easily adapt to a constantly changing game environment through the use of interconnected sensors and behaviors created with the state machine design pattern.

Rotoscoping is an animation technique that translates real movie footage into animation. This technique requires painstaking, time-consuming work from human animators. The goal of this project is to create a digital rotoscoping image filter that can be applied to both static and motion pictures. This project utilizes edge detection computer visualization techniques to automatically detect the edges of objects. These edges can be used to recreate the ink lines found in hand animation. We used color categorization techniques to replace photo-realistic, multi-hued colors with virtual single-tone paints. The results are images that appear hand-drawn, but were created by running a series of filters over photos. We then extended this technique to video. The primary difficulty in performing this rotoscoping technique on video is the incredible length of time it takes to convert a feature length film. We overcame this difficulty by breaking the video into several smaller video clips and submitting them to a HTCondor distributed computing cluster. Each node in the cluster could work independently rotoscoping a small part of the video. This approach reduced the runtime from days to hours.

Motion picture recording is switching from film to digital. As a result there is an increased demand for video filtering and digital color correction, tasks previously performed physically and chemically. This project attempted to create a filter to replicate the look of 1970s television. The most difficult part of creating this filter is reducing the now standard 16:9 aspect ratio to the 1970s TV standard 4:3. The standard technique for rescaling images/video either stretches the image or cuts off the edges. Neither technique is particularly satisfactory. We implemented an improved technique developed by Avidan and Shamir called seam carving or liquid rescaling. This technique carves seams through any part of the image, only removing the least important pixels. With this technique the image does not look stretched or squashed and important aspects of the image are preserved. This work extended the seam carving technique, developed for still images, to motion video. It required developing our own digital image processing code, utilizing video library code to convert video to images for filtering (and the reverse), and extending the seam carving process to view a single image as part of a larger stream of images.

Mobile weather applications are popular and common. The goal of this project was to develop a full-featured mobile weather application in a single semester. We built this application in two ways. In the first, we simulated a scenario where the software vendor maintains a weather forecast database. This approach mirrors apps like DarkSky and AccuWeather. We created a weather database on a RaspberryPi and developed a RESTful service to provide a RESTful API for reading and updating this database. We then developed an Android app to fetch this data using the RESTful API and then display it to the user. Our second approach to building a weather app used the more common technique of getting weather data from another provider, like the National Weather Service (NWS). The NWS provides its own RESTful API for getting this data. We were able to modify our weather app to present user-friendly weather information collected from the NWS. This project used MySQL, JDBC, Jersey’s RESTful library, Android, and Volley to create our mobile weather application.

Large online databases such as ISBNdb and OpenLibrary provide data on nearly every book since the invention of the ISBN standard. Using these online resources and a small computer as a server, keeping track of the book information from a personal library is possible. This capability becomes more useful as the size of the personal library increases and when different versions of books are available. The goal of this project was to create an app that would easily lookup and add books to a database. Some obstacles include handling books published prior to 1967, before ISBNs came into use, and the limitations of free APIs such as OpenLibrary. To make a working, flexible system, we used a RESTful service on a Raspberry Pi computer to handle the database and communicate with either a phone or computer interface. Some features of the completed software include the ability to scan the barcode of a book and quickly determine whether that book is owned, get information about the book, and add it to the database. We also included the ability to perform the same operations through manual entry of information when the barcode is not available, or the ISBN is nonexistent.

EVE Online is a science-fiction, massively multiplayer online game that involves building spaceships and fitting them with various modules to conduct player versus player or player versus environment activities. The fitting of these ships is important to the player’s success. There are two problems with the game’s built-in fitting simulator. The first is that it requires players to be logged into the game on a PC to create a fitting. This prevents players from trying out fitting ideas when they are away from their desks. The second problem is that the built-in fitting simulator only includes limited information compared to third party programs. There already exists a popular desktop application for calculating ship fitting called Python Fitting Assistant, or PYFA for short, and a web-based service called EVE Workbench. Neither of these applications supports our goals of ship fitting on the go. This project attempts to create an Android application called the EVE Mobile Fitting Tool to fill this gap. We leveraged the following technologies to create the EVE Mobile Fitting Tool: Java, the Jackson JSON library, the Room persistence library, EVE’s Swagger RESTful service, Linux, and cloud storage.

Image and video filters were once the work of chemists and lighting specialists. However, with the prevalence of digital recording for films and TV and the spread of digital cameras these old filtering techniques need to be translated into software. This project focused on creating novel image and video filters like one which replaced colored pixels with small images of letters and numbers. ASCII art is a technique where the artist “draws” a picture using a text-editor (like Notepad) to create an image from letters and symbols entered on the keyboard. ASCII is usually done “by hand”. One goal of this project was to create an automated ASCII filter: given a digital image our filter would replace the colored pixels with black and white images of letters, punctuation, and numbers. We were able to create this filter for both still images and video. One difficulty with applying a filter to video is the incredible length of time it takes: days to convert a feature length film using standard hardware. We solved this problem by running our filter in a distributed system using HTCondor.

The proliferation of remotely controlled devices in the home has made managing all the attendant remote controls unwieldy. This project created a low-cost remote control hub that can control all of the infrared (IR) devices in your living room. Any device that replaces a bunch of remotes with a single remote control has the danger of failure if that remote is lost or damaged. Our approach was to create an extensible remote control hub that can, in turn, be controlled by any number of smart devices. We developed a RESTful API for our hub that allows for control of IR devices using apps written in any language with a RESTful library (a lot of languages support RESTful services). We also developed a web-based interface to the remote controlled devices leveraging the already developed RESTful service. Providing an open API to the remote control hub opened it to attack from malicious users. Therefore, we need to develop security measures for our hub. We created a username/password system with API keys that means that users do not need to enter their password every time they want to issue a command.

The goal of this project is to generate infinite caves procedurally so that a player may explore them without encountering a recurring pattern. The project also utilizes Virtual Reality (VR); the user will be able to put on a VR Headset and become immersed in a randomly generated cave system. One of the challenges that needed to be overcome was that uniform random number generators did not generate natural looking caves. Introducing VR to the project created the additional challenge of preventing the user from becoming motion sick. These challenges were both addressed through hours of research into many different topics such as Perlin Noise, Perlin Worms, and code optimization.

The goal of this project is to generate an infinite maze procedurally so that a player may explore it without encountering a recurring pattern. The project also utilizes Virtual Reality (VR); the user will be able to put on a VR Headset and become more immersed in a procedural environment. One of the challenges that needed to be overcome was efficiently generating new parts of the maze while the player walked. Introducing VR to the project created the additional challenge of preventing the user from becoming motion sick. These challenges were both addressed through hours of research into many different topics such as breadth first graph traversal and code optimization.

This project hoped to improve the AI of video game bosses using a technique called statecharts. Traditionally boss AI is implemented using decision or behavior trees. However, a tree-based solution can lead to needless repetition, overlap, and ultimately incorrect behavior. We decided to explore using a technique from embedded systems called statecharts or hierarchical state machines to implement boss AI. This technique let us better visualize the multiple possible states a boss could be in simultaneously and then create predictable (to the programmer) behaviors for the boss to execute.

This project hoped to improve the AI of video game cars in open world driving simulations. Traditionally non-player vehicles are guided on the road using decision or behavior trees. However, a tree-based solution can lead to needless repetition, overlap, and ultimately incorrect behavior. Cars can get stuck or unexpectedly drive on the sidewalk. We decided to explore using a technique from embedded systems called statecharts or hierarchical state machines to implement boss AI. This technique let us better visualize the multiple possible states a car could be in simultaneously and then create predictable (to the programmer) behaviors for the cars to execute.

The nominal goal of this project is to use the International Movie Database to develop a phone app that plays the game Six Degrees of Kevin Bacon. The real goal is to gain experience using Amazon’s S3, HTCondor, JSON, RESTful services, NoSQL databases, and Android client-server application development. IMDB makes an abridged version of its database available on the Amazon Web Services S3 data storage platform. We extracted this data from S3 and wrote distributed high-throughput code to convert it into a format we could use. Running our data conversion software took 6 days to run on roughly 60 computers using the HTCondor system. Next, we stored this converted data into a NoSQL database to provide a high performance remote interface for this data. Future work includes, developing the graph traversal software to calculate the path and distance between any two actors and make this feature remotely available via a RESTful service for Android devices.

Home automation is something big that we will be seeing in the near future. Many devices that we use in our homes are controlled by infrared signals. Current high end phones have built in infrared blasters that can be used to control many devices in our homes. The goal of this project is to make this functionality available to users who have mid-to-low cost phones with only a small investment. As a solution to this problem, we installed the LIRC infrared control software on a Raspberry Pi that we had wired with an infrared emitter and receiver. Because LIRC does not have a very user friendly interface, one goal of this project was to develop an android and a web app interface to work with LIRC. This presented an additional problem: how to build the project in such a way to support both an android and web interface with a minimum of repeated effort.

Many times each day, owners of cellphones use their phone’s lock screen in order to access their device. The goal of this project has been to take advantage of the action of unlocking one’s device by incorporating an element of self-help into the process. Every time a user who is interested in learning a new field attempts to access their device, that user is faced with a problem pertaining to a subject they are interested in learning more about. After many repetitions of this scenario, the user will have increased their understanding of this field. Through this project, we have explored the idea of a self-help lock screen by creating a lock which requires the user to solve a chess puzzle in order to unlock their phone. One issue which posed to be problematic was the chess puzzles becoming stale. If the user were to use the lock screen for long enough, we would need to make sure that they would not come across the same problem multiple times. We overcame this issue by changing the lock screen so that it would access a server which sends it new chess puzzles.

Virtual Reality is currently the hottest way for people to play video games because it provides an immersive and interactive world to explore. It uses computer software to create sounds, realistic images, and other effects to simulate a virtual setting. The current craze started on the Oculus Rift headset and has incited other companies to make their own, but most are expensive or require another system to play. Instead of buying an expensive headset, anyone with a smartphone can play in Virtual Reality with Google’s cheap alternative, the Google Cardboard. The goal of this project was to complete a prototype of a VR game that can be used on Android with Google Cardboard. Some of the limitations of creating a VR Mobile game are time and people, this project only having only two people and a limited amount of time. To accomplish this, we used a 3D game engine called Unity, which has built in support for Google’s VR. The software provides an editor where developers build and script games then seamlessly export the to both Android and Apple phones. Using this tool, we accomplished our goal and created the foundation for an entertaining Virtual Reality Mobile game.

The purpose of this project was to create an easy to use, real-time app that would help visitors navigate the Lynchburg College campus. To achieve this goal, we used a new technology called augmented reality. This technique superimposes computer generated graphics onto a live camera feed. In this project, we developed a phone app that superimposed labels over a live feed of campus buildings and landmarks. In this way, a visitor could easily find the building they are looking for simply by panning their phone’s camera over the campus.

It can be easy to determine a person’s phone password by either looking over their shoulder or watching their finger movements. In this project, we develop a one-way function that allows a phone user to unlock their phone in full view of a snooper without giving away the password. In general, computers are good at one-way functions, but humans are not. To solve this problem, we based our one-way function on the popular board game Mastermind.

The CPU scheduler for the Linux scheduler is over 8000 lines of code. In addition, several parts of the scheduler are inefficient. By examining the underlying mathematical models for the scheduler and using more appropriate data structures we believe we can reduce the amount of code and improve the efficiency of the scheduler. We also think that it will be possible to add additional features that will improve usability.

The Condor High Throughput Computing system is designed to create a single super computer from a collection of individual machines. This presents a classic resource distribution problem: given multiple users, how should the machine resources be divided amongst them. Condor uses an exponential decay model to determine resource allocation. This project attempts to analyze the potential shortcomings of such an approach.

Computational simulation and data analysis provides useful feedback for a wide variety of both conceptual and real-life situations. A common objective in using these techniques is to examine and determine strategies for games. The board game Monopoly is an elaborate competition that combines a bit of luck with a mixture of mathematical, financial, and property management skills. Through a methodical computer simulation and an in-depth examination of the data produced, various strategies in the game of Monopoly have been made evident. These strategies are based on which properties and groups of properties are calculated to hold the best return on investment, the most efficient method of purchasing and placing houses and hotels per property, and the most effective way to increase income.

Contemporary data analysis presents a new problem: many of today's data sets are so large that traditional data processing methods become too slow and inefficient. These data sets require a new approach to file storage and management. One solution is a distributed file system, which uses a computer network to allow multiple users to access and share files. Because hardware failure is the norm rather than the exception, these systems must provide efficient fault tolerance. Replication is necessary to prevent data loss and enhance accessibility. If all data is stored on one machine, transfer of data input and output weighs heavily on the system, reducing efficiency and increasing processing time. Because the distributed file system allows multiple machines to access one large data set simultaneously, they can collaborate and achieve a solution more quickly. In this project, a distributed file system will be implemented using the machines in Hobbs 113 and 124 to enhance the Computer Science department's resources for solving complex problems.

The aim of this research is to deconstruct the high-level application features of the Android operating system into its standard operating system components. Specifically, we will examine I/O, process/thread architecture, and memory management.

Rotten Tomatoes is a well-known website that aggregates critic and user movie reviews. We have noticed that in some instances users and critics disagree about a movie's quality. Rotten Tomatoes provides an application programming interface (API) that allows computer programs to extract information from their large database. Using this API, we have collected a large body of data from their movie database. With this data we determined what percentage of movies feature a significant difference between critic and user reviews. We also hope to find some common characteristics between these movies. For example, are critics harsher on comedies or Mathew McConaughey movies than audiences? This project includes several interesting technical challenges, most notably how to collect and manage such a large body of data. The API limits users to 10,000 queries a day. This is far too little for our purposes. Therefore to collect this data, we needed to create a local database and an automated system to add new movies to this database everyday using our allotted 10,000 queries. The large size of this local database makes performing data analysis on it difficult. To solve this problem, we devised a series of increasingly specific analyses to extract useful correlations.

Augmented reality is a type of virtual reality that tethers the physical world to a computer-created world, enhancing the physical world with computer manipulations, i.e. adding useful graphics and interactive points. The goal of this project is to use augmented reality to create a virtual graffiti app that would allow a person "tag", place an image or text, in the augmented reality version of the world. Using a device, such as a phone or tablet, they will then be able to walk around the physical world and see their image or text "floating" in midair exactly where they placed it.

Each evening, when the last student leaves the lab, hundreds of computers become unused resources for several hours. The goal of our project is to harness these unused compute cycles to conduct scientific research. To accomplish this goal, we have installed the Condor High Throughput Computing (HTC) middleware on a test bed of 18 computers in Hobbs. Installing Condor on this test bed involved several system administration challenges. During this process we even discovered a bug in the Condor software, which the developers at the University of Wisconsin quickly fixed. To illustrate the effectiveness of using Condor to solve computationally expensive problems, we are working on a HTC solution to the game Dots and Boxes. Dot and Boxes is a two player pencil and paper game. The board is a grid of dots and players take turns connecting the dots to create boxes. The winner is the player who completes the most boxes. A complete searchable solution to Dots and Boxes will allow a player to make the optimal move during each turn. Creating this solution would take many months if run on a single machine; using our Condor test bed, we expect to solve this problem in a few weeks.