Вообще
А* не обязательно работает с сеткой, он работает с любым графом.
Есть еще один классный способ, я читал о нем в презентации Valve. Суть примерно такая:
То есть тот же самый
A*, но не по клеточкам, а по "навигационной сетке". Те участки карты, где ничего нет (или нет непроходимых препятствий) мы пересекаем по прямой, в те же где что-то нам мешает мы просто не заходим (препятствие занимает всю клетку, отведенную ему). Довольно просто на самом деле. Главное научиться разбивать свою карту при добавлении на нее объектов.
PS
Если нужен тот самый pdf с презентацией, погуглите по запросу "the ai systems of left 4 dead"