Comment by dgb23

WC1 has fairly blocky movement and is grid based. It seems like units literally move from tile to tile so to speak.

If this is actually the case, you could try the Lee algorithm: https://en.wikipedia.org/wiki/Lee_algorithm. It's extremely simple and effective.

You might want to try adjusting it for diagonal movement and you probably don't want to store obsolete path sections, but only turns.