Hi, I know a couple of pathfinding algorithms like A*. The algorithms I know require a cell grid, where you tell for each cell if its blocked or not. Pretty easy to use on a terrain for example. But now I have more complex scenes. They are not big most of the times, but they can have things like stairs and multiple stores. Luckily my enemies are pretty dumb, they don't have to find cover or something like that. The only thing they have to do is walk towards the player, or towards a door in that scene. But for example, 2 doors are above each other. The upper door can be accessed via a stair and a bridge somewhere. Now the enemy wants to access the upper door. If he's capable at least, because some enemies can't climb stairs at all. Now I think I can't just use a 2D grid. It should be at least a 3D grid. But how to calculate which cells are blocked, and how to use it? I could also make "railtracks" to all doors. In that case I don't need a grid. But the enemies could become predictable then, and how can they walk towards the player to "catch" him then? Greetings, Rick

I believe the most common technique is to use pre-existing (hand-placed or generated) paths for long-distance path-finding ("find" or "reach" the player), and, if necessary, use a dynamic A* for short-distance pathing("Catch" the player).

For example, say your AI want to "catch" the player. you could divide the walkable area of your map in convex polygons, place a pathing node inside each polygon, and a link between the node of adjacent polygons. On you are on a polygon adjacent to the player's, you can drop pathfinding and just run toward it.

Every AI books I've read have suggestions and idea on this, its a very popular subject, since this problem arise in a LOT of games.

"you could divide the walkable area of your map in convex polygons, place a pathing node inside each polygon, and a link between the node of adjacent polygons."

I never read any books about it, so sorry for stupid questions. But if I understand you right, I should place a node in (the center?) of each polygon that could be walked. Then I need to search for neighbour polygons. If they have a nood to, I can lay a "line" between them. Eventually, I could extra information per "line". Because not all enemies can use all lines. For example, a guy driving on wheels can't use the stairs.

Am I correct? Sounds like a nice solution, but only 1 thing... how to determine if a polygon is walkable or not? Maybe there is no other way in my case, but it would be nice if the nodes and lines are calculated automatically of course. Maybe I should look at the normals... To steep means not accessible, unless you are spider man.

By the way, I guess this a relative memory friendly solution. When using 2D/3D cell grids, you often have way too many cells. I use a simplified model for each scene, so the polycount probably lies somewhere between 50 and 200.

Thanks for the tips!
Rick

Quote: Original post by spek
I know a couple of pathfinding algorithms like A*. The algorithms I know require a cell grid, where you tell for each cell if its blocked or not.

You must not know your algorithms very well, then. A* is a general algorithm to find optimal paths in a graph, aided by a heuristic. As long as you can clearly describe what your graph is, you don't need any new algorithms.

One possible way of organizing your graph would be to partition the reachable parts of your scene into convex volumes (axis-aligned boxes might be enough for most cases). The volumes can be placed by hand or automatically. You should provide your algorithm with a way to determine which volumes are contiguous to a given volume. You can augment your graph with connections that require special actions, like using an elevator, jumping of crouching.

Another way of organizing your graph would be to place key locations by hand in your scene, also with connections between them. Two key locations should be connected if going from one to the other is a trivial problem. The definition of "trivial" will depend on how smart your agents are when it comes to moving to a nearby location.

HI Spek.

Here you have a couple of papers about the subject!
I'm sorry, but I couldn't see wich one is most intersting for your problem. But here you have :) :

http://del.icio.us/gorogoro/pathfinding

Quote: Original post by spek
"you could divide the walkable area of your map in convex polygons, place a pathing node inside each polygon, and a link between the node of adjacent polygons."

I never read any books about it, so sorry for stupid questions. But if I understand you right, I should place a node in (the center?) of each polygon that could be walked. Then I need to search for neighbour polygons. If they have a nood to, I can lay a "line" between them. Eventually, I could extra information per "line". Because not all enemies can use all lines. For example, a guy driving on wheels can't use the stairs.

