# A* question

This topic is 3799 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm going to be making a 3D game (SDL/OGL) in which I have AI "somethings" (undecided at the time of writing) moving around a map with obstacles and walls and things, I don't know much about game development (I've yet to make anything but simple experiments) but I'd imagine A* is the way to go for this one. I need some help in generating links between nodes; here's a diagram which will hopefully help explain the thing better: The green polygons are obstacles on the map, the green lines I can make easily enough. The red circles represent the actor and its destination. At the start of the level I presume I need to generate the black lines between the black nodes, however, I only want the black lines to go to any visible nodes, not ones obscured by obstacles, how would I check for this? I guess I could make the links manually, but that would be a wee bit tedious. Then when I want an actor (red dot) to move to another position (other red dot), I presume I would need to add links corresponding to the possible nodes they could move to (purple lines), but the previous issue still applies, how do I check which nodes I can go to? Once all the links are in play I guess the path (thick grey line) should be easy enough to calculate. Also, is this a good approach to take? It seemed pretty logical to me at the time, but if there's a better way to do things then I'd like to investigate. Thanks. =) [Edited by - DeathCarrot on August 9, 2007 6:44:33 AM]

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by DeathCarrotOK, 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

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

##### Share on other sites
Quote:
 Original post by DrEvilHow exactly is that a 'better' approach than a simple line test to see if lines between waypoints cross obstacle lines?

Quote:
 Original post by ToohrVykYou 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).

##### Share on other sites
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.

##### Share on other sites
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).

##### Share on other sites
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

##### Share on other sites
Quote:
 Original post by ToohrVykAgreed, 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.

##### Share on other sites
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 =)

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

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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?

##### Share on other sites
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).

##### Share on other sites
Quote:
 Original post by DeathCarrotI 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.

##### Share on other sites
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).

##### Share on other sites
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.

##### Share on other sites
That makes sense, I understand how smoothing like that is applied to triangulated graphs, but not fully connected ones as, well, they're already fully connected =)

But yeah, I see now how I could work with triangulated graphs, might make a simple test app tomorrow to see how it works in practice if I'm not too busy.

Thanks.

##### Share on other sites
Trying to follow the AI side of this...

I was hoping that the secondary edges (the ones that are not in the triangulation) would actually be detected and considered at search time, not as a post-processing step on the already created path.

So instead of doing something like this:

path = A*(to, from) // returns 'ABCDEF'
find_and_remove_redundant_edges(path) // returns 'ACEF'

the idea is that A* itself perceives the existence of the extra edges without the need to put them in the original triangulation, in this way, a truly optimal path would be found.

But I really don't know A*, so I'm gonna go read, and then come back to this :)

OK, and the other thing I said, about not taking the optimal path to begin with, I guess in a field with some rocks in it, I can see that it shouldn't be difficult to find the optimal path, but in a large building complex, maybe the optimal path really isn't obvious.

##### Share on other sites
Quote:
 Original post by SymphonicTrying to follow the AI side of this...I was hoping that the secondary edges (the ones that are not in the triangulation) would actually be detected and considered at search time, not as a post-processing step on the already created path.So instead of doing something like this:path = A*(to, from) // returns 'ABCDEF'find_and_remove_redundant_edges(path) // returns 'ACEF'the idea is that A* itself perceives the existence of the extra edges without the need to put them in the original triangulation, in this way, a truly optimal path would be found.But I really don't know A*, so I'm gonna go read, and then come back to this :).

A* is a graph algorithm, it works with edges and nodes, dont forget that.

Computing and using the "Fully connected" graph will work for very small projects, but will become terribly inneficient as the size and complexity of your levels increase, as others already explained.

Take a 30 nodes example. With a full connectivity graph, we are talking up to 870 edges. With a correct triangulation, I believe the maximum number of edge will be 6*n (dont ask me the proof, I read it somewhere). So 180 edges at most, less if you use a polygonal navmesh.

Now with 1000 nodes, which isnt that much really. triangular navmesh: 6000 edges at most. Full connectivity: up to almost 1 million edges. *whistle*

##### Share on other sites
It's not necessary to know every possible edge when finding an optimal path. Even if the complete graph was used, only the edges that are local tangents to both of their obstacles need to be stored. Edges that are not locally tangent to an obstacle will never be used. A line is locally tangent to a polygonal obstacle if the points on either side of the point that the line intersects are both on the same side of the line.

For convex shapes there are 4 shared tangents. Now the number of edges is at most quadratic in the number of obstacles, not the number of nodes. Under most common circumstances, most of these edges will be obstructed by another obstacle.

##### Share on other sites
Quote:
 Original post by VorpyA line is locally tangent to a polygonal obstacle if the points on either side of the point that the line intersects are both on the same side of the line.

Yes, and a tangent to a polygon is a line which intersects the boundary of the polygon, and for which the entire polygon lies to one side.

My Thruff with using the tangent map is that you can create problems for which the tangent map's size is exponential in the number of obstacles.

Not to mention issues like local tangent maps for simple polygons, which have O(n) bounded size.

I'm working on a proof now that A* applied to a triangulation whose path is subsequently optimized for blank spaces will yield an optimal result. I expect the trick to lay in constructing the path using A* and then using A* again to choose the optimal path across all your potential optimizations (this second search tree is linear in the size of the original path).

What concerns me now is that if the triangulation is sufficiently 'bad' you might have chosen a path that's must be longer than the optimal by mistake.