Beco: Difference between revisions

From ZeldaMods (Breath of the Wild)
Jump to navigation Jump to search
imported>Leoetlino
No edit summary
(→‎Getting data for a given coordinate: replace pseudocode with actual C++ source code (from the decomp project))
 
Line 45: Line 45:
The algorithm that returns the custom data that is associated with a coordinate is very simple. It consists of determining the correct row index in the table, then iterating over segments in that row and returning the segment data when the X coordinate is within its bounds.
The algorithm that returns the custom data that is associated with a coordinate is very simple. It consists of determining the correct row index in the table, then iterating over segments in that row and returning the segment data when the X coordinate is within its bounds.


<div class="mw-collapsible mw-collapsed">
For the reference, here is the official, mostly unreversed function<ref>0x7100E41C40 in Switch 1.5.0</ref> that implements the aforementioned algorithm:
<div class="mw-collapsible-content">
<syntaxhighlight lang="c++">
<syntaxhighlight lang="c++">
unsigned int __fastcall eco::getCurrentAreaNum(float posX, float posZ, Ecosystem *ecosystem, EcoMapInfo *info)
s32 Ecosystem::getMapArea(const EcoMapInfo& info, f32 posX, f32 posZ) const {
{
    posX = sead::Mathf::clamp(posX, -5000.0f, 4999.0f);
  float _x; // s2
    posZ = sead::Mathf::clamp(posZ, -4000.0f, 4000.0f);
  float _z; // s0
  int divisor; // w10
  int numEntries; // w12
  float v8; // s4
  signed int c_x; // w8
  float v10; // s0
  float v11; // s1
  int c_z; // w9
  int idx; // w9
  u32 *v14; // x9
  __int64 v15; // x10
  __int64 v16; // x11
  EcoMapEntry *tables; // x12
  EcoMapEntry *_entryEnd; // x11
  EcoMapEntry *_entry; // x10
  signed int totalLength; // w9
  unsigned int result; // w0


  _x = -5000.0;
    const auto epsilon = [](float n) { return n >= 0.0f ? 0.5f : -0.5f; };
  if ( posX >= -5000.0 )
  {
    _x = posX;
    if ( posX > 4999.0 )
      _x = 4999.0;
  }
  _z = -4000.0;
  if ( posZ >= -4000.0 )
  {
    _z = posZ;
    if ( posZ > 4000.0 )
      _z = 4000.0;
  }


  divisor = info->map->divisor;
    s32 x = s32(posX + 5000.0f + epsilon(posX + 5000.0f));
  numEntries = info->map->numTables - 2;
     s32 z = s32(posZ + 4000.0f + epsilon(posZ + 4000.0f)) / info.mHeader->divisor;
  if ( (float)(_x + 5000.0) < 0.0 )
     s32 row = sead::Mathi::clamp(z, 0, info.mHeader->num_rows - 2);
    v8 = -0.5;
  else
     v8 = 0.5;
  c_x = (signed int)(float)((float)(_x + 5000.0) + v8);
  v10 = _z + 4000.0;
  if ( v10 < 0.0 )
    v11 = -0.5;
  else
    v11 = 0.5;
  c_z = (signed int)(float)(v10 + v11) / divisor;
  if ( c_z <= numEntries )
     numEntries = (signed int)(float)(v10 + v11) / divisor;
  if ( c_z >= 0 )
    idx = numEntries;
  else
    idx = 0;


  v14 = &info->tableOffsets[idx];
    if (info.mHeader->divisor == 10)
  if ( divisor == 0xA )
        x /= 10;
    c_x = (0x66666667LL * c_x >> 0x22) + ((unsigned __int64)(0x66666667LL * c_x) >> 0x3F);
  v15 = (signed int)*v14;
  v16 = (signed int)v14[1];
  if ( (signed int)v15 >= (signed int)v16 )
    return 0xFFFFFFFF;


  tables = info->tables;
    if (info.mRowOffsets[row] >= info.mRowOffsets[row + 1])
  _entryEnd = (EcoMapEntry *)((char *)tables + 2 * v16);
        return -1;
  _entry = (EcoMapEntry *)((char *)tables + 2 * v15);
 
  totalLength = 0;
    auto* segmentEnd = reinterpret_cast<const Segment*>(info.mRows + 2 * info.mRowOffsets[row + 1]);
  result = 0xFFFFFFFF;
    auto* segment = reinterpret_cast<const Segment*>(info.mRows + 2 * info.mRowOffsets[row]);
  while ( 1 )
    s32 totalLength = 0;
  {
    while (true) {
    totalLength += _entry->length;
        totalLength += segment->length;
    if ( c_x < totalLength )
        if (x < totalLength)
      break;
            break;
    ++_entry;
        ++segment;
    if ( _entry >= _entryEnd )
        if (segment >= segmentEnd)
      return result;
            return -1;
  }
    }
  return _entry->value;
    return segment->value;
}
}
</syntaxhighlight>
</syntaxhighlight>
</div>
</div>
A cleaner version of this algorithm is given below:
<syntaxhighlight lang="c++">
unsigned int eco::getCurrentAreaNum(float posX, float posZ, Ecosystem* unused, EcoMapInfo* info)
{
  posX = std::clamp(posX, -5000.0, 4999.0);
  posZ = std::clamp(posZ, -4000.0, 4000.0);
  float epsilon1 = (posX + 5000.0 < 0.0) ? -0.5 : 0.5;
  float epsilon2 = (posZ + 4000.0 < 0.0) ? -0.5 : 0.5;
  int x =  posX + 5000.0 + epsilon1;
  int z = (posZ + 4000.0 + epsilon2) / info->header->divisor;
  uint row = std::clamp(z, 0, info->header->numRows - 2);
  if (info->header->divisor == 10)
    x = x / 10 + ((0x66666667LL * x) >> 0x3F);
  uint* offsets = &info->rowOffsets[row];
  if ( offsets[0] >= offsets[1] )
    return 0xFFFFFFFF;


  Segment* segment = reinterpret_cast<Segment*>((char *)info->rows + 2 * offsets[0]);
Source: https://github.com/zeldaret/botw/blob/022f029db1ef03d900fb54bad0807939c9695720/src/KingSystem/Ecosystem/ecoSystem.cpp#L100
  Segment* segmentEnd = reinterpret_cast<Segment*>((char *)info->rows + 2 * offsets[1]);
  uint totalLength = 0;
  while (true)
  {
    totalLength += segment->length;
    if (x < totalLength)
      return segment->value;
    ++segment;
    if (segment >= segmentEnd)
      return 0xFFFFFFFF;
  }
}
</syntaxhighlight>


