3
\$\begingroup\$

I am struggling with implementing continuous path-finding trough visibility graphs. Notice, I know that grids can be used even when movement is not trough grids (e.g. Theta*). But for my current needs, I really have to implement a real visibility graph path-finding.

First, I understand the logic of such an approach: 1) finding the points that go at each corner around obstacles, 2) calculating which of these points have direct connections to each other, 3) then applying A*. I am able to do steps 1 and 3 by my own, but I can't find out how to do number 2. It means, how can I find out which points are visible to each other and then transform it into an array to use with A*, in an efficient manner in terms of computer processing (i.e. avoinding raycast)?

I use Unity and C#, but also favor pseudo-code format. Please, suggestions, tutorials, sources, are all welcome.

\$\endgroup\$
0
\$\begingroup\$

For the first step, I'd use the bounding box of the obstacle to compute the points as it'll be much easier and computationally less expensive. If you want, here's how I'd do it:

//PlayerExtents includes margin for avoidance
Vector2[] GetPointsAroundObstacle(Bounds b) {
    Vector2[] points = new Vector2[4];
    points[0] = new Vector2(b.min.x, b.min.z) - PlayerExtents;
    points[1] = new Vector2(b.min.x - PlayerExtents.x, b.max.z + PlayerExtents.z);
    points[2] = new Vector2(b.max.x, b.max.z) + PlayerExtents;
    points[3] = new Vector2(b.max.x + PlayerExtents.x, b.min.z - PlayerExtents.z);
}

But for my method, you can use a convex/concave hull too so long as the points on the grid form a polygon.

If you are getting the points using the bounding box, the function will return 4 points on the grid. From there it is just a simple matter of seeing which vertices are connected directly to which on a square for the second step.

So if the square/polygon formed is as follows:

   1        2
    - - - -
    -     -
    -     -
    - - - -
   0        3

Where 0, 1, 2, 3, ..., n - 1 are its vertices, then (if I've understood you correctly) simply

0 -> 1, 3; 
1 -> 0, 2;
2 -> 3, 1;
3 -> 2, 0;

This holds true for any n-gon, so you can even use a more complex shape.

Or a simple function for this (I like Python for pseudocode :P) :

def connections(i, n):
    c = []
    c.append(i + 1 % n)
    c.append(wrap(i - 1, n))
    return c

where wrap() is

return i - 1 <= -1 ? n : i - 1

Now you can build the graph of the points around obstacle and use A*.

\$\endgroup\$
  • \$\begingroup\$ Hi Evil, many thanks for your detailed comment, it was interesting to a different approach than mine. I say different, because you can notice that actually I mentioned in the question that I knew how to do the first step (although your solution proved to be slighted more efficient). What I can't figure out how to do is precisely the second step, i.e. building the graph! What you mentioned in that part does not do the job: for a visibility graph it is needed to detect whether connections between vertices are blocked by other polygons defined as obstacles. And that's the harder part of the deal \$\endgroup\$ – MAnd Sep 28 '15 at 5:00
  • \$\begingroup\$ So I haven't done much research on the topic. But let's say you have a graph and an obstacle intersects some edges. You want to find the edges that are intersecting the obstacles or not, yes? \$\endgroup\$ – EvilTak Sep 29 '15 at 1:21
  • \$\begingroup\$ Hi @Evil Tak, that's right. I want to identify, for each vertices in a scene, which other vertices are visible, i.e. do not have any edges between them. I can do that in the naïve way, looping trough each pair of vertices and testing line-line intersections against all edges. However, that's very inefficient and would like to learn the more advanced ways of doing so. \$\endgroup\$ – MAnd Oct 1 '15 at 20:06
  • 1
    \$\begingroup\$ Since this is now effectively a collision detection problem, you can use broadphasing methods to reduce the time complexity. Simple ones would be the Sweep and Prune or the Grid spatial subdivision approach. I wrote an article on Sweep and Prune here: blog.evilstudios.net/2015/09/… Instead of AABBs, you could use an Edge class (you may already have one) and instead of min-max points, make it the vertices of the edge. So in this case, you would pass all the arrays to the Sweep and Prune function, which will do: \$\endgroup\$ – EvilTak Oct 2 '15 at 3:26
  • \$\begingroup\$ Get the list of edges, foreach edge make it such that the lesser one on the current axis (I recommend you do only one axis either X or z) will be vertexA and the other vertexB. Generate the AxisPoints Then perform the insertion sort like I did in the link. You'll know whether the current point is min or max by comparing it with vertexA. Then perform a simple line-line intersection test for those edges which could be overlapping. Your line line intersection test should just involve two dot products in my opinion. \$\endgroup\$ – EvilTak Oct 2 '15 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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