Submission #8566: Bolu & mtbRc's DS Castlevania: Dawn of Sorrow "Soma mode, beat Soma" in 07:15.58

-- Address view for memory writing with zipping
-- Open the memory viewer to see what's actually going on.

if not emu then
  error("This script runs under DeSmuME.")
end

if not bit then
  require("bit")
end

function cvdosPosToMapFlag(x, y)
  x, y = x % 256, y % 256

  local xl, xh = x % 16, math.floor(x / 16) % 16
  local i = (y * 16) + (xh * 46 * 16) + xl
  local pos = 0x20F6E34 + math.floor(i / 8)
  local mask = math.pow(2, math.floor(i % 8))
  return pos, mask
end

gui.register(function()
  local x = memory.readbyte(0x0210F018)
  local y = memory.readbyte(0x0210F014)
  local i = (y * 16) + x
  local pos, mask = cvdosPosToMapFlag(x, y)
  agg.text(140, 5, string.format("%08X:%02x", pos, mask))
  agg.text(140, 24, string.format("[%04X-%04X]", cvdosPosToMapFlag(x - (x % 0x10), 0) % 0x10000, cvdosPosToMapFlag(bit.bor(x, 0x0f), 255) % 0x10000))
  agg.text(140, 43, string.format("[%04X-%04X]", cvdosPosToMapFlag(x - (x % 0x10) + 0x10, 0) % 0x10000, cvdosPosToMapFlag(bit.bor(x, 0x0f) + 0x10, 255) % 0x10000))
  agg.text(140, 62, string.format("(%03d/%X,%03d)", x, x % 16, y))
end)

'''
gocha's cvdosPosToMapFlag Lua function translated to Python.
'''
def posToMapFlag(x: int, y: int) -> tuple[int, int]:
  x, y = x % 256, y % 256

  xl, xh = x % 16, x // 16 % 16
  i = y * 16 + xh * 46 * 16 + xl
  pos = 0x20F6E34 + i // 8
  mask = 1 << i % 8
  return pos, mask

'''
Function that performs the opposite operation to posToMapFlag().

[in]  addr: CV DoS memory address to corrupt.
[in]  mask: bits that produce the desired corruption.
            E.g., 0x7 means that bits 0x1, 0x2 OR 0x4 produce the desired corruption.
[out] list containing all (X, Y) square coordinate pairs that cause the desired corruption.
'''
def mapFlagToPos(addr: int, mask: int) -> list[tuple[int, int]]:
  pos_list = []

  valid_masks = []
  i = 0
  while mask > 0:
    if mask & 1 == 1:
      valid_masks.append(i)
    mask >>= 1
    i += 1

  for maskbit in valid_masks:
    i = (addr - 0x20F6E34) * 8 + maskbit
    xl = i % 16
    for y in range(256):
      for xh in range(16):
        if y * 16 + xh * 46 * 16 + xl == i:
            pos_list.append((xh * 16 + xl, y))

  pos_list.sort()

  return pos_list

'''
Returns whether a X square coordinate is free/stable (True) or transient (False).

[in]  x: The X square coordinate.
[out] Boolean representing if the provided X square coordinate is free.
'''
def free_x(x: int) -> bool:
  rem = x % 10
  return rem == 2 or rem == 4 or rem == 7 or rem == 9

