Path finding in an undirected Graph

stuff about computer science and programming
Post Reply
User avatar
dendiz
Site Admin
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

Path finding in an undirected Graph

Post by dendiz » Wed Oct 10, 2018 9:55 pm

A poor mans path finding algorithm. Given a start node, find any path that leads to the target node.
I use this piece of code to generate a route from a given planet/star system to another one. The stars are guaranteed to be connected.

Driver:

Code: Select all

        public List<StarSystem> FindPath(StarSystem source, StarSystem target)
        {
            var path = new List<StarSystem>();
            Find(source, target, new List<StarSystem>(), path, new HashSet<StarSystem>());
            return path;
        }

Code: Select all

        private void Find(StarSystem source, StarSystem target, List<StarSystem> path, List<StarSystem> validPath, HashSet<StarSystem> visited)
        {
            visited.Add(source);
            if (source == target) validPath.AddRange(path);
            foreach (var neighbor in source.WarpLanes)
            {
                if (visited.Contains(neighbor)) continue;
                path.Add(neighbor);
                Find(neighbor, target, path, validPath, visited);
                path.Remove(neighbor);
            }
            visited.Remove(source);
        }

Post Reply