Pathfinding without a grid.

Seems to me you could use the same polygons that define your boundary to be the vertices for a triangulated nav mesh. Much less memory that rasterizing and potential fields, and without the user input of waypoints.

I would probably set up my map structure where it begins as a walkable plane, and every obstacle you add essentially cuts a new polyon in that plane and triangulates the walk faces each time, keeping a nav mesh in tact as you go.

You could take a look at this, which discusses smooth worlds (at the bottom of the article).

You will find a lot, and I mean a LOT in the game AI litterature about creating navi mesh from your geometry. I remember some good articles in the AI game programming wisdom book...

Since your world is 2d, it should be even easier.
Something like
1) Triangulate your "walkable" area.
2) Merge triangles to convex polygons
3) Run pathfinding in the graph of your convex polygons common edges.

1) 2) easy to do at map compile time.

DrEvil, Steadtler,

I actually decided to try that same approach before I checked back here and got a workable demo up using a 2D navi mesh. It works pretty well (and supports convex polygons) but it seems like this approach would quickly become bloated with a large amount of vertices in the level.

Here's some screenshots if you're interested:

The geometry.


The navigation mesh generated from the geometry:

Quote:

Original post by Cactuar it seems like this approach would quickly become bloated with a large amount of vertices in the level.

Yes, it will. However, once you've tesselated your maps, you should process it again to reduce the number of triangles by merging them into convex polygons. Then using the vertices of the polygons or the midpoints of edges of adjacent polygons, you can perform a simple graph search for pathfinding.

The alternative is to not use a nav-mesh but rather implement free motion. You might like to consider potential field methods and their popular variant, steering behaviours. You'll find a lot of literature on these methods applied to robotics, where free motion planning is ubiquitous.

Cheers,

Timkin

Quote:

Original post by Timkin Quote: Original post by Cactuar it seems like this approach would quickly become bloated with a large amount of vertices in the level. Yes, it will. However, once you've tesselated your maps, you should process it again to reduce the number of triangles by merging them into convex polygons. Then using the vertices of the polygons or the midpoints of edges of adjacent polygons, you can perform a simple graph search for pathfinding.

That would give you only three nodes for your pathfinding, in your examples. I use delaunay on a daily basis in systems up to maybe 30 000 nodes, and why its considered slow by our standards, its still a question of milliseconds, not seconds.

Quote:

Original post by Timkin The alternative is to not use a nav-mesh but rather implement free motion. You might like to consider potential field methods and their popular variant, steering behaviours. You'll find a lot of literature on these methods applied to robotics, where free motion planning is ubiquitous.

By curiosity, would that still be called pathfinding ?

Quote:

Original post by Timkin Yes, it will. However, once you've tesselated your maps, you should process it again to reduce the number of triangles by merging them into convex polygons. Then using the vertices of the polygons or the midpoints of edges of adjacent polygons, you can perform a simple graph search for pathfinding.

I'm not sure I understand. After tesselating my map, as in the screenshot I provided above, I should then turn all of the plane divisions into polygons?

What sort of advantage does that give over the current implementation I have of "Hook every polygon vertice to every other polygon vertice, so long as it doesn't cross a polygon edge and doesn't lie entirely inside of a polygon" ?

Here's a screenshot:


The path seems reasonable enough to me. Do the changes you suggest speed up the graph processing or something?

Quote:

Original post by Steadtler That would give you only three nodes for your pathfinding, in your examples.

No, it would give you one node per adjoining edge. If your convex polygons were triangles, then yes, that's three nodes.

Quote:

I use delaunay on a daily basis in systems up to maybe 30 000 nodes, and why its considered slow by our standards, its still a question of milliseconds, not seconds.

If you can ensure that your graph size is restricted to what you can handle with your computation resources, then obviously you can apply any method you like, because your bounded by your graph and resources, not the method ;)

Quote:

By curiosity, would that still be called pathfinding ?

