毎回微妙に違う経路にするのは、例えば左右どっちを経由しても最終的には同じになるような分岐だとして、
マップ内に見えないマーカーのようなものを埋め込んで置いてはどうだろう。
で、マーカーはランダムに右または左を指して、NPCはそのマーカーにしたがう、と。
もしくはランダムにバーチャルウォールのようなものを発生させるとか。
何にしても、正直にプレイヤーとNPCのマップを同一にしなくてもいいんじゃないかな？