More Precise PathSmoothing

Question

I'm reading a book about AI - Path planning and path smoothing. Yet this book is using c++ code. And i'm coding in c# with the XNA framework.

I have a path smoothing working, yet the book says it can be more precise (but being a bit slower).

This is the code i have until now:

    public static LinkedList<Vector2> SmoothPathEdgesQuick(LinkedList<Vector2> path, Player player)
    {
        LinkedList<Vector2> newLinkedList = new LinkedList<Vector2>();
        List<Vector2> toBeDeleted = new List<Vector2>();

        var edge1 = path.First;
        var edge2 = path.First.Next;
        while (edge2 != null && edge2.Next != null)
        {
            if (player.CanWalkBetween(edge1.Value, edge2.Next.Value))
            {
                toBeDeleted.Add(edge2.Value);
                edge2 = edge2.Next;
            }
            else
            {
                edge1 = edge2;
                edge2 = edge2.Next;
            }
        }
        foreach (var vector2 in path)
        {
            if (toBeDeleted.Contains(vector2))
                continue;
            newLinkedList.AddLast(vector2);
        }
        return newLinkedList;
    }

And this is working as it should work. But the book says it can be more precise by using this code:

void Raven_PathPlanner::SmoothPathEdgesPrecise(Path& path)
{
  Path::iterator e1, e2;

  e1 = path.begin();

  while (e1 != path.end())
  {
    e2 = e1; 
    ++e2;

    while (e2 != path.end())
    {
      if ( (e2->Behavior() == EdgeType::normal) &&
            m_pOwner->canWalkBetween(e1->Source(), e2->Destination()) )
      {
        e1->SetDestination(e2->Destination());
        e2 = path.erase(++e1, ++e2);
        e1 = e2;
        --e1;
      }

      else
      {
        ++e2;
      }
    }

    ++e1;
  }
}

Somehow i don't know how to update my original code to the one below to make my pathsmoothing more precise.

Answer 1

This took some figuring out for myself, but I've got one for you.

Note that in the if statement we have no changes to path (since nothing is removed from it). Now edge2 is changed it it's next every iteration, removing the need of the else statement.

I added nextEdge1Spot to avoid checking whether an edge has been deleted or not.

public static LinkedList<Vector2> SmoothPathEdgesPrecise(LinkedList<Vector2> path, Player player)
{
    LinkedList<vector2> newLinkedList = new LinkedList<Vector2>();
    List<Vector2> toBeDeleted = new List<Vector2>();

    var edge1 = path.First;

    while (edge1.Next != null)
    {
        var edge2 = edge1.Next;
        var nextEdge1Spot = edge1.Next;

        while (edge2 != null && edge2.Next != null)
        {
            if (player.CanWalkBetween(edge1.Value, edge2.Next.Value))

                //'Delete' all the skipped edges.
                var tempValue = edge1.Next;
                while (!tempValue.Equals(edge2))
                {
                    toBeDelete.Add(tempValue);
                    tempValue = tempValue.Next;
                }

                //Also delete edge2.
                toBeDeleted.Add(edge2);

                //Next time edge1 has to start here.
                nextEdge1Spot = edge2.Next;
            }

            edge2 = edge2.Next;
        }

        edge1 = nextEdge1Spot;
    }

    foreach (var vector2 in path)
    {
        if (toBeDeleted.Contains(vector2))
            continue;
        newLinkedLast.AddLast(vector2);
    }

    return newLinkedList;
}

Personally I would do the same as what the book does, removing nodes from the list you receive. But this should align well with your current code.

Hope it helps! :)