I've been thinking about this again. I was originally trying to build something like this for my joke game Tomb of the Dead; but rather than putting it off I might be better typing it on the forum, without disconnections and editor trouble to distract me; so a first top-of-my-head version of the code is there if I decide to use it. And it's here for anyone else to comment on; and to draw inspiration from if it helps you to understand my thought process :)

The idea here is that the map is divided into 'chunks'; groups of rooms connected together. The engine can generate a random map layout, but rooms in the same chunk will always be positioned together.

We'll do it recursively (yes, I know there's a memory overhead to that) in order to make rollback easier. We could use a modified DLX algorithm; but thanks to Quest's slow dictionaries we would end up creating hundreds of temporary objects to store data; which is not ideal. (Actually… one option would be to hand everything over to Javascript, run map generation on the client side, and then hand control back to Quest when it's finished… this would remove the risk of the script timing out, as well. But… that's a bit silly)

I'll start by picking some attributes we will need for keeping track of stuff. I'll give the rooms attributes to store their coordinates in the grid temporarily. I'm going to give each room an attribute map_coordinates (a string of the form "x;y;z" for quicker comparisons). My system will assume that the player starts at 0/0/0 unless otherwise specified, and won't move around rooms that have numbers preassigned.

Note that at this point I am NOT dealing with some of the funky stuff that gridmap does; like rooms of different sizes, and exit lengths. This means that the coordinates I'm using are not necessarily the same as map coordinates, and are all integers. Maybe I'll change that later; but it seems like it might be a much bigger headache.

Let's have some attributes that the user can set on rooms to control map generation. These might not be implemented in the first version of the code, but I'll try to keep them in mind so they won't be too hard to add later:

• map_cloneable - if true, this room can be cloned to build up the map. This attribute will be checked when it's time to add the room to the map. If only some rooms in a chunk are cloneable, they ones that aren't will appear in the first copy to be placed.
• map_clone_limit - maximum number of clones for this room (if given)
• map_clone_substitutes - when cloning this room, replace it with an alternative from this list (so if you have a dozen single rooms which could be found along a certain corridor, you could use this so that they're treated identically for the purposes of making the map, and then one is selected when it's time to actually clone them - meaning that each room doesn't get considered separately when working out whether they will fit. Note that using this for chunks which aren't the same size and shape may result in overlapping rooms)
• map_required - if true, any layout which can't include this room will result in starting over. When the game starts, it will run room generation until all required rooms are placed; other parts of the map (such as mazes of potentially-infinite clone rooms) can be filled in as the player explores them.
• map_allow_overlap - if true, this room can be in the same place as another room. May apply by default for rooms reachable by "in" or "out" exits; if I remember.
• map_attempt - a script to run when the map tries to connect this room. This may be done a dozen times, as the map tries different options, so the script shouldn't be one which takes a long time to run. This script can use the variables xpos, ypos, zpos (integers), entrancefrom (room object), entrancedirection ("north", "south", etc), and entrancereverse (the reverse exit which will be moved into this room, if applicable) to find out about where the script is trying to place it. The stringlist maperrors will initially be empty; but adding any element to it will prevent the room being placed here.
• map_initialise - a script to run after giving the room its final coordinates.

We can also have rooms with randomisable exits (which connect the chunks together). Exits can be given the attributes:

• random_to - a list of rooms, or a string attribute of the form kitchen;tunnel6;room12;room15, specifying which rooms which the exit can go to (connecting their chunks)
• random_to_expression - an expression which generates a list of possible destinations (overriding the above)
• map_required_exit - if true, this exit must go somewhere. If all of the destinations on the list have been placed elsewhere, or there's no space for them, this will cause map generation to back up.
• map_dummy_exit - What to do if none of the random options can be placed here. If a string, it will be treated as a locked message for the exit ("This way is blocked", for example). If an object (or objectlist to pick one), that object will be cloned here to replace the exit (so you could have an object which is a barred door or a pile of rocks blocking a tunnel, for example). If false, the exit will be removed. If true, the exit will be left as-is (treated as non-random).
• map_wonky - If true, this exit doesn't set the coordinates of the room on the other side. For example, if the description says you crawl through a maze of ductwork and don't know which way you're going, the rooms on either side of it could be anywhere.
• map_create_reverse - if the attribute refers to an object or exit, it will be moved to the destination room to act as the other side of this door. If false, no reverse exit will be created. If true, create a standard exit in the other direction. (Allows exits to be one-way; or to have other descriptive attributes)

