0
$\begingroup$

I need a pathfinding algorithm that considers the history of visited nodes and varies its path depending on some rules (like already visited). Are there good approaches serving this purpose?

To be more specific: Let's say I have a graph representing a map. I want to find a Route from B to D: Once I am in D following B->C->D, I want to calculate a new path, let's say to A. The shortest path would be D->C->B->A. But I want a path with unvisited nodes even if it's longer than the shortest possible path. The new path should be the shortest among all possible paths according to the rules. Another example is the game "snake". Seeing the grid as a graph I cannot visit already visited nodes as fas as the corpus (of the snake) is in that node (or I have visited the node t time steps ago)

Maybe the problem is too specific and I have to implement some basic pathfinding algorithm in a wider algorithm.

$\endgroup$
  • 1
    $\begingroup$ You could just find any implementation of the A* algorithm and modify it by adding a 'visited' flag to each node. Then exclude moves to nodes that have this flag set. $\endgroup$ – Oliver Mason Mar 26 '19 at 9:43
  • $\begingroup$ @OliverMason I was thinking of something similiar. Like having a hashed value that lists all visited nodes as values, but I was hoping for a well known approach that can be used with more rules like "if this kind of node was visited twice, dont visit it again". And if possible not to use customized solutions but rather go with something known. I was thinking of using a signal interpreted petri net and even PDDL but both are not suitable for my purpose. $\endgroup$ – Bryan McGill Mar 26 '19 at 9:51
1
$\begingroup$

Yes, this is easily solved using the A* algorithm. Once your agent has visited a particular node, increase the cost of that node to infinity and recalculate the path.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.