#2 – Delving Deeper

SpelunkBotsCoverPhotoFor the entirety of Spring 2015 Jordan Rowe will be officially a member of the SpelunkBots team with the job title ‘Spelunky Assistant’.

Since the last post, they have been working tirelessly to update the documentation, to make it more ‘first time user friendly’, as well as tweak the SpelunkBots DLL to optimise methods and fix bugs. There’s also an official web page now, check it out!

In light of a paper written by Tommy Thompson and with reference to TinySubVersions, I have been looking into how a SpelunkBot can play the randomised campaign of Spelunky and be able to orientate itself within a variable environment, purposefully heading to the exit by systematically working out where it is.

The biggest problem with this is the ‘fog of war’ that is overlaid onto the game map, to stop the bot simply looking up the map file and creating an A* based search on its path to the exit. Doing so would be more ‘cheating’ and less ‘playing’ Spelunky, the way a human would.

The current example bot included in the framework is ‘FishBot’ (named after its creator Chris Fisher). This solution to the navigation issue is simple, we chose a direction, left or right, and walk there… and continue to walk there… and if we find there is a block in our way we jump over it… and keep walking.
UNTIL we find a three or so high stack of blocks, something we can’t jump over, at which point we turn back to the other direction and walk back the way we have come. If theres a ledge we happily walk off the edge, no matter how dangerous or considering a way back up.

SpelunkyMapGenerated01
Entrance at top left, exit bottom left.

This approach works better than expected (at least on the times it doesn’t fall down a pit it can’t get out) due to one convenient fact. The entrance to a Spelunky level is always on the top ‘floor’ of the map and the exit on the bottom.

This rule of the map generation system, whilst not explicitly stated to the player, subtly provides them with a general purpose of direction when navigating the subterra caverns. Most importantly it provides us with a general direction which our bot needs to head.

The next fact we can use to our advantage is that the map is divided into ‘rooms’ on a 4×4 basis. A start room is chosen and a path is built left or right until such time as the conditions to drop down are fulfilled. This iterates until the bottom row is reached at which point if we attempt to drop the exit room is placed.
The remaining spaces are populated with rooms that are not part of our solution path. Each room has between 0-4 exits and falls into 4 main categories:

SpelunkyMapGenerated02
Examples of all room types, including several versions of 0 rooms
  • 0 rooms are the left over spaces that represent rooms not part of our solution (may have any number of exits, as far as I’m aware)
  • 1 represents rooms with a left and right exit only
  • 2 is for left, right and bottom (in some cases this also includes the top)
  • 3 is for left, right and top only.

The aim of the navigation bot is to attempt to calculate which room it is in at current, thus aiding it to deduce the solution path, thus helping it to work out where the exit is for the level. In theory if the bot can correctly deduce the room types it will always be able to navigate the map (though things will get more hairy in later levels, when more tiles are removed from the rooms).
The current room can be deduced fairly reliably by applying a few logical constants.

SpelunkyMapGenerated04Exits
Exits of each room have been marked in blue, while the room boundaries have been shown in red. Note the 1 block wide frame that contains the player is not part of this generation sequence.
  1. The beginning room will always be of Type1.
  2. The beginning room will always be on the top row.
  3. A room of Type3 will always have a room of Type2 above it.
  4. If there is an exit out the bottom of the floor the room is either Type0 or Type2.
  5. Each of the top three rows can only have one room of Type2 each.
  6. The bottom row cannot have a Type2 room.
  7. Each of the bottom three rows can only one room of Type3 each.
  8. The top row cannot have a Type3 room.
  9. The exit will always be on the bottom row.
  10. If we are in a room with the exit we no longer need to worry about where the exit is (obviously).

These will be true for every Spelunky generated level we come across. So what can we do with this information?
Lets look at some pseudo-code:

// *disclaimer* this code is not very efficient but vaguely stands to show how one might implement the threoy
// Using an array to get a rough idea of the room layout for this level
// To reinforce some math on the map dimensions
// Each room is 10 blocks wide and 8 blocks tall
// Each level have 4 rows of 4 rooms
// The total level size is 40 blocks wide by 32 blocks tall
// Including the single block border the level is in fact 42 blocks wide by 34 blocks tall