Through most of the robotics literature its still called pathfinding, because they don't tend to consider deliberative pathfinding, as AI people do. From the AI perspective, the distinction is made between reactive planning/pathfinding and deliberative planning/pathfinding. From the Control Theory perspective, everything is reactive (all deliberation was done at the time of controller design), although they still like to think that they're 'finding a path'. Think of it more as a method of (very) limited horizon graph search. You get to look at only your next step and make a decision. ;)

Quote:

Original Post by CactuarI'm not sure I understand. After tesselating my map, as in the screenshot I provided above, I should then turn all of the plane divisions into polygons?

They're already polygons. You could simplify them to reduce the complexity of your graph. However, if your levels are as simple as the sample image, then you don't need to do this... which was the point Steadtler was making by indicating he does a graph search on a Delaunay triangulation in fast enough time to make it workable.

Btw Steadtler, do you do your search on a heirarchical mesh from your triangulation, or just use the base tesselation?

Cactuar, By your pic it looks like you have overlapping triangles, is that correct? If so that's a problem, and is giving the appearance of more triangles in the nav mesh than should be. It should have like 6 triangles, rather than 9ish due to overlapping. Additionally you may want to put some implied additional vertices that surround the map so you get the exterior walk faces. In the image example, they might be at the 4 corners of the image, or if the map has huge expanses of walk faces it might be useful to tesselate the edges of the bounds a bit.

Also, if you set it up right it's not bloated with additional vertices. For example I would have each walk face be defined as an index to a master list of vertices that contains all the vertices of the obstacles, plus the 4 or so that make up the world bounds, and perhaps have obstacles be defined as lists of indices as well.

As Timkin mentioned, after you generate the mesh from triangles, you might look into merging triangles into convext polygons, using something like the Hertel-Mehlhorn Algorithm

The nicest thing about a navigation mesh is that it's a 'complete' representation of the walk faces. It gives you an idea about how much room you have in the area you are standing. This can have benefits in avoidance calculations, and automatically account for holes in the floor and stuff, though that part probably isn't much use to you. The nature of a nav mesh gives you knowledge of edges and walls and stuff.

Check out this neat little application: http://www.ai-blog.net/archives/000091.html
Click on the picture.

It demonstrates many different pathfinding techniques such as 4 way grid, 8 way grid, quad tree, hex grid, corner graph, waypoint graph, navmesh(triangle), navmesh(convex poly). Though unlike the app shows, I would prefer to generate the path through the edges rather than through the triangle centers.

Quote:

Original post by Timkin Quote: Original post by Steadtler That would give you only three nodes for your pathfinding, in your examples. No, it would give you one node per adjoining edge. If your convex polygons were triangles, then yes, that's three nodes.

My bad, I was thinking 3 convex polygons. Hum, for the purpose of finding an optimal path, shouldnt you keep the whole edge, instead of using the mid-point of adjacent edges? Then you can apply a hierarchical pathfinding, first on the edges, next on a discreet set of points of the chosen edges... Or is it better to smooth your movement when you arrive near a node, using the lenght of the edge as the strenght of the smoothing? I dont know if Im clear here... Im just thinking, except for mostly linear paths, you will rarely want to pass trough the midpoints of the edges...

Quote:

Original post by Timkin If you can ensure that your graph size is restricted to what you can handle with your computation resources, then obviously you can apply any method you like, because your bounded by your graph and resources, not the method ;)

Oh alright :P I just wanted to show triangulation is not that bad of a process.

Quote:

Original post by Timkin Through most of the robotics literature its still called pathfinding, because they don't tend to consider deliberative pathfinding, as AI people do. From the AI perspective, the distinction is made between reactive planning/pathfinding and deliberative planning/pathfinding. From the Control Theory perspective, everything is reactive (all deliberation was done at the time of controller design), although they still like to think that they're 'finding a path'.

You know, I always disliked how, in AI litterature, they tend to talk about reactive systems in the planner chapter. I guess I associate 'planning' with deliberation. To me, its not as much planning as strolling around and hoping you'll get there :P. Which is good, if obstacles are few... But thanks for giving me the distinction :)

Quote:

