Efficient coding: Examples using the Angband dungeon generation code Notes: Before we start this essay, let us first note that the Angband dungeon generation code is not a major factor in slowing down the game, because it is called only when the player changes level. On the other hand, it does take a fair bit of time on slower machines, time that - with a little ingenuity - we can shorten. Use a code profiler, and one discovers that using the random number generator is time-consuming. "rand_div()" (the guts of the RNG) is the most expensive dungeon generation-related function for almost all variants. Set up some testing code to count calls to "rand_div()", test in the appropriate places, loop dungeon generation 5000 times, print the output to screen, and you get something similar to the following: Average calls per dungeon level, at level 50 [Angband - version 2.9.1] calls needed to make rooms: 1,943 calls needed to make tunnels and doors: 3,546 calls needed to make streamers: 3,141 calls needed to place stairs: 2,325 calls needed to make monsters: 2,269 traps, rubble, objects, player: 566 time needed on test computer to make 5000 levels: 43 sec. Explaination: Although the low-level dungeon generation code is relatively inefficient, the small number of cpu-intensive rooms keeps things fast. With one greater vault every 200 levels at level 50, and efficient object and monster selection code, Standard Angband is no slowpoke. [Oangband - version 0.5.1] calls needed to make rooms: 1,302 calls needed to make tunnels and doors: 665 calls needed to make streamers: 88 calls needed to place stairs: 36 calls needed to make monsters: 1,190 traps, rubble, objects, player: 535 time needed on test computer to make 5000 levels: 30 sec. Explaination: Oangband makes a lot more special rooms of almost all kinds, with one greater vault every 25 levels at level 50. It also uses somewhat more involved monster-selection methods. However, this variant does benefit from some relatively efficient low-level code. [Zangband - version 2.5.2 beta] calls needed to make caverns, special 1,336 calls needed to make rooms: 3,310 calls needed to make tunnels and doors: 4,220 calls needed to make streamers, rivers: 3,871 calls needed to place stairs: 25 calls needed to make monsters: 4,057 traps, rubble, objects, player: 602 time needed on test computer to make 5000 levels: 93 sec Explaination The figure for stair placement is low because the code actually starts off requiring three /floors/ next to the location being tested, not walls. Rooms and monsters are high because Zangband has a lot of special rooms and powerful monsters. Making a river is about as expensive as making five streamers; because rivers are considerably rarer, they don't add as much to the the average number of calls. Same story with the special caverns and lake levels - each one is mighty expensive, but they aren't too common. [Zangband - version 2.5.3 beta] calls needed to make caverns, special 2,569 calls needed to make rooms: 7,363 calls needed to make tunnels and doors: 3,673 calls needed to make streamers, rivers: 3,531 calls needed to place stairs: 60 calls needed to make monsters: 3,651 traps, rubble, objects, player: 8,021 time needed on test computer to make 5000 levels: 121 sec Explaination: The new object generation code includes a function called "kind_is_theme()", which accounts for almost half the calls to "rand_div()" during the creation of a dungeon, on average. This function, its large number of "rand_div()" calls, and the function "monster_dungeon()" accounts for the increase in time taken. ---------------- Testing Methods ---------------- - All variants were compiled "out of the box", with no changes, using the makefile "makefile.dos", as supplied. Zangband was tested with zero random quests. The testing code with the counters for "rand_div()" was not timed. - Dungeon generation was looped for 5000 times, using a test in "generate_cave()", right at this line of code: /* Accept */ if (okay) break; ---> if ((okay) && (num > 4998)) break; This means that two kinds of dungeon generation will not be captured: That which is not called at 2500 feet, and that which requires that the player do something special on the previous level (Oangband themed levels, for example, require a wait of at least 1000 game turns). ---------------- Optimizing for efficiency ---------------- The easiest of all slowdowns to fix is the placement of stairs. Stairs want to be near three walls; hunting for such a grid randomly is almost an exercise in futility; lower the request to two walls, and you save at least 9 calls in 10. An even more effective method is to store likely-looking tunnel grids. Next comes streamer generation; paying over 3000 calls / level for an "extra" is bloat. We can get quite good results by using a table of 47 randomized 1s and 0s, rotating it by streamer diameter grids each move, and making streamers only affect the axis perpendiular to their axis of movement (if they are moving diagonally, they affect a cross-shaped area each move). Even with extra code stuck in to make the streamers turn, we can easily save 99% of the calls. Monsters can be dealt with too. No monster really needs more than about 12 HP dice, because 12dX has a fairly small random factor. If we want even less variability, just tack on the FORCE_MAXHP flag. Doing this might (at an educated guess) save approximately 2 calls in 5. Finally, the tunnelling code. This is the biggest target - 3,500 calls is a lot - and the least easy to rejigger and get good results. As I have found out to my cost, this is a tricky, subtle piece of code. We can start off by transforming most of the "rand_int()" checks into checks against timers. For example, when the tunnel turns randomly, a timer is set to a random number. It is counted down by one every move. When it reaches zero, the tunnel turns randomly again, and the timer is reset. A handy side-effect of this is that tunnels are guaranteed to never move more than a certain number of grids in a straight line, which cuts down a little on the off-screen instadeaths.