== Usage in ''Breath of the Wild'' ==
== Usage in ''Breath of the Wild'' ==

Latest revision as of 01:22, 24 November 2021

beco is a file format that is used for storing per-coordinate data.

Structure

beco files are little endian on Switch and big endian on Wii U.

Header

Offset Type Description
0x0 u32 Magic (0x00112233)
0x4 u32 Number of rows
0x8 u32 Divisor
0xc u32 Padding

Offsets

Offset Type Description
0x0 u32[num_rows] Offsets to row data, divided by 2 and relative to the start of the row section

Rows

Segment

Offset Type Description
0x0 u16 Custom data
0x2 u16 Length (X axis)

This structure is repeated until the entire row has been covered by segments. The sum of all segment lengths is equal to the length of the map on the X axis.

Operations

Getting data for a given coordinate

The algorithm that returns the custom data that is associated with a coordinate is very simple. It consists of determining the correct row index in the table, then iterating over segments in that row and returning the segment data when the X coordinate is within its bounds.

s32 Ecosystem::getMapArea(const EcoMapInfo& info, f32 posX, f32 posZ) const {
    posX = sead::Mathf::clamp(posX, -5000.0f, 4999.0f);
    posZ = sead::Mathf::clamp(posZ, -4000.0f, 4000.0f);

    const auto epsilon = [](float n) { return n >= 0.0f ? 0.5f : -0.5f; };

    s32 x = s32(posX + 5000.0f + epsilon(posX + 5000.0f));
    s32 z = s32(posZ + 4000.0f + epsilon(posZ + 4000.0f)) / info.mHeader->divisor;
    s32 row = sead::Mathi::clamp(z, 0, info.mHeader->num_rows - 2);

    if (info.mHeader->divisor == 10)
        x /= 10;

    if (info.mRowOffsets[row] >= info.mRowOffsets[row + 1])
        return -1;

    auto* segmentEnd = reinterpret_cast<const Segment*>(info.mRows + 2 * info.mRowOffsets[row + 1]);
    auto* segment = reinterpret_cast<const Segment*>(info.mRows + 2 * info.mRowOffsets[row]);
    s32 totalLength = 0;
    while (true) {
        totalLength += segment->length;
        if (x < totalLength)
            break;
        ++segment;
        if (segment >= segmentEnd)
            return -1;
    }
    return segment->value;
}

Source: https://github.com/zeldaret/botw/blob/022f029db1ef03d900fb54bad0807939c9695720/src/KingSystem/Ecosystem/ecoSystem.cpp#L100

Usage in Breath of the Wild

beco files are used in Breath of the Wild to map coordinates to arbitrary u16 data. Three beco files are used for different purposes: FieldMapArea.beco, MapTower.beco and LoadBalancer.beco.