Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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 ?

share|improve this question
    
Retagged with C# and 2D, don't see why click-to-move or world-to-screen would be needed as tags. Also, just so that everything can be focused, it doesn't seem like the second question that you ask is really related to your first one. Please post that in a separate question. –  Noctrine Jul 30 '10 at 19:30
    
Why would you have a scrolling window? Usually the window is just a view port into a certain part of your world. You could definitely make a linear equation from point a to point b. Then you could use some curving functions to do some cool stuff like accelerate at the beginning and slow down at the end. –  Michael Coleman Dec 4 '10 at 18:40
    
I mentioned it as an example, I don't use scrolling window. You might have missundertood the forcing the user to navigate himself on the map instead of auto-navigating the user per click which basicly is when the user clicks on a determinated place it will move the window as the player moves but if players tries to clikc inside a house where the door is closed for example, it will walk toward the house on a straight line and stop at the first obstacle which means that the user does not have a auto navigating click to move but he has to click making his own way to the place he wants to go. –  Prix Dec 4 '10 at 22:23

2 Answers 2

up vote 5 down vote accepted

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:

visibility graph

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<Vector2> Vertices;
    }

    List<SimplePolygon> Outlines;
    List<SimplePolygon> 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<Vector2> 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<Vector> 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.
share|improve this answer
    
Awesome answer, I'm not even going to bother answering because I think you've covered anything I could say. +1 –  FullyLucid Dec 14 '11 at 2:49

Well... While you're learning don't forget that Google is your true friend in this endevour.

Step 1 is to get the mouse location -- http://msdn.microsoft.com/en-us/library/bb197572.aspx

Step 2 is to move sprite to Location A to Location B which involves basic physics/movement -- http://www.xnadevelopment.com/tutorials/thewizard/theWizard.shtml

The idea is the same moving the mouse is for getting your destination where the user clicks. You are still going from point A to point B.

What you're describing is an implementation detail which you can determine how you want to handle. I'm assuming your working with some sort of grid. The tiles on these grids will have specific properties like walkability. Attempt to move your sprite one step closer in the direction of the destination, if a tile is not walkable, stop.

If you want your sprite to actually get to the desination you would want to implement an actual pathfinding algorithm which analyzes your tiles walkability.

share|improve this answer
    
thanks for the first link which does help but the second not as much, i have updated my question with a few other points if u dont mind checking... thanks. –  Prix Jul 30 '10 at 18:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.