Is there a way to calculate an optimal route between multiple nodes with different types of travel

Question

In the game EVE Online there is a map with systems, these systems can be traversed by gates or jump drives but there are some limitations:

• If the system is in range (jump drives have a max range based on geographical distance)
• Jump drives can not be used in certain systems
• Certain classes of ships can not enter certain systems
• The jump drive has a cooldown on usage which increases based on how recently you've used it.

The data for the location of systems in space is available, as is the list of gates which connect systems

I'm trying to calculate an optimal route between two systems, I expect most ideal solutions will make use of both gates and the jump drive because gating is riskier and slower (based on size of system which is also data which is available) and jumping is instant but subject to a cooldown which increases based on how many times you've jumped with the cooldown.

I'm aware there are likely to be numerous solutions to this problem, I've used NetworkX in the past but I'm struggling to understand how I would express the limitations I have in a library like NetworkX, it seems like cost is the way to go about this? but I don't know if it is enough to model this problem?

I'm not looking for someone to give me a complete solution, just hoping for some pointers on if NetworkX is the right way to go, academic research in the same area etc.

Answer 1

• Construct a graph with vertices representing "systems".
• Remove vertices representing systems that your ship cannot enter
• Add edges between every pair of vertices that are within jump range of each other
• Add edges between every pair of vertices that are connected by a "gate"
• Apply Dijkstra algorithm to find your path between systems

This will give you a feasible path. It may not be "ideal". Since you have not told us what makes a path more or less ideal, it is hard to say more. You hint that there may be costs involved. Perhaps "gates" are more or less expensive than "jumps" - in which case you adjust the edge weights appropriately and Dijkstra will give you the cheapest path.

---

Edge cost depends on previous path.

If the cost of C-D depends on which of A or B are on the path, there are two ways to handle it:

for simple, small problems

Modify the graph:

for large complex problems

Modify the code to calculate the cost on the fly by examining the current path to the node being visited, rather than just looking it up in a table of edge costs.