Other settings:

• game.map_max_filler - the maximum number of cloneable, non-required rooms that the system will place in a row before it temporarily excludes them from the next placement. If you've got a bunch of mapped out sections for your castle, and then some cloneable generic corridors and storerooms to fill out the space between them, then you don't want it to waste time filling in the negative space in the map with storerooms before it realises that the throne room complex is too big to fit anywhere.

Now, I think a sensible algorithm would be:

1. Place the starting room.

When a room is placed (including the starting room) it would:

1. Assign coordinates to all the rooms connected to it
2. If any of the rooms collides with coordinates that have already been used, return failure.
3. If all required rooms and exits have been placed, return success.
4. Loop over the randomisable exits out of the area that's currently connected
   5. Loop over the list of options for where that exit can connect to. For each option (in random order):
      • Try to place that room next to that exit. If it returns success, we return success as well
   6. If the exit isn't required, do whatever its dummy behaviour is before trying the next option
   7. If the exit is required, we can't place this room here. Undo all the coordinate allocations from step 2 above, and return failure.
5. If we get here without returning, then we can't connect any more chunks to the map anywhere, and there are unplaced required rooms. So undo all the coordinate allocations from step 2 above, and return failure.

Wow… I've been typing for ages and I'm still on the pseudocode. Going to leave this here and go for a walk; will turn that into actual code later. Any ideas/feedback would be appreciated.

EDIT:
I think that for something like this, cloneable rooms are a good idea. If you just have map regions, it would be easy to end up in a situation where they collide, but having a small chunk (like one or two corridors) would make it possible to fit in the important rooms. However, if we reach an impossible situation and have to backtrack, creating and destroying objects is rather intensive for Quest. Therefore I think it would make more sense to make a list of rooms to clone, and only actually create stuff when we know the layout works.

And a first piece of actual code: A utility function to convert various data types to an objectlist (which will be useful in a few places).

<function name="MakeObjectList" parameters="input" type="objectlist">
  todo = NewList ()
  output = NewObjectList ()
  list add (todo, input)
  while (not ListCount (todo) = 0) {
    item = ListItem (todo, 0)
    list remove (todo, item)
    switch (TypeOf (item)) {
      case ("string") {
        foreach (part, Split(item)) {
          if (IsInt (part)) {
            list add (todo, ToInt (part))
          }
          else {
            list add (output, GetObject (part))
          }
        }
      }
      case ("int") {
        for (i, 1, item) {
          list add (output, null)
        }
      }
      case ("list", "objectlist", "stringlist") {
        foreach (part, item) {
          list add (todo, part)
        }
      }
      case ("object") {
        list add (output, item)
      }
      case ("script") {
        invoke (item, QuickParams ("items", output, "parameters", todo))
      }
      default {
        JS.console.log ("Warning: Can't convert " + ToString (item) + " (" + TypeOf (item) + ") to object in MakeObjectList")
      }
    }
  }
  return (output)
</function>

EDIT2:
A second function, this time to add a single room to an existing chunk. This does it recursively, because that seems like the simplest way to do it. The actual chunk-connecting code will be pretty similar to this, but with a lot more complex stuff added.

This time, I'm actually passing a bunch of stringlists to the function; it will return the number of rooms added, but will pass back a lot more data by adding items to those lists. This seems to make more sense, as it means we don't need to take a long time massaging the data into a usable format to pass back and forth.

Parameters:

• room - rooms to add
• xpos, ypos, zpos - coordinates for the room
• rooms_by_coords - dictionary mapping coordinate strings ("X;Y;Z") onto the rooms that can be found there. Value will be a room name, to account for clones. Clones will show as "roomname=number"; for example, the 3rd clone of hallway1 will be named "hallway1=3". Because a chunk might already contain multiple rooms at the same coords for some reason (such as in/out exits or nested rooms), this will be a dictionary of stringlists containing the names.
• rooms_in_chunk - as above, but for rooms added in this chunk. Tracked separately so that they could easily be removed if it turns out the room isn't allowed here.
• pending_exits - an objectlist, containing exits from which new chunks could be reached
• pending_required - an objectlist of required rooms which haven't yet been reached
• mapwarnings - a stringlist of warnings, which may be displayed on the console so that users can figure out why their map has problems
• maperrors - a stringlist of errors found while trying to lay out the map. If this has any elements in it, the chunk will probably fail to be generated; but we don't abort right away in case another script wants to overrule it

