Use new random corridor algorithms sometimes

10% of rooms-and-corridors levels will randomly choose from one of
random corridor algorithms, 3 out of 4 of which are new, so 7.5% of
levels will use one of the new ones.

I'm making this change even though it's not in UnNetHack because it's
such a shame to have this new feature and never have players experience
it.

From SporkHack; which revision?  Who knows; SporkHack's Subversion repo
is down again, so I can't get an annotate on the line this change comes
from.
Improve circular corridor algorithm

Levels with rooms connected using the new circular connection algorithm
now actually look circularly connected.  It works by sorting the rooms
by their rotational position relative to the center of the map.  Without
this, levels using the circular corridor algorithm looked like a mess of
corridors, with a long 'artery' corridor through the middle.

This uses a nested function and atan2() for sorting, which are C99, but
other places use snprintf(), so it's fine.  This also requires
libnitrohack to link against libm, C's standard math library.
Improve star corridor algorithm

Levels with rooms connected using the new star connection algorithm now
use the most central room to connect to all the other ones, instead of
the left-most.  Without this, the level would look a bit like a dead
squid, often with wide horizontal corridors, which didn't look too nice.
CS629a: Sometimes generate split rooms in dungeons

Just short of 1 in 10 random room-and-corridor levels will contain a
room split horizontally or vertically.  (It's 'just short' since split
room creation can sometimes fail if minimum dimensions aren't met.)

Compared to UnNetHack, this feature is actually enabled and used, though
it took a lot of effort and original code to make it work reliably.
Virtually none of the original split room code is used here anymore
since it wasn't great (e.g. unused variables, repeated code, useless
calls to topolgize()), though the current code is inpsired by it.

Here's a list of the issues I faced to make this work:

    1. Ugly wallification - The connection of the middle wall used
       single corner connecting tiles instead of double corner ones.
       Forcing do_room_or_subroom() to always use wallification() fixed
       this.  Since this was all that do_room_or_subroom()'s is_room
       argument did, I removed it.

    2. Disconnected levels (1) - Corridors would often hit an obstacle,
       change direction and just barrel to the edge of the level, never
       connecting to its target.  It was caused by rooms trying to dig
       corridors to the unreachable shared wall of either of the split
       room halves.  To solve this, I guaranteed split room halves be
       connected, and allowed split room halves to act as proxies for
       each other when this situation happened.  This led to...

    3. Broken door bookkeeping (1) - join() had to be changed to handle
       joining of split rooms: don't try to create a corridor, track the
       first door in both rooms instead of making two, using add_door()
       directly.

    4. Broken door bookeeping (2) - Calling add_door() before
       sort_rooms() caused add_door() calls afterwards to go haywire.
       This is because add_door() assumes each room's list of tracked
       doors (including fdoor starting index and doorct length) is in
       the same order as the rooms themselves.  I fixed this by making
       sort_rooms() re-order any existing doors to match the new room
       order.  I did this instead of changing add_door() to preserve the
       room-door ordering, in case existing or future code relies on it.

    5. Disconnected levels (2) - Even with the split room fixes,
       corridors would still fail.  NetHack's corridor digging algorithm
       is very sensitive to room positions (particularly near level
       edges) and even room sizes (which determine relative door
       positions).  Here's roughly how it works:

           while not at target
               fail if tries > 500
               step forward
               fail if at the edge of the level
               dig out the corridor
       (a)     if moving laterally to target
                   if can turn 90 degrees to target
                       turn 90 degrees to target
                       jump to top of while loop
               if can move forward
                   jump to top of while loop
       (b)     we're blocked, so turn 90 degrees to target
       (b)     if turn isn't blocked
       (b)         jump to top of while loop
               emergency reverse!

       The way lateral checks work is that it divides the coordinates
       around the target into quadrants: top, bottom, left and right.
       If a sufficiently large room becomes an obstacle to a corridor,
       it's possible for the corridor to move into another quadrant but
       away from the target, which (a) fails to account for.  I fixed
       this by enhancing this turn check to include checks for when the
       corridor moves away from the target, allowing the algorithm to
       correct itself in such cases.

       The steps marked (b) are obstacle handling.  A large enough room
       near the edge of the level could cause the 90 degree turn here to
       run into that edge.  I fixed this by scouting in both of the
       possible directions before commiting to one that would work, so
       if a right-headed corridor was blocked and needed to choose
       between going up or down, and down struck the edge of the level,
       it'd choose to go up, even if its target was technically below it
       in the y coordinate.

       Apart from those problems, I had to ensure that split rooms had
       at least as much of an empty border around them as normal rooms,
       since corridor digging relies on them, so the border (margin)
       calculations in mk_split_room() mimic those in create_room().

All these changes have been tested through 50 full main dungeon runs,
which comes to about 1250 normal room-and-corridor levels (assuming
there are 25 such levels in an average game), so it should all be
stable.

At the end of this all, I accomplished the following:

    * working split rooms
    * let add_door()/join() be used before and after sort_rooms()
    * improved corridor algorithm to cover more cases and scout ahead
      before choosing a direction around an obstacle

This commit uses nested functions for the sort_room() changes, which is
a C99 feature.

According to UnNetHack, this is one of a group of changes from SporkHack
r640-642.
Avoid randomly choosing corridor style 1 (random)

... since it often looks ugly.  The code for this style is kept for
compatibility with future changes from UnNetHack, SporkHack or any other
source that uses the optional argument to RANDOM_CORRIDORS in its
special level files.
CS629b: Sometimes add corpse to iron bar niches

2 in 3 niches made with iron bars will have a random @ corpse inside.

According to UnNetHack, this is one of a group of changes from SporkHack
r640-642.
Fix port of CS94

Missing comma in list of hallucinated monsters, my bad.
Bring back SHOPTYPE environment variable

I think this was originally removed in the big DEBUG code purge, but
it's very useful so I'm bringing it back.  When the SHOPTYPE environment
variable is set and the game is in wizard mode, it will generate rooms
of the following types:

    exact shop name or item class symbol
        the chosen shop, even if the room has more than one door

    z or Z      zoo
    m or M      morgue
    b or B      beehive
    p or P      lemure pit
    t or T      court
    s or S      barracks
    a or A      anthole
    c or C      cockatrice nest
    r or R      dilapidated armory
    l or L      leprechaun hall
    _           temple
    n           garden
    }           swamp
    g or G      general store