You could break down the checks over multiple frames. Instead of doing 1000 checks before moving the character, you can do 100. Then move the character in the direction of the best guess. While moving the character to the new location, you do the next 100 checks and adjust the character if needed for the new information. If it takes the character 1 second to move a full square away and your game loop is running 30 fps, you will have the correct path calculated by the time the character is 1/3 of the way to it's first square, masking any corrections you had to make along the way. And of course, you now have an additional 20 frames left to calculate the next position, assuming that the destination is also moving, such as when a monster is chasing the player; otherwise no more checks are necessary.