Степени двойки

Материал из Posmotre.li
Перейти к: навигация, поиск
TVTropes.pngTV Tropes
Для англоязычных и желающих ещё глубже ознакомиться с темой в проекте TV Tropes есть статья Powers Of Two Minus One. Вы также можете помочь нашему проекту и перенести ценную информацию оттуда в эту статью.
Склифосовский.pngВкратце
От 0 до 255. Или от −128 до 127.
« Чем отличается начинающий программист от законченного? Начинающий думает, что в килобайте 1000 байт[1], законченный — что в километре 1024 метра »
— Народное творчество
« В мире есть два вида чисел: ноль, и те, которые приводят к ошибке переполнения »
— Автор неизвестен

Компьютеры работают с числами. Причём в подавляющем большинстве случаев число разрядов в этих числах ограничено[2]. Что будет, если место есть под три цифры, а нам надо записать число 9 999? Правильно, одна девятка куда-то потеряется и получится 999. Что будет, если мы к этому 999 прибавим единичку? Получится 1000, но первая цифра опять куда-то потеряется и 1000 превратится в 000. Это собственно суть арифметического переполнения и есть. Для геймера это означает, что невероятно раскачанный персонаж с 999 пунктами здоровья внезапно помрёт, получив еще один пунктик здоровья сверху (999+1=0).

Вернемся теперь к заглавной теме. В отличие от людей, компьютер работает в двоичной системе счисления. То есть знает только две цифры — ноль и единицу. Попытки сделать десятичные[3] или троичные компьютеры предпринимались, но как-то не прижилось. Поэтому описанное в абзаце выше переполнение происходит не когда число достигает степени десятки, а когда оно достигает степени двойки. И вместо 999+1=0 выходит 255+1=0. Пока все понятно и далекому от компьютеров человеку. Однако давайте подумаем, что будет, если теперь вычесть из нуля единицу? Говорите, будет −1? Нет, компьютер у нас знает ноль, знает единицу, а этот ваш минус не знает. Поэтому мы договоримся, что если первая двоичная цифра — ноль, значит число положительное (0 001 = 1). А если единица — отрицательное (1 001 = −1)[4]. Тут жадные программисты и говорят: не хотим мы целый разряд под знак тратить, дайте нам беззнаковые числа. Окей, дают им беззнаковые числа. Но теперь при вычитании из нуля единицы опять фигня получается — ноль превращается в 255! Ну или еще какое-то значение 2n−1. Тут внимательный читатель может возразить: постойте, постойте, даже калькулятор в подобных ситуациях просто выдаст ошибку. Правильно, процессор тоже в таких ситуациях вывешивает флажок (даже два) «ребят, тут фигня какая-то вышла». Но так уж повелось, что в целях повышения быстродействия никто на этот флажок не смотрит.

Стоит отметить, что всё вышесказанное актуально в основном для старых игр. Компьютеры тогда были 8–16-разрядными (с пониманием чисел больше 65535 проблемы), памяти мало (мегабайт оперативки — это круто, да и зачем — «640 килобайт хватит всем»), а у программистов было модно экономить на всем (да зачем тратить на число целых два байта? И одного хватит). Теперь компьютеры стали 64-битовыми (числа переполняются в районе 9 223 372 036 854 775 807), памяти — гигабайты, так что вышеописанные проблемы отошли в прошлое.

Другая проблема связана с представлением дробей. Мы привыкли использовать для всего десятичные дроби, однако компьютеру привычнее работать с двоичными числами. Только двоичным числом представить банальное 0,1 не получится, поэтому приходится округлять. Глюки с подобными числами обычно проявляются в том, что значение, двигаясь попеременно то в одну, то в другую сторону не может достигнуть нуля, хотя и должно по всем законам математики.

Что и на каких значениях переполняется[править]

Тип Диапазон Примечание
Целое 1 байт от 0 до 255 Обычно жизнь, количество предметов если их мало, встречается в старых играх, бывает если исчисляется что-то небольшое
Целое 2 байта от 0 до 65535 Обычно жизнь, количество предметов, ресурсы, бывает в старых играх (не не настолько старых, как предыдущий пункт), или если программист решил с большими значениями не заморачиваться
Целое 3 байта от 0 до 16777215 Используются в играх под эмуляторами Sony Playstation, Super Nintendo и др.
Целое 4 байта от 0 до 4294967295 Обычно деньги
Целое 8 байт от 0 до 18446744073709551616 Деньги если они измеряются миллиардами
С точкой 4 байта от 1,5 × 10^(−45) до 3,4 × 10 ^ 38 Используются в некоторых играх, особенно компании Microsoft
С точкой 6 байта от 2,9 × 10^(−39) до 1,7 × 10^38 Используется в DOS играх, сделанных на Turbo Pascal
С точкой 8 байта от 5.0 × 10^(-324) до 1.7 × 10^308 Используется в играх Macromedia Flash
С точкой 10 байта от 3.4 × 10^(-4951) до 1.1 × 10^4932 Используется в основном в математических программах

