[Zebestov]

1. Измеряем предположительную длину шага персонажа
2. Рисуем несколько вертикальных полосочек с найденным в п.1 интервалом
3. Анимируем движение группы полосочек на два интервала влево на такое количество кадров, за которое мы хотим сделать два шага (левой, правой)
3. Ставим персонажа, скажем, левой пяткой на полосочку
4. Анимируем ходьбу персонажа со всеми там амортизациями и раскачиваниями туловища так, чтобы визуально ноги не "проскальзывали"

Если делать как-то так, то персонажа можно будет просто плавно двигать с заведомо известной скоростью (pixels per frame) а внутри просто проигрывать соответствующую анимацию ходьбы.