I have an object whose boundaries can be define using a convex collider. I have an AI which needs to outline that structure to patrol it. The object is dynamic and composed of pieces like LEGO, each having its own convex collider. I am looking for algorithms that can be used to trace this dynamic object, maintaining a variable distance away from the object.

Below is an illustration of the issue,

  • Red - Long Distance Trace
  • Green - Short Distance Trace
  • Black - Structure

enter image description here

I would need the AI to trace both the red (Long distance trace) and the green (Short distance trace) path. What path algorithm should I use for this?

Here are some examples to consider

enter image description here enter image description here enter image description here


Raycasts and steering

You'll find the path as you go, casting rays and checking for different cases.

enter image description here

  • Pink - Your entity
  • Red - Offset ray. Cast perpendicular to the forward of your entity. Maintains a specific distance from the wall and used to ensure the wall is still there.
  • Blue - Look ahead ray. Looks ahead for the wall and is responsible for the origin of the green ray.
  • Green - Normal ray. A ray from the contact point of the Blue ray, in the direction of the normal of the surface. Used to detect if an opening is too small to enter.

enter image description here

Here the lookahead ray and green ray determine that the passage ahead is too narrow to go down. This is because the green ray hit a wall. This triggers a turn opposite the Offset ray, in this case, to the right.

enter image description here

Here, the lookahead ray detected a wall perpendicular to the forward vector (you should create your lookahead ray to detect these situations before the red ray detects the end of the wall). This triggers a right turn.

enter image description here

Once again, we've found a wall perpendicular to the forward vector. Turn right.

enter image description here

Here, the red ray finds that the wall has run out, this means a left turn.

enter image description here

And again, the red ray finds the wall has run out, left turn.

So the cases we're looking for:

  1. Lookahead ray finds a passage that's too small to enter, turn away from red ray.
  2. Lookahead ray finds a wall in front of us, turn away from the red ray.
  3. Red ray finds the wall has ended, turn towards red ray.

The green line is a fairly trivial modification, where we just have a small lookahead that looks directly ahead and turns opposite the red ray when it detects a wall. And the red ray turns towards the red ray when it detects lack of wall.

  • \$\begingroup\$ How do you determine the lookahead ray? \$\endgroup\$ – DarkDestry Jun 18 '16 at 10:29
  • \$\begingroup\$ Also, consider this example: i.imgur.com/KXOIfk2.png \$\endgroup\$ – DarkDestry Jun 18 '16 at 11:08
  • \$\begingroup\$ To my understanding, this is similar to left wall tracing. That is a good approach. One that I have considered. However, the agent will have to be size aware of which path is non-traversable. The agent should not clip through a wall just to get to where it needs to be. \$\endgroup\$ – DarkDestry Jun 18 '16 at 11:12
  • \$\begingroup\$ Look ahead ray will have to be decided by the various cases, it'll depend on the distance for gaps you want to avoid. You can add a forward looking ray to solve the additional case. The forward looking ray will turn away from the red ray when it detects a wall. \$\endgroup\$ – MichaelHouse Jun 18 '16 at 14:52

Use the normals of your surfaces to calculate this.

Essentially, you're taking your existing edge, and growing it. Then, in some cases, optimizing it to cut out loops or tight corners.

For each corner, you get the averaged normal for the two surfaces that make up that corner. For interior corners, since the average would be pointing towards each other, you'd use the cross product to get the perpendicular vector.

This will grow the edge. This works great for your green line, since it's the same edge as your shape. However, for your red line, this can produce problems. You can use some pathfinding shortcut techniques to optimize out sharp turns.

enter image description here

For example, you'd want the shortcut between 4 and 9, so you can skip 5-8. There's a few approaches to this. For example, detecting loops, like 5-8 would create or a pathfinding optimization for reducing redundant nodes.

enter image description here

Check page 12.

Likely the easiest way of detecting these loops is to find nodes that are close together and remove them. Build up your entire path, then test each node and its neighbors to ensure they aren't too close. If nodes are removed, repeat the comparison until no nodes are removed. In my example image, nodes 6 and 7 would be removed for being too close. That would reorder nodes 5 and 8 to be nodes 5 and 6. Then nodes 5 and 6 would be removed for being too close. After that, there are no more nodes that are too close.

  • \$\begingroup\$ To my understanding, your solution acts upon a fixed path that would be built at load time. However, the issue I have is that my structure can and will change during runtime. This would mean a complete recalculation for all active AI on each change of the structure. Additionally, the method proposed on detecting loops is by a distance check. the 2 points may cross each other that it fails the distance check but is still a loop. If using the pathfinding shortcut, the AI will not follow the green line but instead jump from 1 to 9. \$\endgroup\$ – DarkDestry Jun 17 '16 at 22:44
  • \$\begingroup\$ Depending on the size of the structure, this can be recalculated at run time. You can optimize by storing normals as properties of the structures. You'll have to see how long it takes to run before discounting it for needing to be run when the structure changes. If you can provide an example where a loop is created where the loop contains nodes that are far apart, please present it. Finally, the pathfinding shortcut can be tailored to your needs, you can set a maximum distance for the shortcuts. \$\endgroup\$ – MichaelHouse Jun 17 '16 at 22:50
  • \$\begingroup\$ Illustrated here, i.imgur.com/RRx5oCP.png It would result in false node removal at the circled point. Even if it did not result in the false removal of node, it would still loop within the interior of the structure. As indicated by the cyan line \$\endgroup\$ – DarkDestry Jun 17 '16 at 22:51
  • \$\begingroup\$ That's why you only check neighboring nodes and their proximity to each other. Those nodes would not be removed, but neither would the loop. I'm not sure that example is legitimate however, since the offset of the corners is not a consistent length. \$\endgroup\$ – MichaelHouse Jun 17 '16 at 22:55
  • \$\begingroup\$ Here is an example that would fail in your solution. i.imgur.com/Emra3ZW.png. Following your solution, it would not be able to detect hollow structures. Those blue lines are copy and pasted this time. \$\endgroup\$ – DarkDestry Jun 17 '16 at 23:11

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.