Ticket #156: notes.txt

This folder contains a patch of the majority of the Oangband dungeon generation
code, suitable for installation over a clean copy of Angband 2.9.3.  There will some
issues when installing on anything higher.

Installation is very easy:
 - replace "generate.c" with the enclosed copy, recompile.
 - open up "/lib/edit/vault.txt", and do the following _in order_:
   - change all occurances of "X:7" to "X:6".
   - change all occurances of "X:8" to "X:7".

What parts of the Oangband dungeon generation code got included:

I. Room placement

Rooms are now built in descending order of difficulty.  Because the code builds
greater vaults first, they usually appear when requested.  For each type of room,
the code finds out how many it is allowed to build; you may specify this number by
editing a table.  You want three greater vaults on average per level at level 30?
Barring a few caveats, like limited monsters, objects, and space, you'll actually
/get/ three greater vaults on average per level at level 30.  For each room of that
type allowed, the code dynamically allocates 11x11 dungeon blocks.  All rooms are
now aligned in 11x33 rectangles, because there is no longer a need to ever have
rooms out of alignment.  Small rooms are placed very flexibly, using up as little
as one dungeon block.  This makes for more natural-looking dungeons.  Large rooms
are aligned towards the edges of the dungeon - again, this improves their appearance
on the standard screen.  A handy side-effect of all this is that any room can be any
size; Chris Weisiger can make his vaults as big as he wants.

There have been various changes to room allocation chances; they are /not/ intended
as a final draft.  If you choose to adopt this code, I will supply a reference table
that duplicates the current Angband room generation probabilities (the actual
probabilities, not the theoretical - the two differ greatly!).

II. More powerful monster-selection code

Monster nests have been combined with monster pits*.  A room of this type may have an almost
infinite variety of monsters in it, from the familiar orc pits and jelly nests, to the unfamiliar
sonic dragon pits, to the totally unheard-of Ogre pits, schools of sorcery, and fire elementals'
playgrounds.  Creating new types of pits involves choosing selection criteria, which may take the
form of restrictions on symbol, monster race, breaths, or color.  For example, one creates a pit
of fire elementals by requiring 'v's and 'E's, than requiring the colors TERM_RED and TERM_L_RED.
The monsters in a pit may be ordered or randomly placed; some monster-selection categories choose
one kind, some the other.

This code is not only used for pits.  Special varieties of ordinary rooms include
checkerboard rooms with undead and rooms with collapsed ceilings harboring creatures
of earth.  The only limits here are those of imagination.

As with the room generation probabilities, the choices for monster selection in pits
are just for show.  You can easily duplicate the traditional Angband pits, have the
pleasure of designing your own, or encourage people to get creative.

The combination of pits and nests means that there are seven kinds of rooms now, not
eight.  This means that lesser vaults are type 6 and greater vaults are type 7.


III. New tunneling code

The tunnelling code has been greatly revised, and many of the annoying little problems
that it has suffered from are now gone.  It now heads for vault entrances (see file
"vault_entrance.gif", is less liable to turn the dungeon into Swiss Cheese, is
guaranteed not to go in a straight line for longer than line of sight, does not
place doors two grids beyond where it should as it leaves the initial room, has new
checks to confirm that it's actually connected all the rooms, can cope with
non-rectangular "natural-looking" and circular rooms (this is the most important
advance from the standpoint of variants such as Zangband), and is better able to
handle varied terrain.

Note, however, that I still consider this code to be in beta; it has known areas of weakness.


IV.  Other changes
- The streamer code is much, much more efficient.  Streamers now vary in width and can twist and
  turn as they travel through the level.
- The structure "dun_data" is considerably smaller.
- Characters now usually start off in hallway alcoves, which really cuts down on the insta-deaths.
  The searching routine for stair placement is a great deal faster.
- Ragged edges and pillars are never generated in rooms with dimensions divisible by two, for
  neatness' sake.
- Various efforts have been made to speed things up, increase robustness, and reduce the number
  of internal failures; two examples are the depth-variant criteria used by auto-scum, and new
  checks against the limits on monsters and objects.


----------------------------------------------------

what didn't get included:

- My name in the copyright listing at the top of the file.  If you choose to adopt all or part
  of the code, and decide those portions adopted change the nature of dungeon generation
  sufficiently to warrant that kind of recognition, fine.  If you don't, also fine.

  The other stuff that didn't get included is more O-specific (e.g. themed levels),
  or requires code in other files to function properly (specified types of monster
  or objects in vaults).

- chambered or starburst rooms
- huge rooms
- "interesting" rooms (minor vaults)
- themed or "Moria" levels
- varieties of ordinary rooms requiring special terrain
- code related to bigscreen 
- the ability to place objects of a specific type (like amulets)
- The ability to generate monsters quickly
- The ability to place monsters of a specific race or of a defined category (like "magic-user")
  in vaults
- code to prevent monsters from being randomly generated in areas where monsters of
  specific types were placed