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.

Improve this question
$\endgroup$
2
  • 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
    Commented Mar 26, 2019 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
    Commented Mar 26, 2019 at 9:51

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .