Inspiration
One of our team members was using Google Maps the other day to find a route and realized that route finding is a relatively new technology that would have been absolutely helpful for people back then, especially those who had to walk long ways. One of the first such examples that came to their mind was the Oregon Trail.
What it does
Our app is meant to help travellers moving west during the westward expansion of the United states. Oftentimes travelers would get lost or stuck by taking the wrong path. Our webapp is designed to reduce those kinds of negative and often deadly experiences. The user gives us their destination and then we calculate the best possible route for them to take. We take into account different points of data including: major water sources, elevation changes and weather. There is also functionality for travelers to create markers on the map with important information or to ask for help for others to see.
How we built it
To collect the topography information and water information we used OpenCV (computer vision) on various maps and satellite images; for example, we used KMeans color segmentation to segment the image by color (and therefore elevation). We then used these images to create a matrix of points each with individual relationships and weights to each other. Specifically, we prioritized maintaining a constant, low elevation and moving around bodies of water. These nodes, along with the users start and finish points, are piped into a modified a* (a star) path finding algorithm which weighs all of the information and determines the best possible path. This is then sent back to the user and displayed as a polyline and two markers on the map. The backend is a python flask app hosted on Heroku. It uses flask HTTP request routes to communicate with the backend. It has sqlite3 and SQLAlchemy database which stores all of the user posts. The frontend is written with html, javascript, and jquery. It uses the Leaflet.js API for the map.
Challenges we ran into
One challenge was the image processing. It took two days to find and process the correct images needed to map the elevation and water proximity scores into the pathfinding algorithm. The a-star algorithm itself was slow at first as samples became larger in size, but we were able to significantly shorten request times by prioritizing distance to destination more. One other challenge was hosting our backend Python, and it took more than a few hours to set up a Flask app and SQLAlchemy database to deploy on Heroku.
Accomplishments that we're proud of
Many of the accomplishments we are proud of include the challenges we faced and were eventually able to solve, such as the image processing and backend deployment. We are also proud of the new things we tried, such as using the SQLAlchemy database and implementing a Leaflet.js map into our website.
What we learned
Not only did we learn new tools and software such as SQLAlchemy and Leaflet.js, but more specifically the new methods and strategies we utilized to solve problems. For example, we learned that it was easier to segment an image by elevation using KMeans color segmentation with OpenCV. We also learned that SQLAlchemy is an easy replacement for Firebase (something we had used in previous projects) for Python, and that Leaflet.js is a great open-source map replacement for Google Maps API (which may not always be free).
What's next for PathFinder
We definitely wish to implement a resources management tab to alert when the traveler is low on resources such as food and water. Expanding upon the SQLAlchemy database, we can also store other user’s locations in case users want to trade with each other or team up on their journey. We are also considering a weather tool that calls a weather API and changes a user’s path in real-time. One other factor to consider is taking note of animals’ natural habitat to help the user avoid potentially dangerous locations.
Log in or sign up for Devpost to join the conversation.