'''
Computes the distance travelled when moving from one point in such a way that passes through a second point.
It also computes the final position of the movement that begins at the first point and passes through the second point.
The final position might not be the second point, if the second point is not free/stable.
Thus, the returned distance might be greater than the distance between the two points, if the second point is not free/stable.
This function assumes Soma is zipping in the usual Lost Village zipping spot.

[in]  p1: point (X, Y) from which the movement begins. Must be free.
[in]  p2: point (X, Y) to pass through.
[out] The distance, measured in estimated frames, travelled on the movement that begins at p1 and passes through p2 optimally.
[out] The end position of the movement, which will not be p2 if p2 is not free.

NOTE: The returned values are estimates, and should always be checked in-game.
Sometimes the game does not work as expected and modeled here.
'''
def distance(p1: tuple[int, int], p2: tuple[int, int]) -> tuple[int, tuple[int, int]]:
  x1, y1 = p1
  x2, y2 = p2

  cost = 0
  # It is called "cost" instead of "distance" because it is measured in frames.
  # I.e., it is the minimum amount of frames required to move from p1 to p2 and finish the movement.

  # Cannot go to the left:
  if x2 < x1:
    return 0x7fff, (0, 0)

  # Check that x1 is free:
  if not free_x(x1):
    print(f"WARNING: origin point {p1} is not free.")

  # Compute the real end position after movement that passes through p2:
  if not free_x(x2):
    rem = x2 % 10
    if rem == 0 or rem == 5:
      x2 += 2 # Soma will travel this many X coordinates more
      y2 -= (32 + 8) // 3
      # In the time it takes to reach the next free X coordinate and be able to move,
      # Y will be decreased so many times.
    elif rem == 1 or rem == 6:
      x2 += 1 # Soma will travel this many X coordinates more
      y2 -= (16 + 8) // 3
      # In the time it takes to reach the next free X coordinate and be able to move,
      # Y will be decreased so many times.
    elif rem == 3 or rem == 8:
      x2 += 1 # Soma will travel this many X coordinates more
      y2 -= (16 + 16) // 3
      # In the time it takes to reach the next free X coordinate and be able to move,
      # Y will be decreased so many times.
  # All the values used in this previous if-block have been deduced empirically.

  # Calculate how many frames it takes to move on the X coordinate:
  while x1 != x2:
    rem = x1 % 10
    if rem == 4 or rem == 9:
      x1 += 3
    else:
      x1 += 2
    cost += 41

  # Adjust the Y coordinate:
  # Compute how it has changed during the movement on the X axis.
  y1 -= (cost // 3)

  # Adjust the Y coordinate so that the destination coordinate is below the current coodinate:
  while y2 > y1:
    y1 += 256

  # Calculate how many frames it takes to move to the desired Y coordinate:
  cost += (y1 - y2) * 3

  return cost, (x2, y2)

'''
Computes the distance between two points (square coordinate pairs) in controlled oob.
As Soma's speed in X and Y are independent of each other, the total distance
is equal to the maximum of the independent X and Y distances.
This function also measures distances in frames.

[in]  p1: One of the points.
[in]  p2: The other points.
[out] The distance between the points, in frames.
'''
def controlled_oob_distance(p1: tuple[int, int], p2: tuple[int, int]) -> int:
  x1, y1 = p1
  x2, y2 = p2

  # Account for the possibility of over/underflowing the coordinates:
  dx = min(abs(x2 - x1), abs(x2 - x1 - 256))
  dy = min(abs(y2 - y1), abs(x2 - x1 - 256))

  # Traversing one X square coordinate takes 53 frames with Black Panther.
  # Falling through one Y square coordinate takes 49 frames.
  return max(dx * 53, dy * 49)

-- Address view for memory writing with zipping
-- Open the memory viewer to see what's actually going on.

if not emu then
  error("This script runs under BizHawk.")
end

function cvdosPosToMapFlag(x, y)
  x, y = x % 256, y % 256

  local xl, xh = x % 16, math.floor(x / 16) % 16
  local i = (y * 16) + (xh * 46 * 16) + xl
  local pos = 0x20F6E34 + math.floor(i / 8)
  local mask = 1 << math.floor(i % 8)
  return pos, mask
end

while true do
  local x = memory.read_u8(0x0210F018)
  local y = memory.read_u8(0x0210F014)
  local i = (y * 16) + x
  local pos, mask = cvdosPosToMapFlag(x, y)
  gui.drawText(140, 5, string.format("%08X:%02x", pos, mask))
  gui.drawText(140, 24, string.format("[%04X-%04X]", cvdosPosToMapFlag(x - (x % 0x10), 0) % 0x10000, cvdosPosToMapFlag(x | 0x0f, 255) % 0x10000))
  gui.drawText(140, 43, string.format("[%04X-%04X]", cvdosPosToMapFlag(x - (x % 0x10) + 0x10, 0) % 0x10000, cvdosPosToMapFlag(x | 0x0f + 0x10, 255) % 0x10000))
  gui.drawText(140, 62, string.format("(%03d/%X,%03d)", x, x % 16, y))
  emu.frameadvance()
end

-- Castlevania: Dawn of Sorrow - RNG simulator
-- This script runs on BizHawk

if not bit then
  require("bit")
end

-- pure 32-bit multiplier
function mul32(a, b)
  -- separate the value into two 8-bit values to prevent type casting
  local x, y, z = {}, {}, {}
  x[1] = a & 0xff
  x[2] = (a >> 8) & 0xff
  x[3] = (a >> 16) & 0xff
  x[4] = (a >> 24) & 0xff
  y[1] = b & 0xff
  y[2] = (b >> 8) & 0xff
  y[3] = (b >> 16) & 0xff
  y[4] = (b >> 24) & 0xff
  -- calculate for each bytes
  local v, c
  v = x[1] * y[1]
  z[1], c = (v & 0xff), (v >> 8)
  v = c + x[2] * y[1] + x[1] * y[2]
  z[2], c = (v & 0xff), (v >> 8)
  v = c + x[3] * y[1] + x[2] * y[2] + x[1] * y[3]
  z[3], c = (v & 0xff), (v >> 8)
  v = c + x[4] * y[1] + x[3] * y[2] + x[2] * y[3] + x[1] * y[4]
  z[4], c = (v & 0xff), (v >> 8)
  v = c + x[4] * y[2] + x[3] * y[3] + x[2] * y[4]
  z[5], c = (v & 0xff), (v >> 8)
  v = c + x[4] * y[3] + x[3] * y[4]
  z[6], c = (v & 0xff), (v >> 8)
  v = c + x[4] * y[4]
  z[7], z[8] = (v & 0xff), (v >> 8)
  -- compose them and return it
  return (z[1] | (z[2] << 8) | (z[3] << 16) | (z[4] << 24)),
         (z[5] | (z[6] << 8) | (z[7] << 16) | (z[8] << 24))
end

--[ DoS RNG simulator ] --------------------------------------------------------

local DoS_RN = 0

function DoS_Random()
  DoS_RN = (mul32(bit.arshift(DoS_RN, 8), 0x3243f6ad) + 0x1b0cb175) & 0xffffffff
  return DoS_RN
end

function DoS_RandomSeed(seed)
  DoS_RN = seed
end

function DoS_RandomLast()
  return DoS_RN
end

--------------------------------------------------------------------------------
if not emu then
  error("This script runs under BizHawk.")
end

local RNG_NumAdvanced = -1
local RAM = { RNG = 0x020c07e4 }
local RNG_Previous = memory.read_u32_le(RAM.RNG)

while true do
  local searchMax = 300

  RNG_NumAdvanced = -1
  DoS_RandomSeed(RNG_Previous)
  for i = 0, searchMax do
    if DoS_RandomLast() == memory.read_u32_le(RAM.RNG) then
      RNG_NumAdvanced = i
      break
    end
    DoS_Random()
  end
  RNG_Previous = memory.read_u32_le(RAM.RNG)

  DoS_RandomSeed(memory.read_u32_le(RAM.RNG))
  rng = DoS_Random()
  prev_rng = RNG_Previous
  gui.drawText(116, 5, string.format("NEXT: %08X", rng))
  gui.drawText(116, 21, "ADVANCED: " .. ((RNG_NumAdvanced == -1) and "???" or tostring(RNG_NumAdvanced)))

  emu.frameadvance()
end