Graph Searching algorithm

Question

Here is the problem: I have to find a path from the starting point to the destination with following considerations.

In the given graph a point could be either

• (1) A Checkpoint--> this point must be there in the final path calculated

• (2) A Mine--> this point should not
  be there in the final path calculated

• (3) A neutral point--> this point
  may/may not be there in the final
  path calculated

I need an algorithm to this. Kindly help.

Answer 1

Well, I think you can use Dijkstra's algorithm (Or something similar, I'm suggesting Dijkstra's because it is exhaustive and general and you did not provide that much info about your data) to find the shortest path... with these modifications:

1. Checkpoints have a value of equal to the negative of the number of neutral points.
2. Mines have a value equal to the number of neutral points.
3. Neutral points have a value of 1.

Dijkstra's will find the shortest path (path with the lowest weight), which is guaranteed to cross all the checkpoints and avoid all the mines.

It's not a fast algorithm though, so it might not work if your map is too large.

Answer 2

If your checkpoints need to be visited in a specific order, Dijkstra's algorithm is an easy solution. You can use the algorithm against subsets of the graph. The subsets will be graphs where the starting and ending nodes are checkpoints (or the opening or closing nodes of the graph). You can use edge weights to represent nodes that shouldn't be visited.

However, I would suggest A* Pathfinding as it is probably more suited to what you are trying to do. There is a lot of sample code out there.

Here is a good tutorial to get you started:

A* Pathfinding for Beginners

You can represent your mines and checkpoints as weights in the graph, or by using heuristics. This will most likely depend on whether checkpoints are ordered or not.

Gamedev.net is your friend. Good luck!

Answer 3

Personally I would use a depth first search (DFS) for this. Dijkstras algorithm is for computing a shortest path, based on some edge distance function (you haven't mentioned any distances between nodes so I assumed there are none).

The DFS can be modified thus (assuming s is your source and t is the destination):

• First remove all "mine" nodes and their adjacent edges. If a mine node cannot be visited then it might as well be removed as no incoming or outgoing edge from it can be used in the path.
• Perform DFS from node s.
• Once the DFS has been performed you will have a set of sequences of nodes e.g. [s, a, b, d, e, t], [s, b, d, t, e] and so on.
• If any of these sequences contain all checkpoint nodes preceding node t then this is a suitable path.
• If there are no such sequences in the DFS results then there is no path meeting the criteria. Either you have to miss out a checkpoint or visit a mine to reach the destination.

This may not be the most efficient algorithm, but should work for finding a path. There are also no promises that a path you pick from the DFS result is the optimal path.

(This assumes checkpoints can be visited in any order)