Part of my program is a variable-sized set of Star Systems randomly linked by Warp Points. I have an A* algorithm working rather well in the grid, but the random warp point links mean that even though the systems have X,Y coordinates for where they're located on a galactic map, a system at 2,3 isn't always linked directly to a system at 2,4 and so the shortest path may actually lead away from the target before it heads back towards it. I think this limitation eliminates A* since there's almost no way to get a good heuristic figured out.
What I've done instead is a recursive node search (I believe this specific pattern is a Depth-First Search), and while it gets the job done, it also evaluates every possible path in the entire network of systems and warp points, so I'm worried it will run very slowly on larger sets of systems. My test data is 11 systems with 1-4 warp points each, and it averages over 700 node recursions for any non-adjacent path.
My knowledge of search/pathfinding algorithms is limited, but surely there's a way to not search every single node without needing to calculate a heuristic, or at least is there a heuristic here I'm not seeing?
Here's my code so far:
private int getNextSystem(StarSystem currentSystem, StarSystem targetSystem,
List<StarSystem> pathVisited)
{
// If we're in the target system, stop recursion and
// start counting backwards for comparison to other paths
if (currentSystem == targetSystem)
return 0;
// Arbitrary number higher than maximum count of StarSystems
int countOfJumps = 99;
StarSystem bestSystem = currentSystem;
foreach (StarSystem system in currentSystem.GetConnectedStarSystems()
.Where(f=>!pathVisited.Contains(f)))
{
// I re-create the path list for each node-path so
// that it doesn't modify the source list by reference
// and mess up other node-paths
List<StarSystem> newPath = new List<StarSystem>();
foreach (StarSystem s in pathVisited)
newPath.Add(s);
newPath.Add(system);
// recursive call until current == target
int jumps = getNextSystem(system, targetSystem, newPath);
// changes only if this is better than previously found
if (jumps < countOfJumps)
{
countOfJumps = jumps;
bestSystem = system;
}
}
// returns 100 if current path is a dead-end
return countOfJumps + 1;
}