A* question

In theory, you cast out all rays to every possible corner, and then cull those which intersect obstacles. This is possible when precompiling the map, but not advised.

A better approach is to use occlusion: for every obstacle edge, compute the "invisibility cone" that goes out from that edge (if you prefer, the shadow that would be cast by the edge if there was a light at the starting point) and eliminate all points in the scene which fall within that cone (as well as any obstacle edges fully within that cone as well). You may use a partitioning scheme, such as a quadtree, to optimize this in order to eliminate large chunks at a time (if you start with obstacles very close to the visibility point, you should eliminate 60% of your scene in a handful of comparisons.The remaining points are those which are visible, and should thus be linked.

OK, I looked into it, and I'm sorry to say I'm still completely lost - I understand what you're getting at with the occlusion business, I've looked at a couple of tutorials and articles which seemed relevant, but I still don't understand how I can compute the "invisibility cone" (I'm still new at this).
Also, what would be the best way to check whether an object/polygon/edge was intersecting a line/ray? I can imagine checking every edge for an intersection every time a node is checked is probably not the best way. I know I can eliminate half of the edges by pre-calculating normals for the edges and doing a dot product to see if it's facing towards or away from the node, but that's as far as I get...

Thanks.

Look in the AI game programming Wisdom series of books (or the web!) for articles about Navigation Mesh (Navmesh) generation. The one in the 3rd book is quite good IMO, tho I see there are several articles about this comming in the 4th book.

There is also the Point of Visibility (PoV) approach, which is what PathEngine use I believe. Personally, I prefer navmeshes.

Quote:

Original post by DeathCarrot OK, I looked into it, and I'm sorry to say I'm still completely lost - I understand what you're getting at with the occlusion business, I've looked at a couple of tutorials and articles which seemed relevant, but I still don't understand how I can compute the "invisibility cone" (I'm still new at this).

Consider the triangle ABC, where A is your currently examined point and BC is your currently examined edge. An object (point or edge) is inside the invisibility cone if and only if:

1. It is on the same side of AB as C
   
2. It is on the same side of AC as B
   
3. It is not on the same side of BC as A

How exactly is that a 'better' approach than a simple line test to see if lines between waypoints cross obstacle lines?

Quote:

Original post by DrEvil How exactly is that a 'better' approach than a simple line test to see if lines between waypoints cross obstacle lines?

Quote:

Original post by ToohrVyk You may use a partitioning scheme, such as a quadtree, to optimize this in order to eliminate large chunks at a time (if you start with obstacles very close to the visibility point, you should eliminate 60% of your scene in a handful of comparisons).

Right, but it's significant extra work when the savings he's likely going to see may be insignificant. A brute force line test method is a more than suitable option as well. I could be wrong, as he didn't specify either way he was planning to use large numbers of obstacles or total vertices. Just thought it a bit premature to call the much simpler method 'not advised' when the little information provided in the request seems to imply(to me) the target usage is likely on the simpler side. No biggie.

Agreed, a straightforward approach would work if there were ~200 vertices on the scene. For large numbers of vertices, I believe it would become a bit too long (around 250 million edge-ray tests for 1000 vertices).

This problem falls under the broader problem of skeletonisation ('skeletonization' for our non-standard English writers... check both spellings if searching online).

As has been mentioned, point-to-point visibility tests are viable in real time only for small scenes. That is why pathing graphs based on visibility techniques are almost always computed offline at design time.

For much larger scenes with many thousands to millions of vertices, you might consider using a random tree approach... or look into the skeletonisation techniques commonly used in mobile robotics.

Cheers,

Timkin

Quote:

Original post by ToohrVyk Agreed, a straightforward approach would work if there were ~200 vertices on the scene. For large numbers of vertices, I believe it would become a bit too long (around 250 million edge-ray tests for 1000 vertices).

With such a large number (ie- N = 1000) you could probably do a 'reasonable' optimization of limiting the candidate set from each origin vertice by a max (box) range to the other vertices. A box radius of say 1/16th the width of the map (entire box being 1/8th) would give you something like a N x N/64 edge candidates x N/64 line segments to test intersection (each nav vertice corresponds to a obstacle vertice which provides 2 obstacle edges to test). That would be more like 256,000 intersection tests for about 1000 obstacle points.

If the obstacles dont move then all this could be precalculated of course.
Some minor analysis could be done on the results (ex- if one nav point isnt well connected (too few unblocked edges..) then a larger box radius could be used and the results recalculate for that one point.

Thanks for the replies everyone =D

I've been thinking about the layout of the maps in the game and I'm currently envisioning the environments much like diablo's random outdoor maps (well, I can't remember how diablo 1 did it, but diablo 2 at least - I may even look into generating them randomly), so basically a large outdoor area with a few (5-10 I guess) buildings/obstacles per cell, only I would leave cell boundaries open instead of having a path connecting them.
I guess this means cells will be pretty small in terms of complexity, so brute forcing should be feasible. I'd need to check each vertex against verticies of the current cell and all adjacent cells, but that should still keep the vertex count in the low hundreds for the most part - only the adjacent cells because I think I'm going to limit view distance to 1 cell width.
There's probably going to be a lot of cells but that's only a linear increase instead of a not-so-linear one.



Here's a possible mockup of some cells to help visualise it (possibly a wee bit more complex than the final thing, but you get the idea), the insides of the buildings would of course be handled separately, there would just be exterior nodes at the corners and entrance(s) (I guess the navmeshes Steadtler recommended could be more useful for the insides).
Doesn't look like a couple of nodes should take a huge amount of time to check viable nodes in real-time as well (for the initialisation of A*), given that most of the time I guess the actor and its destination won't need to go around anything anyway so they'll only need to check each other and no A* requried.

