Optimizing mon_create_drop()

[PowerWyrm]

Since the release of 3.3, monsters now carry their drops as soon as they are placed in the dungeon. This means that a *lot* of objects are created deep in the dungeon, especially when GVs and U pits are generated.

While this isn't really important in V, I face a big problem in my real-time multiplayer variant. Sometimes, the generation of deep levels take more than one second to complete. During that time, other players face a complete game freeze. This means that I need to optimize how monster inventories are filled...

Looking at mon_create_drop(), I can't see much to do to improve generation speed. Anyone got any idea?

[Magnate]

How about getting much much stricter about what monters can carry? We already have a partial implementation of drop profiles, in that you can specify certain things that the monster must drop, but see ticket #600 for the fuller design intent. My thinking is that if you give each monster a fairly small selection of things it can carry, the generation will be much quicker than picking from the full range of all objects.

You then have to rebalance item generation, of course - but it'd be worth it if you could significantly increase the speed. But come to think of it, building custom allocation tables for each drop profile would probably be slower than picking from the pre-existing table of all objects! Doh.

See also ticket #674, which is orthogonal - binary search would make picking from allocation tables faster.

Other possibilities include:

- fix the allocation table for artifacts at the start of the game - like for base objects. Re-roll if you get one that's already been created, and don't allow specified drops to become artifacts.

- fix the allocation table for egos at the start of the game

(there are lots of changes to generation in v4 which actually make it slower, but they show how the allocation tables are created - all you'd need to do is decide to fix some parameters and do them up front)

- go back to creating monster drops on death. The main reasons for this change were to facilitate stats collection (which you don't need) and to facilitate thievery (which we haven't implemented yet).

[fizzix]

This is an interesting concern. Specifically it conflicts with a mantra of dungeon level creation, in that it is allowed to be slow. Obviously this works, and is good design for single player, but doesn't work at all for multi-player.

Some suggestions for multi-player.

Defer monster drop creation until death.

Defer monster drop creation until the first time the monster interacts with the player.

Pre-create levels, adding more as needed. (you can imagine a 15 s pause to create several more levels)

greatly reduce the frequency of pits deep in the dungeon.

[Zyphyr]

You could generate levels in the background when nothing else is happening (or make your variant multi-threaded and use a seperate thread).

If someone is running around level 82, generate an 81 and an 83. Whichever you don't use can be held onto for later use and then disposed of when nobody is near it.

[Rydel]

You'd also want to generate 84 in case they use a scroll of Deep Descent
So, on dlvl N, generate N-1, N+2, and N+2
In town, generate dlvl 1, 2, and recall depth

Correction: DD now drops 5 levels, so N-1, N+1, and N+5

[PowerWyrm]

As I see it, I could create monsters without their drops and slowly add those drops as players wander through the dungeon. This should fix the problem nicely.

[d_m]

Looking at mon_create_drop(), I can't see much to do to improve generation speed. Anyone got any idea?

Are you sure that this is the function making generation so slow?

I can imagine trying to speed up generate.c in other ways. But I haven't profiling mon_create_drop() itself.

I'm wary of endorsing threads or something like that but in this case it might be a good idea... I fear that rewriting these things to run asynchronously would be a huge pain.

[PowerWyrm]

Are you sure that this is the function making generation so slow?

I can imagine trying to speed up generate.c in other ways. But I haven't profiling mon_create_drop() itself.

I'm wary of endorsing threads or something like that but in this case it might be a good idea... I fear that rewriting these things to run asynchronously would be a huge pain.

Yes, it's mon_create_drop()... or more precisely the repetition of calling mon_create_drop() for all monsters during level generation. What I did to fix the problem in my variant is the following:
- only call mon_create_drop() in place_monster() if the dungeon is ready (cave->generated = TRUE)
- when generating a level (cave->generated = FALSE), only record the origin of monster drops in a new variable (m_ptr->origin)
- delay the creation of monster drops in process_monster()
- create monster drops when a monster dies if not already created (this could happen if a monster is killed before it can act once)