Fightanimationen austauschen

[Hendrik]

So schlimm ist das gar nicht. Ein Algorithmus mit kubischer Laufzeit zum optimalen Packen ist schnell ausgedacht, und mit etwas Hirnschmalz kriegt man das auch mit quadratischer Laufzeit hin. Wobei mit einem modernen Prozessor bei diesen kleinen Bildern auch kubische Laufzeit kein Problem sein sollte.

Spoiler

Code:

# PowerPack schreibt das Bild rückwärts
for i in image.size downto 0 do
  # Suche in den bisher geschriebenen Daten das längste Muster,
  # das mit den aktuell zu schreibenden Bilddaten identisch ist
  longest_pattern_index = longest_pattern_size = 0
  for j in image.size downto i do
    k=0
    # Suche Muster an Position j
    while image[i-k] == image[j-k] do
      k+=1
    end
    # Vergleiche mit längstem bereits gefundenen Muster
    if (k > longest_pattern_size) then
      longest_pattern_index = j
      longest_pattern_size   = k
    end
  end
  # Ist das Muster zu kurz, um damit Bits zu sparen?
  if (longest_pattern_size < 3)
    # Dann füge das nächste Pixel ein
    pp_add_pixel(image[i])
  else
    # Schreibe alle einzeln eingefügten Pixel (siehe oben) auf einmal
    pp_flush_pixels()
    # Schreibe eine Referenz auf das längste gefundene Muster in die Datei.
    pp_write_pattern(longest_pattern_index, longest_pattern_size)
  end
end
# Schreibe alle einzelnen Pixel, die noch übriggeblieben sind, in die Datei.
pp_flush_pixels()

Die Arbeit steckt darin, dass PP ein bitweise arbeitet und man höllisch aufpassen muss, dass alle Offsets korrekt sind und die Bits richtig gesetzt.