Я кстати когда то заботился об этом очень сильно.
Если в вашем случае приходится обрабатывать Астар в каждом цикле(кадре) то лучше расчитывать не от старта к финишу, а наоборот. При этом не придется обрабатывать все соседние 'клетки' на цену пути, достаточно будет довести путь до финиша и предпоследняя 'клетка' станет указателем для движения. В большинстве случаев такой способ в разы сократит время на поиск.
Конечно можно закритиковать такой способ навязывая идеал в том что Астар должен расчитыватся полностью и один раз(к примеру если вам требуется расчитать короткий путь от Челябинска до Саранска), но в игре где обстановка меняется постоянно классический Астар проиграет.
Это примерные показатели затронутых клеток для расчета пути за один цикл. На самом деле их пути будут равны.