Pathfinding on a 2D Polygonal Map

I haven’t had much time to update the blog lately (mostly due to having to crunch work on my thesis) and for that I apologize. But since it’s been one month since my last post, I decided to write something up today, even if it’s not a full blown article with source code like my previous posts.

So, here’s the deal! I’ve been working on 2D point-and-click graphic adventure game engine and editor lately, and what I’d like to share today is the general idea of how I ended up implementing the pathfinding for my engine.

If you’ve never seen a 2D point-and-click graphic adventure game, it’s a game genre that used to be really popular during the 90s. I think this video sums it all up (literally):

So, in most point-and-click graphic adventure games, whenever you click on the screen, your character tries to get as close as he can to that location, while evading all the obstacles along the way. But unlike a tile-based game where the walkable areas are easily represented by a regular grid, the floor on a graphic adventure game can have virtually any arbitrary shape.

In the old days (in the golden era of LucasArts and the SCUMM) they would often represent the walkable areas as a set of walk boxes, which were really nothing more than simple horizontal trapezoids laid down to cover the entire floor area. A pre-processing stage would then calculate the shortest path between each and every walk box, and store the results in a matrix, so they could simply be looked up at runtime (which traded an higher memory footprint for increased performance).

Nowadays, computers have become so advanced that it’s not really necessary to do this – we can simply run the pathfinding in realtime and be done with it. And as for the floor representation, I wanted something that would be easier to define in my editor than trying to manually cover the floor with individual trapezoids. I wanted the user to be able to simply *draw* any shape he wanted, no matter how complex, and have the character automatically know how to navigate it!

So here’s a video of what I came up with:

Algorithm

The pathfinding algorithm used in the video is really just a regular A*. I recommend this resource to learn how to implement it in C#, and what I used is pretty much just a direct translation from the method described there! What’s more special here is how the graph is created, which is what enables us to walk all over the surface of the polygon without ever leaving it, and always finding the shortest route possible. So, here’s the process needed to create the graph:

  1. First, create a graph node for each concave vertex of the polygon. If the polygon has holes, then you should also include the convex vertices of the hole polygons.
  2. Run a line-of-sight algorithm between each pair of graph nodes and link those which are in direct line-of-sight from each other.

As an example, here’s a simpler polygon than the one in the video. I’ve marked all the concave vertices with a circle, and you can also see the connections between each of them. This is all you need to be able to walk over the polygon!

This sort of graph is usually referred to as a visibility graph, and because of that, the pathfinding method I used is also known as points-of-visibility pathfinding. You can read more about it in the first two Game Programming Gems books, on the articles “The Basics of A* for Path Planning” and “Expanded Geometry for Points-of-Visibility Pathfinding” respectively. The graph could still be optimized to remove a lot of redundant edges that will never be needed to move around obstacles, but I left that for a later stage since I’m not running into any performance issues at the moment.

With your graph structure created, you can apply the A* algorithm over it by following these steps:

  1. First verify if both the start and end points of the path are inside the polygon. If the end point is outside the polygon you can optionally clamp it back inside.
  2. Then start by checking if both points are in line-of-sight. If they are, there’s no need for pathfinding, just walk there!
  3. Otherwise, add the start and end points of your path as new temporary nodes to the graph.
  4. Connect them to every other node that they can see on the graph.
  5. Run your A* implementation on the graph to get your path. This path is guaranteed to be as direct as possible!
  6. Finally, remove the two temporary nodes from the graph.

Taking the graph from earlier, this process could be represented as something like:

Where the red and green dots are the start and end nodes which have been added to the graph, and linked to every other node they can see (the green lines). Then a path is taken from this new graph (the light blue line).

Code Snippets

I don’t have a full sample that I can share at this moment, but I’ll describe two of the most tricky parts of the process. Hopefully you can figure out the rest from the references I gave above.