Примеры[править]

Как ограничение[править]

  • Традиционная плитка — 16×16 пикселей.
  • WarCraft II, StarCraft — ограничение на ману в 255 единиц.
    • В StarCraft обработано: энергии (космооперной маны) может быть либо 200 (без апгрейда), либо 250 (с апгрейдом и у героев), либо 180 (у брудлингов, которые теряют 1 единицу в секунду и живут 3 минуты с обоснованием, что без энергии жить не могут).
    • В эпичном редакторе карт Warcraft II на лимите в 255 завязано практически все: 25500 — максимум НР любого юнита, 2550 — максимум его цены (в каждом ресурсе), 255 — максимум его маны, защиты, базового и проникающего урона.
      • Вот только максимум разведки все-таки 9, максимум дальнобойности 15, а некоторые апгрейды стоят 3000.
      • Также в Wacraft II на карте одновременно не могло существовать более 255 юнитов любого типа (считая строения и считая юниты всех игроков, включая нейтральные объекты) — при попытке создать больше игра выдавала «Cannot create more units».
  • В играх серии Heroes of Might and Magic у одного игрока не может быть больше 8 героев.
    • Точнее, героев может быть сколько угодно, не может быть больше восьми армий в поле. По городским гарнизонам, а в четвёртой части и в охране шахт, можно иметь сколько угодно героев.
    • В четвёртой части также существует предел юнитов в 1 отряде — 32767.
  • The Elder Scrolls IV: Oblivion — ограничение на уровень характеристики или навыка в 255 единиц. Лучше всего заметно на скорости бега и высоте прыжка. Впрочем, эти значения не получить без читов.
  • В различных цветовых моделях значения каналов от 0 до 255.
  • Размеры текстур: 256×256, 512×512, 1024×1024 и т. д. Многие игры позволяют расширить текстуру вдвое или вчетверо (на этом основаны HD Pack’и старых игр). Но сделать её, например, 1000×1000 не даст уже видеоплата новые расширения команд графического процессора (уже несколько лет как) позволяют подобное сделать, однако, делать так всё же не стоит — хоть видеокарты и поддерживают текстуры, не являющиеся степенями двойки, на практике такие текстуры заметно тормозят. Потому такие картинки популярны в демках «вау! посмотри, как мы можем!», но практически не встречаются в реальных играх.
    • в готовой игровой текстуре, в которую добавлены Mip-уровни, намеренно вводится дополнительный пиксель на стороне, в сторону которой упакованы мипы. Т. е. разрешение бывает, скажем, 4097х1024. Так надо.
  • Mount & Blade — В Истории Героя в отряд персонажа могло входить только 32 вида юнитов, что обламывало любителей модов, которые хотели собрать легион из бессмертных NPC.
  • Вселенная X — от центра сектора можно отлететь максимум на 4294,967295 км, далее происходит переполнение, и расстояние меняет знак. Пролетев дальше, корабль возвращается в исходную точку.
  • Civilization III — число цивилизаций было ограничено числом 31 (32-е место занимали варвары, за которых нельзя играть). Это аукнулось не только мододелам, но и самим разработчикам, когда во втором аддоне (Conquests) число играбельных цивилизаций довели до 32, но для одной просто не хватило места. «Хотите играть за Австрию? Диалоги, записи в энциклопедии и анимацию лидера мы вам добавили, а дальше вы уж как-нибудь сами — в файле сценария удалите любую цивилизацию, добавьте вместо неё Австрию, вручную пропишите ей города, лидеров и установите ссылки у юнитов и построек» — ответили разработчики.
    • До кучи число городов на карте было ограничено 255 (проблема для мододелов, решивших воссоздать политическую карту 20 века на «огромной» карте), но при таком количестве городов обсчёт всех автоматических действий на каждом ходу всё равно занимал столько времени, что доводить до такого мало кому хотелось.
    • Такое же ограничение существует в Rome Medieval II: Total War (31 фракция + неиграбельные мятежники). Побороть его разработчики смогли лишь в 2021 году.
  • Touhou Project — в ранних частях максимально возможным значением Power было 128. При этом, числом оно обозначалось только до 127, а потом просто писалось MAX.

