Pre game loading time vs. in game loading time

Question

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.

Answer 1

BerickCook has expressed the idea correctly. Leave the calculations where they are if they work properly now.

If you can do the calculation before and you are sure you will not need them mid-game, then do it before. Else do it after loading. If the calculation during the game is unnoticeable you could do it there. If at some point the complexity evolves and the calculations become too heavy start optimizing.

But one thing: if your calculations are implemented to run mid game you can always force them to be performed during loading anyway.

There are numerous solutions:

• calculate/load the paths during level creation/loading
• use a second thread to calculate the paths
• optimize your algorithms
• use an interruptible system if you have no access to threading.

I have seen and used the last option in a mass market game. Simply make sure you properly save all the data needed for the calculation to resume, and check regularly for remaining time/operations during the calculation.

Depending on your case, the interruptible system could give preliminary and partial solutions that can be used event before the calculation has ended.

---

Edit: answering @Keeper

The "interruptible algorithm" was useful only because of the constraints we had. Basically we palliated to the lack of multithreading.

At one point we had a game where the AI had to compute large amounts of moves based on multiple dictionaries. During this calculation all animations would stop because the dictionaries were expanded with more data and the dataset holding the data was changed and less efficient when the game was adapted for multiplayer (where the AI had to interact even for the player's moves). We had only one thread available for the game loop (the imperative being the multi-platform code must run on all supported platforms). At this point it was decided to break the calculation algorithm so we could interrupt it. Therefore we couldn't just use the recursive system that was in place as variables could not be saved. The functions were replaced with objects which simply held all the necessary variables and pointers to parent and child objects. I don't remember the full implementation but each object had a way to:

• save the status of its current computations
• interrupt either at the end of a loop or during a loop (when a child object interrupts)
• exit when time's out
• resume where it stopped either restarting a loop at the right index or calling the child object currently being at the top of its children stack.
• clean everything if the computation is interrupted
• give the best partial result.

Only the most expensive operations were broken into separate objects and it took some time to find the right places where we could stop the calculations, but in the end it works very well.

We lost performance, but perceived performance was much better for the user as animations ran smoothly on all platforms, all platforms could then use the larger dictionaries without suffering from choppy animations or freezes. Also this allowed us to run multiple instances in parallel when we needed it later.

Of course now on the iPhone and iPad the game doesn't need this, using a second thread would be ideal. But I suspect the code is still there.

Answer 2

For now, since calculating the paths mid-game is unnoticeable, that is the ideal approach. If / when it gets to the point where gameplay is interrupted by the calculations, then switch it over to per-calculating the paths before the level is loaded.

Longer initial loading times are forgivable, but random FPS fluctuations during play generally aren't.

Answer 3

One possibility if you need it is to move the calculations to a second thread as almost every PC has more than one CPU core these days.

The basic process would be:

• When a creature requests a path add the request to a thread safe request queue and signal the thread.
• Creature stands idle while waiting for the thread to pop the entry off that queue, process it, and put it on a completed list.
• Each frame check the completed list from the main thread and assign completed paths to creatures.

You have to watch out for a few extra edge cases too (e.g. what if the creature dies before the request is processed).