// populate initial values that mean nothing to our 0-3 room numbering.
void Init()
{
  int roomsArray[4][4]{{5,5,5,5}
                      {5,5,5,5}
                      {5,5,5,5}
                      {5,5,5,5}};
  // Row, collumn coordinates and room type
  int currentRoom[3]{{5,5,1}};
}
int roomAbove[3]{5,5,5};

//loop on repeat for whole time bot is running
void FindNextRoom()
{
  if (exitInRoom())
  {
    // In accordance with rule 10
    GoToExit();
    // We don't know where we are in new room
    Init();
  }
  else
  {
    if(currentRoom[0]==5 && currentRoom[1]==5)
    {
      WhereInTopRow();
    }
    else if (ValidCords())
    {
      // We can start applying our rules!
      // Lets start with no.3
      if (currentRoom[2]==3)
      {
        roomAbove[2] = 2;
      }
      // Rules 5 and 6
      if (currentRoom[0] == 3 ||
          roomsArray[currentRoom[0]][0] == 2 ||
          roomsArray[currentRoom[0]][1] == 2 ||
          roomsArray[currentRoom[0]][2] == 2 ||
          roomsArray[currentRoom[0]][3] == 2)
      {
        currentRoom[2] != 2;
      }
      // Rules 7 and 8
      if (currentRoom[0] == 0 ||
          roomsArray[currentRoom[0]][0] == 3 ||
          roomsArray[currentRoom[0]][1] == 3 ||
          roomsArray[currentRoom[0]][2] == 3 ||
          roomsArray[currentRoom[0]][3] == 3)
      {
        currentRoom[2] != 3;
      }
      MoveToNextRoom();
    }
    else
    {
      // uh, oh something has gone wrong and we don't know were we are again
      currentRoom = {5,5,5};
    }
  }
  return;
}

bool ExitInRoom()
{
  // Code for checking if exit is in this room
}
bool ValidCoords()
{
  // Check for if our coordinates are valid in the bounds of 0-3
}
bool CanExitLeft()
{
  // Return true if can enter another room via the left hand exit
}
bool CanExitRight()
{
  // Return true if can enter another room via the right hand exit
}


// Figure out where on the top row we are placed
void WhereInTopRow()
{
  // In accordance with rule 2 above
  currentRoom[0] = 0;

  if (!CanExitLeft())
  {
    // We must be in top left
    currentRoom[1] = 0;
    // In accordance with rule 1
    roomsArray[0][0] = 1;
  }
  else if(!CanExitRight())
  {
    // We must be in top right
    currentRoom[1] = 3;
    // In accordance with rule 1
    roomsArray[0][3] = 1;
  }
  else
  {
    // We are in one of the middle two rooms
    // Try placing the rooms one either side of and work our way across
    // Also have to map most/all of top row, eurgh
  }

  return;
}

void MoveToNextRoom(int currentRoomType)
{
  switch (currentRoomType)
  {
    case 0:
      // exit back through the side which we just came in to rejoin exit path
      break;
    case 1:
      // move either left or right into an unmapped room
      break;
    case 2:
      // move down, with caution to avoid fall damage
      break;
    case 3:
      // move left or right
      break;
    default:
      // uh, shouldn't happen
      break;
  }
}

NB rule 9 is never applied in code, this is because our moving left and right on the bottom row will find the exit room automatically. It is still useful to keep in mind however as it means we must always try and travel to the bottom of the level.

SpelunkyMapGenerated05Finally, an easy working example of our code.

  • Starting on the top row we pick either left or right and move into the room on that side.
    (If our choice was left, we move into room0, realise this, turn back and head into the unmapped room on our right).
  • We have ended up in a room1 whichever direction we pick.
  • Next we head into the next unmapped room left or right, in this case we go right again, we’re at room2.
  • we drop down. room3
  • can’t go right any more so we go left. room 1
  • then left again. room1
  • and once more. room2
  • drop down to room3
  • left, left, left takes us through room1, room1 and into room2
  • down into room3
  • OH! the exit is in this room, Level Complete!

This process should get you through all 5 of the example levels pictured in this post (which, not so coincidently, I have added to the source for SpelunkBots). The next level of refinement is to efficiently deal with enemies and traps, after which our little bot will be well equipped to deal with working campaign levels.

Advertisements