Hmm.. For the real-time creation of nodes for the start and end points, I think it may be enough just to check for obstacles between the two, and add edges between the nodes and the nearest obstacles to them as going around that object is pretty much a given (unless the nearest obstacle is a small one and there's a bigger one behind it, but that's a small compromise). So in the case of the image I made for the first post, only the triangle's and pentagon's verticies would be added to the edges to check with A*.

Thanks =)

Hum... Somehow, Im thinking delaunay triangulation to create the navigation graph, with dynamic path smoothing to remove unneccessary turns.

For scattered convex obstacles, steering behaviors or potential fields could also work, completely eliminating the need for a navigation graph, and possibly making it easier to implement more complex movement patterns.

I think you might be onto something with steering. I know I'm going to be implementing several steering behaviours into the AI anyway (e.g. flocking and seeking for groups of minions or enemies), I was going to assign the path nodes given by A* as seek targets but I guess simple obstacle avoidance should be enough for most cases.

From what I've seen/read, obstacle avoidance is generally good for smaller obstacles, but what if I need something to move from behind that large building to the other side? Some relatively smart form of wall following? Certainly doesn't sound like a walk in the park; but I guess we left triviality a while back.

I had a look at delaunay triangulation, and it looks like the graph it generates is a bit different from what I'm looking for (I certainly got the impression it would create paths that flowed from one object to the next, rather than finding the shortest path between potentially distant objects).

I just hope I'm not getting in over my head, this is for my 3rd year project at uni and it just seems to be getting more and more ambitious =( Still haven't worked out what to do about navigating interiors and other room-like environments, implementing PSSM or CSM for shadows on the rendering side, or how/where I'm going to create/get the models/textures/sounds required for the game. But I digress...

Thanks.

DeathCarrot, I'm a seasoned user of Computational Geometry, and not an AI programmer, so consider that a grain of salt;

I would solve this problem using ANY triangulation algorithm (not specifically Delaunay, which can be difficult for a computational geometry novice to code), it will give you a more sparse graph than you want, this is true, but I have done some graph searching problems on triangulations and it is fairly trivial to search 'across' triangles to find shorter edges which connect between vertices.

Imagine if in your original image, you removed one of every pair of edges that cross each other (bear with me), then as you searched the graph, thanks to it being a triangulation, every time you add a node to a search path you check to see if you can simplify the chain by creating a straight line from an earlier node to this one.

I think you'll find that the triangulation makes this very inexpensive, that the intermediate edges you create this way can be added to the graph so that in future they won't be recomputed (AI remebering things), and that you'll be able to compute the triangulation of the space on the fly, because triangulation itself is a fairly inexpensive algorithm, even in sub optimal implementations.

Another thing I was thinking about was (and this is an AI themed issue) that it actually seems less sensible to me to have actors that find the shortest path everywhere they go, maybe just a sensible path would suffice? Can you even do that?

I can certainly see that creating edges for new nodes when the graph is triangulated will be a hell of a lot easier computationally than to check all possible edges, but I don't understand how I'd go about making the subsequent movement fluid and predictable.

I think shortest paths tend to look natural enough, if I'm in a field and I need to navigate to the other side of a large boulder or a house, I can realistically estimate what the shortest path should be and I would certainly take it in real life. Smoothing of turns using steering behaviours is easy enough (and might work pretty much automatically already as there should be a natural repulsion to objects on the map).

Quote:

Original post by DeathCarrot I can certainly see that creating edges for new nodes when the graph is triangulated will be a hell of a lot easier computationally than to check all possible edges, but I don't understand how I'd go about making the subsequent movement fluid and predictable.

Thats what the path smoothing is for. To take your very first example, A* would have returned a 4 nodes solution using only adjacent nodes. Then path smoothing, making a quick visibility check, would have removed the second node (left to right), making the path exactly what you want.

It seems the idea you have is to keep a full connectivity matrix between navigation nodes. Its certainly not impossible, but as others pointed out, it scales too badly with the number of nodes.

I'm not sure I'm following you, how is a less than 4 node solution possible for the path in my original post? I guess I'm not sure what you mean by path smoothing, and I can't find anything relevant on the interweb (although I'm tired and grumpy so I may not have looked hard enough).
Also, again, I may have missed the point of your post, but my issue was not with A*, but with the triangulation - wouldn't the actor want to jump from an object to another nearby object and so on rather than taking the quickest route to the destination if I just created a triangulated mesh instead of a more completely connected approach? Kind of like stepping on scattered stepping stones when you could just as easily walk in a straight line to where you need to go.

But anyway, I'm starting to sway away from the whole drawing edges and nodes business to just using dynamic steering behaviours for obstacle avoidance, and that's something I know I can implement (granted, implementing some posh path-finding scheme could add some buzzword candy to my dissertation/thesis - but I guess there's still interior navigation which needs to be considered).

The idea behind the triangulation method is you'll end up with fewer edges than if you tried to create all possible edges. The path is then smoothed to avoid jumping all over the place.

Let's say the path is ABCDEF. If AC does not pass through any obstacles then B can be removed from the path, and AC can optionally be added to the navigation graph. Let's say AC passes through an obstacle (use quadtrees or something to limit the number of obstacles that need to be checked). So B is necessary. Now look at node D. Is AD a valid path? Is BD a valid path? And so on, for node E you'd check AE, BE, CE. The smoothed path isn't guaranteed to be optimal and the order in which you check for connecting segments can affect the result, but it will eliminate the random zig zagging that could be caused by only using a triangulation as the graph.