Random and path dependent traversal cost for each node (Grid Graph)

General Grid graph
#1

Hey there :slight_smile:

I try to generate paths that are NOT the shortest and feature some sort of random direction changes.

Please see the attached image to get an idea:

Pathing_Example
Pathing_Example2390×3889 313 KB

For my problem we assume that we only have walkable nodes and there are no obstacles. The black line shows an example of a typical shortest path without diagonals. However, for my project I’m more interested in paths like Zig-Zag 1 or Zig-Zag 2.

What I need help with:
I think that similar paths could be generated when a) the traversal costs of all nodes could be completely randomized for a single path request or b) when I could set the traversal costs of each node contingent on the previous path by e.g. increasing the traversal cost if the last nodes in the path pointed in the same direction.

However I tried the following to apply randomized cost but it failed to generate the desired results.

 private Path CalculateStartingPath(Vector3 _startPos, Vector3 _targetPos)
    {
        ABPath path = ABPath.Construct(_startPos, _targetPos);
        path.traversalProvider = new RandomZigZag();

        AstarPath.StartPath(path, true);

        path.BlockUntilCalculated();

        return path;
    }

    class RandomZigZag : ITraversalProvider
    {
        public bool CanTraverse(Path path, GraphNode node)
        {
            return DefaultITraversalProvider.CanTraverse(path, node);
        }

        public uint GetTraversalCost(Path path, GraphNode node)
        {
            // Use the default costs and add random values
            System.Random random = new System.Random();
            return DefaultITraversalProvider.GetTraversalCost(path, node) + (uint) random.Next(0, 10000);        
        }
    }

Is there another way to achieve what I try to do?
And: Is there a way to set the traversal costs of a single node contingent on the previous nodes to account to emphasize more directional changes?

Many thanks in advance :slight_smile:

#2

The easiest option I think would be if I could access the path in in the ITraversalProvider and the previous nodes. However, I can not get the previous nodes when I try the following:

        public uint GetTraversalCost(Path path, GraphNode node)
        {
            Debug.Log(path.vectorPath.Count); /// -> yields 0 
            Debug.Log(path.path.Count); /// -> yields 0
        }

I also found this post that talks about something similar and it seems like it should be possible.

What am I doing wrong?

#3

Hi

A random walk like that is not something this package is well suited for generating. You can apply random penalties, but I don’t think they’ll get you the behavior you want. You want some recursive algorithm to do a DFS over the graph. That is not something which is included in this package.

1 Like
#4

Many thanks for your reply.

Would it however be possible to change the node penalties like this within the TraversalProvider:

    public uint GetTraversalCost(Path path, GraphNode node)
    {
             // pseudocode:
             // step 1: check the directions of the previous path nodes
             // step 2: apply penalties for the current node contingent on the previous nodes
    }
#5

No. A node’s cost cannot depend on the nodes leading up to it. This breaks some assumptions made by the A* algorithm.

1 Like
#6

Ah damn :confused:
Thanks for letting me know.