One essential part of the process is knowing if two points inside a polygon are in line of sight or not. In order to do that, I run a line segment intersection test between the line segment formed by both nodes, and all edges of the polygon. If both nodes are in line-of-sight, then the test should return false. It’s not very efficient since I compare against all edges of the polygon, but it gets the work done. Heres the helper method I use for the line segment intersection test:

The other important point is to know whether a vertex in a polygon is convex or not. I use the following method for this (remember, if the polygon you’re testing is a hole, then you should invert the result):

To check if a point inside a polygon I used the following method which has some extra code added for tolerance near the edges:

And to check for line of sight between two points inside the polygon,  it was basically this:

Finally, you might have noticed how in the video I was joining and subtracting polygons from each other while drawing. This process was made easy due to a library called Clipper (which you can get here). It’s pretty easy to use! What I’m doing is close to:

And that’s all for today, I hope you enjoyed it. I don’t have any source code at this time, since this is still coupled with my game engine, but I might get to it sometime in the future when I have more time. Until then!

27 Comments.
  1. Pete Street says:

    Sweet stuff, as usual.

    • Thanks Pete!

      I think I might write another article related to this topic soon. Before turning to points-of-visibility pathfinding, I had a navigation mesh system implemented. It would also take any polygon like this, and automatically generate a navigation mesh (made up of convex polygons only) for it, which looked pretty neat!

      But I didn’t like some of the paths it created and I ended up scrapping all of it and changing to this scheme because it always gives THE shortest path possible.

  2. Josh Duncan says:

    I like it! I have a algo written at the moment but it uses 13 bytes per co ordinate, so once you get a map of around 2500×2500 it uses almost 83mb of ram, let alone maps of size 20000×20000! You wouldn’t happen to have some code or some samples you could send me to use this, as it seems faster, more like what I need and more efficient than mine.

    Thanks, Josh

    • Sorry for the very late reply. I’ve been inactive for a while. Just to note that if you’re using a tile map, then this approach is not all that appropriate, because it will be difficult to figure out where to place the nodes. You could try creating a quadtree from the map, as it will result in a lot less nodes if there’s a lot of open areas. Either way I’ll try to post a sample of this article soon.

  3. Leandro says:

    Hi David!. Excellent tutorial, thank you so much! I wanted to ask you, which method did you use to clamp the point back inside the polygon? Thanks again!! :)

    • Hello! It’s nothing special really. The basis was a “GetClosestPointOnLineSegment” method which returns the closest point on a line segment to a certain location. Basically a projection / dot product and clamping the result inside the line segment. Using this, if the point is outside the polygon, I repeat that for every edge of the polygon and return only the closest match of all.

  4. Yani says:

    Any chances of releasing a sample of the project you showed in the video?

  5. Leandro says:

    Thank you David! That’s exactly what I’m doing, but for some reason, just sometimes, even when the new point lay on the edge of the polygon, the algorithm considers that it is outside the polygon.
    If you could post your source code, it would be great! :)
    Thanks again!!

    • I know what you mean, I had a lot of problems because of that. My first solution involved keeping a second copy of the polygon that was expanded by one or two pixels, and using that polygon to do the checks. But later I managed to add tolerance to all of my checks. I’ll make a full sample later, but for now here’s the point in polygon test I used:

      http://pastie.org/5579312

      The main point of interest is line 20, and what I’m doing is basically comparing the point against a very thin ellipse placed on top of the edge. If the point is inside that ellipse, then I immediately consider it to be inside (or outside depending on the value of “toleranceOnOutside” which is useful for holes). This allows the algorithm to behave correctly even when the point is on the edge.

  6. hu says:

    http://www.david-gouveia.com/davidgouveiacom/wp-content/uploads/2011/05/VisibilityGraph.png

    thanks david, but this map considered 3 polygon or 1? i considered it as 1 polygon, and can’t check vertex is convex or not. but if there are 3 polygon, how can i check a point inside the map or not?

    • Hello and sorry for the delay!

      I consider that as a single polygon with two holes. I’m storing this information in a Polygon class that is something like this:

      class SimplePolygon {
      – List(Vector2) Vertices;
      }

      class Polygon {
      – List(SimplePolygon) Outers;
      – List(SimplePolygon) Holes;
      }

      So in this case I have three SimplePolygons, but they’re all stored inside of a Polygon class, one in the Outers list and the other two in the Holes list.

      So in order to check if a point is inside the polygon, first I check that it is NOT inside any of the holes, and only then do I check that it is inside any of the outers.

      About the vertices being convex or not, the thing to understand is that a vertex that is convex on one of the polygon holes, is actually concave in relation to the entire polygon. So you can use the same test, but invert the result.

      Or in my case, since the convexity test is based on the winding order of the polygons, I defined my holes already using the reverse winding order from the outers, so that I can use the exact same test without changing the sign.

      Hope this answered your questions.

    • hu says:

      nice design man :D, that’s mine
      class Mesh
      {
      – list nodes;
      – list edges;
      }
      class Node
      {
      – int x, y;
      – bool concave;
      }
      class Edge
      {
      – Node A, B;
      – int length;
      }
      ————————–
      it’s hard to implement some algorithm. it seem i should clear and write new code :D

  7. Leandro says:

    Hi David! Sorry I took so long, thank you so much for your help, now it works perfectly! :D

  8. Pepe says:

    Hey David, i am currently working on “The Inner World” our own first 2D point & click adventure. I am currently optimizing my pathfinding stuff (which i started nearly 1 year ago) and i am getting sick of the old walk boxes stuff i did back there. I started rewriting the stuff in order to build an A* Graph – and stumbled across your implementation here. Is there any possibility to get the src-code of your demo project? I am curious about your line of sight implementation!

    Greetings,
    Pepe

    • Hello,

      I’m sorry for the delay. I did promise to share the source code before, but I need to remove all the dependencies from the project where I used this system first, which is taking some time.
      But I’d be happy to answer your questions meanwhile! About the line of sight implementation, the way I implemented is not really efficient, but I was more concerned with getting it to work correctly. I had a lot of trouble finding information on the subject online, so the way I used is pretty much made up, and probably not the best way to do it.

      I’m posting the gist of it below. I brute-force this test between each pair of nodes when creating the graph. Also, the point in polygon and line segment cross tests need to be implemented in a way that has some degree of tolerance to floating point errors.

      [sourcecode language=”csharp”]
      bool InLineOfSight(Polygon polygon, Vector2 start, Vector2 end)
      {
      // Not in LOS if any of the ends is outside the polygon
      if (!polygon.Inside(start) || !polygon.Inside(end)) return false;

      // In LOS if it’s the same start and end location
      if (Vector2.Distance(start, end) < epsilon) return true;

      // Not in LOS if any edge is intersected by the start-end line segment
      foreach (var vertices in polygon) {
      var n = vertices.Count;
      for (int i = 0; j < n; i++)
      if (LineSegmentsCross(start, end, vertices[i], vertices[(i+1)%n]))
      return false;
      }

      // Finally the middle point in the segment determines if in LOS or not
      return polygon.Inside((start + end) / 2f);
      }
      [/sourcecode]

    • Pepe says:

      Hi David,

      no need for excuses there! Last night i tried it myself and came up with nearly the exact same simple brute-force implementation like you did there :) The middlepoint of the LOS determines if it’s a LOS inside the poly or not. But Thanks a lot anyway for this cool article! I’m just finishing my A* stuff on this am lookin’ forward how our main character will get around obstacles now :) Of course i am still lookin forward to some demo code too.

      Greetings,
      Pepe

  9. Paduraru Ciprian says:

    Hello David! Nice article, but i have one question: How would you adapt the algorithm if you have entities (for which we want to find paths) of different sizes ? At this moment i think I should move the graph nodes with a certain distance away from the original position. But it looks error prone.

    • Hello! As you would expect, that is not an easy problem to solve. It is something that I have never implemented although I have read about it in some book (probably one of the Game Programming Gems book, or AI Game Programming Wisdom).

      If I remember correctly, the key point was first to create a polygon to represent the bounding area of the entity, and use the Minkowski sum algorithm to create an expanded version of the floor polygon by combining it with the entity polygon. Then you would create the graph from this expanded version of the polygon and everything from there would be the same as before. The entity polygon would ideally be a circle since it is immune to rotation, but even an approximation would result in too many added vertices, so I think you should probably use something simple such as a square, pentagon or hexagon.

      After applying the Minkowski sum, I imagine you would also need to validate the polygon and merge all the overlapping portions. For instance if you had a narrow corridor in your map, and your character was larger than the corridor, after the expansion, both corridor walls would be overlapping, so the corridor should be removed completely from the polygon. If possible, try to find external libraries to do these operations for you.

  10. Simon says:

    Interesting. Are you handling things like scaling the character by virtual distance from the screen (either something simple like a scalar based on y-pos or perhaps a more complex distortion?)

    Also, how do you handle defining when the character should be drawn before/behind certain objects/layers?

    I’m also planning a point and click adventure and stumbled across this while considering architecture.

    In any case, it looks very slick :)

    • Hello, thanks for dropping by!

      To answer your questions:

      1) I implemented character scaling by adding two scale values to each room (one for the top of the room and one for the bottom). Then I interpolate between those scale values depending on the Y position of the entity compared to both of those values.

      2) For sorting entities, I divided every room into three layers: background, foreground, and dynamic. Entities on the background layer are always drawn first, entities on the dynamic layer are drawn next, and entities on the foreground layer are always drawn last. For entities on the dynamic layer, their number is small enough that I can sort them by their Y positions every frame, using a stable sort algorithm, so that entities that are closer to the top of the room get drawn before the others.

      Best regards,
      David Gouvia

  11. Tijs says:

    Hello,

    Can you please elaborate on when a vertice is convex or concave? In my current engine I check all vertices against eachother, but that is too slow.

    Thank you!

    • Tijs says:

      Also, very interested in other performance tips!

    • Tijs says:

      And finally, the e-mail address you provide in about doesn’t seem to work.

    • Hello,

      Thanks for letting me know about the e-mail. I changed host and forgot to setup the e-mail forwarder. I’m looking into it now :)

      I posted the convexity test in this article. Search for the “IsVertexConcave” function, which only needs to check 3 vertices to give a result. I run that function once for each vertex in the polygon. But since this only needs to happen when the polygon changes, It did not give me any performance problems.

      Overall, I did not implement anything special to improve performance, because I did not find it necessary. I tested it with a very, very complex polygon, and ran the pathfinder every frame without any problems. Add that to the fact that for the game I needed to use this on, the polygons were always going to be a lot simpler, and I would only need to run the pathfinder whenever the user clicked on the floor, so the implementation seemed good enough as it is.

  12. csisy says:

    Hey!

    Nice article, I’ve thought about something similar.

    I’m working on a 3D click to move (like Diablo) game. What do you think: could it be viable to define only the obstacles? I mean I haven’t “outer” polygon, just the holes which can be convex or concave, doesn’t really matter.

    Then, when something moves, update the links in the graph, running line of sight for all vertices. However, I fear that it could be slow to check the whole graph per frame.

    A space partitioning could be used to check the line of sight from start to end faster.

    The other way is to connect the holes with only one link and use Theta* instead of A*. It checks line of sight inside the pathfinding algorithm. Which means, updating a graph can be more cheaper (you have to find only one connection between two holes), however the Theta* is slower than A* (because of the extra check)

    • csisy says:

      Hi again,

      I’ve implemented it pretty fast (of course I have to optimize and refactor it a little bit :)) and works pretty well on a small graph.

      Here is a video about it:
      http://youtu.be/YywDuAi_yzk

      I’ve chosen A* instead of Theta*, beucase the graph won’t change in every frame. Maybe won’t change at all. So I have to compute connections just when it has been modified (plus the start and end node connection).

Leave a Reply