Exploring continuous graph pathfinding

The algorithm sends out multiple rays to find possible paths
Using an iterative process, the code will keep improving the rays’ paths, creating shorter and shorter paths
The system ends up finding the shortest path from the start point to the finish

Inspiration

Our Inspiration stemmed mainly from this years theme, ‘exploration’. We considered everything from exploration games to exploring pure mathematical theories. We came to the conclusion that we wanted to work on a system that with a bit of development, could be implemented and used in the real world by anybody.

What is our project?

Our project is a path-finding algorithm designed to navigate a map that shows areas of different ‘terrain’ with different weights. It uses a ray-tracing algorithm to calculate the path of least resistance from a given start point to an end point across different areas. These maps and the densities of the areas can be created by the user to mimic real world maps or in other applicable situations.

The process

We started the process with a lot of thorough planning, deciding on different roles and tasks for each of us in the group. Some of us focused on designing the front end of the system in Svelt which would allow the user to create their own maps. Others worked on the underlying algorithm using Snell’s Law to calculate the refractions of different light rays (representing possible paths) based on the densities of the different areas. With enough rays, the algorithm can find the fastest route across the map.

Challenges we faced

The main challenge we ran into was time pressure, 24hrs isn’t as long as you think it is and we ended up rushing towards then end. We definitely have learnt a few things from this project. Most importantly, we’ve decided in the future we need to periodically check and debug the code before introducing new aspects because it makes it faster and easier in the long run.

Accomplishments that we're proud of

We are especially pound of creating multiple systems to compare to our main project. Alongside our ray-tracing algorithm we also looked into Dijkstra, A* and Bi-directional search systems. These were algorithms that we found and implemented to improve our own system and ours ended up being much more efficient.

What's next for Exploring continuous graph pathfinding

If we were to keep developing this project we would work on making it more efficient until let he point where it could path-find through incredibly complex/large areas of land. At the moment the algorithm is too slow to work through much bigger areas but with some work it could begin path-finding though big real world maps.

Another idea we toyed with was mapping in 3-dimensions. This would mean we could map floors on buildings or use air pressure zones too calculate the fastest routes for planes. This could be then extended to any number of dimensions for theoretical use.