Hi, I am trying to get to grips with pathfinding and all that comes with that. I started programming C++ and OpenGL about 1½ years ago now and I'm happy to say that I've sort of got most of it down now. I'm able to do stuff! Hehe. Now I've started thinking about AI for my game project. I'm still some way away from actually implementing anything but I think I need to get some things sorted out first. The picture below contains a few paths and variaties to them. Questions, then (with the "there are no stupid questions" motto in mind): 1: In the first path, I have a starting point and an end point (red). When I start out I try to find the next waypoint/node and then move to it. Then I calculate again if the distance to the end node is shorter by moving forward or backward and move again and do this until I reach the end point. On the second path, the blue background is a navigation mesh. I have here used the midpoint of the polygons as nodes and move between them. My question regarding this first set of pictures is: What is the difference between using a navigation mesh and just using nodes? To me it seems like the same thing. 2: The path on the bottom left shows an end point (red) between and outside the waypoints (black). What if the user wants to move here? I can't support it since I haven't put a node there. This turns out to be an invalid move. And even if the user clicked to move ON the path but between nodes it'd be invalid nice there are no nodes there. Only travel information. This begs the question: What if I want complete movement between nodes and at least a bit outside of the given path, how would I accomplish that? It'd force me to put nodes right next to each other all over the map to give the player the ability to move wherever he or she wants to. Using a navigation mesh I get more nodes "automagically". If I use quads, I've got 4 vertices per polygon which can act as nodes and the midpoints of 4 lines + the middle line dividing the polygon into triangles. A total of 9 nodes to a single polygon. What if the user then clicks in a space between the middle line and an outer line or vertex? It would result in that the user gets frustrated because he can't control his character enough, when he clicks the map, the character moves allmost to the correct spot. However, considering that this spot might lie beyond a wall giving the enemy AI the opportunity to kill the players character... not a solution. 3: If I meet and obstacle on the way (as in the fourth path) I need steering AI which can navigate around this "unwalkable" obstacle. But how far out from the path should the AI walk? 4: Consider the last image of a navigation mesh and nodes. From Node 2 to Node 3 and then to Node 4... however, moving from Node 2 to Node 4 might be a more suitable path, since it's faster. The navigation mesh can't handle the AI moving in that direction, though. Because the mesh doesn't extend that way. And if I were to put a polygon there, filling up the space, the polygon would become large and the user would be able to click it, resulting in the character moving from edge point to edge point but never to the middle, or off centre or anything on that big polygon. Thank you in advance for taking the time to read this post. Marcus Axelsson

Quote: What is the difference between using a navigation mesh and just using nodes? To me it seems like the same thing.

One answer here is the old refrain, "A* is just a graph search algorithm;" this would be followed by pointing out that the vertices in your graph need not correspond to points per-se (although graphs are usually drawn that way), and that for instance the graph vertices when you use a navmesh are in fact entire polygons. Then we'd compare and contrast how the more abstract graphs are related to the geometry in the two cases of a "navmesh" and "nodes." And I will emphasize this point a little: The graph is abstract, and although it is drawn as lines in space with points as vertices, make sure you're used to thinking of these vertices and edges as possibly also corresponding to other things, like polygons/regions/etc, either in your environment or in more abstract state spaces.

In general, the navmesh idea has the advantage that your graph encodes more information. If you use the "node method" (by which we mean "graph vertices correspond to points in the environment") and you're not exactly on a node, it's not clear what you should do: Go to the nearest node? There might be an obstacle between you and it. Something else? Whereas with a navmesh, you are always in a region corresponding to a graph vertex, so there's none of this ambiguity. Continuing this line of thought, navmeshes also give you e.g. clearance information: An edge in a navmesh can have an associated "width" label, which determines which units (of different sizes) can traverse it.

On the other hand, the "node method" is useful for situations in which it is not easy to break the space you're pathfinding in down into polygonal regions. This is particularly the case for more abstract "pathfinding" (called "planning" in the literature), like finding a path through the joint space for a robot arm to get it to grasp something. For these kinds of applications, so-called "randomized sample-based planners" or "probabilistic roadmaps," etc -- which are essentially "node methods" -- are popular.

I know I just spent a bunch of time talking about just one aspect of your post, but I'm sure it'll all get addressed before long! :-)

Quote: Original post by Emergent
One answer here is the old refrain, "A* is just a graph search algorithm;" this would be followed by pointing out that the vertices in your graph need not correspond to points per-se (although graphs are usually drawn that way), and that for instance the graph vertices when you use a navmesh are in fact entire polygons. Then we'd compare and contrast how the more abstract graphs are related to the geometry in the two cases of a "navmesh" and "nodes." And I will emphasize this point a little: The graph is abstract, and although it is drawn as lines in space with points as vertices, make sure you're used to thinking of these vertices and edges as possibly also corresponding to other things, like polygons/regions/etc, either in your environment or in more abstract state spaces.

