C# Pathfinding, smooth movement enemy to player. Walk around solids

Question

I need a way to implement path-finding into my game.

For example A* or Euclidean would work well for this.

I have a multi dimensional array of my Tile class which has a rectangle for bounds and a is_solid variable. The player is not restricted to the tiles and has free movement. So the enemy will smoothly path-find its way to the player.

I have tried implementing examples on the web, or on the fellow Stackoverflow database. But to no avail, I can't modify them to work with my project.

Got any examples/tutorials which you think would suit the way I developed my game and I could implement into my game more easily.

Answer 1

I did it this way with the help of this great article:

public class MyEdge//used edges and notes for my graph
{
    public int To { get; private set; }
    public int From { get; private set; }

    protected MyNode from;
    protected MyNode to;


    public MyEdge(int from, int to, MyGraph g)
    {
        From = from;
        To = to;
        this.from = g.GetNode(from);
        this.to = g.GetNode(to);
    }

    public MyNode NodeFrom()
    {
        return from;
    }

    public MyNode NodeTo()
    {
        return to;
    }
}

public class MyNode
{
    public int Index { get; private set; }
    public Vector2D Pos { get; private set; }
    public List<MyEdge> Edges { get; private set; }

    public MyNode parent = null;
    public double G = double.MaxValue;
    public double H = 0;
    public double F { get { return G + H; } }


    public MyNode(int x, int y)
    {
        Edges = new List<MyEdge>();
        Pos = new Vector2D(x, y);
        Index = -1;
    }
    public MyNode(Vector2D pos)
    {
        Edges = new List<MyEdge>();
        Pos = pos;
        Index = -1;
    }

    public MyNode(int x, int y, int idx)
    {
        Edges = new List<MyEdge>();
        Pos = new Vector2D(x, y);
        Index = idx;
    }
    public MyNode(Vector2D pos, int idx)
    {
        Edges = new List<MyEdge>();
        Pos = pos;
        Index = idx;
    }
}

Note: A edge has the nodes and a node has the edges. This is for better performance

public List<MyNode> GetPath(Vector2D startPoint, Vector2D endPoint)
    {
        //create the open list of nodes, initially containing only our starting node
        //create the closed list of nodes, initially empty
        List<MyNode> open = new List<MyNode>();
        List<MyNode> closed = new List<MyNode>();


        //Find the starting node
        MyNode start = FindNearestNode(startPoint);
        if (start == null)
            return null;

        //Find the ending node
        MyNode end = FindNearestNode(endPoint);
        if (end == null)
            return null;

        start.G = G(start.Pos, endPoint);
        start.H = H(start.Pos, endPoint);
        open.Add(start);


        while (open.Count != 0)
        {
            //consider the best node in the open list (the node with the lowest f value)
            double d = open.Min(x => x.F);
            MyNode curr = open.First(x => x.F.CompareTo(d) == 0);

            closed.Add(curr);
            open.Remove(curr);

            //If current node is goal              
            if (curr == end)
            {
                //Loop over the parents to get the path
                List<MyNode> ns = new List<MyNode>();
                MyNode n = end;
                ns.Add(n);
                while (n != start)
                {
                    ns.Add(n.parent);
                    n = n.parent;
                }
                ns.Reverse();
                return ns;
            }

            for (int i = 0; i < curr.Edges.Count; i++)
            {
                MyNode possibleNeigbour = curr.Edges[i].NodeTo();
                if (closed.Contains(possibleNeigbour))
                {
                    //ignore it
                }
                else if (!open.Contains(possibleNeigbour))
                {
                    possibleNeigbour.G = G(possibleNeigbour.Pos, endPoint);
                    possibleNeigbour.H = H(possibleNeigbour.Pos, endPoint);
                    possibleNeigbour.parent = curr;
                    open.Add(possibleNeigbour);
                }
                else if(open.Contains(possibleNeigbour))
                {
                    if (possibleNeigbour.G < curr.G)
                    {
                        possibleNeigbour.parent = curr;
                    }
                }
            }
        }
        
        return null;
    }