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

TV Tropes Для англоязычных и желающих ещё глубже ознакомиться с темой в проекте TV Tropes есть статья Powers Of Two Minus One. Вы также можете помочь нашему проекту и перенести ценную информацию оттуда в эту статью.

Короче, Склихосовский! От 0 до 255. Или от −128 до 127.

«	Чем отличается начинающий программист от законченного? Начинающий думает, что в килобайте 1000 байт, законченный — что в километре 1024 метра	»
— Народное творчество

«	В мире есть два вида чисел: ноль, и те, которые приводят к ошибке переполнения	»

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

Вернемся теперь к заглавной теме. В отличие от людей, компьютер работает в двоичной системе счисления. То есть знает только две цифры — ноль и единицу. Попытки сделать десятичные или троичные компьютеры предпринимались, но как-то не прижилось. Поэтому описанное в абзаце выше переполнение происходит не когда число достигает степени десятки, а когда оно достигает степени двойки. И вместо 999+1=0 выходит 255+1=0. Пока все понятно и далекому от компьютеров человеку. Однако давайте подумаем, что будет, если теперь вычесть из нуля единицу? Говорите, будет −1? Нет, компьютер у нас знает ноль, знает единицу, а этот ваш минус не знает. Поэтому мы договоримся, что если первая двоичная цифра — ноль, значит число положительное (0 001 = 1). А если единица — отрицательное (1 001 = −1). Тут жадные программисты и говорят: не хотим мы целый разряд под знак тратить, дайте нам беззнаковые числа. Окей, дают им беззнаковые числа. Но теперь при вычитании из нуля единицы опять фигня получается — ноль превращается в 255! Ну или еще какое-то значение 2ⁿ−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.
    • Ха, в четвертой! Вот тут пишут про вторую - http://faqs.org.ru/games/strat/hmm26.htm

Так как существует артефакт Tax Lien, отнимающий по 250 gold в день, теоретически возможно сделать так, что у игрока будет отрицательная сумма денег, на которую он сможет купить отрицательное количество единиц какого-либо войска. Дерутся отрицательные войска плохо (погибают при любом повреждении), зато при покупке отрицательного количества число единиц войска, обитающих в данном строении, увеличивается; при попытке разделить -N единиц войска единственная возможность - поделить на 1 и -(N+1), таким образом можно "наотщипывать" сколь угодно большое войско; отрицательное войско может быть проапгрейжено за отрицательные деньги, то есть с приплатой игроку.

• 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 века на «огромной» карте), но при таком количестве городов обсчёт всех автоматических действий на каждом ходу всё равно занимал столько времени, что доводить до такого мало кому хотелось.
  • В более старых цивах ограничение было на 255 юнитов. В CivIII юнитов уже может быть до 4096, некоторые до этого доигрывались (все дальнейшие юниты при попытке построить их просто забирают ресурсы в никуда, на чем основана одна из тактик борьбы с ИИ на особо высокой сложности).
  • Такое же ограничение существует в Rome Medieval II: Total War (31 фракция + неиграбельные мятежники). Побороть его разработчики смогли лишь в 2021 году.
• Touhou Project — в ранних частях максимально возможным значением Power было 128. При этом, числом оно обозначалось только до 127, а потом просто писалось MAX.

Как ошибка

• Duck Hunt — после 99 уровней начинается нулевой. На этом уровне вы обязательно проиграете — утки начинают летать по глючной траектории, а собака будет рандомно высовываться и смеяться, даже не спугивая уток.
  • Впрочем, чисто теоретически его можно пройти, в таком случае начинается обратно 1 уровень со сбросом скорости уток до обычной. Другое дело, что это без читов крайне сложно и возможно лишь чисто теоретически — хотя в мировом рекорде по очкам игрок все-же умудрился сбить 2 утки на 0 уровне — а значит, теоретически кто-то может насобачиться и пройти его без читов.
• Старая добрая 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 к влиятельности — и всё сразу же возвращается на круги своя: «подданные смеются», «его никто не уважает» и т. п.
• В S.T.A.L.K.E.R. можно перегрузить положительную репутацию. Видимо, люди не верят, что кто-то в Зоне может быть таким добрым.
• Transport Tycoone Deluxe. Если в редакторе карты построить город, а потом быстро-быстро его сносить, иногда изменения численности обрабатываются некорректно и получаются города с населением около 65536 человек. Такой город в игре активно привлекает субсидии, но при этом не дает пассажиров на станции (потому что число пассажиров зависит не от населения города, а от домов в окрестности станции, а дома снесены).
• Анекдот о Ли Цинъюне, умершем на 256-м году жизни от переполнения счётчика.

Как багофича

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

Отрицательные значения

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

Примеры

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