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.

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.