Thoughts about the grid map

I've been thinking about the way Quest handles the grid map; and realising that the code is quite inefficient. Now, looping over all the exits in the game every time a player enters a room might not seem like a lot of work, but for the webserver that's running so many games at once, I think this could be putting quite a load on it.

So I'm wondering if it might be possible to write a function which calculates the coordinates of all rooms, without so many loops necessary. I'm doing this by introducing the concept of 'worlds'; a group of rooms which are connected to each other by directional exits.

Each world will be named after the first room in it, and worlds will be merged when a room appears in more than one.
As there isn't an easy way to distinguish between an object and a room, I'll use the presence of exits to decide what is a room.

I'll give each room a set of attributes: grid_x, grid_y, grid_z, and grid_w, as accessing these is faster than looking stuff up in a tree of dictionaries.

// a dictionary of which rooms are in each world; the key is the world name and the value is a list of rooms
rooms_by_world = NewDictionary()

// now let's make the map
foreach (exit, AllExits()) {
  // We only care about directional exits that connect two rooms
  if (DoesInherit (exit, "direction") and HasObject (exit, "parent") and HasObject (exit, "to")) {
    from = exit.parent
    to = exit.to

    if (HasString (from, "grid_w")) {
      // We have coords for the source room
      //   we only need to do anything if the rooms aren't already connected
      if (not Equals (from.grid_w, to.grid_w)) {
        worldlist = DictionaryItem (rooms_by_world, from.grid_w)
        xpos = from.grid_x + Grid_CalculateCoordinateOffsetX (from, exit, to)
        ypos = from.grid_y + Grid_CalculateCoordinateOffsetY (from, exit, to)
        zpos = from.grid_z + Grid_CalculateCoordinateOffsetZ (from, exit, to)

        if (HasString (to, "grid_w")) {
          // we already have a map for the destination room, so link the whole map together
          //   but move the smaller map, for speed
          otherworldlist = DictionaryItem (rooms_by_world, to.grid_w)
          if (ListCount(worldlist) > ListCount (otherworldlist)) {
            xoffset = xpos - to.grid_x
            yoffset = ypos - to.grid_y
            zoffset = zpos - to.grid_z
            worldname = from.grid_w
            rooms_to_move = otherworldlist
            dictionary remove (rooms_by_world, to.grid_w)
          }
          else {
            xoffset = to.grid_x - xpos
            yoffset = to.grid_y - ypos
            zoffset = to.grid_z - zpos
            worldname = to.grid_w
            rooms_to_move = worldlist
            dictionary remove (rooms_by_world, from.grid_w)
          }
          foreach (room, rooms_to_move) {
            room.grid_w = worldname
            room.grid_x = room.grid_x + xoffset
            room.grid_y = room.grid_y + yoffset
            room.grid_z = room.grid_z + zoffset
            list add (worldlist, room)
          }
        }
        else {
          // destination room is new
          to.grid_w = from.grid_w
          to.grid_x = xpos
          to.grid_y = ypos
          to.grid_z = zpos
          list add (worldlist, to)
        }
      }
    }
    else {
      if (HasString (to, "grid_w")) {
        worldlist = DictionaryItem (rooms_by_world, to.grid_w)
      }
      else {
        // both rooms are new to us, so we add the destination to the map
        to.grid_w = to.name
        to.grid_x = 0
        to.grid_y = 0
        to.grid_z = 0
        worldlist = NewObjectList()
        list add (worldlist, to)
        dictionary add (rooms_by_world, to.name, worldlist)
      }
      // we have the destination room, but not the source
      from.grid_w = to.grid_w
      from.grid_x = to.grid_x - Grid_CalculateCoordinateOffsetX (from, exit, to)
      from.grid_y = to.grid_y - Grid_CalculateCoordinateOffsetY (from, exit, to)
      from.grid_z = to.grid_z - Grid_CalculateCoordinateOffsetZ (from, exit, to)
      list add (worldlist, from)

      // For convenience, give each room a list of its exits
      from.grid_exits = NewObjectList()
    }
    list add (from.grid_exits, exit)
  }
}

With a couple of functions to do the actual calculation:

<function name="Grid_CalculateCoordinateOffsetX" parameters="from, exit, to" type="double">
  foreach (direction, Split("east;west;northeast;northwest;southeast;southwest")) {
    if (DoesInherit (exit, direction+"direction")) {
      if (EndsWith (direction, "east")) {
        exit.grid_offset_x = from.grid_width
        exit.grid_end_x = 0
        return (0 - exit.grid_length - to.grid_width)
      }
      else if (EndsWith (direction, "west")) {
        exit.grid_offset_x = 0
        exit.grid_end_x = to.grid_width
        return (exit.grid_length + from.grid_width)
      }
    }
  }
  exit.grid_offset_x = from.grid_width / 2.0
  exit.grid_end_x = to.grid_width / 2.0
  return ((from.grid_width - to.grid_width) / 2.0)
</function>

<function name="Grid_CalculateCoordinateOffsetY" parameters="from, exit, to" type="double">
  foreach (direction, Split("north;south;northeast;northwest;southeast;southwest")) {
    if (DoesInherit (exit, direction+"direction")) {
      if (StartsWith (direction, "north")) {
        exit.grid_offset_y = from.grid_length
        exit.grid_end_y = 0
        return (0 - exit.grid_length - to.grid_length)
      }
      else if (StartsWith (direction, "south")) {
        exit.grid_offset_y = 0
        exit.grid_end_y = to.grid_length
        return (exit.grid_length + from.grid_length)
      }
    }
  }
  exit.grid_offset_y = from.grid_length / 2.0
  exit.grid_end_y = to.grid_length / 2.0
  return ((from.grid_length - to.grid_length) / 2.0)
</function>

<function name="Grid_CalculateCoordinateOffsetZ" parameters="from, exit, to" type="double">
  if (DoesInherit (exit, "downdirection")) {
    return (-exit.grid_length)
  }
  else if (DoesInherit (exit, "updirection")) {
    return (exit.grid_length)
  }
  else {
    return (0)
  }
</function>

Then when the coordinates of a room are needed, we can just look them up:

<function name="Grid_CalculateMapCoordinates" parameters="room, playerobject">
  if (not HasString (room, "grid_w")) {
    // This room isn't on the map, so we add it. Maybe the player got teleported into an unconnected room?
    // or the map has been dynamically modified?
    // First try regeneration the map using the big function above:
    Grid_CalculateAllCoordinates()

    // And if that didn't work, the room really has no exits, so we make a solitary room and clear the map
    if (not HasString (room, "grid_w")) {
      room.grid_w = room.name
      room.grid_x = 0
      room.grid_y = 0
      room.grid_z = 0
    }
  }

  // Just to make sure, in case the player teleported
  Grid_SetGridCoordinateForPlayer (playerobject, room, "x", room.grid_x)
  Grid_SetGridCoordinateForPlayer (playerobject, room, "y", room.grid_y)
  Grid_SetGridCoordinateForPlayer (playerobject, room, "z", room.grid_z)
  room.grid_render = true

  foreach (exit, room.grid_exits) {
    // coords for the adjacent room
    Grid_SetGridCoordinateForPlayer (playerobject, exit.to, "x", exit.to.grid_x)
    Grid_SetGridCoordinateForPlayer (playerobject, exit.to, "y", exit.to.grid_y)
    Grid_SetGridCoordinateForPlayer (playerobject, exit.to, "z", exit.to.grid_z)
    exit.to.grid_render = true
    if (DoesInherit (exit, "compassdirection") and not GetBoolean (exit, "grid_render")) {
      // and for the exit
      Grid_SetGridCoordinateForPlayer (playerobject, exit, "x", room.grid_x + exit.grid_offset_x)
      Grid_SetGridCoordinateForPlayer (playerobject, exit, "y", room.grid_y + exit.grid_offset_y)
      Grid_SetGridCoordinateForPlayer (playerobject, exit, "end_x", exit.to.grid_x + exit.grid_end_x)
      Grid_SetGridCoordinateForPlayer (playerobject, exit, "end_y", exit.to.grid_y + exit.grid_end_y)
      exit.grid_render = true
    }
  }
</function>

Still a work in progress… and has the disadvantage that you'll have to regenerate the map if an exit moves. But I think it makes more sense to do it this way.


Log in to post a reply.

Support

Forums