# How to find path in graph without crossing the walls?

I would like to know how to find path in a graph while having the edges "double-sided". Consider this scenario:

I have list of the line segments. These represents "walls" or rather impassable edges (in a game). I then plan in a next step to build a connected graphs (where possible). I'm trying to determine the feasibility at this point. If there's even a solution to this (it should in my opinion).

I don't need to know about A* or other algorithms per se, but rather how to not walk through the walls as seen in figure B. Any ideas?

I was wondering if I could turn segments to polygons (by adding width). Then make an union of these polygons and then treat them rather as polygons. But I would like to know whether there is a way to do it without this hassle. Also I'm not sure I want to add any width to the lines necessarily.

• Check out Half-edge data structure. While it's not a ready solution for your problem, it should give some inspiration on how to modify your data structure to fit the given problem. Nov 17, 2014 at 6:49
• msell: I will check that out as well. Probably kinda agrees with Russell's solution. Nov 17, 2014 at 9:27
• Please post your solution as an answer to the question, not an update to the question. You also have the option of selecting it as the correct answer. Nov 17, 2014 at 18:45
• I've accepted Andrew Russell's answer because it was the original answer. My only spawned from his by inspiration. What would be the point of me having an answer. I won't accept my own answer if I can choose some else's also correct answer. But if you're forcing me to this pointless task. So be it. I hope that's it. I would like to leave this page without returning few minutes later only to find it removed completely. Thanks. Nov 17, 2014 at 19:00

The problem is with how you are formulating your navigation graph. If you'll allow me to butcher your diagram:

Here is what the navigation graph should look like. For each node in the original graph with n edges, where n > 1, it should be replaced with n nodes. (Notice that each node in the graph is connected by two edges.)

Inserting start and end nodes is a little more tricky. I'd probably start by giving each edge in the updated graph a normal, so you can determine which edges are facing towards the point you wish to insert. The nodes connected to such edges would then be candidates to connect to your inserted nodes.

Once you have the correct graph, you can apply the usual navigation algorithms like A*.

• That's a good idea. Let me give it a try. Nov 17, 2014 at 9:14

You're misrepresenting your graph. What you really have is something more like this:

Where the red dots are your nodes, and the blue lines are your edges. This can be produced by creating four nodes for every node in your current graph. (There are actually even more edges that would be valid here as you could move diagonally between a number of these nodes.

The original graph can be used to ensure that the new edges don't cross any of your old edges, but it can't really be used for pathing as it is.

• I'm really sorry, but the circles were meant to signify the vertexes. They are not that big in reality. My fault, I thought it was obvious, but obviously it wasn't obvious. :) Nov 17, 2014 at 9:13
• @SmartK8: This answer seems to say essentially the same as Andrew's answer. Nov 17, 2014 at 15:58
• @SmartK8 Essentially, you're using the graph that's representing your non-walkable areas to try and find a walkable path. That doesn't work. One way or another, you need to create a new graph for the walkable areas, where the non-walkable graph is used to construct that graph. Nov 17, 2014 at 16:02
• The edges are non-walkable "areas". Your final polygon also shows the non-walkable areas. As well as in your polygon solution is to hug the walls, solution in original graph was to hug walls. Even though I accepted the answer it only inspired me (normal) to do a real deal. Which is measuring the leftmost point (angle). If the leftmost point is the end point you're done. Then I've done same thing for the right side and whichever path is shorter I will use. No need to recreate graphs, no conversions, only few angle calculations. The irony is that I've done it before (my article on CodeProject). Nov 17, 2014 at 16:41
• My image is of a graph, not a polygon. I included your original graph only for illustration purposes. Just as Andrew created a new graph, not a polygon. Glad you got it working. Nov 17, 2014 at 16:57

Update solution: Even though I was inspired by Andrew Russell's solution. For anyone interested. I've solved it in the end as such.

• 1) I first detect intersection (point I) with graph (or multiple graphs afterwards).
• 2) Then I find point in angle higher than angle from an incoming point (Intersection -> Start). Such point is marked yellow. I'm only concerned with points connected to one currently being processed + start/end point. If left-most angle point is end point, we're done.
• 3-6) Left-most points are processed and slowly the path around left side of the walls is constructed. This is very fast because no change in structure is needed. Only angle calculation for few points.
• 7a) Now I gathered the left part. I can now do the same (from point 1) and walk around the right side (right-most angle) this time.
• 7b) I have now left solution and right solution. The shorter one is my final solution.

If somehow I would end-up at start point as my left-most (right-most respectively), in that case there exists no actual solution.

Note: The main advantage is that no graph recreation is needed, and it works on existing structure. Also it doesn't need no other path-finding graph algorithm.

Still again thanks to Andrew Russell for giving me that aha! moment. ;)