1
\$\begingroup\$

How do I remove the unnecessary nodes from the path to make it as short as possible? Idealy I'd like the result path to look like the green line. The red thingy is not walkable.

enter image description here

        var newPath = new List<Vector3>();
        var nodes = p.vectorPath;
        int lastCp = 0;

        List<int> toRemove = new List<int>();

        for (int i = 2; i < nodes.Count; i++)
        {
            if (IsPassable(nodes[lastCp], nodes[i]))
            {
                toRemove.Add(i - 1);
            }
            else
            {
                lastCp = i - 1;
            }
        }

        for (int i = 0; i < nodes.Count; i++)
        {
            if (!toRemove.Contains(i))
            {
                newPath.Add(nodes[i]);
            }
        }

Here's my attempt to solve the problem and it usualy works well but sometimes if I stand next to obstacle I get the orange line in the picture above.

I'm assuming the path has at least 3 nodes.

nodes is a list of Vector3 (the positions of grey dots on picture), IsPassable returns true if the path between two given Vector3 is passable.

newPath idealy should contain two points in the case of example path above.

EDIT:

I know why the algorithm doesn't work in this case (look at @Draco18s answer below). What I don't know is how to fix it so it always returns the shortest path regardless of start and target location.

\$\endgroup\$
1
\$\begingroup\$

Your method works just as you've programmed it: that is, nodes are being removed. The problem with getting the orange path instead of the yellow sometimes has to do with the fact that you trimmed Node3 (Node0 being the first, where the character is) and so the first non-trimmed node is Node10 at the corner with the orange line. Node11 isn't reachable from Node0 because of the obstacle, so your final path is 0 --> 10 --> 19 whereas the yellow line is 0 --> 3 --> 19.

It is because 0 --> 4 is uninterrupted (IsPassable(0,4) returns true), which causes the removal of Node3.

If you were to trim in reverse you would have similar problems with a destination very close to an obstacle, while the example case here would work beautifully.

\$\endgroup\$
  • \$\begingroup\$ Thank you for input. I know why the algorithm behaves that way (should probably mention that, will update question). What I don't know is how to fix it so it'll always return the shortest path. \$\endgroup\$ – kasztelan Dec 14 '15 at 19:36
  • \$\begingroup\$ In order to do that, you should loop through the array to find a node such that Node[n-1] - Node[n] has a different vector than Node[n] - Node[n+1] and then test IsPassable(n-1, n+1). If true, remove n and recheck. That way you're cutting off the extremes of the corners first, slicing them off slightly until the optimal path is found (it may be suboptimal by 1, e.g your example returning 0 --> 2 --> 18 -->19 but its close enough to not make that big of a difference). Also make sure not to slice the same side first every time, or you'll end up in a similar position. \$\endgroup\$ – Draco18s Dec 14 '15 at 19:40
  • \$\begingroup\$ That is, if Node[n-2] - Node[n+1] AND Node[n-1] - Node[n+2] (with n being the previously removed node) both differ, don't always pick the same one. Randomly choose between the two or alternate back and forth. Edit: thinking about this some more, you'd want to pick the one with the shorter distance. That would insure the best trim. \$\endgroup\$ – Draco18s Dec 14 '15 at 19:44

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.