Greetings. I've got a problem and I'd like to know all possible solutions before I proceed with an implementation. My 2D game world uses polygons to define "non-walkable" regions. I need a way to pathfind in this world. So far, solutions I've considered are: 1) Potential fields (probably generated when the level is saved). 2) Rasterizing the polygons into a grid for A* (also when the level is saved). 3) A graph of waypoints placed by the mapper or generated from the paths created by the potential fields in (1). Is there anything else I should look at? What are some common pathfinding algorithms used in 3D games? Thanks in advance.

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.