Как ошибка[править]

  • Duck Hunt — при прохождении 99 уровней, начинается нулевой. На этом уровне, вы обязательно проиграете — утки начинают летать по глючной траектории, а собака будет рандомно высовываться и смеяться, даже не спугивая уток.
  • Старая добрая Heroes of Might & Magic III. При получении 75 УР система опыта игры начинает вести себя неадекватно: герою сразу присваивается 88 УР, и начиная с этого момента качаться выше становится не просто глупо, но и опасно. При дальнейшем повышении опыта у героя, его значение превращается в отрицательное количество и УР станет нулевым, либо машина зацикливается и предлагает герою в принципе бесконечную возможность повышения уровня. В первом случае герой фактически теряет прокаченного героя, получая взамен героя с 0 УР, во втором — само продолжение игры становится невозможным из-за «застревания» на бесконечно открывающихся окнах достижения нового уровня.
  • X-COM: UFO Defense — как только сила или запас ходов солдата превысит 255, он становится немощным. В более поздних версиях на то и другое поставили предел 80.
  • Civilization — сумасшедший Ганди. Городская легенда гласит, что уровень агрессивности в игре определялся однобайтовой неотрицательной переменной, у самых агрессивных правителей она была равна 10, у Ганди — единице. Открытие демократии снижало агрессивность на два, в результате чего у Ганди получался «минус один», вместо какового в данном случае присваивалось максимально возможное значение переменной, то есть 255. Это превращало данного пацифиста в кровожадного маньяка с мотивацией «Что бы такого сделать плохого», от отзыва договоров до тотальной ядерной войны, причем — все сразу в один ход, или около того.
    • Это именно городская легенда. В «Цивилизации-1» были три уровня воинственности, а поскольку Ганди развивал науку, он часто первым разрабатывал бомбу и на переговорах заявлял: «Наши требования подкреплены ядерным оружием».
  • Pirates! — одна из самых первых культовых игр была, тем не менее, чрезвычайно глючной именно из-за неотслеживаемых переполнений.
  • Hearthstone — если атака или здоровье существа превысит 2 147 483 648 (то есть 2 в степени 31), то существо умрет.
    • В одном из дополнений это использовали как фичу.
    • Существует основанное на синергии Пробойника из Растахановых игрищ, Земляной чешуи из Экспедиции в Ун’Горо и Пчёл из Спасителей Ульдума комбо, позволяющее Друиду получить 2560 единиц брони, основанное на удвоении атаки через урон «ниже нуля». В 2020 комбо исчезло из Стандарта.
  • Panzer General первых версий: в режиме игры по переписке один из противников мог оказаться с отрицательным значением престижа… Не-а, его престиж оказывался больше 65500!
  • Дальнобойщики: в одном из мест карты можно разогнаться и перемахнуть через ограждающие карту горы. Тогда машина будет падать в ничто, пока ее координата по оси Z не достигнет минимального значения. После этого она перенесется на небо и начнет падать оттуда.
  • «Star Wars: Knights of the Old Republic II: The Sith Lords» — Ханхарру можно повысить силу за счет интеллекта. Раз за разом. В определенный момент интеллект падает ниже нуля… до 255-ти.
  • Pac-Man — разработчики первой версии аркады не предусмотрели какого-то конца игры, предполагая, что возрастающая сложность не даст игрокам продвинуться слишком далеко. Но некоторые игроки всё-таки смогли пройти 255 уровней… и на 256-м игра начинала некорректно отрисовывать лабиринт (подробное описание см. в википедии).
  • В Fallout 4 отсутствует ограничение на получение уровня, однако игра не может переварить значения уровня выше 65535, и вылетает.
  • Total War Attila — таким образом можно было обнулить себе казну. А в Warhammer пытались поломать значение отрицательного дохода, но игра перестала адекватно считать содержание армий раньше.
  • Total War Medieval 2 — иногда на трон всходят безумцы и/или параноики, находящиеся не в ладах с реальностью. Такие персонажи имеют из-за своих свойств −1 или −2 к влиятельности (основной параметр, характеризующий персонажа как короля). Если они также не обладают никакими примечательными чертами (дающими уже «плюс» к влиятельности), то получается… влиятельность 10 (максимальное значение!). «Подданные боготворят этого правителя». Курьёз по-своему историчен, потому что в реальности тоже случалось, что сумасшедшие визионеры обретали прочную любовь подданых — разумеется, не тех, кто с ними сталкивался лично. А самое забавное, что стоит такому правителю немного «исправиться» — получить какой-нибудь бафф +1 к влиятельности — и всё сразу же возвращается на круги своя: «подданные смеются», «его никто не уважает» и т. п.

