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.
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.
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:
- 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).
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
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)
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)
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:
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;
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:
- Add a List inside the character to store the path he's currently following.
- On each Update cycle take the first value from the list and move your character towards it.
- If he gets close enough to the destination, remove the first element from the list and repeat.
- If the list becomes empty, he has reached his destination.