# How can I remove unnecessary nodes from my path?

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.

        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]))
{
}
else
{
lastCp = i - 1;
}
}

for (int i = 0; i < nodes.Count; i++)
{
if (!toRemove.Contains(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.

It is because 0 --> 4 is uninterrupted (IsPassable(0,4) returns true), which causes the removal of Node3.
• 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. Dec 14 '15 at 19:40
• 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. Dec 14 '15 at 19:44