ターン制シミュなら経路探索のコストはそこまで気にする程でも無いと思う。
ヘクスのマップ(配列じゃなくてハッシュ)、地形によるロスあり、移動力10って条件で
探索を1000回繰りかえしたけど一秒もかからない(つまりミリ秒以下)
ファミコン時代とかなら突き詰める価値はあったと思うけどね。