published on June 23, 2025 in devlog
Michi shares some technical insights on how the pathfinding algorithm works.
Michi (molp)
As mentioned in last week's devlog #487, I am currently working on mission planning and pathfinding on the server side.
After the first few experiments worked out very well, I started the actual implementation. To keep things simple, I'm first going to implement the pathfinding only for the existing game elements and add support for the gateways later on.
On the technical level, the mission planning is now a two-step process: In the first step, I'm using the new system to find one or more paths from the origin to the destination. The second step then takes the path and converts it into a list of flight segments, essentially what you see when you plan a mission with the SFC command. While the first step is new, I plan to reuse as much code as possible for the generation of the flight segments.
In case you’re interested how the first part works under the hood: the algorithm that finds the paths between two locations works on a directed graph. A graph consists of nodes and edges, directed means that the edges have a direction. For example, you could have an edge from nodes A to B, meaning you can travel from A to B, but not B to A. That seems counterintuitive at first, given that ships should be able to travel freely between any planet, for example. In the end, it simplifies creating the routes though.
Remember, the pathfinding step should produce a list of flight segments and these segments have types: LANDING, TAKE_OFF, TRANSIT, JUMP and so on. So by having one edge from the surface to the orbit (TAKE_OFF) and one from the orbit to the surface (LANDING) I don't have to determine which type of segment I’m working with in step 2.
The nodes in the graph don't reflect the systems, planets and stations 1:1 in the game. For example, when flying out of the system, ships have to fly for a while until their FTL drives are charged and they reach the jump point. The jump point is part of the flight model, but it can’t be the destination or origin of a flight in the game world. It helps the pathfinding though, because going to an outbound jump point is a DEPARTURE segment (followed by a JUMP) and arriving at an inbound jump point going towards a planet is an APPROACH segment. There is also an edge from every inbound jump point of a planet to every outgoing with a CHARGE edge. It is used when the system is just an intermediate system in a longer flight.
As you can see, creating the graph and writing tests to cover a wide range of potential flights is a bit of work. I'm almost done with it though and started to work on generating the flight segments from the pathfinding results.
As always, we'd love to hear what you think: join us on Discord or the forums!
Happy trading!