Hi, can anyone teach me how to do pathfinding in a 3D terrain made up of triangles of various sizes? How would the cost of moving onto each polygon be calculated since their sizes are not the same. I have seen A* being applied to uniform rectangular grids but in the the triangle mesh case but have no idea how to apply it in this case. Thanks a lot...

The standard way is to just overlay a 2D grid over the terrain and use A*. It''s not difficult, and gives very good results.

Another method it to take the vertices of the terrain and use those as possible A* destinations.

Yet another would be to figure out all the obstacles on the terrain, and partition the terrain into sectors which don''t have any obstructions in them. Then just A* between the sectors.

War Worlds - A 3D Real-Time Strategy game in development.

Thanks a lot for helping out, can u specify how to actually overlay a uniform grid over a mesh with triangles of varying sizes? Do i just make any grid and calcuate the cost of moving onto it by considering the average terrain cost of all the triangles that partially lie in the grid?

For your world, is the cost of moving through any given polygon uniform? Or do polygons representing terrain sections have different slopes? One would envisage that it takes more fuel (be it petroleum or glycogen) to travel up a hill than it does to travel down one, or on level ground. It also takes more fuel to cross rough terrain than it does smooth terrain. Are these factors important in your model or are you simply interested in shortest distance paths?

Timkin

Edited by - Timkin on July 22, 2001 9:46:49 PM

The world the units would be travelling through would have different slopes plus other varying terrain cost built into them. Thus, i trying to find the most efficient path through the terrain. I have already modelled the tanks to slow down when travelling upslope but i need them to avoid obstacles and move intelligently. I thought of doing the 2d grid method and project the sloping polygons onto the grid but in the end, there will still be a number of projected polygons lying together in one square grid. Guess i could caculate which polygons lie in which grid and take the average cost of them but seems too complicated(slow). Any suggestions?

You don''t need to use a regular grid (i.e. made up of squares)

Why not use the vertices of the triangles as points in the grid, and each edge off the vertex is a possible path to the next vertex. It''s not really all that more complicated, it just means you need to figure out a good way of storing your vertex and edge data.

War Worlds - A 3D Real-Time Strategy game in development.

Dean Harding is right. Generally, you use A* with a grid of squares. But there''s no reason not to search all triangles that share edges/verteces with the given triangle instead of all grid squares that share an edge with the current grid square. This might result in trees in which each node has a very different number of branches, so you might not be able to use a simple binary tree; you''d have to construct a more flexible tree of some sort of node struct.

Thanks everyone, been a great help, think will now go and try to connect nodes to the center of each triangle and run A* through the graph.

Just one quick issue to raise. If you perform pathfinding along the edges of your terrain polygons, then you can to consider how to apply your movement costs to your path segments. Additionally, do you want your agents walking ''around'' the terrain, or through it?

Timkin

Actually, my units are supposed to be able to move through the polygons interior and not along the edges. I have already coded motion from a start point to a destination point for a given start heading and end heading but still thinking of how to apply it to A*