Original post by Timkin Think of it more as a method of (very) limited horizon graph search. You get to look at only your next step and make a decision. ;)

Thats wierd, thats what my boss do, and *they* call that planning too! ;)

Quote:

Original post by Timkin Btw Steadtler, do you do your search on a heirarchical mesh from your triangulation, or just use the base tesselation?

Sorry for the misunderstanding, we dont use the triangulation for search purpose. Cant say more than this :P

Thanks for your insights as always.

Quote:

Original post by DrEvil Check out this neat little application: http://www.ai-blog.net/archives/000091.html Click on the picture. It demonstrates many different pathfinding techniques such as 4 way grid, 8 way grid, quad tree, hex grid, corner graph, waypoint graph, navmesh(triangle), navmesh(convex poly). Though unlike the app shows, I would prefer to generate the path through the edges rather than through the triangle centers.

Thanks! The convex polygonal navigation mesh in that demo is exactly what I'm looking for. I have an algorithm in mind, but I'd be glad if you could provide a link to any neat algorithm you know of for this.

I don't have a ton of links on the subject, but here you go:

http://www.cs.ubc.ca/spider/snoeyink/demos/convdecomp/MCDDemo.html
http://www.bringyou.to/compgeom/

Quote:

Original post by Steadtler Hum, for the purpose of finding an optimal path, shouldnt you keep the whole edge, instead of using the mid-point of adjacent edges? Then you can apply a hierarchical pathfinding, first on the edges, next on a discreet set of points of the chosen edges...

That's basically the methodology akin to the 'framed quad-tree' approach. Most certainly the more information you keep, the more 'optimal' path you can achieve; whether that is optimal as in shortest, or smoothest, or some other metric.

Quote:

Or is it better to smooth your movement when you arrive near a node, using the lenght of the edge as the strenght of the smoothing?

This is a very common approach used in robotics. There are two basic choices: 1) pass close to the waypoint while cutting the corner; or, 2) pass through the waypoint by swinging wide (either before or after the waypoint). This gives some degree of smoothness of velocity changes while maintaining essentially linear path segments, which make the task of designing tracking controllers to follow them far easier.

Quote:

I dont know if Im clear here... Im just thinking, except for mostly linear paths, you will rarely want to pass trough the midpoints of the edges...

Absolutely. In games particularly though, as you would know, pathfinding is more about finding a useable solution quickly and then refining it to make it look nice. The alternative is to spend more effort finding a better path in the first place. Since the former may use the same computational resources but is easier to understand, implement and debug, most programmers favour that approach. That's not to say it's better. ;)

Quote:

You know, I always disliked how, in AI litterature, they tend to talk about reactive systems in the planner chapter. I guess I associate 'planning' with deliberation. To me, its not as much planning as strolling around and hoping you'll get there :P. Which is good, if obstacles are few... But thanks for giving me the distinction :)

I tend to agree. I prefer the view that reactive systems are described by an agent function of some form that maps states to actions. The view that this is planning though (and not purely reaction) is that traditionally, such agent functions were learned offline; for example, the determination of an optimal policy. During run time, this is just a reactionary system - detect which state you are in and apply the action appropriate to that state - but the creation of that policy is a planning problem (one usually solved with dynamic programming). The other perspective is that you can view planning as finding the solution to a problem defined on an horizon. Full deliberative planning would have the horizon at the goal (and is often intractable in the real world). Many robotics applications rely on finite horizon planning (the horizon is somewhere between the agent and goal). Reactive planning is just an horizon of length equivalent to one action. Indeed, in many adaptive planning methodologies these days, they tend to solve the problem on a limited horizon, commit to executing just one step and then resolve the problem after that step (or during it). This is both deliberative and reactionary. It's also computationally expensive and not very 'intelligent', which is why I've published an information theoretic method for deciding when it was appropriate to replan that is far more efficient. ;) (Got to sneak in those gratuitous self plugs!)

Quote:

Sorry for the misunderstanding, we dont use the triangulation for search purpose. Cant say more than this :P

Nps. Gotta love NDAs... not! ;)

Cheers,

Timkin