<function name="AddRoomToChunk" parameters="room, xpos, ypos, zpos, rooms_by_coords, rooms_in_chunk, pending_exits, pending_required, mapwarnings, maperrors" type="int">
  // TODO
</function>

Just realised I never finished this. That's what happens when I try to make something in my own project; I just get too many other things demanding my attention. Thought that doing it on a forum post might be easier, but…

Well, here's a little bit more, anyway. Utility functions first

<function name="AddRoomCoordsToDictionary" parameters="dict, coords, roomname, mapwarnings">
  if (DictionaryContains (dict, coords)) {
    list = DictionaryItem (dict, coords)
  }
  else {
    list = NewStringList ()
    dictionary add (dict, coords, list)
  }
  if (ListContains (list, roomname)) {
    list add (mapwarnings, "Adding room '" + roomname + "' to list at coords " + coords + ". Room already present.")
  }
  else {
    list add (list, roomname)
  }
</function>

<function name="RemoveRoomCoordsFromDictionary" parameters="dict, coords, roomname, mapwarnings">
  if (DictionaryContains (dict, coords)) {
    list = DictionaryItem (dict, coords)
    if (ListContains (list, roomname)) {
      list remove (list, roomname)
    }
    else {
      list add (mapwarnings, "Removing room '" + roomname + "' from dictionary at coords " + coords + ". Room doesn't exist here.")
    }
  }
  else {
    list add (mapwarnings, "Removing room '" + roomname + "' from dictionary at coords " + coords + ". No rooms at these coordinates.")
  }
</function>

