Graph Linecast on a grid graph with areas of various penalties


#1

I am interested in buying the pro version, but I can’t find the answer to this question in the online documentation.

Does graph raycasting take into account area penalties of walkable areas when determining the path the agent should take? Here is a mockup of what I am talking about:

As you can see, there is a grid with some blocking terrain to the left, the agent to the right, and a triangular area between the two with a high penalty. The Unity arrows behind the wall indicate the agent’s target. I highlighted the inside of the triangle to make it easier to see. The yellow area has a penalty of 100,000 and the rest of the grid has no extra penalty. I set the penalty to 100,000 to make this example more obvious.

Without raycasting, the agent avoids the yellow area (as it should) and also doesn’t walk into the unwalkable areas. The movements the agent makes are all straight or at 45 degree angles, which is the expected behavior, but I’d rather have the agent move in straight lines instead of zigzagging everywhere.

With physics raycasting from the Raycast Modifier (Script), the agent walks through the yellow area like it doesn’t have a penalty at all.This is not desired behavior because it seems to make the tags and penalties pointless.

Will graph raycasting take into account area penalties?

In the above image, I want the agent to move in a single straight line from where it starts to the bottom point of the yellow triangle area before navigating to the target. Is this behavior possible? It doesn’t have to be done with raycasting if there is some other way to make it happen.


#2

Hi

Currently that modifier does not take penalties into account in any way. It is possible for the API to return a list of all nodes that were traversed, and thus it should be possible to modify the RaycastModifier to take them into account. It is however not obvious in what way they should be taken into account. In your case a simple check for “if there is any penalty along the line, just don’t simplify that part” could work. However if you have more complex penalty regions it might not produce the best results.


#4

Thanks for the quick reply. The maps I was thinking of making were going to be about as complex as this:

The above map is 2D but I want to make something similar in 3D so it doesn’t look as flat; it wouldn’t have different layers or floors. It would have several different terrains (plains, roads, mountains, forests, etc) and movement speeds.

What do you think would be the best way to achieve that with A* Pathfinding Project?


#5

Hi

If you have a low number of terrain types I would recommend using tags for this. Then in the RaycastModifier you could modify the check to only simplify regions that go through a single terrain type. I think that would work very well for you. I can show you how to modify it.


#7

Thanks for the replies. I think I might be interested in that.

Also, is it possible to change an agent’s movement speed based on the tag or penalty of an area the agent is moving over?

As an example, moving through the yellow area in the first image I linked would change the Max Speed from 10 to 5 until it reached a new area.

I looked at the Documentation and I found “currentR” in the Path class. When it says it is the node that is “currently being processed” does that mean it is the node that is being traveled to, traveled from, or something else?


#8

The easiest solution is to do something like this in a separate script:

IAstarAI ai;

void Awake () {
    ai = GetComponent<IAstarAI>();
}

void Update () {
    var node = AstarPath.active.GetNearest(ai.position).node;
    if (node != null) {
         switch(node.Tag) {
         case 0: ai.maxSpeed = 5; break;
         case 1: ai.maxSpeed = 2; break;
         default: ai.maxSpeed = 1; break;
    }
}

To modify the graph linecast you would have to open the RaycastModifier.cs file, then you have to disable a special case for grid graphs: set the betweenNodeCenters variable to false.

Then change the line that looks like

return !rayGraph.Linecast(v1, v2, n1);

to

RaycastHit hit;
List<GraphNode> trace = ListPool<GraphNode>.Claim();
if (!rayGraph.Linecast(v1, v2, n1, out hit, trace)) {
    return false;
}
// Ensure all nodes have the same tag
for (int i = 0; i < trace.Count; i++) {
    if (trace[i].Tag != trace[0].Tag) return false;
}
return true;

The currentR node is in the Path class and that is used when calculating the path that the agent follows, not when the agent follows the path.