I’m just trying to get into AI and pathfinding and there are a few things I’m wondering about:
I know that most of the old rts games like Age of Empires 1, Stronghold Crusader etc. used an underlying grid made of hexagons or other polygons. They used this for pathfinding and unit placement and I also know how to implement A* for such an grid.
But in more recent rts games as Age of Empires 3 or Company of Heroes etc. you at least visually can’t see that they use such an grid. The units seem to turn “freely”, and not only in the directions a grid binds them to. What general approaches do they take to make that happen?
I read about collision meshes, but as I understand it those also just divide the world into polygons, so you’re again bound to some grid. Did I understand that right?
Also for the panda3d ai library, to make patfinding work, you also have to subdivide your mesh in smaller faces with your modler programm. Is panda3d ai library therefore “grid based” or is it “navmesh based”?
Check out this powerpoint on pathfinding, it has helped me immeasurably. The “next corner” method near the end is what you are looking for. You can apply this to navmesh or any shape of tiles. http://www.navpower.com/gdc2006_miles_david_pathplanning.ppt
Hi teedee,
that’s a very interesting paper, although I would like to know some more details on parts of it.
Google doesn’t help too much on “next corner approach”.
Do you know any resources that talk about that approach in more detail?
I have one question on the next corner approach:
Is that technique only meant for steering behaviours like flocking, when you have computed a path already, or is it also meant for pathplanning?
The author also talks about naviagtion meshes with arbitrary convex polygon structures. How can A* star be modified to work on such navigation meshes?
I don’t know of any better explanation of the method, although if you step through the slides you can pretty much convert it from written word to code.
This technique is meant for any situation where you have used A* to decide what “tiles” the path will take and then reduce it to the least number of turns.
A* with navigation meshes you should be able to find a lot of info on. In a grid you know which tile you are starting on and which you are ending on, with a navmesh you must do a bit of work to locate these tiles. In a grid you know the neighbouring tiles are the surrounding ones, with a navmesh you must store neighbour information associated with each tile. In a grid the “distance cost” to move one tile is always one, with navmesh that cost is calculated from the area of the tile.
Hi teedee,
I’m wondering about how the cost calculation in a navmesh might work. I mean depending on where you enter a polygon the cost for moving to the next polygon might differ, right?
How is that handled normally?
You can approximate it by pre-calculating the distance from each edge to the center of the face. Then you can just add these two numbers together to get the distance, no calculation needed at runtime. I find that this gives quite good enough results.
Hi teedee,
thank you for your help.
I don’t want to annoy you, but I got one additional question about the paper: The author is talking about partitioning a polygon into convex areas. He’s introducing a metric that has to be minimized, when paritioning: straight line distance/perimeter distance.
My question is: What exactly is that perimter distance?
The sum of the perimeters of both polygons that you will get by partitioning? Or only the perimeter of one of them, but which one would I have to choose?
To be honest, not 100% sure. My interpretation would be that you start with one point (doesn’t matter which), and keep expanding it to include more points. At some point the distance between the end-points of this growing perimeter will reach a minimum, and then begin to grow farther apart again. You want to stop at the minimum before it starts getting farther apart since that would make the shape non-convex.
I’ve always worked with manually made navmeshes which can be fairly quick to make with a bit of practice, though if you come up with an automatic process as described in the document that could be a great solution as well.
Hmm, sounds like a good approach.
The only problem I see is that, when you select the first three points to build the first triangle, that will be extended further on, you would have to check, if you are selecting a polygon, that has an straight line between the endpoints, that is outside the original polygon.
To check this you would have to calculate an arc, which would include the calculation of two squareroots.
EDIT: Thinking about it more conseqeuntly, you actually never have a gurantee that you just did select a vertex at which there is an arc >180°. The rule of only reducing the straight line distance can’t gurantee for that. You would have to mark every vertex at which there is an arc >180° before you could begin the partitioning process. This will be a real performance killer, I guess.
Nevertheless, I’m gonna try it out.
EDIT2: I’m a little stuck at this, because I don’t know of an easy way to find those special vertices at which the polygon is concave.
Scalar prodcut can’t help, because asin does only map to [0,180] degrees.
Another method that should work is to test which side of the edge the next point lies on.
Start at point A, then form a line by continuing to point B.
The next point, call it C, will either be on the “left” or “right” of that line.
If it was on the left side, then the next point D should also be on the left side of the line formed by point B and C.
If it is on the other side then you would have your >180 scenario.
Here is a function I use to check what side of a line a point is on (I might have “a” and “b” mixed up there, but for this scenario it doesn’t matter):
def ray_side(b, a, c):
"""a = ray origin, b = ray target, c = test point
return negative for left, 0 for on, and positive for right
the coordinates are 3d but the math is 2d"""
return (b[0] - a[0]) * (c[2] - a[2]) - (b[2] - a[2]) * (c[0] - a[0])
Oh and you would have to change the 2’s to 1’s if you are using the default Z-up coordinate system.
Before putting too much more work into this I’d recommend checking out features the Panda AI has, as it might already do what you need. I haven’t taken a look myself, so I couldn’t say.
Thank you for the pointer.
The problem the Panda AI has is that navigation meshes have to be manually created.
But I want a system where the navigation mesh should also be allowed to incorporate dynamic changes to the environment. Therefore I will need some automatic navmesh generation system.
I’m not sure if this might be helpful to you or not, but i had started to work on pathfinding quite some time ago, and i digged out what i had for snizzo who also had questions about pathfinding. It’s in a very early stage, and doesn’t handle dynamic regeneration of the navigation mesh yet (work about that should get done soon i hope), but it’s a start and maybe there will be functions in there that you can use.
Any feedback about how to improve things is very welcome.
To test it, download the archive at :
After putting some work into this, I now got partitioning of convex polygons working.
If the convex polygon, where a “hole” polygon is inside, is known, then I can also repartition that into new polygons.
But the thing is that a “hole” in the navigation mesh that is caused by a new object that is placed in the world might intersect with multiple polygons of the navigation mesh. Therefore I would habe to cut that “hole” into new parts, to be allowed to run the normal partition algorithms. Figuring out that cut process is giving me a lot of trouble.
