単に斜めの優先順位を下げればいいだけだと思うが。

4方向(1つ前のマスを除く)に移動可能なマスがあるか?
YES  その方向に進む。
NO  斜め4方向に移動可能なマスがあるか? YES その方向に進む