I am working on a 3d game on a terrain made of a regular grid of vertices and faces. Some faces should not be walkable because too steep, difficult terrain, underwater etc.

My only experience with pathfinding ai so far is within a voxel world where I used a kind of floodfill(??) approach: try every possible way until finding the destination by chance and remember how to get there as fast as possible. But my map now is pretty large and destinations may be very far, so I guess this would be too slow for a large number of AIs.

Any suggestions?

A* star works very well with or without uniform grids, and there is a huge amount of tutorials available online for it.

It's pronounced, and sometimes written, A-star, which can also be googled for.

Pathfinding in general is slow, so you'll still want to save the path and only recalculate it when necessary. It's faster than flood-filling though - and kinda similar. It flood-fills but intelligently, hypothesizing what directions are best, saving work.

Thanks for replies. I will look into this A*. Maybe it's not so different from what I already did in my other game. It will probably just come down to finding the right resolution of waypoints to get decent performance, so I might have to skip some terrain nodes between waypoints.

I am such a fan of A* that I wrote a library for it. If you are using C++ it might be a quick way to get pathfinding working for you: https://github.com/leethomason/MicroPather

Here is another excellent starter for A* algorithm with an implementation in Cocos2D

http://www.raywenderlich.com/4946/introduction-to-a-pathfinding

The "flood fill" algorithm is essentially Dijkstra's. A* is an optimisation of it.

You can use these even if you don't have a regular grid on your ground, just *pretend* that you do have such a regular grid, and run the algorithm anyway. You only need to write a function "can I pass this point", which needs to be conservative enough that your moving units can actually pass that point to its adjacent points without encountering any new obstacles - so the "can I pass this point" function might need to take into account the distance of nearby objects, and return false even if the point itself appears passable.

Anyway, give it a go, and you'll easily get something that works.