I'm really trying to understand this, but I'm not. I don't know if it's my english that's not good enough or if I'm just daft. But, a vertex is a vertex and a line is a line, what else could they be? I have always thought that a vertex is a representation of a corner/meeting point on a polygon, a connecting point for the lines building the polygon. Say that you have a quad polygon, that is 4 vertices connecting four outer lines and one inner is connecting to 2 of those 4 polygons. If I'm to think of this polygon as a region encompassed by lines, then what's the middle line doing? Are you talking about triangles? In that case we've got 3 vertices and three lines connecting and none in the middle. So talking about polygons gets relative to how it's built. Right?

Quote: Original post by Emergent
In general, the navmesh idea has the advantage that your graph encodes more information. If you use the "node method" (by which we mean "graph vertices correspond to points in the environment") and you're not exactly on a node, it's not clear what you should do: Go to the nearest node? There might be an obstacle between you and it. Something else? Whereas with a navmesh, you are always in a region corresponding to a graph vertex, so there's none of this ambiguity. Continuing this line of thought, navmeshes also give you e.g. clearance information: An edge in a navmesh can have an associated "width" label, which determines which units (of different sizes) can traverse it.

Do you mean that on a "node graph" we're allways moving on a straight path from one point to the next, and on a navmesh we're moving in relation to the points, being careful not to move outside the polygon creating the region we're in?
If so, couldn't this navmesh behaviour be accomplished by using some sort of "leash" connected to the path. This leash wouldn't be able to get longer than X units before the unit needs to find another path or stop.
I'm not trying to argue, I'm just trying to understand the differences.
The width argument, I get. Since there's no region to relate to the "unit" needs to move straight along the path and there's no way to check if the "units" bounding box is outside the active region/polygon. However with a navmesh we can do collision testing and more.
Am I getting this right?

Quote: Original post by Emergent
On the other hand, the "node method" is useful for situations in which it is not easy to break the space you're pathfinding in down into polygonal regions. This is particularly the case for more abstract "pathfinding" (called "planning" in the literature), like finding a path through the joint space for a robot arm to get it to grasp something. For these kinds of applications, so-called "randomized sample-based planners" or "probabilistic roadmaps," etc -- which are essentially "node methods" -- are popular.

Using this information, a navmesh is better suited for pathfinding in games since most everything is done in polygons (in a 3D game, that is).

Quote: Original post by Emergent
I know I just spent a bunch of time talking about just one aspect of your post, but I'm sure it'll all get addressed before long! :-)

Oh, don't worry about it. It's great, actually. If I can get this much information on the other questions in my topic I'll be a happy guy :)

Quote: Original post by tre
I'm really trying to understand this, but I'm not. I don't know if it's my english that's not good enough or if I'm just daft. But, a vertex is a vertex and a line is a line, what else could they be?

The words "vertex" and "edge" have different meanings in geometry and graph theory.

Let's state a formal definition: A graph G is a pair G=(V, E), where V is some finite set, and E is a subset of VxV. We call the set V the vertices or nodes of the graph G. We call E the edges of G. If whenever an edge e1=(v1,v2) exists in E, another edge e2=(v2,v1) also exists in E, then we call the graph G undirected.

Let me clarify one bit of notation: When I write 'VxV,' I'm referring to the Cartesian product of V with itself. Basically, if you have two sets A and B, then an element of the set C=AxB, if you were to implement this in a programming language, would be a struct containing an element of A and an element of B.

Usually to visualize a graph (say, on paper), you represent the elements of V by points in the plane, and the elements of E by arrows pointing between them. And if G is undirected then we drop the arrowheads and just draw line segments. However, in principle, V and E are just sets.


Example 1: Suppose V1={1,2,3,4} is a subset of the integers, and

E1 = {(1,2), (2,1),      (2,3), (3,2),      (3,4), (4,3),      (4,1), (1,4)}

and we define the graph G1=(V1,E1). You notice by looking at E1 that G1 is undirected. We would draw the graph G1 like,

    1 ---- 2    |      |    |      |    4 ---- 3 .

Example 2: Suppose V2 is a set of polygons, and we define the set E2 by stating that for any polygons p1 and p2 in V2, the graph-theoretic edge e=(p1,p2) exists in E2 if and only if the polygons p1 and p2 share a geometric edge.

For instance, consider the polygons p1,p2,p3 drawn below:

  ___________ |\          /\ | \        /  \ |  \  p2  /    \ |   \    /  p3  \ | p1 \  /        \ |_____\/__________\

So, using the definitions of example 2,
V2 = {p1, p2, p3}
and

E2 = {(p1,p2), (p2,p1),      (p2,p3), (p3,p2)}.

If we were to draw the graph G2 in the usual way, with graph vertices as points and graph edges as line segments, it would look like,

  p1 ----- p2 ----- p3

which is the line graph on three vertices.

Clearly, what I described in Example 2 was actually a navmesh.

Make sense?

Gaar? :)


I will take some time, reading this again and again. I will probably be posting questions after that :D

Edit: OH! Thanks for taking the time. I'm not complaining!

Just have to make a quick comment about your figures, tre. They look very good! What program did you use to make them?

Alex

Quote: Original post by alexjc
Just have to make a quick comment about your figures, tre. They look very good! What program did you use to make them?

?? Looks like 10 minutes in Visio to me.

Quote: Original post by alexjc
Just have to make a quick comment about your figures, tre. They look very good! What program did you use to make them?

Alex

They're quick mockups. Just five minutes in Photoshop, but thanks :)