Jump to content

Collision map file: Difference between revisions

Collision map file (view source)

Revision as of 14:44, 22 April 2025

3,836 bytes added ,  Yesterday at 14:44
Navigation meshes
VisualWikitext
(Unknown block 1)
(Navigation meshes)
 
(3 intermediate revisions by the same user not shown)
Line 6: Line 6:


= File format =
= File format =
{| class="wikitable"
<syntaxhighlight lang="c">
|-
struct collision_map_file  {
! Type || Description
  /* offset 0x00 */ char magic[4]; // "HP" followed by two null bytes
|-
 
| char[4] || Magic number ("HP\0\0")
  // Byte offset from start of this struct to the tile_data struct
|-
  /* offset 0x04 */ u32 offsetToTileData;
| u32 || Offset from start of file to [[#Tile data]]
 
|-
  // Byte offset from start of this struct to the zone_data struct
| u32 || Offset from start of file to [[#Zones]]
  /* offset 0x08 */ u32 offsetToZones;
|-
 
| u32 || Offset from start of file to [[#Unknown block 1]] (maybe related to enemy patrolling?)
  // Byte offset from start of this struct to the PathData struct
|-
  /* offset 0x0c */ u32 offsetToPaths;
| u32 || Offset from start of file to [[#Unknown block 2]] (maybe related to enemy patrolling?)
 
|-
  // Byte offset from start of this struct to the NavMesh struct
| || Tile data
  /* offset 0x10 */ u32 offsetToNavmesh;
|-
};
| || Zones
</syntaxhighlight>
|-
| || Unknown block 1
|-
| || Unknown block 2
|}


= Tile data =
= Tile data =
Line 95: Line 90:
</syntaxhighlight>
</syntaxhighlight>


= Unknown block 1 =
= Paths =
<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
struct UnknownBlock1 {
struct PathData {
   /* offset 0x00 */ u32 itemCount;
   /* offset 0x00 */ u32 pathCount;
   /* offset 0x04 */ UnknownBlockItem items[itemCount];
   /* offset 0x04 */ Path paths[pathCount];


   UnknownBlockData data[];
   PathNode nodes[];
};
};


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


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


struct UnknownBlock1Data {
struct PathNode {
   u16 a, b, c, d;
   /* 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;
};
};
</syntaxhighlight>
</syntaxhighlight>


= Unknown block 2 =
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'' (<code>NavRect</code>). 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'' (<code>NavPortal</code>). 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 <code>st01_02a</code>, 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:
 
[[File:St01_00a_navmesh.png]]
 
<syntaxhighlight lang="c">
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];
};
</syntaxhighlight>
 
To retrieve the distance between portals ''i'' and ''j'':
<syntaxhighlight lang="c">
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];
}
</syntaxhighlight>


= See also =
= See also =
Retrieved from "https://boktaihacking.net/wiki/Special:MobileDiff/424...448"