K
Классная игра
Size: a a a
2020 October 03
K
И геймплей у тебя интересный
MS
Графон еще - единичками в паттернах рисуются красивые лучики!
SS
В итоге с каждым чанком ассоциирована 63-битная мапа с оверлапящимися блоками разного размера.
А почему 63битная?
MS
Потому что на самом деле это бинарное дерево!
MS
Общий алгоритм -
Определяем порядок нашего размера аллокации, из порядка получаем уровень в битмапе (которая на самом деле бинарное дерево), ходим по битам в пределах уровня пока не упремся в нолик, если уперлись - делаем ор мапы со значением в константном массиве из картинки выше.
Определяем порядок нашего размера аллокации, из порядка получаем уровень в битмапе (которая на самом деле бинарное дерево), ходим по битам в пределах уровня пока не упремся в нолик, если уперлись - делаем ор мапы со значением в константном массиве из картинки выше.
MS
Этот ор - это на самом деле функция "пометить занятыми все ячейки в дереве, являющиеся парентами или чайлдами этой ячейки"
2020 October 04
R
(я не внемлил советам Романа и решил задрочиться с иерархией)
Вообще с иерархией хорошая идея. Но как бы ее за O(1) реализовать
MS
Вообще с иерархией хорошая идея. Но как бы ее за O(1) реализовать
let level_map = map | !LEVELВроде так?
let index = level_map.trailing_ones()
*map |= ALLOCATION_BITS[index];
MS
Для мапы где нулевые биты значат „свободно“, а LEVEL значит битмапа с текущим уровнем иерархии выделенным единицами.
MS
(отредактировал код)
MS
Т.е.: делаем так, чтоб нули были только на нужном нам уровне, находим сдвиг ближайшего нуля, сетим этот индекс.
MS
Вау. Я это только что придумал, на самом деле. У меня в коде луп. Это точно будет работать?
MS
Вроде ж должно.
MS
MS
Ты говорил про О(1) по всему аллокатору.
MS
А как такое возможно, даже с не-иерархическим аллокатором?
R
Амортизированная О(1) конечно же