Collision map file

Collision map files are stored in directory id_low = 0xd710, id_high = 0x9305 in the Master file table. They contain the gameplay relevant details of a map. This includes heights, collision data, event triggers, and so on. They do not include graphics (tile sets, tile maps, palettes, etc.).

Compression

Most (all?) maps are stored LZ77 (swi 0x11) compressed. When loading a map, the game checks if the map file starts with the ASCII characters "HP" (hex: 0x48, 0x50). If it does, then the map file is not compressed, and used by the game as-is. If it does not start with these characters, the game will LZ77 decompress it to EWRAM (in Boktai 1: to 0x0202a400). Note that the first 4 bytes after decompression must be discarded (they will contain the uncompressed length of the file).

File format

struct collision_map_file  {
  /* offset 0x00 */ char magic[4]; // "HP" followed by two null bytes

  // Byte offset from start of this struct to the tile_data struct
  /* offset 0x04 */ u32 offsetToTileData;

  // Byte offset from start of this struct to the zone_data struct
  /* offset 0x08 */ u32 offsetToZones;

  // Byte offset from start of this struct to the PathData struct
  /* offset 0x0c */ u32 offsetToPaths;

  // Byte offset from start of this struct to the NavMesh struct
  /* offset 0x10 */ u32 offsetToNavmesh;
};

Tile data

struct tile_data {
  u32 unknown_1;
  u16 width;
  u16 height;
  u32 unknown_2;
  tile[height*width] tiles;
};

// Note how stairs and height are packed into a single byte, making this struct 4 bytes long.
struct tile {
  tile_effects effect;
  u8 obj;
  u8 stairs_and_height;  // top 4 bits = stairs, bottom 4 bits = height
};

// Bitmask, multiple effects per tile are supported
enum tile_effects : u16 {
  wall = 0x0002,    // an always inaccessible tile
  unknown = 0x0004  // sometimes used directly on loading zone tiles
  noise = 0x0020,   // alerts enemies when stepping onto the tile
  ice = 0x0040,
  lava = 0x0080,
  void = 0x0100,    // fall down and die
  unknown = 0x0400, // wall-ish
  unknown = 0x0800, // sometimes used near loading zones pointing NW
  unknown = 0x1000, // sometimes used near loading zones pointing NE
  // other bits unknown
};

enum tile_stairs : u8 {
  none = 0x00,
  vertical = 0x10,   // from south -> north
  horizontal = 0x20, // from east -> west
};

• tile.obj: This determines the sprite that is used to occlude Django when he should be covered by the tile. Purely visual. 0 = default, other values need to be documented.
• tile.height: A tile is only accessible to Django if he's either coming from a tile at the same height, or coming via a suitable stair tile.

Zone data

Zones are triggers for events (cutscenes, loading zones, etc.). The map file only defines the geometry of each zone. Behaviour is linked to zones by scripts (using the ctrl 0xd4cb instruction). Zone boundaries are more precise than tile boundaries: A tile is 256x256 units in size, and zone boundaries can start/end at any point within a tile).

struct zone_data {
  u8 count;
  u8 unknown_1;
  u16 unknown_2;
  zone[count] zones;
};

struct zone {
  // X/Y coordinates: 1 tile = 256 units
  i16 start_x;
  i16 start_y;
  i16 end_x;
  i16 end_y;
  // Z coordinate: 1 tile = 16 units
  i8 start_z;
  i8 end_z;
  // Used by scripts to link behaviour to a specific zone using its ID
  u16 id;
};

Paths

struct PathData {
  /* offset 0x00 */ u32 pathCount;
  /* offset 0x04 */ Path paths[pathCount];

  PathNode nodes[];
};

struct Path {
  /* offset 0x00 */ u16 nodeCount;

  // Byte offset from start of PathData to first node
  /* offset 0x02 */ u16 nodeOffset;
};

struct PathNode {
  /* offset 0x00 */ u16 x; // 1 tile = 0x100
  /* offset 0x02 */ u16 y;
  /* offset 0x03 */ u8 delay; // In frames, after performing the command
  /* offset 0x04 */ u8 param; // Command-specific parameter
  /* offset 0x06 */ u16 command;
};

Commands:

• 0x00: Move to x/y
• 0x10: Turn
• 0x30: Fall asleep
• 0x90/0xb0/0xe0: Show question mark
• 0xa0/0xe0: Go to space
• 0xd0: Start searching

Navigation mesh

TODO: This description is for Boktai 1 only. The navigation mesh data (may?) have changed in Boktai 2.

The navigation mesh is used to guide NPCs between arbitrary points on the map. A navigation mesh contains three data structures:

• A list of rectangles (NavRect). Each rectangle is axis-aligned and free of obstacles. For any two points within the same rectangle, the shortest path between them is a straight line. Every walkable tile on the map should be covered by at least one NavRect.
• A list of portals (NavPortal). NavRects always have at least one tile of overlap with adjacent NavRects, and at the center of each overlapping area there is a portal.
• A distance map containing the distance between each possible pair of portals (as calculated by a path-finding algorithm).

For example, here is an image of Boktai 1's st01_02a, the exterior portion of the entrance to Bloodrust Mansion. A subset of NavRects are shown as green rectangles. Note how there is one tile of overlap between the long vertical road, and the small horizontal paths sticking out of the road. At the center of each overlap is a blue marker, representing a portal:

struct NavMesh {
  // Number of elements in the rects array
  /* offset 0x00*/ u16 countRects;
  /* offset 0x02*/ u16 countPortals;
  /* offset 0x04*/ u16 countDistanceMap;

  // Byte offset from start of this struct to the rects array
  /* offset 0x08*/ u32 offsetToRects;
  /* offset 0x0c*/ u32 offsetToPortals;
  /* offset 0x10*/ u32 offsetToDistanceMap;

  NavRect rects[];
  NavPortal portals[];

  // The distance map is stored in a compressed form: On a logical level, it is
  // a matrix with countPortal rows and countPortal columns, where each element
  // in the matrix is the distance between the two portals.
  // However, since the distance between two points is the same in either
  // direction, we only store the top-right half of the matrix (the bottom-left
  // half is a mirror image). And since the distance between a portal and
  // itself is zero, we don't store the diagonal either.

  // If two portals are connected via a straight line, then the distance is just
  // sqrt((x1-x2)^2 + (y1-y2)^2)). If there is no path at all between two
  // portals, then the distance should be set to 0xffff.
  u16 distanceMap[];
};

struct NavRect {
  // 1 tile = 1
  /* offset 0x00 */ u8 minX;
  /* offset 0x01 */ u8 minY;
  /* offset 0x02 */ u8 maxX;
  /* offset 0x03 */ u8 maxY;

  // Indices into NavMesh.portals. At most 12 portals per rect, unused elements
  // in this array must be at the end of the array, and set to 0xff.
  u8 portals[12];
};

struct NavPortal {
  // 1 tile = 0x100
  /* offset 0x00 */ u16 x;
  /* offset 0x02 */ u16 y;
  /* offset 0x04 */ u16 unknown_0x04;

  // Indices into NavMesh.rects. At most 6 rects per portal, unused elements
  // in this array must be at the end of the array, and set to 0xff.
  /* offset 0x06 */ u8 rects[6];
};

To retrieve the distance between portals i and j:

u16 GetDistance(u16* distanceMap, u16 countPortals, int i, int j)
{
  if (i == j) {
    return 0;
  }
  if (j < i) {
    // Ensure i < j
    std::swap(i, j);
  }
  int index = i*countPortals + j - ((i+2)*(i+1) >> 1);
  return distanceMap[index];
}

See also

• Collision map files (Boktai 1)