Поиск пути для игр

Какие алгоритмы поиска пути используются в играх всех типов? (Во всяком случае, из всех типов, в которых перемещаются персонажи. )Использовался ли когда-нибудь тип Дейкстры? Я не собираюсь ничего кодировать; просто занимаюсь исследованием, хотя если вы вставите псевдокод или что-то в этом роде, это будет нормально (Я понимаю Java и C++ ).

Я знаю, что A *похож на алгоритм, используемый в 2D-играх. Это здорово и все такое, но как насчет 2D-игр, которые не основаны на сетке -? Такие вещи, как Age of Empires или Link's Awakening. Нет четких квадратных пространств для навигации, так что же они делают?

Что делают 3D-игры? Я читал эту штукуhttp://www.ai-blog.net/archives/000152.html, которая, как я слышал, является большим авторитетом в этом вопросе, но на самом деле она не объясняет, КАК после установки мешей выполняется поиск пути. ЕСЛИ *— это то, что они используют, то как что-то подобное делается в 3D-среде? И как именно работают сплайны для скругления углов?