<function name="RollbackCoordsDictionaries" parameters="masterdict, rollbackdict, mapwarnings">
  foreach (coords, rollbackdict) {
    roomlist = DictionaryItem (rollbackdict, coords)
    while (not ListCount (roomlist) = 0) {
      roomname = ListItem (roomlist, 0)
      RemoveRoomCoordsFromDictionary (masterdict, coords, roomname, mapwarnings)
      RemoveRoomCoordsFromDictionary (rollbackdict, coords, roomname, mapwarnings)
      room = GetMapBaseRoom (roomname, mapwarnings, maperrors)
      if (not room=null) {
        switch (TypeOf (room, "map_coordinates")) {
          case ("string") {
            if (room.map_coordinates = coords) {
              room.map_coordinates = null
            }
            else {
              list add (maperrors, "Removing room '" + roomname + "' from " + coords + ", but it's at " + room.map_coordinates)
            }
          }
          case ("list", "stringlist") {
            if (ListContains (room.map_coordinates, coords)) {
              list remove (room.map_coordinates, coords)
            }
            else {
              list add (maperrors, "Removing room '" + roomname + "' from " + coords + ", but it's at " + room.map_coordinates)
            }
          }
          default {
            list add (maperrors, "Removing '" + roomname + "' from " + coords + " but its map_coordinates is 
 "+room.map_coordinates + "' ("+TypeOf (room, "map_coordinates") + ")")
          }
        }
      }
    }
  }
</function>

<!-- This function may have more sanity checks added later - like checking for clones of a non-cloneable room -->
<!-- For now it will just let errors slip through, so isn't very robust -->
<function name="GetMapBaseRoom" parameters="roomname, mapwarnings, maperrors" type="object">
  split = Instr (roomname, "=")
  if (split = 0) {
    room = GetObject (roomname)
  }
  else {
    room = GetObject (Left (roomname, split - 1))
  }
  if (room = null) {
    list add (maperrors, "Failed to get base room for '" + roomname + "'")
  }
  return (room)
</function>

And then we move on to actual logic:

<function name="AddRoomToChunk" parameters="room, xpos, ypos, zpos, rooms_by_coords, rooms_in_chunk, pending_exits, exits_to_create, pending_required, mapwarnings, maperrors" type="int">
  coords = "" + x + "/" + y + "/" + z
  roomname = room.name
  if (IsRoomAtCoordinates (room, coords)) {
    return (0)
  }
  else if (HasAttribute (room, "map_coordinates")) {
    switch (TypeOf ((room, "map_coordinates")) {
      case ("string") {
        if (room.map_coordinates = "") {
          room.map_coordinates = coords
          list add (mapwarnings, "Room " + room.name + " had empty string in coords")
        }
        else {
          if (not GetBoolean (map, "cloneable")) {
            list add (mapwarnings, "Cloning non-cloneable room " + room.name)
          }
          // TODO - change the attribute to a list
        }
      }
      case ("stringlist", "list") {
        // TODO
      }
      default {
        list add (maperrors, "Couldn't add '" + room.name + "' at coords " + coords + " - map_coordinates is " + room.map_coordinates + " (" + TypeOf (room, "map_coordinates") + ")")
      }
    }
  }
  else {
    // room hasn't been placed yet
    if (GetBoolean (room, "cloneable")) {
      roomname = roomname + "=1"
      room.map_coordinates = NewStringList ()
      list add (room.map_coordinates, coords)
    }
    else {
      room.map_coordinates = coords
    }
  }
  AddRoomCoordsToDictionary (rooms_by_cords, coords, roomname, mapwarnings)
  AddRoomCoordsToDictionary (rooms_in_chunk, coords, roomname, mapwarnings)
  roomsadded = 1
  // TODO - loop over exits and call this function again for adjacent rooms
  return (roomsadded)
</function>

EDIT: I've made a couple of attempts to fill in the incomplete bits of this function, and I keep finding unexpected complexity as a result of the clones. It might be better to disregard clones for now, and then add them in once the rest of the code is done.

Okay… here's a simplified version without support for cloneable rooms

<function name="AddRoomToChunk" parameters="room, xpos, ypos, zpos, rooms_by_coords, rooms_in_chunk, pending_exits, pending_required, mapwarnings, maperrors" type="int">
  coords = "" + x + "/" + y + "/" + z
  roomname = room.name
  if (HasString (room, "map_coordinates")) {
    if (not Equals (coords, room.map_coordinates)) {
      list add (maperrors, "Room " + room.name + " has already been placed at " + room.map_coordinates + ". Can't place it at " + coords + ".")
    }
    return (0)
  }
  else {
    // room hasn't been placed yet
    room.map_coordinates = coords
  }
  AddRoomCoordsToDictionary (rooms_by_cords, coords, roomname, mapwarnings)
  AddRoomCoordsToDictionary (rooms_in_chunk, coords, roomname, mapwarnings)
  if (ListContains (pending_required, room)) {
    list remove (pending_required, room)
  }
  roomsadded = 1

  // TODO - loop over exits and call this function again for adjacent rooms
  foreach (door, AllExits()) {
    if (door.parent = room) {
      if (HasAttribute (door, "random_to") or HasAttribute (door, "random_to_expression") and not GetBoolean (door, "random_done")) {
        list add (pending_exits, door)
      }
      else if (not GetBoolean (door, "map_wonky")) {
        xdest = xpos
        ydest = ypos
        zdest = zpos
        foreach (dir, Split("north;south;east;west;northeast;northwest;southeast;southwest;up;down")) {
          if (DoesInherit (door, dir + "direction")) {
            if (not Instr(dir, "north") = 0) {
              ydest = ydest - 1
            }
            else if (not Instr(dir, "south") = 0) {
              ydest = ydest + 1
            }
            if (not Instr(dir, "west") = 0) {
              xdest = xdest - 1
            }
            else if (not Instr(dir, "east") = 0) {
              xdest = xdest + 1
            }
            if (not Instr(dir, "down") = 0) {
              zdest = zdest - 1
            }
            else if (not Instr(dir, "up") = 0) {
              zdest = zdest + 1
            }
          }
        }
        roomsadded = roomsadded + AddRoomToChunk (door.to, xdest, ydest, zdest, rooms_by_coords, rooms_in_chunk, pending_exits, pending_required, mapwarnings, maperrors)
      }
    }
  }
  return (roomsadded)
</function>