The Pathfinding Problem
As I jumped into my first doctoral course, I was met with an initial assignment focused on the theory of computation. I read about complexity in relation to the amount of decision-making or branching involved in an algorithm. This was a throwback to some more traditional computer science material I read in my undergraduate program. Certainly not what I expected to see for a first assignment in a doctoral program. But there I was, contemplating high-complexity problems.
My mind focused immediately on the Pathfinding Problem. The Pathfinding Problem involves finding the shortest path between two points in a maze or grid while avoiding obstacles. It is considered a high-complexity problem for several reasons, including multiple possible routes, decision-making at each step, dealing with obstacles or blocked passages, and optimizing the traveled path with considerations for the shortest path or cost efficiency.
I was thinking about the pathfinding problem while contemplating how to best explain the problem. Suddenly, I was on the latest space game release from Bethesda, Starfield. I am playing this game with my son, which is likely too much. The basic premise is that the player is the captain of a spaceship tasked with exploring distant galaxies, trading with alien civilizations, and completing various missions across this virtual environment consisting of thousands of planets. If we think of this virtual world as a grid (or graph in computational terms), each planet, moon, or space station would serve as a node, and the paths between them would be the edges connecting the nodes. Obstacles include asteroids, hostile enemy ships, or even electromagnetic fields, which could disrupt our ship’s systems and send us spinning into the void. We could plot the most efficient course using pathfinding algorithms and consider variables corresponding to our play preferences, such as the shortest distance or refueling costs.
Among the pathfinding algorithms at our disposal, we find:
Get Beyond Merit’s stories in your inbox
Join Medium for free to get updates from this writer.
- Breadth-First Search (BFS) is a fundamental algorithm for traversing (or searching) tree or graph data structures. Initiating from a chosen node (planet, moon, or space station), it examines all adjacent nodes at the present depth prior to moving on to nodes further away. This method ensures we explore every potential node, but might not be the most fuel-efficient option, especially for nodes further away from our starting point.
- Grid-Based Mapping divides our universe into a manageable matrix of navigable cells. Each cell in the grid represents a sector of space, categorized by navigability, including considerations for open space lanes and enemy territories. This can simply be our task of mapping the universe and enabling real-time navigation and strategic planning based on what we encounter within sectors.
- A* is an informed search algorithm, or a best-first search, equipped with heuristic knowledge about the goal’s location. This enables A* to weigh paths more judiciously, focusing on cost or fuel efficiency.
- Dijkstra’s Algorithm, renowned for pinpointing the shortest path across a network of varying costs. It calculates distance, time, fuel, and congestion metrics to assign a cost to each path. However, since it does not have heuristic insights, efficiency may suffer in larger, more vast, or more complex universes.
While these algorithms could address our pathfinding problems, the next era in computing, quantum technology, may revolutionize pathfinding. In the context of space exploration, quantum algorithms could evaluate possible paths across the galaxy in parallel, identifying optimal routes almost instantaneously. This would also enable us to adapt to shifting political allegiances or emerging space anomalies much easier while offering greater strategic depth overall to the gameplay. This transition from classical algorithms is not just a technical upgrade; it represents a paradigm shift in how we conceive navigation both in the real world and in virtual spaces.
So, that’s what I wrote in my paper. A space game that I related to the pathfinding problem, which related to the concept of high-complexity problems. This is not what I expected along the path of my doctoral journey, but here we are playing Starfield.
