2

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 for this.

Improve this question
5
  • "Checkpoints", hmm? Must they be visited in order? Commented Aug 17, 2009 at 16:49
  • What have you done so far to try and create the algorithm? Commented Aug 17, 2009 at 16:53
  • Do you know the total number of checkpoints on a given graph? I assume you have to see all of them. Commented Aug 17, 2009 at 16:54
  • Do u need the shortest path? what is cost of traversing and edge, is it symmetrical across the graph Commented Aug 17, 2009 at 17:22
  • @Nick Lewis: Check points would be given in the order of proximity to the starting point. So, no special thing for order, i guess. <pre>@LFSR Consulting: I was trying to modify Dijkstra's for this purpose. It hasn't worked out yet. <pre>@BlueNovember: Yes you do. Input is as follows: 1. Final point. 2. No of check points. 3. That many check point coords. 4. No of danger points. 5. That many coords. <pre>@Kazoom: It isnt symmetrical across the graph and I just need to traverse through all the check points not passing through the danger points. Not really reqd that it must be the shprtest path Commented Aug 18, 2009 at 5:02

4 Answers 4

Reset to default
4

First remove the mines and make a list of the checkpoints.

Then you'll almost certainly have to do a depth-first or breadth-first search. Which one depends on the graph. I'd suggest trying a breadth-first search, with a decent pruning heuristic. A seeker starts at the starting point, then whenever it has a choice to make it copies itself and goes both ways. It keeps two lists: the checkpoints it's visited, and the neutral nodes it's visited since its last checkpoint. When it visits a neutral node it writes its checkpoint list on the wall, and erases any lists that are subsets of its own. It will terminate itself if it encounters one of the following conditions:

  • It visits a node already on one of its lists.
  • It sees a checkpoint list on the wall that is a superset of its own.
  • It arrives at the destination without having visited all the checkpoints.

That should be enough to get you started. There are other optimisations (such as removing dead ends) that may be worthwhile, depending on the graph.

(EDIT: scratched that last condition when I saw that it would make some graphs impossible.)

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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!

Improve this answer

Comments

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.

Improve this answer

6 Comments

The classical Dijkstra does not work for negative edges. See here: en.wikipedia.org/wiki/Dijkstra%27s_algorithm Also - in your solution there might be negative cycles - so Bellman-Ford also won't do.
Shouldn't mines have an infinitely large weight, as they cannot be present in the final path?
I think the negative cycle problem can be solved by keeping track of which checkpoints have already been visited.
One more thing - the weights in Dijkstra are expected to be on the edges, and not on the nodes. Are you referring to a different algorithm maybe?
Well, edges can simply be the cost of going into a node.
|
1

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)

Improve this answer

3 Comments

DFS keeps track of whether nodes have been visited and will not visit a node if it is marked as having been visited previously. E.g. in a 3-cycle of nodes n1-n2-n3-n1, node n1 may be visited first (and marked as visited), followed by n2 and n3, but at n3 the DFS will not revist n1 because it is marked as "visited".
Sorry for late response, I'll clarify my original comment. I think standard dfs will produce valid but not necessarily shortest paths. In your example, could a cycle of n1-n2-n3-n1 produce n1-n2-n3 as a valid route, even if n1-n3 was shorter? (Btw, are you the same Tom I know from Warwick? If so, small world! -Richard)
Indeed I am! It's a very small world. Although I guess thats the miracle of the intertubes at work. :-) I see what you mean about the cycles producing non-optimal paths. To find the shortest, the DFS could be modified somehow to take into account the edge weights when it picks an path, although this probably would have to utilise some form of lookahead.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.