I'm developing a game in which a random maze is included.
There are some AI creatures, lurking the maze. And I want them to go in some path according to the mazes shape.

Now there are two possibilities for me to implement that, the first way (which I used) is by calculating several wanted lurking paths once the maze is created.
The second, is by calculating a path once needed to be calculated, when a creature starts lurking it.

My main concern is loading times. If I calculate many paths at the creating of the maze, the pre loading time is a bit long, so I thought about calculating them when needed.
At the moment the game is not 'heavy' so calculating paths in mid game is not noticeable, but I'm afraid it will once it will get more complicated.

Any suggestions, comments, opinions, will be of help.

Edit:

As for now, let p be the number of pre-calculated paths, a creatures has the probability of 1/p to take a new path (which means a path calculation) instead of an existing one.
A creature does not start its patrol until the path is fully calculated of course, so no need to worry about him getting killed in the process.