Am I correct? Sounds like a nice solution, but only 1 thing... how to determine if a polygon is walkable or not? Maybe there is no other way in my case, but it would be nice if the nodes and lines are calculated automatically of course. Maybe I should look at the normals... To steep means not accessible, unless you are spider man.

By the way, I guess this a relative memory friendly solution. When using 2D/3D cell grids, you often have way too many cells. I use a simplified model for each scene, so the polycount probably lies somewhere between 50 and 200.

Thanks for the tips!
Rick

There is no stupid question, only inquisitive idiots. Fortunately, you are not of of them! You are very correct. Constructing the polygon/convex volume map is however a problem that depends heavily or the engine you use, and the map representation you have.

alvaro is right, even if a tad... direct. A* doesnt imply a grid. A* is a nheuristic case of the Dijkstra that find shortest paths in *any* positive weighted graph. Graph theory is very interesting and extremely useful in pathfinding. For example, several graph algorithm could be used to divide a surface in convex polygons (e.g. Delaunay triangulation?).

Thanks again, also Gorogoro for you links!

Yeah, A* does not depend on a 2D/3D grid indeed. But so far I was always using it that way. I think putting a node per polygon is a good solution, since it's still pretty easy to calculate automatically. And I add an option so that the user an edit links/paths mannually anyway (for special paths, or "jumps").

But now I came into another question. Via a pathfinding algorithm you can search the shortest way through the node links. I suppose these nodes have a position too, so I imagine they are in the centre of their polygons. Now I know which nodes/polygons to pick, but the problem still is not 100% solved!

If I walk from node to node (read polygon centre to polygon centre), this is not the shortest route. Maybe almost, but there are situations you walk a little bit too far. And maybe you walk a little weird in case the polygons are lied next to each other in a specific shape. As if you were drunken. Making splines/curves will help to prevent "robot-walk", but you are still drunken in some cases. Luckily my monsters are stupid (slow zombie-like things), but that should not be because of incomplete pathfinding of course.

I was thinking about a way that the monster tries to "put" a single straight line between his current point and end-point. If it's broken (it floats, or overlaps non-choosen polygons), he will try 1 node before the end-point. And so on, until he finds a node he can reach in a straight line (without coming outside the choosen polygons by the pathfinding). Basically, I mix raycast intersecting with another pathfinding algorithm that goes through the node-graph first.

I think it works pretty good, although raycasting could be a little bit slow. My mesh that is used for the pathfinding is simple luckily. But maybe there are smarter/faster ways to go from A to B, given a list of nodes/polygons that are free to use.

Greetings,
Rick

A good trick if you don't necessarily want to check navmesh polys or want to have slighly more unpredictable routes is to assign a radius to a route-graph node, the chords of which identify allowable path positions (which should be validated by navmesh). When deciding movement, you can assign a random destination point within the target radius, meaning that the precise line taken for each traversal of the graph can vary.

Quote: Original post by spek

I was thinking about a way that the monster tries to "put" a single straight line between his current point and end-point. If it's broken (it floats, or overlaps non-choosen polygons), he will try 1 node before the end-point. And so on, until he finds a node he can reach in a straight line (without coming outside the choosen polygons by the pathfinding). Basically, I mix raycast intersecting with another pathfinding algorithm that goes through the node-graph first.

I think it works pretty good, although raycasting could be a little bit slow. My mesh that is used for the pathfinding is simple luckily. But maybe there are smarter/faster ways to go from A to B, given a list of nodes/polygons that are free to use.

Greetings,
Rick

Yeas, that is the smothed algorithm for pathfinding using meshes (p.E.).
I also used the midle of the triangle to set the pathfindingnodes. But I'm not using raycasts for smothe.

I make a line beetween points and then i'm going to the neighors nodes to see if the line is there. This way you only check the neighbors of the node you are and when your line is in another polygon, I see the neighbors of that polygon.