Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Development

Reply
 
Thread Tools Display Modes
Old November 7, 2011, 16:53   #1
PowerWyrm
Prophet
 
PowerWyrm's Avatar
 
Join Date: Apr 2008
Posts: 2,652
PowerWyrm is on a distinguished road
Optimizing mon_create_drop()

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?
__________________
PWMAngband variant maintainer - check http://powerwyrm.monsite-orange.fr (or http://www.mangband.org/forum/viewforum.php?f=9) to learn more about this new variant!
PowerWyrm is offline   Reply With Quote
Old November 7, 2011, 17:14   #2
Magnate
Angband Devteam member
 
Join Date: May 2007
Location: London, UK
Posts: 5,057
Magnate is on a distinguished road
Send a message via MSN to Magnate Send a message via Yahoo to 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).
__________________
"3.4 is much better than 3.1, 3.2 or 3.3. It still is easier than 3.0.9, but it is more convenient to play without being ridiculously easy, so it is my new favorite of the versions." - Timo Pietila
Magnate is offline   Reply With Quote
Old November 7, 2011, 19:09   #3
fizzix
Prophet
 
Join Date: Aug 2009
Location: Madison, Wisconsin, US
Posts: 3,002
fizzix is on a distinguished road
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.
fizzix is offline   Reply With Quote
Old November 7, 2011, 19:48   #4
Zyphyr
Adept
 
Join Date: Jan 2008
Posts: 135
Zyphyr is on a distinguished road
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.
Zyphyr is offline   Reply With Quote
Old November 7, 2011, 21:36   #5
Rydel
Apprentice
 
Join Date: Jul 2008
Posts: 88
Rydel is on a distinguished road
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
Rydel is offline   Reply With Quote
Old November 8, 2011, 08:27   #6
PowerWyrm
Prophet
 
PowerWyrm's Avatar
 
Join Date: Apr 2008
Posts: 2,652
PowerWyrm is on a distinguished road
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.
__________________
PWMAngband variant maintainer - check http://powerwyrm.monsite-orange.fr (or http://www.mangband.org/forum/viewforum.php?f=9) to learn more about this new variant!

Last edited by PowerWyrm; November 8, 2011 at 12:44.
PowerWyrm is offline   Reply With Quote
Old November 8, 2011, 13:17   #7
d_m
Angband Devteam member
 
d_m's Avatar
 
Join Date: Aug 2008
Location: Philadelphia, PA, USA
Age: 39
Posts: 1,516
d_m is on a distinguished road
Quote:
Originally Posted by PowerWyrm View Post
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.
__________________
linux->xterm->screen->pmacs
d_m is offline   Reply With Quote
Old November 9, 2011, 12:14   #8
PowerWyrm
Prophet
 
PowerWyrm's Avatar
 
Join Date: Apr 2008
Posts: 2,652
PowerWyrm is on a distinguished road
Quote:
Originally Posted by d_m View Post
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)
__________________
PWMAngband variant maintainer - check http://powerwyrm.monsite-orange.fr (or http://www.mangband.org/forum/viewforum.php?f=9) to learn more about this new variant!
PowerWyrm is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Gripes -- equipment optimizing program juggle5 Vanilla 37 November 24, 2012 23:11


All times are GMT +1. The time now is 15:49.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.