Posted: Thu Feb 15, 2007 7:14 am Post subject: path algorithm or lib for RTS -------------------------------------------------------------------------------- I'm wondering whether anyone can offer advice on the following problem for my RTS: Calculate a path from A to B on a terrain with the following conditions: - The path is represented by straight lines. The less turns the better, so I'm not after curved paths. - The path avoids collisions with objects. These maybe walls, circular objects (people or trees) or square objects (buildings) I'm weighing up whether I do this in 2D or 3D. There are no overhangs so 2D is possible. A* will give a jaggered result if using a mesh for the terrain. ie if A and B is in a straight line, A* may bounce around the mesh faces (is there any way around this?) Also I don't think A* algorithms will work when some objects move. Building a node graph would be complex. I looked at opensteer. The demo seems to be a calculate as you go algorithm. ie the chasing objects calc their path per frame. In my case I need an algorithm that plots the path before moving. I looked at ODE. That surely looks like overkill. Any ideas? Thanks!

To get the maximum straight lines, you simply need to smooth the resulting path. For each sequence of of 3 point A-B-C in your path, you draw a straight line between A and C. If there is no obstacles on the line, you can remove B from the path. Do this until you cannot remove any more path points.

A* can work if the objects move, but you consistently need to update the "world" representation A* will use, and re-compute any path that lies under the changes. Im no big fan of using navmeshes for RTS, somehow I think grids might work better. If you have a lot of units (and units collision), you might want to look into cooperative pathfinding.

In the book AI Programming Wisdom, there is an article by Dan Higgins on A* as they applied it to the game Empire Earth. While the focus is on performance, it might give you some good insight.

Good luck!

Path smoothing normally has issues when used in practice. That sort of corner cutting check only works decently in a relatively open environment. You will run into problems, particularly in the presence of holes if there are any in the game. I'd recommend penalizing non straight expansions during your A* processing. You should be able to easily get a good path from A* by penalizing any changes in directions in the cost calculations.

If you know the paths of the obstacles moving in time you can still use an A* search, although now you would be planning in a state X time space.

If you don't know how the world is changing you can use algorithms like Anthony Stentz's D*, which is A* with a few extra tricks to allow repairs to the graph when nodes are changed because of unforseen obstacles.

Thanks for the advice everyone.

Quote:
To get the maximum straight lines, you simply need to smooth the resulting path. For each sequence of of 3 point A-B-C in your path, you draw a straight line between A and C. If there is no obstacles on the line, you can remove B from the path. Do this until you cannot remove any more path points.

There is a slight problem with path smoothing. I would need to test collisions again with the mesh. ie if A-B-C and testing A -> C, i need to check whether the straight line from A -> C only crosses A, B, C. if the line crosses another facec D, then extra tests need to be made whether D is walkable terrain. Also 1 straight line from A -> C may give different results than another line from A -> C...AAAAARRH!!

Quote:
I'd recommend penalizing non straight expansions during your A* processing. You should be able to easily get a good path from A* by penalizing any changes in directions in the cost calculations.

That would be a good idea to get a straight line of faces. However this will still create a subtle jaggered line as the player moves from 1 face to another. I would need an algorithm that plots points in the faces that creates the best straight line. Again, I am confronted with the problem of lines going outside the faces of the face list.

Quote:
Im no big fan of using navmeshes for RTS, somehow I think grids might work better

Is a nav mesh what we are talking about here? (ie A* over a terrain mesh).

A grid could be a good idea for approximation. The smaller the squares the more accurate but more expensive...

I could use an alg that avoids a square if any part of a unit lands on a square.