Как багофича[править]

  • Pokemon — начиная с первого поколения, где покемонов было всего 151, а слотов для их размещения, соответственно, немного больше (256—151=105 «лишних» слотов). В итоге неиспользуемые были просто забиты MissingNo. и прочей забагованной ерундой, которая, однако, многим игрокам сама по себе пришлась по нраву. Так и повелось с тех пор.
    • На принципе переполнения также завязаны многие хакерские приёмчики вроде «Berry glitch», при помощи которых можно копировать вещи, превращать одних покемонов в других и так далее.

Отрицательные значения[править]

Как было замечено, сейчас проблемы с памятью компьютеров исчезли, и восприятие отрицательных чисел пришло в норму. Но это породило другой математический глюк, достаточно редкий и очень забавный, а зачастую полезный. Суть в том, что от пробивания значением потолка или дна образуется не максимально, а минимально противоположный результат, он тем больше, чем сильнее пробитие: допустим, у нас атака наносит урон в 10 единиц. Но вот на её обладателя повесили пачку дебаффов урона суммарной силой 11. При использовании такой атаки игра вычитает из десяти одиннадцать, а потом получившееся значение вычитает из здоровья цели. И если программист что-то не досмотрел и не сделал ограничения и проверки, оно оказывается отрицательным. В результате игра, повинуясь написанной формуле и законам математики, вычитает из вражеского хп −1, и урон превращается в лечение.

Примеры[править]

  • S.T.A.L.K.E.R., самый первый — если набрать редких артефактов на 30 % сопротивления одному типу аномалий так, что оно перевалит за сотню, нахождение в этой аномалии начнёт вас лечить и чинить снаряжение. Пофикшено.
  • Дилогия Divinity: Original Sin — аналогично: если сопротивление у кого-то больше 100 %, то данное воздействие начинает его лечить. Это уже фича, а не баг.
  • DotA 2 — тот самый случай с уроном. Достигается сложно и, скорее всего, пофикшен.
  • Адский эксплойт в ранних версиях Silent Storm: прокачкой рукопашного боя затраты очков действия на него уменьшаются до нуля, а потом удары начинают давать очки действия, позволяя зачистить карту без передачи хода противнику. Причём бить можно было вообще всё подряд.
  • Warframe — сабж заботливо обыгран, и крит шанс при желании разгоняется за 300 %, а урон многократно критических попаданий рассчитывается по специальной формуле. Но вот появились моды разлома, которые могут давать бонусы и штрафы практически к любому параметру. В том числе и множителю критического урона, который может от этого опускаться ниже единицы, и таким образом урон от крита становится меньше обычного.
  • Minecraft — как фича. У блоков есть прочность, которая уменьшается в процессе разбивания, и блок ломается по достижении нуля. А у коренной породы, ограничивающей мир снизу, значение отрицательное, что для игры является сигналом к игнорированию любого урона блоку. В ранних версиях можно было сначала вывести прочность блоков коренной породы сначала в положительную сторону переполнением, а потом и снести эту положительную часть, уничтожив блок, но на это требовалось очень много динамита, возможно пофикшено.
  • StarCraft 2 — долгое время был следующий баг: если бронебойной ракетой «Воронов» загнать броню юнитов в минус, то иллюзии, порождаемые часовыми протоссов, начинали наносить 0-(-значение брони) урона. Очевидно, что в игре 1x1 эксплуатировать его невозможно, а вот в командных играх — вполне.

Примечания[править]

  1. В 1998 году придумали двоичные приставки (кибибайт), которые из-за неблагозвучности приживаются плохо.
  2. Бывает еще «длинная арифметика», но она тормозная. Поэтому вы вряд ли встретите ее за пределами математических программ, которым вот кровь из носа, а нужно пересчитать все атомы во Вселенной.
  3. Первые компьютеры как раз чаще были десятичными — потому что иначе либо требовался отдельный блок преобразования двоичных чисел в десятичные и обратно, либо нужно было учить операторов оперировать восмеричными или шестнадцатеричными числами, что было бы потенциальным источником ошибок. Но десятичная логика была чересчур сложной и вскоре от неё отказались, однако ещё какое-то время на мини-компьютерах, наподобие советского МИР-а, применялась двоично-десятичная система — когда число разбивается на десятичные цифры и каждая представляется в двоичном коде. Более того, несколько команд для работы с такими числами сохраняются непонятно для чего и в современных процессорах
  4. Обычно используется более хитрый «дополнительный код», но суть примерно та же, так что замнем для ясности.