.O.
..O Deniz's personal pages
OOO

Graph path finding

August 1, 2016

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:

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;
}

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


It’s also possible to implement this iteratively. The following implements Lee’s Algorithm (which does find the optimal solution but is rather inefficient)

func find_path(map, src, target):
var queue = []
var visited = []
var expansion = []
for i in range(map.size()):
visited.append([])
expansion.append([])
for j in range(map[0].size()):
visited[i].append(false)
expansion[i].append(0)
if map[i][j] != 0:
visited[i][j] = true
else:
visited[i][j] = false
var marker = 1
queue.push_back({'node': src, 'dist': marker})
expansion[src.y][src.x] = marker
visited[src.y][src.x] = true
while queue.size() > 0:
var cur = queue.pop_front()
if cur['node'] == target: break

var neighbors = get_neighbors(map, cur['node'])
queue.push_back({'node': adj, 'dist': cur['dist'] + 1})
var path = [target]
var cur = target
marker = expansion[target.y][target.x]
if marker == 0:
return []
while cur != src:
var neighbors = get_neighbors(expansion, cur)
marker -= 1
break
return path


Lee’s algorithm works by expanding a “wave” from the source cells to all the cells in the grid. Assuming s = start, d = destination, 0 = walkable, * = obstacle and movement is permitted in the cardinal directions only:

s 0 0 0 0
* 0 * 0 0
0 0 * 0 0
0 0 0 d 0
0 * 0 0 0


A BFS is done and each neighbors distance from the start cell is recorded.

s 1 0 0 0
* 0 * 0 0
0 0 * 0 0
0 0 0 d 0
0 * 0 0 0


only 1 neighbor cell is walkable

after all the cells have been visited the expansion matrix is like this:

s 1 2 3 4
* 2 * 4 5
4 3 * 5 6
5 4 5 d 7
6 * 6 7 8


The path is found by starting at the target and walking backwards towards the neighbor with the smaller number.

Tags: #programming