xna - 2D Game C# click-to-move samples?

Currently I am learning how to use XNA by making a 2D Game. So far I am doing okay, but I want to implement a click-to-move instead of using the keys to walk around but I haven't found any samples around and I am sort of clueless on how to approach it.

I know that XNA works well for xbox controls and keyboard but I haven't seen anything related to mouse interaction at all also I dont really mind about xbox since I am not aiming for anything else other then a PC game.

So what I am looking for is some samples of how the click-to-move is calculate done, and if the mouse icon displayed in game is also worked from the xna framework or if u have to make it your self in order to make the current tile glow or display that the mouse is there or something alike.

---

UPDATE:

Moving with the mouse is not quite the same, you have to consider obstacles aswell at least in my case of what i am planning...

For example i want the clicks to be considered as straight walking forcing the user to navigate himself on the map instead of auto-navigating the user per click so if he clicks past a wall for example it will walk to the wall and stop instead of finding the route to the other side if there is one... another doubt that comes to my mind using the getstate of X and Y for example on a scrolling window will it actually recognize where the mouse is or there will be the need of world-to-screen calculation to disclose where is point B that was clicked by the user ?

---

Thanks for any help and advices...

PS: Could someone perhaps add the click-to-move tag or world-to-screen ?

PPS: why it does not allow me to add the C# tag to it ?

Answer

Edit: Okay, I've just read from one of your comments that you don't want automatic navigation. In that case, only consider the final section in this post ("Walking that Path") with the simple case that the list only stores the place where your mouse clicked and clears itself when an obstacle is found in the way. I also just noticed that you mentioned tiles once in the post. In that case there's no need for a visibility graph, the grid itself can be used to run A-star on. Anyway I'm still posting this as a more general solution to the 2D point and click navigation problem.

What you're asking for is how to do pathfinding on a 2D environment. I've written an article before outlining one technique that is capable of solving that problem. I'll start by laying down a link to the article, and then add a brief explanation of the algorithm.

http://www.david-gouveia.com/pathfinding-on-a-2d-polygonal-map/

Of course, this is not the only way to solve it. I'm using a visibility graph. You could also use a navigation mesh. Or a grid. The visibility graph has one particular advantage that it always returns the most direct path between points without needing to do any path straightening. And building the visibility graph on top of a polygon you can specify the walkable regions precisely.

Concept

The main idea here is to represent your walkable region as a polygon and construct a visibility graph using the polygon's concave vertices. If the polygon contains holes you'll use their convex vertices too.

Creating a visibility graph means taking every node (or vertex in this case) of the graph and connecting it to every other vertex that it can "see". You need some line-of-sight check to do this. The one I used is built on top of a simple line segment intersection test, with a few added checks.

Then whenever you want to find the path between two locations, you add those temporarily to the visibility graph and just run a classic A* pathfinding algorithm on it.

Here's what the whole structure looks like:

Where:

• The yellow lines are the polgyon representing where you can walk.


• The white circles are the polygon vertices that make up the visibility graph (nodes)


• The purple lines connect vertices that are in line of sight of each other (edges).


• The light blue line is an example of finding a path between two locations (green dot and red dot).



• The light green lines are temporary edges added to the graph along with the starting and ending nodes in the path (green dot and red dot).

Implementation

1) Representation

About implementing this, first you need to have a way to represent a polygon for your floor. The following class should be enough:

public class Polygon
{
    public class SimplePolygon
    {
        List Vertices;

    }

    List Outlines;
    List Holes;
}

2) Selecting Nodes

Then you need a way to go through each of the polygon's vertices and decide whether they should be nodes in the visibility graph. The criteria for that is concave vertices in the outline and convex vertices in the holes. I use a function like this:

public static bool IsVertexConcave(IList vertices, int vertex)
{

    Vector2 current = vertices[vertex];
    Vector2 next = vertices[(vertex + 1) % vertices.Count];
    Vector2 previous = vertices[vertex == 0 ? vertices.Count - 1 : vertex - 1];

    Vector2 left = new Vector2(current.X - previous.X, current.Y - previous.Y);
    Vector2 right = new Vector2(next.X - current.X, next.Y - current.Y);

    float cross = (left.X * right.Y) - (left.Y * right.X);

    return cross < 0;

}

3) Selecting Edges

Now you'll need to go through every pair of these vertices and decide if they're in line of sight or not. I used the following method as a starting point for that check:

static bool LineSegmentsCross(Vector2 a, Vector2 b, Vector2 c, Vector2 d)
{
    float denominator = ((b.X - a.X) * (d.Y - c.Y)) - ((b.Y - a.Y) * (d.X - c.X));

    if (denominator == 0)
    {

        return false;
    }

    float numerator1 = ((a.Y - c.Y) * (d.X - c.X)) - ((a.X - c.X) * (d.Y - c.Y));

    float numerator2 = ((a.Y - c.Y) * (b.X - a.X)) - ((a.X - c.X) * (b.Y - a.Y));

    if (numerator1 == 0 || numerator2 == 0)
    {
        return false;

    }

    float r = numerator1 / denominator;
    float s = numerator2 / denominator;

    return (r > 0 && r < 1) && (s > 0 && s < 1);
}

But had to resort to using a few other hacks for stability on edge cases, so it's not in good condition to post. Still trying to find out a clean and stable solution to the problem.

4) Construct the Graph and Run A-star

You'll need to create a visibility graph using those vertices and edges, and run A* on it. For learning how to construct a graph and apply A* I recommend studying the following article:

http://blogs.msdn.com/b/ericlippert/archive/2007/10/02/path-finding-using-a-in-c-3-0.aspx

You might then want to encapsulate all of this in a single class, so that you have an easy interface to use, such as:

public class Floor
{
    public Floor(Polygon polygon) 
    { 
        _polygon = polygon; 
        BuildGraph();
    }


    public IEnumerable GetPath(Vector2 start, Vector2 end)
    {
       // Add start and end as temporary nodes and connect them to the graph
       // Run A* on the graph
       // Remove temporary nodes and edges
    }

    private Polygon _polygon;


    private Graph _graph;
}

This way you only need to create a Floor instance and call the GetPath method on it whenever you need to find the path between two locations.

5) Walking that Path

Finally you need to make your character walk the generated path. He needs to have some kind of internal memory for that, but it's not too hard to implement that. For instance:

1. Add a List inside the character to store the path he's currently following.


2. On each Update cycle take the first value from the list and move your character towards it.


3. If he gets close enough to the destination, remove the first element from the list and repeat.



4. If the list becomes empty, he has reached his destination.