Super Market Sweep

Inspiration

Our inspiration was the idea was an interesting problem to tackle not only as an efficient way to traverse a store, but a method to make an NP hard problem, easier.

What it does

The program opens in Unity and allows a user to build the store's grid, obstacles, and checkpoints the user would like to visit in the store. These can all be selected with a simple to use UI. After the user builds all of these, the user submits build of the store and the program runs through an algorithm to determine the best route.

How we built it

The program was built in C# with Unity and the greedy salesman algorithm was programmed in Java. The two communicate to one another through text files.

Challenges we ran into

The first large challenge we ran into was discovering that the problem we were trying to solve was, in fact, an NP hard problem. This allowed us to explore opportunities of was to cheat this system such as the greedy salesman algorithm. Making the java and C# programs talk to each other was another obstacle we did not consider to be as complicated. In the end, we figured out the line of code to execute a jar file and everything worked well.

Accomplishments that we're proud of

Implementing the java code with A* and greedy salesman algorithms was a huge accomplishment and a major portion of our coding. On top of this, the UI that was built in Unity proved to be pretty efficient at displaying the message we wanted to achieve.

What we learned

NP hard problems are hard. On top of this, we learned implementation between different languages should not be saved for last and, in fact, should probably be tested first.