Русский
Русский
English
Статистика
Реклама

Algorithms

Под капотом сортировок в STL

08.10.2020 16:23:54 | Автор: admin


Стандарт С++ почти никогда не указывает, как именно должен быть реализован тот или иной std алгоритм. Дается только описание того, что на входе, что на выходе и асимптотические ограничения по времени работы и памяти. В статье я постарался прикинуть, какие математические алгоритмы и структуры данных имели ввиду авторы стандарта, указывая ограничения для той или иной сортировки и для некоторых других алгоритмов. А так же как эти алгоритмы реализованы на практике.


При написании статьи я использовал стандарт C++17. В качестве реализаций рассматривал GCC 10.1.0 (май 2020) и LLVM/Clang 10.0.0 (март 2020). В каждой и них есть своя реализация STL, а значит и std алгоритмов.


1. Однопоточные реализации


1.1. Готовые сортировки


  • std::sort(). Еще в стандарте C++98/C++03 мы видим, что сложность алгоритма примерно n*log(n) сравнений. А также есть примечание, что если важна сложность в худшем случае, то следует использовать std::stable_sort() или std::partial_sort(). Похоже, что в качестве реализации std::sort() подразумевался quicksort (в худшем случае O(n2) сравнений). Однако, начиная с C++11 мы видим, что сложность std::sort() уже O(n*log(n)) сравнений безо всяких оговорок. GCC реализует предложенную в 1997 году introsort (O(n*log(n)) сравнений, как в среднем, так и в худшем случае). Introsort сначала сортирует как quicksort, но вскоре переключается на heapsort и в самом конце сортировки, когда остаются небольшие интервалы (в случае GCC менее 16 элементов), сортирует их при помощи insertion sort. А вот LLVM реализует весьма сложный алгоритм с множеством оптимизаций в зависимости от размеров сортируемых интервалов и того, являются ли сортируемые элементы тривиально копируемыми и тривиально конструируемыми.
  • std::partial_sort(). Поиск некоторого числа элементов с минимальным значением из множества элементов и их сортировка. Во всех версиях стандарта сложность примерно n*log(m) сравнений, где n количество элементов в контейнере, а m количество минимальных элементов, которое нужно найти. Задача для heapsort. Сложность в точности совпадает с этим алгоритмом. Так и реализовано в LLVM и GCC.
  • std::stable_sort(). Тут немного сложнее. Во-первых, в отличии от предыдущих сортировок в стандарте отмечено, что она стабильная. Т.е. не меняет местами эквивалентные элементы при сортировке. Во-вторых, сложность ее в худшем случае n*(log(n))2 сравнений и n*log(n) сравнений, если есть достаточно памяти. Т.е. имеется ввиду 2 разных алгоритма стабильной сортировки. В варианте, когда памяти много подходит стандартный merge sort. Как раз ему требуется дополнительная память для работы. Сделать merge sort без дополнительной памяти за O(n*log(n)) сравнений так же возможно. Но это сложный алгоритм и не смотря на асимптотику n*log(n) сравнений константа у него велика, и в обычных условиях он будет работать не очень быстро. Поэтому обычно используется вариант merge sort без дополнительной памяти, который имеет асимптотику n*(log(n))2 сравнений. И в GCC и в LLVM реализации в целом похожи. Реализованы оба алгоритма: один работает при наличии памяти, другой когда памяти не хватает. Обе реализации, когда дело доходит до небольших интервалов, используют insertion sort. Она стабильная и не требует дополнительной памяти. Но ее сложность O (n2) сравнений, что не играет роли на маленьких интервалах.
  • std::list::sort(), std::forward_list::sort(). Все перечисленные выше сортировки требуют итераторы произвольного доступа для задания сортируемого интервала. А что если требуется отсортировать контейнер, который не обеспечивает таких итераторов? Например, std::list или std::forward_list. У этих контейнеров есть специальный метод sort(). Согласно стандарту, он должен обеспечить стабильную сортировку за примерно n*log(n) сравнений, где n число элементов контейнера. В целом вполне подходит merge sort. Ее и реализуют GCC и LLVM и для std::list::sort(), и для std::forward_list::sort(). Но зачем вообще потребовались частные реализации сортировки для списков? Почему бы для std::stable_sort() просто не ослабить итераторы до однонаправленных или хотя бы двунаправленных, чтоб этот алгоритм можно было применять и к спискам? Дело в том, что в std::stable_sort() используются оптимизации, которые требуют итераторы произвольного доступа. Например, как я писал выше, когда дело доходит до сортировки не больших интервалов в std::stable_sort() разумно переключиться на insertion sort, а эта сортировка требует итераторы произвольного доступа.
  • std::make_heap(), std::sort_heap(). Алгоритмы по работе с кучей (max heap), включая сортировку. std::sort_heap() это единственный способ сортировки, алгоритм для которого указан явно. Сортировка должна быть реализована, как heapsort. Так и реализовано в LLVM и GCC.

Сводная таблица


Алгоритм Сложность согласно стандарту C++17 Реализация в GCC Реализация в LLVM/Clang
std::sort() O(n*log(n)) introsort -
std::partial_sort() O(n*log(m)) heapsort heapsort
std::stable_sort() O(n*log(n))/O(n*(log(n))2) merge sort merge sort
std::list::sort(), std::forward_list::sort() O(n*log(n)) merge sort merge sort
std::make_heap(), std::sort_heap() O(n*log(n)) heapsort heapsort

Примечание. В качестве реализации в GCC и LLVM указан алгоритм, который используется для больших сортируемых интервалов. Для особых случаев (не большие интервалы и т.п.) часто используются оптимизации.


1.2. Составляющие алгоритмов сортировки


  • std::merge(). Слияние двух сортированных интервалов. Этот алгоритм не меняет местами эквивалентные элементы, т.е. он стабильный. Количество сравнений не более, чем сумма длин сливаемых интервалов минус 1. На базе данного алгоритма очень просто реализовать merge sort. Однако напрямую этот алгоритм не используется в std::stable_sort() ни LLVM, ни в GCC. Для шага слияния в std::stable_sort() написаны отдельные реализации.
  • std::inplace_merge(). Этот алгоритм также реализует слияние двух сортированных интервалов и он также стабильный. У него есть интерфейсные отличия от std::merge(), но кроме них есть еще одно, очень важное. По сути std::inplace_merge() это два алгоритма. Один вызывается при наличии достаточного количества дополнительной памяти. Его сложность, как и в случае std::merge(), не более чем сумма длин объединяемых интервалов минус 1. А другой, если дополнительной памяти нет и нужно сделать слияние "in place". Сложность этого "in place" алгоритма n*log(n) сравнений, где n сумма элементов в сливаемых интервалах. Все это очень напоминает std::stable_sort(), и это не спроста. Как кажется, авторы стандарта предполагали использование std::inplace_merge() или подобных алгоритмов в std::stable_sort(). Эту идею отражают реализации. В LLVM для реализации std::stable_sort() используется std::inplace_merge(), в GCC для реализаций std::stable_sort() и std::inplace_merge() используются некоторые общие методы.
  • std::partition()/std::stable_partition(). Данные алгоритмы также можно использовать для написания сортировок. Например, для quicksort или introsort. Но ни GCC ни LLVM не использует их на прямую для реализации сортировок. Используются аналогичные им, но оптимизированные, для случая конкретной сортировки, варианты реализации.

2. Многопоточные реализации


В C++17 для многих алгоритмов появилась возможность задавать политику исполнения (ExecutionPolicy). Она обычно указывается первым параметром алгоритма. Алгоритмы сортировок не стали исключением. Политику исполнения можно задать для большинства алгоритмов рассмотренных выше. В том числе и указать, что алгоритм может выполняться в несколько потоков (std::execution::par, std::execution::par_unseq). Это значит, что именно может, а не обязан. А будет вычисляться в несколько потоков или нет зависит от целевой платформы, реализации и варианта сборки компилятора. Асимптотическая сложность также остается неизменной, однако константа может оказаться меньше за счет использования многих потоков.


Тут ключевое слово может. Дело в том, что однопоточные реализации, описанные выше, подходят для соответствующих алгоритмов, какая бы политика исполнения ни была задана. И однопоточные реализации часто используются на настоящий момент не зависимо от политики исполнения. Я рассмотрел следующие версии:


  • LLVM/Clang (Apple clang version 11.0.3 (clang-1103.0.32.62)) и MacOS 10.15.4. В этом случае заголовочный файл execution не нашелся. Т.е. политику многопоточности задать не получится;
  • LLVM/Clang 10.0.0 сборка из brew. Тот же результат, что и в случае Apple clang;
  • GCC 10.1.0 файл execution есть и политику задать можно. Но какая бы политика ни была задана, использоваться будет однопоточная версия. Для вызова многопоточной версии необходимо, чтобы был подключен файл tbb/tbb.h при компиляции на платформе Intel. А для этого должна быть установлена библиотека Intel Threading Building Blocks (TBB) и пути поиска заголовочных файлов были прописаны. Установлен ли TBB проверяется при помощи специальной команды в gcc: __has_include(<tbb/tbb.h>) в файле c++config.h. И если данный файл виден, то используется многопоточная версия написанная на базе Threading Building Blocks, а если нет, то последовательная. Про TBB немного подробнее ниже.
    Дополнительную информацию о поддержке компиляторам параллельных вычислений, как впрочем и другой функциональности, можно посмотреть здесь: https://en.cppreference.com/w/cpp/compiler_support

3. Intel Threading Building Blocks


Чтоб стало возможным использовать многопоточные версии разных алгоритмов, на сегодня нужно использовать дополнительные библиотеку Threading Building Blocks, разрабатываемую Intel. Это не сложно:


  • Клонируем репозиторий Threading Building Blocks с https://github.com/oneapi-src/oneTBB
  • Из корня запускаем make и ждем несколько минут пока компилируется TBB или make all и ждем пару часов, чтоб прошли еще и тесты
  • Далее при компиляции указываем пути к includes (-I oneTBB/include) и к динамической библиотеке (у меня был такой путь -L tbb/oneTBB/build/macos_intel64_clang_cc11.0.3_os10.15.4_release -ltbb, т.к. я собирал TBB при помощи Apple clang version 11.0.3 на MacOS)

4. Эпилог


Как кажется, когда комитет C++ описывает те или иные особенности языка в стандарте, он предполагает те или иные сценарии использования и те или иные алгоритмы реализации. Часто все развивается, как предполагалось. Иногда идет своим путем. Иногда не используется вовсе. Какие бы ни были реализации тех или иных алгоритмов или структур данных сегодня, завтра это может измениться. Измениться впрочем может и стандарт. Но меняясь, стандарт почти всегда обеспечивает совместимость с ранее написанным кодом. При выпуске новых версий компиляторов, могут меняться и реализации. Но изменяясь они предполагают, что разработчики полагаются на стандарт. На мой взгляд, имеет смысл понимать, как обычно реализуются те или иные части стандартной библиотеки. Но полагаться при разработке нужно именно на ограничения заданные стандартом.


Ссылки на упомянутые алгоритмы и библиотеку:



Благодарности


Большое спасибо Ольге Serine за замечание по статье и картинку.

Подробнее..

Взламываем Ball Sort Puzzle

08.01.2021 12:15:36 | Автор: admin
Определение кружочков при помощи OpenCVОпределение кружочков при помощи OpenCV

Ball Sort Puzzle это популярная мобильная игра на IOS/Android. Суть её заключается в перестановке шариков до тех пор, пока в колбах не будут шарики одного цвета. При этом шарик можно перетаскивать либо в пустую колбу, либо на такой же шарик.

Так случилось, что я в неё залип. Очнулся примерно через месяц, на 725 уровне. Он мне никак не давался насколько бы глубоко я не пытался продумать свою стратегию. В итоге с этим вопросом я вышел в интернет, и заодно выяснил несколько интересных особенностей головоломки.

Во-первых, игра бесконечна почти бесконечна. По крайней мере уже сейчас на YouTube есть прохождения всех уровней в плоть до 5350, а в телеграмме гуляют скриншоты 10к+ уровней. Вторая особенность, и вот это уже некрасиво, не у всех уровней есть решение.

Ну это ни в какие ворота против нас играет коварный ИИ. Нужно действовать соответственно!

Под катом мы:

  • Придумаем алгоритм, решающий эту головоломку (Python)

  • Научимся парсить скриншот игры, чтобы скармливать алгоритму задачки (OpenCV)

  • Напишем телеграм бота, который будет принимать скриншоты и возвращать решения

  • Выстроим CI/CD через GitHub Actions и задеплоим бота на Яндекс.Функции

Погнали!


Алгоритмическое решение задачи

Решать такую задачу было весьма занимательно. Поэтому предлагаю заинтересованному читателю попробовать решить её самостоятельно.

Я же в первую очередь решил побить проблему на сущности. Это сделает алгоритм чуть более элегантным, а так же поможет в будущем парсить скриншоты игры:

class Color
class Color:    def __init__(self, symbol, verbose_name, emoji):        self.symbol = symbol        self.verbose_name = verbose_name        self.emoji = emoji    def __repr__(self) -> str:        return f'Color({self})'    def __str__(self) -> str:        return self.emoji
Beta-редактор хабра ломается на рендеринге emoji :poop:Beta-редактор хабра ломается на рендеринге emoji :poop:
class Ball
class Ball:    def __init__(self, color: Color):        self.color = color    def __eq__(self, other: 'Ball'):        return self.color is other.color    def __repr__(self):        return f'Ball({self.color.verbose_name})'    def __str__(self) -> str:        return str(self.color)
class Flask
class Flask:    def __init__(self, column: List[Color], num: int, max_size: int):        self.num = num        self.balls = [Ball(color) for color in column]        self.max_size = max_size    @property    def is_full(self):        return len(self.balls) == self.max_size    @property    def is_empty(self) -> bool:        return not self.balls    def pop(self) -> Ball:        return self.balls.pop(-1)    def push(self, ball: Ball):        self.balls.append(ball)    def __iter__(self):        return iter(self.balls)    def __getitem__(self, item: int) -> Ball:        return self.balls[item]    def __len__(self) -> int:        return len(self.balls)    def __str__(self) -> str:        return str(self.balls)
class Move
class Move:    def __init__(self, i, j, i_color: Color):        self.i = i        self.j = j        self.emoji = i_color.emoji    def __eq__(self, other: 'Move') -> bool:        return (self.i, self.j) == (other.i, other.j)    def __repr__(self) -> str:        return f'Ball({self})'    def __str__(self) -> str:        return f'{self.i} -> {self.j}'

Для решения будем использовать метод поиска с возвратом (Backtracking).

Решение задачи методом поиска с возвратом сводится к последовательному расширению частичного решения. Если на очередном шаге такое расширение провести не удается, то возвращаются к более короткому частичному решению и продолжают поиск дальше. Данный алгоритм позволяет найти все решения поставленной задачи, если они существуют.

В случае с нашей игрой это метод применяется так: мы рекурсивно обходим все возможные перестановки шариков (move) до тех пор, пока

  • Либо нас не выкинет наш критерий остановки решённый пазл

  • Либо в нашем хранилище состояний (states) не будет всех возможных перестановок в таком случае решения нет

    def solve(self) -> bool:        if self.is_solved:            return True        for move in self.get_possible_moves():            new_state = self.commit_move(move)            if new_state in self.states:  # Cycle!                self.rollback_move(move)                continue            self.states.add(new_state)            if self.solve():                return True            self.rollback_move(move)        return False

Алгоритм достаточно прямолинейный и далеко не всегда выдаёт оптимальное решение. Тем не менее он справляется с решением большинства задачек из игры за 1 сек.

Проверим алгоритм на чём-нибудь попроще:

def test_3x3():    data_in = [        [color.RED, color.GREEN, color.RED],        [color.GREEN, color.RED, color.GREEN],        [],    ]    puzzle = BallSortPuzzle(data_in)    result = puzzle.solve()    assert result is True    play_moves(data_in, puzzle.moves)
Алгоритм в действииАлгоритм в действии

Полная версия программы доступна на github.

Распознавание скриншотов игры

Мы будем работать с .jpg картинками двух видов

Скриншоты уровней игры Скриншоты уровней игры

Каждый чётный раунд игры состоит из 11 колб и 36 шариков, а нечётный 14 колб и 48 шариков. Чётные и нечётные раунды отличаются расположением колб, но на счастье всё остальное у них одинаковое по 4 шарика в колбе, 2 колбы пустые, цвета используются одни и те же.

Первое, что хочется сделать это обрезать рабочую область, оставив только колбы с шариками. В противном случае наша программа за шарики может принимать элементы управления, фон или рекламу. Для этого отрежем по четверти сверху и снизу изображения.

class ImageParser:    def __init__(self, file_bytes: np.ndarray, debug=False):        self.image_orig = cv2.imdecode(file_bytes, cv2.IMREAD_COLOR)        self.image_cropped = self.get_cropped_image(self.image_orig)    @staticmethod    def get_cropped_image(image):        height, width, _ = image.shape        quarter = int(height / 4)        cropped_img = image[quarter : height - quarter]        return cropped_img
Рабочая областьРабочая область

Теперь будем искать кружочки. В библиотеке OpenCV ровно для этих целей существует метод HoughCircles. Чтобы его использовать нужно перевести изображение в чёрно-белый вид, а также "эмпирически подобрать" параметры поиска. Чтобы найденные кружочки потом расфасовать по колбам, нормализуем и отсортируем их.

    @staticmethod    def normalize_circles(circles):        last_y = 0        for circle in circles:            if math.isclose(circle[1], last_y, abs_tol=3):                circle[1] = last_y            else:                last_y = circle[1]        return circles    def get_normalized_circles(self) -> List[Any]:        image_cropped_gray = cv2.cvtColor(self.image_cropped, cv2.COLOR_BGR2GRAY)        circles = cv2.HoughCircles(image_cropped_gray, cv2.HOUGH_GRADIENT, 2, 20, maxRadius=27)        if circles is None:            raise ImageParserError("No circles :shrug:")        circles = np.round(circles[0, :]).astype("int16")        ind = np.lexsort((circles[:, 0], circles[:, 1]))        circles = circles[ind]        circles = self.normalize_circles(circles)        ind = np.lexsort((circles[:, 0], circles[:, 1]))        circles = circles[ind]        return circles
Отсортированные шарики слева-направо, сверху-внизОтсортированные шарики слева-направо, сверху-вниз

Дальше будем определять цвет шарика.

Из-за того, что Telegram жмёт картинки мы не можем просто взять цвет центрального пикселя он может быть артефактом компрессии. Поэтому найдём доминирующий цвет, тот который в кружочке встречается чаще всего.

    @staticmethod    def get_dominant_color(circle) -> Color:        colors, count = np.unique(circle.reshape(-1, circle.shape[-1]), axis=0, return_counts=True)        dominant = colors[count.argmax()]        return dominant
Найденные кружочки Найденные кружочки

Этот доминирующий цвет мы будем сравнивать с изначально заданными цветами, и искать ближайший. В данной задаче нам на помощь приходит Евклидово расстояние и теорема Пифагора: если представить цвет точкой в трёхмерном пространстве, то расстояние до любой другой точки этого пространства:

d = \sqrt{(r2-r1)^2 + (b2-b1)^2 + (g2-g1)^2}

Посчитаем такое расстояние до каждого из изначально заданных цветов и найдём минимальное

RBG_TO_COLOR = {    (147, 42, 115): VIOLET,    (8, 74, 125): BROWN,    (229, 163, 85): L_BLUE,    (68, 140, 234): ORANGE,    (196, 46, 59): BLUE,    (51, 100, 18): GREEN,    (35, 43, 197): RED,    (87, 216, 241): YELLOW,    (125, 214, 97): L_GREEN,    (123, 94, 234): PINK,    (16, 150, 120): LIME,    (102, 100, 99): GRAY,}COLORS = np.array(list(RBG_TO_COLOR.keys()))def get_closest_color(color: np.ndarray) -> Color:    distances = np.sqrt(np.sum((COLORS - color) ** 2, axis=1))    index_of_smallest = np.where(distances == np.amin(distances))    smallest_distance = COLORS[index_of_smallest].flat    return RBG_TO_COLOR[tuple(smallest_distance)]  # type: ignore

Далее нам остаётся только распределить шарики по колбам. Итоговый class ImageParser доступен на github.

Преобразуем программу в Telegram Bot

Узнать про то, как сделать телеграм бота на Python можно сразу из нескольких статей на хабре. Я лишь опишу пару нюансов, с которыми столкнулся.

Так как наш бот хоститься на Яндекс.Функции триггером к его запуску будет запрос на заданный нами webhook.

Whenever there is an update for the bot, we will send an HTTPS POST request to the specified url, containing a JSON-serializedUpdate.

Если в сообщении есть массив photo, то можно увеличить вероятность распознавания шариков выбрав фотографию с максимальным весом:

if photos := message.get('photo'):    # here photos is an array with same photo of different sizes    # get one with the highest resolution    hd_photo = max(photos, key=lambda x: x['file_size'])

Чтобы скачать картинку, придётся сделать 2 запроса к Telegram API

# Получение данных о файле, нас интересует ключ ответа file_pathGET https://api.telegram.org/bot{BOT_TOKEN}/getFile?file_id={file_id}# Получение самого файлаGET https://api.telegram.org/file/bot{BOT_TOKEN}/{file_path}

В остальном же всё просто получаем картинку, скармливаем её парсеру и затем алгоритму-решателю.

main.py
def handler(event: Optional[dict], context: Optional[dict]):    body = json.loads(event['body'])  # type: ignore    print(body)    message = body['message']    chat_id = message['chat']['id']    if photos := message.get('photo'):        # here photos is an array with same photo of different sizes        hd_photo = max(photos, key=lambda x: x['file_size'])  # get one with the highest resolution        try:            file = telegram_client.download_file(hd_photo['file_id'])        except TelegramClientError:            text = "Cant download the image from TG :("        else:            file_bytes = np.asarray(bytearray(file.read()), dtype=np.uint8)            try:                image_parser = ImageParser(file_bytes)                colors = image_parser.to_colors()            except ImageParserError as exp:                text = f"Cant parse image: {exp}"            else:                puzzle = BallSortPuzzle(colors)  # type: ignore                solved = puzzle.solve()                if solved:                    text = get_telegram_repr(puzzle)                else:                    text = "This lvl don't have a solution"    else:        return {            'statusCode': 200,            'headers': {'Content-Type': 'application/json'},            'body': '',            'isBase64Encoded': False,        }    msg = {        'method': 'sendMessage',        'chat_id': chat_id,        'text': text,        'parse_mode': 'Markdown',        'reply_to_message_id': message['message_id'],    }    return {        'statusCode': 200,        'headers': {'Content-Type': 'application/json'},        'body': json.dumps(msg, ensure_ascii=False),        'isBase64Encoded': False,    }

Отмечу ещё один нюанс: телеграм очень строго следует политике экранирования спецсимволов. Для Markdown это:

To escape characters '_', '*', '`', '[' outside of an entity, prepend the characters '\' before them.

Любой такой неэкранированный символ и вы не увидите ответа в телеграм-чате. И останется только гадать является ли это ошибка интеграции или вот такой коварный баг. Будьте осторожны.

Деплой бота в Яндекс.Функцию

Про создание Я.Функции также есть отличная статья от @mzaharov. Там подробно описан процесс заведения функции, а также установки вебхука для телеграмм бота.

Я расскажу как сделал Continuous Delivery при помощи GitHub Actions. Каждая сборка мастера увенчивается деплоем новой версии функции. Такой подход заставляет придерживаться модели разработки GithubFlow с его главным манифестом

Anything in themasterbranch is always deployable.

Каждая сборка мастера состоит из 3ёх этапов

  • lint (black, flake8, isort, mypy) проверка кода на соответствие всем стандартам Python 2020

  • test тестируем программу с помощью pytest, поддерживая качество и покрытие кода

  • deploy непосредственно заливаем новую версию приложения в облако

Деплоить будем с помощью Yandex-Serveless-Action уже готового Action для использования в своих пайплайнах

  deploy:    name: deploy    needs: pytest    runs-on: ubuntu-latest    if: github.ref == 'refs/heads/master'    steps:      - uses: actions/checkout@master      - uses: goodsmileduck/yandex-serverless-action@v1        with:          token: ${{ secrets.YC_TOKEN }}          function_id: ${{ secrets.YC_FUNCTION_ID }}          runtime: 'python38'          memory: '256'          execution_timeout: "120"          entrypoint: 'main.handler'          environment: "\            TELEGRAM_BOT_TOKEN=${{ secrets.TELEGRAM_BOT_TOKEN }}"          source: 'app'

Переменные окружения программы и сборки спрячем в GitHub Secrets на уровне репозитория.

Результат

Пример работы @ballsortpuzzlebotПример работы @ballsortpuzzlebot

Бота можно найти в telegram по позывному @ballsortpuzzlebot.

Все исходники на Github.

Присоединяйтесь к маленькому community любителей этой игры в telegram. Бот был добавлен в группу и внимательно следит за всеми отправленными картинками.

Бонус! Уровни, у которых нет решения
Lvl 4091Lvl 4091Lvl 6071Lvl 6071

Мой алгоритм умывает руки говорит что перебрал все возможные комбинации и решения нет. Возможно это баг алгоритма.. или QA-отдел мобильной игры просто забил на эти уровни, так как не предполагал, что кто-то так далеко зайдёт)

Заключение

Для меня это был интересный опыт скрещивания технологий (Telegram API + Python + OpenCV + Lambda). Надеюсь он окажется полезен кому-нибудь ещё.

Найденные баги, предложения по оптимизации алгоритма, или даже PR в репозиторий крайне приветствуются

С новым годом!

Подробнее..

AI на минималках 2 Генератор стихов на Prolog

30.01.2021 00:09:39 | Автор: admin

AI на минималках 2: Генератор стихов на Prolog


Мемная картинка


На картинке четверостишье, сгенерированное моей программой.


Оказывается "стихи" писать легко, нужно только знать несколько необходимых ингредиентов: размер, ритм, рифма. "Стихи" в кавычках, потому что в настоящем стихосложении, как и в любом другом искусстве, незыблемых законов нет. Однако в классике очень много правил, при соблюдении которых получается писать неплохие стихи, даже если вы никогда раньше этого не делали. Причём эти правила довольно просто программируются: "в строке должно быть равно N слогов", "нечётные строки должны рифмоваться", "ударные и безударные слоги в строке должны идти в определённом порядке" и т.д. Перечислив все правила, я свёл задачу генерации стихов к простому комбинаторному поиску. Язык Prolog как раз и предназначен для таких задач описании правил и генерации объектов, выполняющих эти правила.


Кто хочет научится писать стихи и познакомиться с Prolog, прошу под кат.


Как научиться писать стихи за 10 минут


Проще всего учиться на примерах великих поэтов. Возьмём классическое стихотворение Тютчева с расставленными ударениями:


Люблю грозу в начале мая, 9
Когда весенний, первый гром, 8
Как бы резвяся и играя, 9
Грохочет в небе голубом. 8


Гремят раскаты молодые, 9
Вот дождик брызнул, пыль летит, 8
Повисли перлы дождевые, 9
И солнце нити золотит. 8


С горы бежит поток проворный, 9
В лесу не молкнет птичий гам, 8
И гам лесной, и шум нагорный 9
Всё вторит весело громам. 8


Ты скажешь: ветреная Геба, 9
Кормя Зевесова орла, 8
Громокипящий кубок с неба, 9
Смеясь, на землю пролила 8


Сразу видно, что стих состоит из нескольких четверостиший, в каждом из которых рифмуются строки одинаковой четности. Заметим, что ударные и безударные слоги чередуются в определённом порядке: _'_'_'_'_ (нижнее подчёркивание означает безударный, а кавычка ударный слог). Такой ритмический рисунок называется размером стиха. Размер состоит из стоп, в каждой стопе ровно один ударный слог. У Тютчева размер двухсложный, с первым безударным, вторым ударным слогом. Такой размер называется ямбом. Есть и другие размеры, например хорей с ударением на первом слоге. Повторение одного размера в четверостишье задаёт стиху ритм, без которого даже с рифмой четверостишье будет звучать как проза.


Системы рифмовки тоже могут быть разные. У Тютчева рифмовка перекрёстная, ещё бывают кольцевая (рифмуются первая с последней и вторая с третьей строки) и смежная (первая со второй, третья с четвёртой).


Рифмовать слова тоже можно по-разному. Различают мужские и женские рифмы. В мужской ударение падает на последний слог, в женской на предпоследний. Есть ещё дактилическая рифма, где ударение падает на второй с конца слог, но к таким словам довольно сложно подобрать пару:


Дело было вечером,
Делать было нечего.


Получается примерно следующий алгоритм написания стихов:


  1. Выберите о чём будет стих. Часто через стихи поэты передают чувства.
  2. Напишите первый черновой вариант, пока без рифмы и ритма.
  3. Подгоните каждую строчку под определённый размер. Важно соблюдать ритмический рисунок.
  4. Зарифмуйте строчки по определённой системе.
  5. Отшлифуйте получившийся текст.
  6. Стих готов!

С практикой вам станет проще рифмовать слова и соблюдать ритм:


Шёл поэт по улице, 7
Кутался в пальто. 5
Всё пройдёт, забудется, 7
Время решето. 5


Обратите внимание, ритмический рисунок совпадает у рифмующихся строчек. У второй и четвёртой хорей получается как бы "рваным", но ритм от этого не страдает.


Введение в Prolog


Теперь сформулируем правила, которым должны удовлетворять четыре строки в четверостишье:


  1. Строчки грамматически корректны, т.е. не нарушают правила русского языка.
  2. Строки рифмуются по определённой системе, возьмём перекрёстную.
  3. У рифмующихся строк совпадает ритмический рисунок.

Мы специально не стали брать "осмысленность" стиха, т.к. это требование в стихосложении довольно субъективное, его сложно объяснить машине, да и вообще, в любой грамматически верной строке можно найти смысл (глокая куздра глокочет бокра и кудрячет бокрёнка).


Получается настоящая комбинаторная задача: в пространстве всех возможных строк найти четыре, выполняющие данные правила. Остаётся только как-то их запрограммировать. В принципе, для этого подходит любой императивный язык, но Prolog подходит лучше всего, т.к. создавался специально для таких задач.


Prolog это логический язык программирования. Он очень сильно отличается от императивных языков тем, что все конструкции декларативные, т.е. программы на Prolog описывают что надо сделать, а не как это сделать. Этим он похож на функциональные языки типа LISP. Prolog моделирует логику предикатов первого порядка.


Prolog можно рассматривать как некую СУБД или экспертную систему, в которой есть знания, и из этих знаний можно делать логические выводы с помощью правил. Знания выражают в виде фактов (предикатов) о внешнем мире. Например, вот так можно записать факт того, что Сократ смертен:


человек(сократ).смертен(Х) :- человек(Х).

Слова в Prolog бывают либо атомами (сократ), либо предикатами (человек), либо переменными (Х). Атомы это некоторые объекты, предикаты это свойства объектов или отношения между ними. Переменные должны начинаться с заглавной буквы, атомы и предикаты с прописной. Предложения должны оканчиваться точкой. В Prolog нет ограничений на латиницу, поэтому слова можно писать и на русском. Первая строчка выражает факт того, что Сократ человек. Вторая моделирует условие "каждый человек смертен". Части импликации разделяются знаком :- и меняются местами.


Теперь если открыть любой интерпретатор Prolog (на маке есть SWI-Prolog), то появится консоль со знаком ?-. Это экспертный режим, где можно задавать вопросы СУБД и получать ответы. Сохранив скрипт в файле socrates.pl и загрузив его командой [socrates]., мы сможем спросить является ли Сократ
смертным:


?- смертен(сократ).true.

Система логически вывела нам факт смертности Сократа. Но это ещё далеко не всё, попробуйте вместо Сократа подставить переменную:


?- смертен(Неизвестно).Неизвестно = сократ.

Prolog сам подобрал единственно возможное значение переменной "Неизвестно". Пролог следует т.н. гипотезе закрытого мира (closed-world assumption) всё, чего нет в базе считается неверным:


?- смертен(аристотель).false.

Хотя Аристотель был таким же человеком, но в нашей программе это не отражено, поэтому Prolog выводит false.


"Хорошо, и как же на этом программировать?" спросите вы. Здесь Пролог очень схож с функциональными языками, где программы определяются рекурсивно. Рассмотрим как вычислить последовательность Фибоначчи. Определим отношение fib(n, f_n), означающее что $n$-ное число Фибоначчи равно $f_n$:


fib(0, 1).fib(1, 1).fib(N, F) :- N #> 1,             M #= N - 1,             K #= M - 1,             F #= G + P,             fib(M, G),             fib(K, P).

Первые две строки задают известный факт, что первый и второй элемент последовательности равны 1. Затем идёт рекурсивное определение, которое можно прочесть так: "Отношение между двумя числами fib(N, F) верно только в том случае, когда N больше единицы, M равно N - 1, K равно M - 1, а F равно сумме G и P, которые находятся в отношениях fib(M, G) и fib(K, P)". Запятые тут означают логическое "И". Операторы сравнения #> и #= нестандартны для Пролога, они находятся в библиотеке CLPFD, идущей вместе с дистрибутивом SWI-Prolog. Эта библиотека "чинит" недостатки стандартных числовых отношений вроде =, > и т.д. Чтобы использовать библиотеку, нужно сразу после старта REPL консоли набрать ?- use_module(library(clpfd)).


Теперь откроем swipl, загрузим скрипт и введём ?- fib(10, X). Пролог выведет X = 89. То есть он подобрал первое значение переменной X, которое удовлетворяет этому отношению. Если нажать клавишу ';', то выйдет false, так Пролог говорит, что других значений X он найти не может. Теперь классный момент: введём ?- fib(X, 13). Пролог выдаст X = 6. То есть так можно вычислять еще и обратную функцию. Мы получили две программы по цене одной!


Ещё интересно как работают списки в Prolog. У списка есть голова (первый элемент) и хвост (остальные). Синтаксис такой: Список = [Голова | Хвост]. Например, если Список = [1, 2, 3, 4], то Голова = 1, а Хвост = [2, 3, 4]. Это разделение очень полезно при рекурсивном определении отношений. Вот так можно закодить отношение freq(E, L, F) которое выполняется когда элемент E входит в список L ровно F раз:


freq(_, [], 0).freq(Element, [Head|Tail], F) :- Head #= Element,                     F #= P + 1,                     freq(Element, Tail, P),                     !.freq(Element, [Head|Tail], F) :- Head #\= Element,                     freq(Element, Tail, F),                     !.

Сначала как обычно выполняется базовый случай: в пустом списке частота любого элемента равна нулю. Роль "любого элемента" здесь играет переменная "_". В Прологе так обозначаются "свободные" переменные, встречающиеся только один раз. Затем рассматривается два случая когда голова списка равна подсчитываемому элементу и когда нет. В первом случае инкрементируется счётчик вхождений элемента в массив. Затем Пролог продолжает рекурсивно пробовать удовлетворять freq. Если запросить ?- freq([1, 2, 2, 3], 2, X), то интерпретатор построит примерно такую цепочку равенств для нахождения правильного значения Х:


X #= X1, Tail = [2, 2, 3]X1 #= X2 + 1, Tail = [2, 3]X3 #= X4 + 1, Tail = [3]X5 #= X6, Tail = []Последний вызов: freq(_, [], 0), X6 #= 0.

Развёртывая равенства получим X #= 2.


Восклицательный знак здесь играет важную роль. Это т.н. "cut operator", который обрезает дерево поиска интерпретатору. Он говорит "если интерпретатор дошел до меня, то не нужно пробовать удовлетворить другой вариант freq". Из-за этого у Х будет только одно возможное значение.


Комбинаторный поиск в Prolog


Prolog идеально подходит для комбинаторного перебора. Нужно только закодировать правила, которым подчиняются перебираемые объекты, и запустить интерпретатор. Рассмотрим классическую задачу генерации всех магических квадратов 3 на 3. Магическим называется квадрат, в котором все числа положительны и различны, а суммы в каждом столбце, строке и диагонали совпадают. Пример:


A|B|C   2|7|6-|-|-   -|-|-D|E|F = 9|5|1-|-|-   -|-|-G|H|I   4|3|8

Каким правилам подчиняются числа в квадрате?


  1. В квадрате 3х3 ровно 9 чисел.
  2. Каждое число целое и строго положительное.
  3. Все числа различны.
  4. Есть 7 равенств, выполняющие условие "магичности" квадрата.

С помощью библиотеки CLPFD можно очень легко закодировать эти правила в Прологе:


magic([A, B, C, D, E, F, G, H, I]) :- Vars = [A, B, C, D, E, F, G, H, I],                                    Vars ins 1..100,                                    all_different(Vars),                                    A + D + G #= B + E + H,                                    B + E + H #= C + F + I,                                    C + F + I #= A + B + C,                                    A + B + C #= D + E + F,                                    D + E + F #= G + H + I,                                    G + H + I #= A + E + I,                                    A + E + I #= C + E + G,                                    label(Vars).

Отношение magic определяет 9 различных переменных из интервала [1, 100] с семью равенств. Функция label позволяет назначить конкретные значения этим переменным. Если запустить ?- magic(S). то интерпретатор Пролога будет последовательно выводить все возможные магические квадраты 3х3.


Вернёмся к нашей оригинальной задаче: генерации стихотворений. Стихотворение состоит из четверостиший. Четверостишие определяется следующими правилами:


  1. Строчки грамматически корректны, т.е. не нарушают правила русского языка.
  2. Строки рифмуются по определённой системе, возьмём перекрёстную.
  3. У рифмующихся строк совпадает ритмический рисунок.

Всё, что нужно сделать это корректно закодировать это правила на Прологе. Самое сложное здесь это первое правило. Грамматическая корректность это довольно непростое требование, грамматика русского языка очень богата, у нас есть спряжения, морфология, и проч. Поэтому я решил взять конкретные шаблоны, которые наверняка будут грамматически корректны. Все слова в настоящем времени и мужского рода:


Нечётные строчки: Прил Сущ Нар ГлагПример: Жёлтый жираф тихо спит, Маленький заяц быстро бежитЧётные строчки: Нар Глаг СущПример: Громко поёт соловей, Быстро играет музыкант

Нужно только добавить достаточно слов каждой части речи, чтобы стихи получались богатыми.


Как это кодировать? Очень просто вначале составляется словарь наподобие такого:


наречие(ушло, 1).наречие(хило, 1).наречие(хорошо, 3).прилагательное(кроткий, 1).прилагательное(дохлый, 1).прилагательное(фирменный, 1).глагол(ценит, 1).глагол(читает, 2).глагол(касается, 2).существительное(бык, 1).существительное(слон, 1).существительное(укротитель, 3).

Второй аргумент указывает на порядковый номер ударного слога. В слове "кроткий", ударение падает на первый слог, а в слове "укротитель" на третий. Эта информация пригодится когда мы будет строить ритмический рисунок строчки.


Затем определяется предикат предложение:


предложение([А, Б, В, Г]) :- прилагательное(А, _),                           существительное(Б, _),                           наречие(В, _),                           глагол(Г, _).

И похожий предикат для чётных строчек. Тогда Пролог будет генерировать корректные предложения запросом ?- предложение(П).


Теперь ко второму правилу рифмовки. Как определить что два слова рифмуются? Рифмуются слова, у которых ударение падает на тот же слог и у которых окончания похожи (зрелый спелый, бедный каретный, новый здоровый). Есть такое понятие парные буквы, наверняка вы ещё их в школе проходили. Вот несколько таких пар:


(а, я).(б, п).(в, ф).(и, ы).(с, ц).

Назовём все такие пары омофонными. Окончания рифмующихся слов могут отличаться, но только если разные буквы будут принадлежать одной паре. Например, пара "бедный каретный", окончания "едный етный" отличаются, но пара (д, т) омофонная, поэтому рифма не нарушается. То есть, рифму можно описать следующим правилом:


  • Окончания рифмующихся слов отличаются не более чем на омофонные пары. Под окончанием здесь понимается часть слова начиная с ударного слога и до конца. Окончания у рифмующихся слов равны по длине.

Чтобы закодировать такое правило надо сначала определить все омофонные пары:


омофон_пара(а, я).омофон_пара(б, п).омофон_пара(в, ф).омофон_пара(г, к).омофон_пара(д, т).омофон_пара(ж, ш).омофон_пара(з, с).омофон_пара(ч, щ).омофон_пара(и, ы).омофон_пара(е, э).омофон_пара(у, ю).омофон_пара(я, а).омофон_пара(п, б).омофон_пара(ф, в).омофон_пара(к, г).омофон_пара(т, д).омофон_пара(ш, ж).омофон_пара(с, з).омофон_пара(щ, ч).омофон_пара(ы, и).омофон_пара(э, е).омофон_пара(ю, у).омофон_пара(н, м).омофон_пара(м, н).омофон_пара(ц, с).омофон_пара(с, ц).

Затем определить предикат "похожие_по_звучанию(Слово1, Слово2)", который выполняется когда слова 1 и 2 отличаются не более чем на омофонные пары:


похожие_по_звучанию([], []).похожие_по_звучанию([Б1|К1], [Б2|К2]) :- Б1 = Б2, похожие_по_звучанию(К1, К2).похожие_по_звучанию([Б1|К1], [Б2|К2]) :- омофон_пара(Б1, Б2), похожие_по_звучанию(К1, К2).

Здесь слово разбивается на список своих букв и рассматриваются два случая: когда буквы равны и когда они принадлежат одной омофонной паре.


Зная всё это, написать предикат "рифмуется(Слово1, Слово2)" не составляет труда:


рифмуется(С1, С2) :- ударение(С1, У1),                     ударение(С2, У2),                     индекс_гласной(С1, У1, И1),                     индекс_гласной(С2, У2, И2),                     atom_chars(С1, Буквы1),                     atom_chars(С2, Буквы2),                     length(Буквы1, Д1),                     length(Буквы2, Д2),                     Д1 - И1 #= Д2 - И2, % ударение на тот же слог                     slice(Буквы1, И1, Д1, Окончание1),                     slice(Буквы2, И2, Д2, Окончание2),                     похожие_по_звучанию(Окончание1, Окончание2),                     С1 \= С2.

Предикат atom_chars позволяет разбить слово на составляющие его буквы, а slice вычленяет ударное окончание из обеих слов. Обратите внимание на последнее требование: C1 \= C2, оно нужно чтобы одно и то же слово не генерировалось при запросе ?- рифмуется(Слово1, Слово2).


Остаётся последнее правило: совпадение ритмического рисунка у строчек. Давайте договоримся, что ритмический рисунок строки будем записывать с помощью букв "б" и "у", где "б" означает безударный слог, а "у" ударный. Сам такой рисунок будем называть "шаблоном".


Например, у строки "Люблю грозу в начале мая" шаблон будет "бубубубуб", т.е. чистый ямб. Хорей будет выглядеть наоборот "убубубуб".


По каждой строчке в стихе можно строить такие шаблоны. Совпадением ритмического рисунка будет совпадение шаблонов. Как строить такие шаблоны? Нужно каждое слово в строке разбить на слоги, ударный слог записать как "у", остальные как "б" и повторить для всех слов.


Я не буду здесь приводить полный код этой процедуры, при желании вы можете ознакомиться с кодом всего проекта в открытом репозитории


Приведу только конечный вид предиката "стих", по которому можно генерировать четверостишия:


стих([П1, Щ1, Н1, Г1], [Н2, Г2, Щ2], [П3, Щ3, Н3, Г3], [Н4, Г4, Щ4], Р1, Р2, Р3, Р4) :-    прилагательное(П1, _),    существительное(Щ1, _),    наречие(Н1, _),    глагол(Г1, _),    ритм_предложения([П1, Щ1, Н1, Г1], Р1),    наречие(Н2, _),    Н1 \= Н2,    глагол(Г2, _),    Г1 \= Г2,    существительное(Щ2, _),    Щ1 \= Щ2,    ритм_предложения([Н2, Г2, Щ2], Р2),    прилагательное(П3, _),    П1 \= П3,    существительное(Щ3, _),    Щ1 \= Щ3,    Щ2 \= Щ3,    наречие(Н3, _),    Н2 \= Н3,    Н1 \= Н3,    глагол(Г3, _),    Г2 \= Г3,    Г1 \= Г3,    ритм_предложения([П3, Щ3, Н3, Г3], Р3),    рифмуется(Г1, Г3),    наречие(Н4, _),    Н1 \= Н4,    Н3 \= Н4,    Н2 \= Н4,    глагол(Г4, _),    Г1 \= Г4,    Г3 \= Г4,    Г2 \= Г4,    существительное(Щ4, _),    Щ1 \= Щ4,    Щ3 \= Щ4,    Щ2 \= Щ4,    ритм_предложения([Н4, Г4, Щ4], Р4),    рифмуется(Щ2, Щ4).классика(Стих) :- стих(А, Б, В, Г, хорей, рваный_хорей, хорей, рваный_хорей), Стих = [А, Б, В, Г].

Здесь включены все три правила стихосложения (грамматическая корректность, рифма, ритм) и ещё добавлены условия на различность X \= Y чтобы слова не повторялись.


Наконец, можно проверить как это всё работает если набрать ?- классика(Стих).


Что дальше?


Понятно, что всё описанное это только proof of concept, можно и дальше развивать эту тему. Например, добавить ещё слов в словарь, расширить грамматику, чтобы она включала разные времена и роды слов. Можно также определить новые шаблоны стихотворений, отличных от классики, да и вообще поле для экспериментов тут очень богатое.


Надеюсь вам понравилась статья и вы узнали что-то новое. Ссылка на репозиторий проекта: prolog-poetry. Там же есть полная инструкция по запуску.

Подробнее..

Перевод Быстрый поиск без индекса

03.07.2020 00:15:20 | Автор: admin

Проблема



У всех нас есть дни на работе, когда кто-то приходит к нам с по-настоящему невыполнимым требованием, для выполнения которого требуется чудо. Мой случай произошел, когда коллега по маркетингу подошел ко мне с на первый взгляд простым вопросом: если бы я мог получить данные из одной таблицы за определенный месяц пару лет назад. Можно сказать, ничего страшного, но я смутно вспомнил, что таблица была очень большой. У таблицы было поле datetime со временем создания, но был ли на этом поле индекс?

Конечно, они также хотели получить данные быстро. Я, как обычно, сказал: Я посмотрю, что я могу сделать и пошел поближе взглянуть на обсуждаемую таблицу. Удача никогда н покинет нас, индекс действительно не существовал, и таблица была огромной. Не проблема, мы можем просканировать таблицу, правильно? Неправильно. Если я чему-то научился за годы работы с базами данных, то этот размер имеет значение. Таблица с сотнями миллионов записей, состоящая из нескольких целочисленных столбцов, была бы достаточно грозной. Затем добавьте различные столбцы varchar и datetime. Теперь это настоящий вызов, не так ли?



Таблица, на которую я смотрел, имела миллиард записей, буквально. Простое сканирование таблицы могло легко занять больше суток, и мне нужно было также обработать извлеченные данные. Кроме того, сканирование таблицы такого размера может оказаться не таким уж благоприятным для общего состояния системы, как кажется на первый взгляд. Все отсканированные страницы должны быть извлечены с дисков в память sql сервера, заполнив её. Это, в свою очередь, выгрузит из кеша страницы данных, которые могут быть использованы для текущих оперативных задач. Запросы ваших текущих пользователей могут ждать дольше, пока сервер перечитывает данные с дисков, вместо того, чтобы быстро повторно использовать страницы данных из памяти. Производительность может снизиться, и в худшем случае сервер может быть полностью поставлен на колени. Таким образом, при сканировании таблицы следует использовать особую технику запускать ее небольшими партиями, сохраняя где-то текущую позицию и промежуточные результаты. Такой подход позволяет серверу перенастраиваться и иметь передышку, не допуская большой просадки производительности.

Поиск



Для всех кто, как и я, закончил обучение довольно давно, переподготовка по теории должна быть в порядке вещей. Бинарный поиск это простой, но чрезвычайно эффективный способ поиска значения в отсортированном массиве (в нашем случае в столбце таблицы). Массив должен быть предварительно отсортирован и конечен. Поиск осуществляется путем сравнения среднего элемента вашего массива с целью. Если они равны, то поиск окончен. Если нет, вы удаляете половину, в которой искомый элемент заведомо отсутствует, и повторяете предыдущий шаг пока не останется один. Найдите середину, сравните цель с ней, если они не равны, снова уберите половину и так далее. Общее количество шагов, необходимых для нахождения цели в худшем случае, когда вы найдете ее к самому последнему шагу, будет log(N), где N число элементов. Сравните это с N / 2, когда вы просто перебираете массив. Вообще говоря, это было бы N, но, если бы мы могли догадаться, ближе ли цель к концу, мы могли бы вернуться назад, таким образом уменьшая общее количество необходимых шагов.

В моем случае, N=1,000,000,000 и вот как я пришел к двум числам выше: 30 и 500,000,000. Идентификатор (ID) играл бы роль перечислителя массива, а datetime создания был бы значением элемента массива. Хотя здесь есть одна оговорка. Перечислитель массива, по самому определению, является непрерывной последовательной последовательностью целых чисел. В идентификаторах таблиц легко могут быть пробелы, из-за удаления записи или повторного заполнения идентификатора. Простое определение середины путем деления диапазона идентификаторов на 2, не следует ожидать, что там будет запись с таким идентификатором. Вместо прямого поиска мне пришлось использовать функцию top (). Что-то вроде этого:

Select top(1) * from Table where id <= @id order by id desc


Я использовал <= и desc потому что я хотел найти значение либо равное или непосредственно перед целью. При условии @l, @r это левая и правая границы соответственно, id это середина, @dt это время создания (creation datetime), tdt это цель и idr реальный идентификатор таблицы (ID), алгоритм может выглядеть следующим образом:

while @l <@rbegin -- найти середину @id = @l +floor((@r-@l)/2) -- найти запись в таблице select top(1) @idr = id, @dt = creation_datetime from Table where id <= @id order by id desc -- переместить границу if(@dt<@tdt) @l = @id +1 else @r = @idend 


Последний найденный idr был бы идентификатор записи, после которой была нужная. Алгоритм имеет что-то вроде левого смещения, то есть тенденция выбирать крайнее левое из всех значений. Так как я хотел, чтобы запись со значением была как можно ближе к цели, я также проверил ближайших левых и правых соседей в таблице чтобы увидеть, был ли один из них лучше. Обратите внимание, что я не использовал реальный идентификатор из таблицы для процесса итерации, как в этом случае, с пробелами в значениях ID и при некоторых обстоятельствах, алгоритм мог уйти в бесконечный цикл.

Написание и тестирование скрипта заняли у меня около часа. Используя его, я нашел первую запись с определенной датой и временем создания. После этого я использовал простой оператор select с предложением where, которое содержало оба условия: id >= @ and creation_datetime >= @dt1 and creation_datetime < @dt2. Мне нужно было только убедиться, что оптимизатор выбрал бы использование первичного ключа вместо индекса или сканирования таблицы. В общем, я сделал это менее чем за 2 часа! Было удивительно вновь обнаружить, что алгоритмы не являются чем-то эзотерическим, похороненным глубоко внутри sql сервера, а скорее тем, что можно легко использовать в повседневной работе.

Ниже весь скрипт, который я написал. Пожалуйста, смотрите комментарии внутри, чтобы понять, как его использовать.
/* Запустите этот скрипт на вашей бд Он найдет значение, равное или непосредственно перед целью. Обратите внимание, что точность datetime ограничена 3 мс*/-- флаг отладки, если установлен, он будет показывать результаты для каждой итерацииdeclare @debug bit = 0-- @Table - имя таблицы, в которой вы хотите искать.declare @Table varchar(128) = 'TableX' -- @Id - имя столбца идентификатора (id) для таблицы declare @ID varchar(128) = 'Id' -- @DateTimeColumn - имя вашего datetime столбца со временем создания в таблицеdeclare @DateTimeColumn varchar(128) = 'created_dt'-- это целевое значение даты и времениdeclare @TargetDateTime datetime = '2020-01-03 18:23:03'declare @Sql varchar(max)set @sql = '-- это ваш отладочный флагdeclare @debug bit = <debug>-- это ваше целевое значениеdeclare @tdt datetime = ''<TargetDateTime>''-- в этой переменной мы сохраняем промежуточное значение (результат деления) declare @id bigint -- это ваши левая и правая границы соответственноdeclare @l bigint, @r bigint-- это переменные, в которых мы храним результаты текущего шага поиска, datetime и идентификатор таблицы соответственноdeclare @dt datetime, @idr bigint-- найти первые левые и правые значенияselect @l = min(<ID>), @r = max(<ID>) from <Table>while @l < @rbegin -- ожидаемый идентификатор set @id = @l +floor((@r-@l)/2) -- найти значение и идентификатор записи select top(1) @dt = <DateTimeColumn>, @idr = <ID> from <Table> where <ID> <= @id order by <ID> desc -- если требуется отладка, покажите текущие значения if( @debug = 1 ) begin select ''@id'' = @id, ''@l'' = @l, ''@r'' = @r, ''@dt'' = @dt, ''@idr'' = @idr end if(@dt < @tdt) set @l = @id +1 else set @r = @idend-- проверьте, есть ли у соседних записей лучшее совпадениеdeclare @t table(id bigint, dt datetime, dlt float)insert @t(id, dt, dlt)select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float)) from <Table> where <ID> < @idr order by <ID> descinsert @t(id, dt, dlt) select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float)) from <Table> where <ID> > @idr order by <ID>insert @t(id, dt, dlt) select @idr, @dt, abs(cast(@dt as float) -cast(@tdt as float))select top(1) @dt = dt, @idr = id from @t order by dlt, id select ''Found Value'' = @dt, ''Record Id'' = @idr'set @sql = replace( replace( replace( replace( replace(@sql, '<ID>', @ID), '<Table>', @Table), '<TargetDateTime>', convert(varchar(50), @TargetDateTime, 121)), '<debug>', @debug), '<DateTimeColumn>', @DateTimeColumn)exec (@sql)
Подробнее..

Слияние списков на python

14.07.2020 20:14:29 | Автор: admin

Сравнение различных методов слияния двух отсортированных списков


Пусть у нас есть два списка (для простоты из целых чисел), каждый из которых отсортирован. Хотим объединить их в один список, который тоже должен быть отсортирован. Эта задача наверняка всем знакома, используется, например, при сортировке слиянием.



Способов реализации (особенно на python) достаточно много. Давайте разберем некоторые из них и сравним затачиваемое время на разных входных данных.


Основная идея алгоритма заключается в том, что, поместив по одной метке в начале каждого списка, будем сравнивать отмеченные элементы, брать меньший из них и передвигать метку в его списке на следующее число. Когда один из списков кончается, нужно добавить остаток второго в конец.


Входные данные не меняются


Пусть есть два списка list1 и list2.
Начнем с самого простого алгоритма: обозначим метки за i и j и будем брать меньший из list1[i], list2[j] и увеличивать его метку на единицу, пока одна из меток не выйдет за границу списка.


При первом сравнении мы выберем минимальный элемент из двух минимальных в своем списке и подвинемся на следующий элемент, поэтому наименьший элемент из двух списков будет стоять на нулевом месте результирующего. Дальше несложно по индукции доказать, что далее слияние пройдет верно.


Перейдем к коду:


def simple_merge(list1, list2):    i, j = 0, 0    res = []    while i < len(list1) and j < len(list2):        if list1[i] < list2[j]:            res.append(list1[i])            i += 1        else:            res.append(list2[j])            j += 1    res += list1[i:]    res += list2[j:]     # один из list1[i:] и list2[j:] будет уже пустой, поэтому добавится только нужный остаток    return res

Заметим, что в данном коде используется только перемещение вперед по списку. Поэтому будет достаточно работать с итераторами. Перепишем алгоритм с помощью итераторов.


Еще изменим обработку концов списков, так как теперь мы не умеем копировать сразу до конца. Будем обрабатывать элементы до того, когда оба итератора дойдут до конца, при этом, если один уже оказался в конце, будем просто брать из второго.


def iter_merge(list1, list2):    result, it1, it2 = [], iter(list1), iter(list2)    el1 = next(it1, None)    el2 = next(it2, None)    while el1 is not None or el2 is not None:        if el1 is None or (el2 is not None and el2 < el1):            result.append(el2)            el2 = next(it2, None)        else:            result.append(el1)            el1 = next(it1, None)    return result

В этой реализации можно вместо добавления по одному элементу (result.append()) собрать генератор, а потом из него получить список. Для этого напишем отдельную функцию, которая будет строить генератор, а основная функция сделает из него список.


def gen_merge_inner(it1, it2):    el1 = next(it1, None)    el2 = next(it2, None)    while el1 is not None or el2 is not None:        if el1 is None or (el2 is not None and el2 < el1):            yield el2            el2 = next(it2, None)        else:            yield el1            el1 = next(it1, None)def gen_merge(list1, list2):    return list(gen_merge_inner(iter(list1), iter(list2))) # из генератора получаем список

Встроенные реализации


Рассмотрим еще несколько способов слияния через встроенные в python функции.


  • merge из heapq. Как говорит документация, эта функция делает именно то, что мы хотим, и больше: объединяет несколько итерируемых объекта, можно задать ключ, можно сортировать в обратном порядке.


    Тогда нам нужно просто импортировать и использовать:


    from heapq import mergedef heapq_merge(list1, list2):return list(merge(list1, list2)) # тоже возвращает генератор
    

  • Counter из collections. Counter умеет считать количество вхождений каждого из элементов, выдавать их в тех количествах, в которых они входят, и еще несколько полезных вещей, которые сейчас не нужны (например, несколько самых часто встречающихся элементов).


    Воспользуемся gen_merge_inner для слияния элементов Counter(list1) и Counter(list2):


    def counter_merge(list1, list2):return list(gen_merge_inner(Counter(list1).elements(), Counter(list2).elements()))
    

  • И, наконец, просто сортировка. Объединяем и сортируем заново.


    def sort_merge(list1, list2):return sorted(list1 + list2)
    


Если можно менять исходные списки


Предположим, что после слияния старые списки больше не нужны (как обычно и случается). Тогда можно написать еще один способ. Будем как и раньше сравнивать нулевые элементы списков и вызывать pop(0) у списка с меньшим, пока один из списков не закончится.


def pop_merge(list1, list2):    result = []    while list1 and list2:        result.append((list1 if list1[0] < list2[0] else list2).pop(0))    return result + list1 + list2

Получили простенькую функцию на 4 строчки, но использовать дальше исходные списки не получится. Можно их скопировать, потом работать с копиями, но это потребует много дополнительного времени. Здесь будут проблемы с тем, что удаление нулевого элемента очень дорогое. Поэтому еще одна модификация будет заключаться в том, что мы будем вместо удаления из начала списка использовать удаление из конца, но придется в конце развернуть списки.


def reverse_pop_merge(list1, list2):    result = []    while list1 and list2:        result.append((list1 if list1[-1] > list2[-1] else list2).pop(-1))    return (result + list1[-1::-1] + list2[-1::-1])[-1::-1]

Сравнение


Пора перейти к самому интересному.
Составим список функций, которые будем сравнивать:


  • simple_merge
  • iter_merge
  • gen_merge
  • heapq_merge
  • counter_merge
  • sort_merge
  • pop_merge
  • reverse_pop_merge

Будем измерять время работы с помощью модуля timeit. Код можно посмотреть здесь.


Разберем несколько ситуаций: оба списка примерно одинакового размера, один список большой, а второй маленький, количество вариантов элементов большое, количество вариантов маленькое. Кроме этого проведем просто общий случайный тест.


Тест первый


Проведем общий тест, размеры от $1$ до $10^5$, элементы от $1$ до $10^6$.


Отдельно сравним pop и reverse_pop:

pop_merge тратит колоссально больше времени в общем случае, как и ожидалось.


Не будем учитывать здесь огромный pop_merge, чтобы лучше видеть разницу между другими:

reverse_pop_merge показал себя относительно неплохо по сравнению с ручной реализацией и heapq_merge.


Методы на итераторах работают еще быстрее, при этом видно, что получилось выгоднее построить генератор, чем добавлять элементы в список.


Тест второй, сравнимые размеры


Размеры будут принадлежать отрезку $[50x, 50(x+1))$, а $x$ увеличиваем, начиная с $1$. Шаг $50$.

Как уже можно видеть pop_merge при небольшом размере списков еще ведет себя как heapq_merge, а дальше обгоняет всех.


Тест третий, один маленький, второй большой


Размер первого равен $x$, размер второго $10^4 + 100x$.

В самом начале (на очень маленьких списках) reverse_pop_merge обгоняет всех, кроме sort_merge, но на чуть больших все выходит на стандартные позиции.


Тест четвертый, много повторных


Размеры фиксированы, а количество элементов увеличивается на $5$, начиная с $1$.

Как видно, на достаточно малых количествах counter_merge оказывается быстрее reverse_pop_merge и heapq_merge, но потом он отстает.


Итоги


Абсолютным победителем оказался sort_merge! Гораздо быстрее просто отсортировать список заново, чем использовать вроде бы линейные от длины списков функции.


На втором месте в подавляющем большинстве случаев идет gen_merge, за ним следует iter_merge.


Остальные методы используют еще больше времени, но некоторые в каких-то крайних случаях достигают результатов 2-3 мест.


P.S.


Код, тесты, jupyter notebook c графиками можно найти на gitlab.


Возможно этот анализ неполон, буду рад добавить к сравнению ваши варианты, предлагайте.

Подробнее..

Выращивание Nested sets в условиях .Net

25.11.2020 12:06:49 | Автор: admin


Привет, меня зовут Антон, и я разработчик. Сына я родил, дом построил купил, осталось вырастить дерево. Так как агроном из меня не очень, пришлось дерево кодить. Наш проект состоит из нескольких микросервисов на .Net Core, в PostgreSQL базе хранятся сущности, которые образуют иерархические связи. Расскажу о том, какую структуру лучше выбрать для хранения таких данных, почему именно Nested sets, на какие грабли можно наступить, и как с этим потом жить.


Что такое Nested sets


Как растет дерево в саду все знают, а в случае Nested sets дерево растет так: для каждого узла хранится два поля Left и Right, они целочисленные. Логика здесь такая Left меньше чем Right, и, если у узла есть дочерние, то все значение Left и Right дочерних узлов должны быть между соответствующих значений родительского.



Как они растут у нас


У нас под хранение иерархий выделен отдельный микросервис. Фронтеду приходится часто рисовать полное дерево, а также поддеревья элементов в детализированном представлении, тогда как вставлять и переносить элементы надо сравнительно реже. Для такого случая Nested sets подходят как нельзя лучше. Хранится в такой таблице:



Id это идентификатор соответствующей сущности, по нему можно получить полную информацию из подходящего микросервиса. TreeId идентификатор корневого элемента. В проекте деревья в основном небольшие, но их много. Для чтения из базы используется EntityFramework, класс один к одному соответствует структуре таблицы.

Как прочитать


При таком способе хранения получить элементы поддерева просто запрашиваем все узлы, у которых Left больше Left родительского, а Right соответственно меньше. Также проверяем, что все узлы относятся к одному и тому же дереву по колонке TreeId. Это операция, которая необходима чаще других, и выполняется она быстро. К примеру, так:

dataContext.Nodes.Where(_ =>                         _.Left > node.Left &&                         _.Right < node.Right &&                         _.TreeId == node.TreeId); 


Еще одна часто выполняемая операция поиск всех родительских узлов объекта. Здесь тоже несложно запрашиваем узлы дерева, у которых Left меньше Left родительского элемента, а Right соответственно больше. Например, таким способом:

dataContext.Nodes.Where(_ =>                         _.Left < node.Left &&                         _.Right > node.Right &&                         _.TreeId == node.TreeId);


Как вырастить новые ветки


Перейдем к сложной части пересадка, т.е. добавление узлов или перенос из одного поддерева в другое. Разберем, как сделать перенос, т.к. по сути эта операция включает в себя все, что нужно для добавления дочернего элемента.

Первое, что нужно сделать для успешной вставки разрешить только одну операцию вставки или обновления. Для этого воспользуемся блокировкой. Блокировать всю таблицу не имеет смысла, так как узлы могут переходить только в рамках одного дерева, так что достаточно заблокировать только это дерево. Для этого выполним такой SQL запрос:

select * from "Nodes" where "TreeId" = <TreeId> for update; 


Это позволит нам читать элементы дерева сразу, но если потребуется добавить или изменить узел в дереве, где уже начата такая операция, придется подождать завершения предыдущей.

Следующим шагом подготовим место для пересадки создадим промежуток между Left и Right. Посчитаем, сколько место необходимо это разность между Right и Left корневого элемента перемещаемого поддерева. Добавим эту разность ко всем дочерним элементам узла, который станет новым родителем. Здесь можем поймать Exception, и вот почему. Для ускорения поиска и чтения в таблице заведены два B-Tree индекса, на поля Left и Right, и если одновременно менять значения этих полей, EntityFramework может выдать ошибку циклической зависимости, т.к. два индекса могут пересчитываться одновременно на одной строке. Ошибка будет типа InvalidOperationException с таким сообщением:

Unable to save changes because a circular dependency was detected in the data to be saved: 'Node[Modified]< Index { 'Right', 'TreeId' } Node[Modified]< Index { 'Left', 'TreeId' } Node[Modified]'.


Чтобы обойти, просто сделаем два отдельных цикла в одном изменим Left, в другом Right, и, конечно, сохранять изменения будем после каждого из них.

            var nodesToMove = await dataContext.Nodes                 .Where(n =>                     n.Right >= parentNodeRight &&                     n.TreeId == parentNode.TreeId)                 .OrderByDescending(n => n.Right)                 .ToListAsync();              foreach (var n in nodesToMove)             {                 n.Left += distance;             }              await dataContext.SaveChangesAsync();              foreach (var n in nodesToMove)             {                 n.Right += distance;             }              await dataContext.SaveChangesAsync(); 


Далее сама пересадка расстояние переноса будет равно разности между Left нового родителя и Left корня поддерева. Добавим это значение к Left и Right всех узлов перемещаемого поддерева.

            var nodes = await dataContext.Nodes                 .Where(n =>                     n.Left >= node.Left &&                     n.Right <= node.Right &&                     n.TreeId == node.TreeId)                 .ToListAsync();              foreach (var n in nodes)             {                 n.Left += distance;                 n.Right += distance; 


И последнее, что надо сделать закрыть промежуток так, где было перемещенное поддерево. Запросим все узлы правее этого поддерева это будут элементы, у которых Right больше либо равно Left корня поддерева, и передвинем их на освободившееся место. Для этого отнимем от Left и Right всех этих узлов разность между Right и Left корня. Здесь тоже придется сделать два отдельных цикла:

            var nodesToMove = await dataContext.Nodes               .Where(n => n.Right >= gap.Left && n.TreeId == gap.TreeId)               .ToListAsync();             nodesToMove = nodesToMove                 .Where(n => n.Right >= gap.Right)                 .OrderBy(n => n.Right)                 .ToList();              foreach (var n in nodesToMove)             {                 if (n.Left >= gap.Right)                 {                     n.Left -= distance;                 }             }              await dataContext.SaveChangesAsync();              foreach (var n in nodesToMove)             {                 n.Right -= distance;             }              await dataContext.SaveChangesAsync();


Заключение


Посмотрим, что у нас выросло. Мы получили дерево с возможностью быстрого чтения дочерних и родительских элементов. Если в вашем проекте нужно часто читать данные и получать поддеревья, Nested sets отличный выбор. Надо быть готовым к тому, что с операциями вставки и обновления могут возникнуть проблемы, но они вполне решаемые. Если же добавлять и переносить приходится часто, лучше подумать о применении какого-то другого алгоритма, либо рассмотреть некие гибридные варианты. Например скрестить Nested sets и Adjacency List. Для этого в каждый узел, помимо Left и Right, надо добавить прямую ссылку на идентификатор родительского элемента. Это позволит быстрее перемещаться по иерархии и находить родительские и дочерние узлы, и, кроме того, повысит надежность алгоритма.
Подробнее..

Гексагональные тайлоыве миры

23.05.2021 20:21:44 | Автор: admin

Тайловость в играх очень распространенное явление, особенно в играх инди сегмента. Чаще всего используют квадратные тайлы в них проще всего задать необходимые данные, будь то карта уровня или инвентарь. Однако на квадратных и прямоугольных формах возможности подобной системы не ограничиваются.

В топовых играх конца девяностых - начала нулевых часто можно увидеть шестиугольную сетку заместо квадратной в то время это смотрелось очень интересно, в особенности в сочетании с изометрией. Именно о работе с такими сетками и пойдет речь.

Если вы не читали мою предыдущую статью про прямоугольные сетки, то рекомендую ознакомится, потому как я иногда буду опускать некоторые вещи, ссылаясь именно на нее. Дабы не изобретать велосипед, некоторые алгоритмы я взял с этой статьи на английском. Кто не хочет или не может в английский, есть ее перевод на хабре. Все демки и примеры сделаны на движке Godot Engine v 3.2.3 с использованием его встроенного языка.

Думаю в целом его синтаксис ясен, однако оставлю ссылки на некоторые функции:

Система координат

На протяжении всей статьи мы будем работать только с правильными шестиугольниками, у них все стороны равны. Работа с неправильными шестиугольниками лишена смысла в принципе. Если не брать всякие повороты и искажения, существует два вида шестиугольных сеток, вертикально и горизонтально ориентированных:

  • Такие я буду называть вертикальными (у ячейки есть явный вертикальный сосед):

  • А такие горизонтальными (у ячейки есть явный горизонтальный сосед):

Уже на этапе введения координат могут возникнуть проблемы. Дело в том, что в шестиугольной сетке невозможно ввести типичную декартову систему координат - всегда будет ось, вдоль которой у ячейки не будет явного соседа. На самом деле существует огромное количество систем координат для таких сеток. Более подробно о них рассказано в упомянутых вначале статьях. Я рассказывать про каждую не буду, все таки пост больше про использование сеток, а не их исследование.

Пожалуй первое, что приходит в голову, это таки впихнуть декартовы оси, однако для этого по одному из направлений координаты придется смещать:

Такая система называется координатами смещения. Бывает два вида координат смещения - четные и нечетные. Они отличаются лишь выбором соседа для смещения. В моем примере использованы нечетные координаты смещения, т.е. ячейка смещается к нижней в случае вертикальной ориентации или к правой в случае горизонтальной.

Главная проблема этих координат состоит в выборе базисов. Для разных ячеек базис к следующей ячейке может отличаться от того, по которому мы к ней перешли. Если вы помните из статьи про прямоугольные тайлы, там мы обращали матрицу из базисных векторов и умножали на нее радиус-вектор пикселя, получая координаты ячейки. Здесь так не выйдет, провернув тоже самое мы просто получим квадратную сетку.

Вообще у сетки шестиугольников есть три ярко выраженных оси:

Что то напоминает, не находите? Тут три оси, прям как в пространстве. На самом деле гений тот человек - кто не просто увидел, что если взглянуть на куб под определенным углом, то получится шестиугольник, а еще и додумался использовать трехмерные координаты в двумерной сетке шестиугольников. Правда вот попробовав посчитать координаты на двумерной сетке, могут вскипеть мозги, ведь третья ось тут кажется лишней и ее использование будто только мешает. Для разрешения данной ситуации просто посмотрим откуда взялись кубы:

Для получения сетки шестиугольников надо взглянуть в изометрии на пирамидку, на каждом уменьшении высоты которой увеличивается количество кубиков в ряду на один. Включив фантазию, можно увидеть в каждом кубе шестиугольник. Включив внимательность, можно увидеть в левом нижнем углу координаты. Включив логику, можно увидеть, что сумма этих самых координат всегда равна некоторому числу, которое, кстати говоря, может быть любым, ведь мы сами решаем, откуда начнется система координат. В моем случае это 15, просто потому, что система отсчета в этом редакторе начинается с нижнего дальнего угла (в случае изометрического вида). Нам незачем таскать за собой лишнюю константу, поэтому возьмем ее за ноль. Таким образом, сумма трех координат всегда и везде равна нулю, поэтому третья нам попросту не нужна, ведь мы можем получить ее из двух других. Теперь и получается, что "мешающая" третья ось уходит. Наконец то мы можем спокойно направить базисы и у каждой ячейки всегда будет точный сосед, находящийся вдоль оси:

Т.к. у шестиугольника нет левого верхнего угла, мы можем поместить начало координат по сути в любую точку. Самым оптимальным мне показался центр фигуры, ведь относительно него она симметрична.

Преобразование координат

Пожалуй это то, на чем запарываются многие при попытке сделать нечто шестиугольное. Я слышал множество способов, порой они были очень забавные. Например, мне больше всего запомнился способ, где предлагалось сделать невидимую маску с такой же сеткой, где каждая ячейка окрашена в свой цвет, а каждому цвету соответствуют координаты. При смещении курсора смотрим в маску и по цвету определяем координаты. Сложно, с костылями, но работать может. А если мы захотим другой размер? Перерисовывать? Вы тут явно не за этим.

Вообще работать с шестиугольниками неудобно, ведь пиксели то квадратные, поэтому лучше все как то привести к прямоугольникам, что бы можно было использовать типичные матричные преобразования. Для этого найдем диагонали шестиугольника (а - сторона):

Оранжевые (маленькие) диагонали делятся пополам зелеными (большими), а зеленые оранжевыми, если последние провести из середины стороны. Уже получается, что мы можем разделить шестиугольник на 4 прямоугольника. Однако некоторые вершины в таком случае будут лежать где то между углами сетки, а ведь нам хотелось бы, чтобы все они попадали ровно в углы. На самом деле "где то", это ровно по серединке, поэтому разделим большие ячейки еще на пополам, тогда все вершины шестиугольника будут ложиться точно в углы прямоугольной сетки:

Желтую сетку в дальнейшем я буду называть вспомогательной. Для задания ее базисов будем использовать такие значения:

# Для горизонтальных шестиугольниковvar hex_size = 32var short = int(size*sqrt(3)/2) # 1/2 from short hex diagonalvar long = int(size/2) # 1/4 from long hex diagonal

Теперь мы можем выразить базисы шестиугольной сетки, используя базисы вспомогательной сетки:

Запишем все базисы в коде:

...# Transorm2D в godot - это матрица 3x2, где последняя строка указыает# смещение объекта, в дальнейшем она не будет использоваться совсем, # поэтому считайте это просто матрицей 2x2. Сделано это для удобства,# на объяснения никак не повлияет.# У нее есть два атрибута - x и y. Каждый из них это вектор. X - представляет# первый столбец матрицы 2x2 (крайняя строка не учитывается), Y - второй столбец.  var grid_basis = Transform2D() # Матрица базисов вспомогательной сеткиvar hex_basis = Transform2D() # Матрица базисов гексагональной сетки...  # Для вертикальной сеткиgrid_basis.x = Vector2(long, 0)grid_basis.y = Vector2(0, short)hex_basis.x = grid_basis.x*3 + grid_basis.yhex_basis.y = grid_basis.y*2# Для горизонтальной сеткиgrid_basis.x = Vector2(short, 0)grid_basis.y = Vector2(0, long)hex_basis.x = grid_basis.x*2hex_basis.y = grid_basis.x+grid_basis.y*3

Я пользуюсь именно встроенными средствами Godot для упрощения работы в целом. Все подобные места будут поясняться в общем виде, как бы это делалось без встроенных возможностей.

Шестиугольник в пиксель

Вот за что я люблю математику, так это за то, что если она работает, то работает везде. Так что для получения центра шестиугольника в пикселях из его координат на сетке надо просто умножить базисы на координаты:

func hex2pixel(hex):return hex.x*hex_basis.x + hex.y*hex_basis.y

Для получения каждой вершины просто прибавляем по нужным базисам:

Тогда для получения вершины в коде прибавляем нужный вектор (см. картинку выше) к центру шестиугольника. Я написал только функцию получения массива вершин, ибо по отдельности они почти никогда не нужны.

Для вертикальных шестиугольников:

func _get_vert_hex_vertices(hex):var pixel = hex2pixel(hex)return PoolVector2Array([pixel+2*grid_basis.x,pixel+grid_basis.x+grid_basis.y,pixel-grid_basis.x+grid_basis.y,pixel-2*grid_basis.x,pixel-grid_basis.x-grid_basis.y,pixel+grid_basis.x-grid_basis.y])

Для горизонтальных шестиугольников:

func _get_hor_hex_vertices(hex):var pixel = hex2pixel(hex)return PoolVector2Array([pixel+grid_basis.x-grid_basis.y,pixel+grid_basis.x+grid_basis.y,pixel+2*grid_basis.y,pixel-grid_basis.x+grid_basis.y,pixel-grid_basis.x-grid_basis.y,pixel-2*grid_basis.y,])

Пиксель в шестиугольник

Наверно самая интригующая часть поста. На самом деле ничего нового почти не будет, ведь для получения вещественных координат ячейки все также обращаем матрицу и умножаем на нее радиус-вектор пикселя:

Для горизонтальной ориентации

В коде это записывается так:

func pixel2hex(pixel):var x = pixel.x/(2*cw) - pixel.y/(6*ch)var y = pixel.y/(3*ch)return round_hex(Vector2(x, y))
Для вертикальной ориентации

В коде это записывается так:

func pixel2hex(pixel):var x = pixel.x/(3*cw)var y = pixel.y/(2*ch) - pixel.x/(6*cw)return round_hex(Vector2(x, y))

Однако я буду пользоваться функцией affine_inverse у Transform2D, для того, что бы при изменении базисных векторов постоянно не менять функции преобразований, позже увидите зачем это надо. Вы скорее всего работаете в другой среде (и зря), поэтому вам придется писать обращение матрицы самостоятельно. Кто не знает как это делается, или забыл, может почитать тут, или переписать следующие функции в свой язык:

Функции
func invert_basis(basis:Transform2D): # обращение матрицыvar det = basis.x.x*basis.y.y - basis.y.x*basis.x.yvar idet = 1.0/det# Я не уверен что Transform2D передается по значению, по этому# копирую данные в новый объектvar res = basisres.y.y = basis.x.x*idetres.x.x = basis.y.y*idetres.x.y = -basis.x.y*idetres.y.x = -basis.y.x*idetreturn resfunc vec_mul_basis(vec:Vector2, basis:Transform2D): # умножение вектора на матрицуvar x = vec.x*basis.x.x + vec.y*basis.y.xvar y = vec.x*basis.x.y + vec.y*basis.y.yreturn Vector2(x, y)func pixel2hex(pixel):return round_hex(vec_mul_basis(pixel, invert_basis(hex_basis)))

Средствами Godot это можно записать всего в одну строчку:

func pixel2hex(pixel):return round_hex(hex_basis.affine_inverse().xform(pixel))

Тут .xform(Vector2) - это метод для умножения матрицы на переданный в него вектор, аналог vec_mul_basis из моего кода. Такой код работает для обеих ориентаций.

Если вы хотя бы бегло прочитали вышеприведенный код, то наверняка заметили функцию round_hex вместо типичных приведений к int. Дело в том, что полных координат у шестиугольника 3, и они обладают условием x + y + z = 0, а после округления каждой из них равенство может нарушиться. Поэтому необходимо задать координату с наибольшей ошибкой округления через две другие, тогда условие выполнится. Да, данный метод полностью слизан отсюда, однако зачем придумывать велосипед, если можно взять готовый? Так же тут используется именно round, а не приведение к int, ведь основание каждой ячейки находится в ее центре, а не в левом верхнем углу, как в случае с прямоугольными сетками:

func round_hex(hex:Vector2):var rx = round(hex.x)var ry = round(hex.y)var rz = round(-hex.x-hex.y) # z = -x-yvar x_diff = abs(hex.x-rx) # Ошибка округления xvar y_diff = abs(hex.y-ry) # Ошибка округления yvar z_diff = abs(-hex.x-hex.y-rz) # Ошибка округления zif x_diff > y_diff and x_diff > z_diff:rx = -ry-rz # Приведение под равенствоelif y_diff > z_diff:ry = -rx-rz # Приведение под равенствоreturn Vector2(rx, ry)

Работает все замечательно:

Вертикальная ориентация
Горизонтальная ориентация

Однако я надеюсь вы не думаете, что сетки, это вручную нарисованные текстуры. Я не самоубийца.

Рисование сеток

Все примеры и объяснения я буду приводить на горизонтальной сетке, ведь для вертикальной они аналогичны. Для рисования последних я просто оставлю готовую функцию.

Для рисования сетки необходимо знать ее размеры. Размеры шестиугольной сетки будем задавать в координатах смещения, так просто понятнее. Тогда по горизонтали будет в два раза больше ячеек вспомогательной сетки, чем шестиугольников, ведь по горизонтали у шестиугольника 2 ячейки. Для нахождения вертикальных размеров заметим, что для перехода к нижнему шестиугольнику мы вниз проходим три вертикальных базиса, однако для крайнего шестиугольника соседа снизу нет, поэтому самая нижняя чать остается неучтенной, так что нужно прибавить единицу:

const hex_map_size = Vector2(7, 7) # размер сетки шестиугольниковvar grid_map_size:Vector2 # размер вспомогательной сетки...grid_map_size.x = hex_map_size.x*2grid_map_size.y = hex_map_size.y*3+1

Для вертикальных шестиугольников все аналогично, только формулы для вычисления ширины и высоты меняются местами:

...grid_map_size.x = hex_map_size.x*3+1grid_map_size.y = hex_map_size.y*2

Сетку из шестиугольников можно разбить на две части, на вертикальные линии и на паттерн вершин:

Будем рисовать каждую составляющую по отдельности. Начнем с вертикальных линий. Можно заметить, что в каждом ряду линии рисуются с интервалом в 2 ячейки, а каждый четный по счету ряд начинается со второй, а не с первой ячейки. Также увидим то, что первый ряд начинается со со смещением в одну ячейку относительно верхей границы, а ряды разделяет одна ячейка. С учетом того, что длина штриха в две ячейки, между верхними концами отрезков находятся три ячейки. Тогда в цикле начинаем с единицы и идем до нижнего края карты с шагом 3, а во втором цикле начинаем со столбца, индекс которого обратен четности ряда, проще говоря 1-i%2, и идем до правого края карты, но на единицу больше, чтобы нарисовать таки крайние линии, с шагом в две ячейки. В кадой итерации второго цикла просто рисуем отрезок высотой две ячейки:

for i in range(1, grid_map_size.y, 3):for j in range(1-i%2, grid_map_size.x+1, 2):VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i, grid_basis.x*j+grid_basis.y*(i+2), color, width, antialiasing)

Этот код будет рисовать только вертикальные линии. Теперь нужно нарисовать паттерн вершин. Есть всего два вида наклонных линий, от нижнего левого угла к верхнему правому (их я буду называть нижними диагоналями), или от верхнего левого к нижнему правому (их я буду называть верхними диагоналями), причем в одной строке они чередуются, а в следующей строке паттерн меняет четность. Четным я буду называть паттерн, начинающийся с нижней диагонали, нечетным - начинающийся в верхней диагонали.

Каждые две строки паттерна разделяют две ячейки, поэтому чтобы перейти от одной к следующей, необходимо сдвинуться на 3 строки вниз. Как я уже говорил, каждую строку паттерн меняет четность, и так совпало, что при переходе к следующей строке ее индекс тоже меняет четность.

Для рисования паттернов пробегаем каждую третью строку, начиная с нулевой, а в каждой строке пробегаемся по столбцам. Тогда для выбора нужной линии сравниваем четности строки и столбца, если они совпадают, то рисуем нижнюю диагональ, иначе верхнюю. Тут я считаю нужным показать, как задается каждый угол ячейки с координатами {j, i} , где j - столбец (как бы x), i - строка (как бы y). Размер ячейки увеличен только для демонстрации:

В коде этот алгоритм выглядит так:

# Drawing verticesfor i in range(0, grid_map_size.y, 3): # рисуем на каждой третьей строкеfor j in range(grid_map_size.x): # крайний столбец не захватываем, т.к. в коде прибавляется единицаif i%2 == j%2: # нижняя диагональCanvas.line(surf, grid_basis.x*j+grid_basis.y*(i+1), grid_basis.x*(j+1)+grid_basis.y*i, color, width, antialiasing)else: # верхняя диагональCanvas.line(surf, grid_basis.x*j+grid_basis.y*i-offset, grid_basis.x*(j+1)+grid_basis.y*(i+1), color, width, antialiasing)

Однако просто нарисовав на холсте сетку, получатся непонятки с координатами:

Дело все в том, что начало координат находится в центре шестиугольника, а начинаем рисовать мы с левого верхнего угла вспомогательной сетки, также как мы это делали с обычными сетками. Для рисования сетки правильно, т.е. из начала координат, необходимо сдвинуть рисование на одну ячейку влево и на две вверх, ведь именно под таким смещением находится начало координат.

Однако и на этом не все. Если просто объеденить весь код выше в одну функцию, то при четных высотах она будет рисовать ненужные хвосты:

Эти хвосты рисуются прямо в углах вспомогательной сетки, поэтому просто добавим уловие, что мы в них не находимся, иначе просто не рисуем тут диагональ.

Соеденив все вместе, получим такую функцию:

func _draw_hor_rect_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var offset = grid_basis.x+grid_basis.y*2# Drawing vertical linesfor i in range(1, grid_map_size.y, 3):for j in range(1-i%2, grid_map_size.x+1, 2):VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i-offset, grid_basis.x*j+grid_basis.y*(i+2)-offset, color, width, antialiasing)# Drawing verticesfor i in range(0, grid_map_size.y, 3):for j in range(grid_map_size.x):if int(hex_map_size.y)%2 == 1 or not (i == grid_map_size.y-1 and (j == 0 or j == grid_map_size.x-1)):if i%2 == j%2:VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(i+1)-offset, grid_basis.x*(j+1)+grid_basis.y*i-offset, color, width, antialiasing)else:VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i-offset, grid_basis.x*(j+1)+grid_basis.y*(i+1)-offset, color, width, antialiasing)

При рисовании вспомогательной сетки кстати тоже используем смещение. На всякий случай оставлю тут и ее рисование, хотя это есть в моей статье про прямоугольные сетки:

func draw_auxiliary_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var offset = grid_basis.x+grid_basis.y*2for i in grid_map_size.x+1:Canvas.line(surf, grid_basis.x*i-offset, grid_basis.x*i+grid_basis.y*grid_map_size.y-offset, color, width, antialiasing)for i in grid_map_size.y+1:Canvas.line(surf, grid_basis.y*i-offset, grid_basis.x*grid_map_size.x+grid_basis.y*i-offset, color, width, antialiasing)

И, как и обещал, функция для рисования вертикально-ориентированной сетки:

func _draw_vert_rect_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var offset = grid_basis.x*2+grid_basis.y# Drawing horizontal linesfor i in range(1, grid_map_size.x, 3):for j in range(1-i%2, grid_map_size.y+1, 2):VisualServer.canvas_item_add_line(surf, grid_basis.x*i+grid_basis.y*j-offset, grid_basis.x*(i+2)+grid_basis.y*j-offset, color, width, antialiasing)# Drawing verticesfor i in range(0, grid_map_size.x, 3):for j in range(grid_map_size.y):if int(hex_map_size.x)%2 == 1 or not(i == grid_map_size.x-1 and (j == 0 or j == grid_map_size.y-1)):if j%2 == i%2:VisualServer.canvas_item_add_line(surf, grid_basis.x*(i+1)+grid_basis.y*j-offset, grid_basis.x*i+grid_basis.y*(j+1)-offset, color, width, antialiasing)else:VisualServer.canvas_item_add_line(surf, grid_basis.x*i+grid_basis.y*j-offset, grid_basis.x*(i+1)+grid_basis.y*(j+1)-offset, color, width, antialiasing)

Результат вполне неплох, нигде линии не рисуются дважды (сетка рисовалась немного прозрачной на черном фоне, а яркость линий везде оинакова):

Сетка вертикальных шестиугольников
Сетка горизонтальных шестиугольников

Однако рендерить такие сетки в реальном времени довольно затратно, тут рисуется множетсво отдельных отрезков, что сильно замедляет работу. Просто для примера, пустое черно окно у меня имеет fps около 950, а при рисовании белым цветом Color8(255, 255, 255, 200) шестиугольной сетки размера 10x10 и размером шестиугольнкиа 32 пикселя, fps примерно 260. Так что рисовать сетки процедурно резонно только на начальном этапе разработки, потом лучше отрендерить ее заранее и использовать как текстуру.

Рисование шестиугольной сетки шестиугольников

Сетки шестиугольников конечно здорово, но иногда хочется чего то большего. Например больше шестиугольников, поэтому сделаем большой шестиугольник из маленьких. Такая сетка может пригодиться, если мы, например, делаем шестиугольные шахматы.

Рисование этой сетки лишь немного сложнее рисования обычной, хотя на первый взгляд мой код похож на код сатаны. Поробую объяснить что откуда взялось. Результат будет примерно таков:

Для начала нам конечно же нужны размеры сеток. Т.к. мы рисуем сетку в виде правильного шестиугольника, ее размер можно задать одним значением. В коде я использую тип Vector2 только для совмещения этой переменной с прямоугольнйо сеткой, при рисовании будет использоваться только X координата. Тогда для задания размеров вспомогательной сетки нужно найти диагональ большого шестиугольника. Для этого вспомним, что бОльшая диагональ шестиугольника в два раза больше его стороны. В нашем случае шестиугольник состоит из маленьких таких же. В таком случае центр будет учитываться два раза, поэтому вычтем единицу:

var hex_map_size = Vector2(5, <не имеет значения>)...var diagonal = hex_map_size.x*2-1

Размеры вспомогательной сетки задаются аналогично тому, что мы делали ранее. Для горизонтальной ориентации ширина будет в два раза больше диагонали, а высота в три раза и еще на единицу больше:

...grid_map_size.x = diagonal*2grid_map_size.y = diagonal*3+1

Для вертикальных значения меняются местами:

grid_map_size.x = diagonal*3+1grid_map_size.y = diagonal*2

Шестиугольную сетку можно точно также разбить на две части, на паттерн вершин и вертикальные линии:

Начнем с рисования вершин. Рисовать каждый слой по-отдельности не имеет сымсла, ведь фигура симметрична. Мы можем разделить всю вспомогательную сетку на четыре части и, нарисовав одну четверть, отобразить ее зеркально на все остальные. Сетка кстати всегда будет делиться ровно, и вот почему. По горизонтали понятно, ведь в формуле ширины мы удваиваем диагональ шестиугольной карты. А эта самая диагональ будет всегда нечетна, ведь мы от четного числа отнимаем единицу (hex_map_size.x*2-1). В формуле высоты вспомогательной сетки мы умножаем эту диагональ на 3, и результат получится тоже нечетным, а после прибавления единицы все выражение становится четным. Таким образом ширина и высота вспомогательной сетки всегда четны, и как следствие, ее можно всегда разделить на четыре одинаковые части:

Тогда мы можем пробегать в циклах только до половин размеров вспомогательной сетки, а для рисования в других частях будем просто отражать точки рисования.

При такой форме сетки рисование вершин начинается не с самой левой колонки и паттерн всегда четный (при рассмотрении одной четверти). При увеличении размера сетки на единицу, первый шестиугольник в самом верхем ряду сдвигается на одну ячейку вспомогательной сетки, т.к. мы увеличиваем в том числе и размер левой грани, в которой под каждым шестиугольником следующий находится не только ниже, но и левее на половину шестиугольника, т.е. на одну ячейку. Тогда каждый следующий паттерн начинает рисоватся на ячейку ближе к левому краю, а самый первый ряд имеет смещение на единицу меньшее, чем размер шестиугольной карты, т.к. первый шестиугольник в нем тоже является частью левой грани, так что под ним шестиугольников меньше на эту самую единицу, чем размер карты.

Также вспомним, что каждый следующий паттерн рисуется со смещением в три ячейки от предыдущего, поэтому в цикле идем от нуля до половины высоты вспомогательной сетки с шагом в три, попутно вычисляя смещение для каждого ряда:

for i in range(0, grid_map_size.y/2, 3): # Drawing vertices  # тут i/3 потому что мы идем со смещением 3, а при расчетах нужен индекс  start = hex_map_size.x-1 - i/3  

Проходить по ширине будем также до середины вспомогательной сетки, начиная с выщитанного ранее смщения:

for i in range(0, grid_map_size.y/2, 3): # Drawing vertices  # тут i/3 потому что мы идем со смещением 3, у при расчетах нужен индекс паттерна  start = hex_map_size.x-1 - i/3    for j in range(start, grid_map_size.x/2):  pass # Пока ничего не делаем

Каждый паттерн при рисовании шестиугольной карты четный, а вот смещение чередует свою четность. Четность начального смещения напрямую зависит от четности размера карты - они противоположны. Двигаясь вниз по рядам паттерна, индекс ряда меняет четность, как и смещение для этого ряда. Если помните, для выбора диагонали при рисовании прямоугольной сетки мы сравнивали четность ряда и колонки. Тут же меняются обе четности, и при разных раземрах карты они будут то совпадать при начальных значениях, то нет.

Приведу пример. Мы рисуем нижнюю диагональ, если индексы ряда и колонки совпадают, иначе верхнюю. Поставим размер карты 5. Тогда начальное смещение будет четным, как и индекс первого ряда (i=0). Исходя из условия, рисуем нижнюю диагональ, как и должно быть. Однако поставив четный размер, скажем, 4, начальное смещение будет нечетным, а вот индекс первого ряда по прежнему четным. Тогда взглянув на условие компьютер выберет верхюю диагональ, а ведь нам все еще для начала нужна нижняя. Вот как это будет выглядеть:

Тут на самом деле всего лишь надо поменять четность паттерна, тогда все встанет на свои места. Получается, выбор условия рисвания нижней диагонали зависит от четности самого размера карты. Тут можно заметить, что разница четностей столбца и ряда в каждой первой диагонали ряда паттерна обратна четности размера карты. А при рисовании паттерна диагонали просто чередуются, как и чередуется четность столбца, и как следствие чередуется равенство разностей четностей ряда и столбца и четности размера карты. Поэтому для выбора диагонали используем равентво abs(i%2 - j%2) != parity, где parity - это остаток от деления размера карты на два. Если это условие верно, рисуем нижнюю диагональ, иначе верхнюю. Получим то что нужно, осталось отразить по красным линиям:

Код рисования четверти всего паттерна
func _draw_hor_hex_grid(surf:RID, color:Color):var parity = int(hex_map_size.x)%2var startfor i in range(0, grid_map_size.y/2, 3): # Drawing verticesstart = hex_map_size.x - i/3 - 1for j in range(start, grid_map_size.x/2):if abs(i%2 - j%2) != parity:# Down diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(i+1), grid_basis.x*(j+1)+grid_basis.y*i, color)      else:# Top diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(i), grid_basis.x*(j+1)+grid_basis.y*(i+1), color)

Для отражения точек рисования отнимаем от края вспомогательной сетки индекс точки, ничего сложного. А вот в коде это выглядит громоздко. Взгляните сами:

func _draw_hor_hex_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var parity = int(hex_map_size.x)%2var startfor i in range(0, grid_map_size.y/2, 3): # Drawing verticesstart = hex_map_size.x - i/3 - 1for j in range(start, grid_map_size.x/2):if abs(i%2 - j%2) != parity:# Down diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(i+1), grid_basis.x*(j+1)+grid_basis.y*i, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i+1), grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*i, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(grid_map_size.y-i-1), grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i), color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(grid_map_size.y-i-1), grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(grid_map_size.y-i), color)else:# Top diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(i), grid_basis.x*(j+1)+grid_basis.y*(i+1), color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i), grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(i+1), color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(grid_map_size.y-i), grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i-1), color)VisualServer.ca

Но ничего страшного, ковид пережили - переживем и это. Зато получаем правильный паттерн для сеток с четными и нечетным размером:

Если вы что то поняли во всей этой мешанине четностей, то либо вы гений, либо у меня получилось что то объяснить. Однако дальше не легче, но радует то, что мы почти нарисовали сетку. Осталось добавить вертикальные линии - это будет финальным боссом в рассказе о рисовании сеток.

Тут я не стал ничего придумывать с отражениями, ведь отрезки рисуются в две ячейки и при отражении некоторые места будут рисоваться два раза, а обрабатывать кучу исключений отдельно не очень хочется. Самым простым решение мне показалось рисовать вертикальные линии также, как мы это делали с прямоугольной сеткой, только отбрасывать линии в углах. Напомню код рисования линий в простой прямоугольной сетке:

for i in range(1, grid_map_size.y, 3):for j in range(1-i%2, grid_map_size.x+1, 2):VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i, grid_basis.x*j+grid_basis.y*(i+2), color, width, antialiasing)

Однако просто скопипастив его в нашу функцию, получим кривое рисование при четных размерах карты, ведь при них первый ряд должен иметь смещение в единицу, а при нечетных этого смещения быть не должно. Это вытекает из смещения первого шестиугольника в первом ряду, при четных значения оно нечетно поэтому и рисуем со смещением, и наоборот. Для выбора смещения сравним четности размера карты и ряда, если они отличаются, то рисуем без смещения, иначе со смещением. Пихать сюда условие не имеет смысла, ведь мы можем выбрать смещение через отличие четности карты и четности столбца конструкцией abs(parity-i%2). Просто напомню - parity это остаток от деления размера карты на два. Проверьте сами, при четных столбцах и нечетных размерах карты получается единица - то самое смещение. Запишем это выражение в смещение в цикле:

for i in range(1, grid_map_size.y, 3):for j in range(abs(parity-i%2), grid_map_size.x+1, 2):VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i, grid_basis.x*j+grid_basis.y*(i+2), color, width, antialiasing)

Цель почти достигнута, осталось избавиться от лишних линий по углам:

Для этого при рисовании линий добавим некоторое условие, что мы хотим нарисовать линию в пределах каких-то границ. Для обозначения границ заметим, что с каждым рядом мы начинаем рисовать на ячейку ближе к левой границе, поэтому границу можно задать как смещение первого ряда минус индекс ряда:

...start = hex_map_size.x-1 - i/3

Однако в нижней половине шестиугольника смещение начинает идти обратно, а индекс ряда только возрастает. Поэтому будем смотерть, в какой половине мы находимся, и выбирать нужную формулу для расчета левой границы. Для нижней части карты используем положение ряда относительно центра карты, просто отняв от его индекса половину ее размера:

...start = (i-grid_map_size.y/2)/3

Это мы задали левые границы. Для правых просто отразим их в силу четности размеров вспомогательной сетки:

for i in range(1, grid_map_size.y, 3):if i <= grid_map_size.y/2:start = hex_map_size.x-1 - i/3else:start = (i-grid_map_size.y/2)/3for j in range(abs(parity-i%2), grid_map_size.x+1, 2):if j >= start and j <= grid_map_size.x-start: # избавляемся от лишних линийVisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i, grid_basis.x*j+grid_basis.y*(i+2), color, width, antialiasing)

Вот и все - финальный босс побежден. Осталось только добавить смещение для расположения сетки в начало координат, offset = grid_basis.x+grid_basis.y*2. Однако тут опять играет роль четность размера карты, так что когда она четна прибавляем к смещению горизонтальный базис ячейки.

Босса то убили, а вот лут забыли. С него мы получили рисование шестиугольных сеток шестиугольников:

Горизонтальная ориентация
func _draw_hor_hex_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var parity = int(hex_map_size.x)%2var offset = grid_basis.x+grid_basis.y*2 + grid_basis.x*(1-parity)var startfor i in range(0, grid_map_size.y/2, 3): # Drawing verticesstart = hex_map_size.x - i/3 - 1for j in range(start, grid_map_size.x/2):if abs(i%2 - j%2) != parity:# Down diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(i+1)-offset, grid_basis.x*(j+1)+grid_basis.y*i-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i+1)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*i-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(grid_map_size.y-i-1)-offset, grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(grid_map_size.y-i-1)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(grid_map_size.y-i)-offset, color)else:# Top diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(i)-offset, grid_basis.x*(j+1)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)for i in range(1, grid_map_size.y, 3):if i <= grid_map_size.y/2:start = hex_map_size.x-1 - i/3else:start = (i-grid_map_size.y/2)/3for j in range(abs(parity-i%2), grid_map_size.x+1, 2):if j >= start and j <= grid_map_size.x-start:VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i-offset, grid_basis.x*j+grid_basis.y*(i+2)-offset, color, width, antialiasing)
Вертикальная ориентация
func _draw_vert_hex_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var parity = int(hex_map_size.x)%2var offset = grid_basis.x*2+grid_basis.y + (1-parity)*grid_basis.yvar startfor j in range(0, grid_map_size.x/2, 3): # Drawing verticesstart = hex_map_size.x - j/3 - 1for i in range(start, grid_map_size.y/2):if abs(i%2 - j%2) != parity:# Down diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*(j+1)+grid_basis.y*(i)-offset, grid_basis.x*(j)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(i)-offset, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(j)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)else:# Top diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(i)-offset, grid_basis.x*(j+1)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)for i in range(1, grid_map_size.x, 3):if i <= grid_map_size.x/2:start = hex_map_size.x-1 - i/3else:start = (i-grid_map_size.x/2)/3for j in range(abs(parity-i%2), grid_map_size.y+1, 2):if j >= start and j <= grid_map_size.y-start:VisualServer.canvas_item_add_line(surf, grid_basis.x*i+grid_basis.y*j-offset, grid_basis.x*(i+2)+grid_basis.y*(j)-offset, color, width, antialiasing)

Пример:

Рисование шестиугольников

Тут на самом деле все просто, можете расслабиться. После этой жести с четностями ничего хуже уже не будет. Для рисования шестиугольников вспомним функции для получения вершин, которые я приводил выше и просто соеденим массив вершин шестиугольника линиями:

Функции для получения вершин, если лень мотать неаверх
func _get_vert_hex_vertices(hex):var pixel = hex2pixel(hex)return PoolVector2Array([pixel+2*grid_basis.x,pixel+grid_basis.x+grid_basis.y,pixel-grid_basis.x+grid_basis.y,pixel-2*grid_basis.x,pixel-grid_basis.x-grid_basis.y,pixel+grid_basis.x-grid_basis.y])func _get_hor_hex_vertices(hex):var pixel = hex2pixel(hex)return PoolVector2Array([pixel+grid_basis.x-grid_basis.y,pixel+grid_basis.x+grid_basis.y,pixel+2*grid_basis.y,pixel-grid_basis.x+grid_basis.y,pixel-grid_basis.x-grid_basis.y,pixel-2*grid_basis.y,])

И рисуем множество линий между точками, не забыв замкнуть цепь:

func _draw_hor_hex(hex, surf, color, width=1.0, antialiasing=false):var points = _get_hor_hex_vertices(hex)points.append(points[0]) # замыкаемVisualServer.canvas_item_add_polyline(surf, points, [color], width, antialiasing)func _draw_vert_hex(hex, surf, color, width=1.0, antialiasing=false):var points = _get_vert_hex_vertices(hex)points.append(points[0]) # замыкаемVisualServer.canvas_item_add_polyline(surf, points, [color], width, antialiasing)

Для заливки шестиугольника, по аналогии с прямоугольником, рисуем полигон:

func _fill_hor_hex(hex, surf, color, antialiasing=false):var points = _get_hor_hex_vertices(hex)VisualServer.canvas_item_add_polygon(surf, points, [color], [], RID(), RID(), antialiasing)func _fill_vert_hex(hex, surf, color, antialiasing=false):var points = _get_vert_hex_vertices(hex)VisualServer.canvas_item_add_polygon(surf, points, [color], [], RID(), RID(), antialiasing)

Выгялдит все это как то так:

Шестиугольные сетки в изометрии

Что может быть лучше сетки шестиугольников? Правильно, сетка шестиугольников в изометрии. Вы могли заметить, что ни в одной функции я не использовал числа - везде я работал с векторами. А это значит, что поменяв базис, автоматически поменяются функции - так и должно работать программирование. Помните, в части про преобразование координат я все вычисления автоматизировал? Так вот, наконец то нам это пригодится.

Как вы уже наверняка поняли, шестиугольная сетка это лишь обертка над обычной прямоугольной, ведь все функции рано или поздно сходятся к работе с базисами вспомогательной сетки. Поэтому для создания изометрии не будем придумывать велосипед, просто зададим ее переменной, отвечающей за искажение отношений горизонтальных размеров к вертикальным:

...const iso_scale = 2.0

Тогда для изменения вида делим y-координату каждого базиса вспомогательной сетки на это искажение:

# Вертикальная ориентацияgrid_basis.x = Vector2(long, 0)grid_basis.y = Vector2(0, short/iso_scale)# Горизонтальная ориентацияgrid_basis.x = Vector2(short, 0)grid_basis.y = Vector2(0, long/iso_scale)

И все, даже не нужно менять базисы шестиугольной сетки, ведь мы их задавали через базисы вспомогательной. Как же хороша эта ваша математика... Вот пример:

На самом деле, благодаря векторным преобразованиям мы можем делать с базисами вспомогательной сетки все что угодно, и все функции все равно будут работать. Поэтому давайте сделаем сетку не просто в изометрии, а еще и повернем ее на 45, также, как мы это делали в статье про прямоугольные сетки:

# для вертикальныхvar pw = int(long*cos(PI/4))var ph = int(short*cos(PI/4))grid_basis.x = Vector2(pw, pw/iso_scale)grid_basis.y = Vector2(-ph, ph/iso_scale)# для горизонтальныхvar pw = int(short*cos(PI/4))var ph = int(long*cos(PI/4))grid_basis.x = Vector2(pw, pw/iso_scale)grid_basis.y = Vector2(-ph, ph/iso_scale)

Напомню, что базисы шестиугольной сетки мы не трогаем, ведь они все так же заданы через базисы вспомогательной. Выглядит вся эта магия как то так:

Красиво, конечно, но игру на этом не сделать. Нужно также уметь что то на этих сетках делать.

Изометрические преобразования

С преобразованиями тоже мудрить ничего не стоит, ведь, напомню, шестиугольная сетка - это только обертка над обычной, поэтому все функции будут работать в штатном режиме. Единственное, что наверно чтоит рассмотреть, это получение ячейки вспомогательной сетки, левый верхний угол которой находится в центре шестиугольника.

Для этого вспомним то, как мы направляли базисы для различных ориентаций шестиугольников. Вот картинка из почти самого начала моего рассказа:

Посмотрев на нее, все сразу становится ясно. В случае горизонтальной ориентации при каждом перемещении по x на шестигольной сетке мы двигаемся на две ячейки вспомогательной, а при движении по y мы движемся на одну ячейку вправо и на три вниз. Для вертикальных применима эта же логика. По этим формулам написать функции можно проще простого:

# Для вертикальныхfunc get_center_cell(hex:Vector2):return Vector2(hex.x*3, hex.y*2+hex.x)# для горизонтальныхfunc get_center_cell(hex:Vector2):return Vector2(hex.x*2+hex.y, hex.y*3)

В изометрии ближние объекты должны рисоваться раньше дальних, и, если помните, в пямоугольных изометрических сетках мы использовали сумму координат. Здесь делаем тоже самое, только находим сумму координат центральной ячейки в шестиугольнике, получаемую по алгоритму выше.

Расстояние на сетке

Часто бывает нужно найти расстояние между двумя шестиугольниками. Для этого заметим, что при перемещении в любой из соседних шестиугольников меняются сразу две координаты из трех, причем не единицу. Тогда сумма модулей всех трех координат либо меняется на два, либо не изменятся вовсе. В таком случае сеточное расстояние от начала координат можно найти как половину суммы модулей трех координат шетиугольника, а для нахождения расстояния между двумя шестиугольниками можно просто найти смещение одного относительно другого через разность. Получается вот такая небольшая функция:

func hex_distance(hex1:Vector2, hex2:Vector2):var dif = (hex2-hex1)return (abs(dif.x) + abs(dif.y) + abs(-dif.x-dif.y))/2 # z = -x-y

Сеточное направление

Начнем с самого простого - выбора направляющего шестиугольника. Кто не понимает о чем речь, заглянет в статью о прямоугольных тайловых мирах. Это один из немногих алгоритмов, где нам понадобится третья координата.

Для нахождения направляющей разделим сетку по трем осям и заметим, что в каждой части получившейся сетки одна из трех координат максимальна по модулю:

Теперь все, что нам нужно, это выбрать нужную часть и, сравнив модули не наибольших координат, выдать одно из осевых направлений, представленное в виде направляющей ячейки. Прямо на осях одна из координат всегда равна нулю, поэтому просто перехватим их как особые случаи. Для указания вдоль оси будем использовать знак разности конечного и начального шестиугольников. Также заметим, что на диагональных ячейках модули не наибольших координат равны, поэтому мы можем смещаться в любую из двух осей. Я выбрал смещение в сторону оси по часовой стрелке, в коде это выражается строгостью знаком сравнения. Для смещения против часовой стоит допустить равентсво. Так выглядит этот алгоритм в коде:

func direct_hex(hex1:Vector2, hex2:Vector2):var dx = hex2.x - hex1.xvar dy = hex2.y - hex1.yvar dz = -hex2.x-hex2.y + hex1.x+hex1.yif dx == 0: # Ось yreturn Vector2(0, sign(dy)) # Возвращаем ось yelif dy == 0: # Ось xreturn Vector2(sign(dx), 0) # Возвращаем ось xelif dz == 0: # Ось zreturn Vector2(sign(dx), sign(dy)) # Возвращаем ось zelse:if abs(dz) > abs(dx) and abs(dz) > abs(dy): # модуль разности по z оказался наибольшимif abs(dx) > abs(dy): # т.к. разность по x больше, значит мы отошли по x дальше, чем по y, значит выдаем ось xreturn Vector2(sign(dx), 0) # возвращаем ось xelse: # т.к. разность по y больше, значит мы отошли по y дальше, чем по x, значит выдаем ось yreturn Vector2(0, sign(dy)) # возвращаем ось y        elif abs(dy) > abs(dx): # модуль разности по y оказался наибольшимif abs(dz) > abs(dx): # по аналогииreturn Vector2(0, sign(dy)) # возвращаем y. Это связанно с представлением z-координаты через две другиеelse: # по аналогииreturn Vector2(sign(dx), sign(dy)) # возвращаем z        else: # модуль разности по x оказался наибольшимif abs(dy) > abs(dz): # по аналогииreturn Vector2(sign(dx), sign(dy)) # возвращаем zelse: # по аналогииreturn Vector2(sign(dx), 0) # возвращаем x

Опять же, тому кто читал мою статью про прямоугольные сетки, понять все это будет проще, ведь в ней я разбирал подобный алгоритм подробнее, однако, я надеюсь, что по комментариям принцип работы алгоритма понятен. Как мы видим, все рабоатет:

На всякий случай скажу, что этот алгоритм не зависит от ориентации шестиугольников, ведь работа идет с их координатами, а координатм внутри сетки вообще плевать на положение шестиугольников в пространстве.

Поиск пути

Основной алгоритм поиска пути тот же, что и у обычной прямоугольной сетки, отличаются только соседи и проверки на нахождение точки внутри карты. Главный алгоритм - A*, его не трогаем совсем.

Соседи у шестиугольника выглядят как то так:

Можно заметить, что соседи также не зависят от ориентации шестиугольников, поэтому в будущем будем пользоваться одной функцией для обоих случаев.

Также у разных видов карты отличаются проверки на принадлежность шестиугольниа им. Алгоритмы для разных ориентаций шестиугольников немного отличаеются, но в целом они похожи, поэтому пояснять я буду только на примере горизонтальных, а для вертикальных оставлю уже готовые функции.

Начнем с прямоугольной карты. Для наглядности напомню как она выглядит:

Синим обозначены границы карты. Оси в такой сетке идут не параллельно сторонам прямоугольника, поэтому просто ограничить их нулем и границей карты не выйдет. Так сработает только для Y оси сетки, а горизонтальные границы зависят от смещения по Y. Перемещаясь вдоль оси Y, расстояние до левой границы в ячейках вспомогательной сетки увеличивается на единицу, значит на половину шестиугольника. Аналогично с правой границей, тоолько до нее расттояние уменьшается. При округлении левой границы используем floor, т.к. когда граница проходит ровно между шестиугольниками, мы вмыбираем тот, что внутри. По аналогии используем ceil для правой границы:

func _in_rect_grid_hor(hex):return hex.x >= -floor(hex.y/2) and hex.x < hex_map_size.x-ceil(hex.y/2) and hex.y < hex_map_size.y and hex.y >= 0

Для вертикальной ориентации логика точно такая же. Вот функция для нее:

func _in_rect_grid_vert(hex):return hex.x >= 0 and hex.x < hex_map_size.x and hex.y >= -floor(hex.x/2) and hex.y < hex_map_size.y-ceil(hex.x/2)

Теперь про шестиугольную карту. Ее вид:

Для простоты вычислений будем считать границы от центра карты. Просто потыкав и посмотрев на координаты я пришел к следующим формулам центров:

# для горизонтальныхfunc _get_hor_hex_map_center():return Vector2(int((hex_map_size.x-1)/2), hex_map_size.x-1)# для вертикальныхfunc _get_vert_hex_map_center():return Vector2(hex_map_size.x-1, int((hex_map_size.x-1)/2))

Каждому смещению по Y соответствует уменьшение длины ряда на единицу, так и будем задавать границы по x. В качестве размеров, ограничивающих карту, возьмем диагональ. Как ее вычислять я рассказывал ранее. Тогда по Y границами будут просто половины этих диагоналей, а по X одна из граней всегда параллельна оси Y, поэтому уменьшаться будет либо правая либо левая граница. Какая именно можно понять по вертикальной половине шестиугольника. Если мы находимся в верхней, то уменьшается левая граница (т.к. правая параллельна оси Y), если в нижней то уменьшается правая граница (т.к. левая паралельна оси Y). А если мы находимся прямо на горизонтальной диагонали то нам плевать, ведь на ней смещение по Y равно нулю.

Вот функции, реализующие данную логику для обеих ориентаций:

# для горизонтальныхfunc _in_hex_grid_hor(hex):    var center = _get_hor_hex_map_center()    var diag = int(hex_map_size.x*2 - 1)    hex -= center # Vector2 passed by value; getting hex regarding map center    if hex.y < 0:        return hex.x >= -diag/2+abs(hex.y) and hex.x <= diag/2 and hex.y >= -diag/2 and hex.y <= diag/2    else:        return hex.x >= -diag/2 and hex.x <= diag/2-abs(hex.y) and hex.y >= -diag/2 and hex.y <= diag/2# для вертикальныхfunc _in_hex_grid_vert(hex):    var center = _get_vert_hex_map_center()    var diag = int(hex_map_size.x*2 - 1)    hex -= center # Vector2 passed by value; getting hex regarding map center    if hex.x < 0:        return hex.y >= -diag/2+abs(hex.x) and hex.y <= diag/2 and hex.x >= -diag/2 and hex.x <= diag/2    else:        return hex.y >= -diag/2 and hex.y <= diag/2-abs(hex.x) and hex.x >= -diag/2 and hex.x <= diag/2

Для проверки поставим условие, что для рисования шестиугольника под курсором он должен быть внутри сетки:

Отлично, теперь можно спокойно реализовывать алгоритм поиска пути:

Ищем путь истинный
class PriorityStack:var items:Arrayfunc _init():items = Array()func empty() -> bool:return items.size() == 0func put(item, priority:int) -> void:if empty():items.append([item, priority])elif priority <= items[0][1]:items.insert(0, [item, priority])elif priority > items[-1][1]:items.append([item, priority])else:for i in range(len(items)):if priority <= items[i][1]:items.insert(i, [item, priority])breakfunc take():return items.pop_front()[0]func in_map(hex):match grid_type:GridTypes.hex:if hex_type == HexTypes.hor:return _in_hex_grid_hor(hex)else: # Verticalreturn _in_hex_grid_vert(hex)GridTypes.rect:if hex_type == HexTypes.vert:return _in_rect_grid_vert(hex)else: # Hor orientationreturn _in_rect_grid_hor(hex)func can_stand(hex:Vector2, obsts:PoolVector2Array):return in_map(hex) and not (hex in obsts)func neighbors(hex_pos:Vector2, obsts:PoolVector2Array):var res:PoolVector2Array = []var _neighbors = PoolVector2Array([Vector2(-1, 0), Vector2(1, -1), Vector2(0, -1), Vector2(1, 0), Vector2(0, 1), Vector2(-1, 1)])for i in _neighbors:if can_stand(i+hex_pos, obsts):res.append(i+hex_pos)return resfunc find_path(start:Vector2, goal:Vector2, obsts:PoolVector2Array):var frontier = PriorityStack.new()frontier.put(start, 0)var came_from = {}var cost_so_far = {}came_from[start] = startcost_so_far[start] = 0var current:Vector2var new_cost:intif not can_stand(goal, obsts):return PoolVector2Array()while not frontier.empty():current = frontier.take()if current == goal:breakfor next in neighbors(current, obsts):new_cost = cost_so_far[current] + 1if not (next in cost_so_far) or new_cost < cost_so_far[next]:cost_so_far[next] = new_costfrontier.put(next, new_cost+hex_distance(goal, next))came_from[next] = currentif frontier.empty() and current != goal:return PoolVector2Array()current = goalvar path = PoolVector2Array([current])while current != start:current = came_from[current]path.append(current)path.invert()path.remove(0) # removes first positionreturn pathfunc hex_distance(hex1:Vector2, hex2:Vector2):var dif = (hex2-hex1)return (abs(dif.x) + abs(dif.y) + abs(-dif.x-dif.y))/2

Данный код я взял напрямую из своей реализации, так что некоторые моменты не освещены, за ненадобностью. Поглазеть на полный код сможете кликнув по ссылке в конце статьи. Так это выглядит:

Растеризация отрезка

Вот с растеризацией у шестиугольной сетки большие проблемы. Можно, конечно, придумать что нибудь с алгоритмом брезенхема для растеризации отрезков, однако я не думаю что вам нужно растеризовывать по 1000 отрезков за кадр, поэтому на оптимизацию позволим себе немного подзабить и воспользуемся линейной интерполяцией, которую кстати и предлагает автор популярной англоязычной статьи. Думаю почти все знают что такое линейная интерполяция, поэтому просто оставлю тут рализацию алгоритма:

Растеризуем нерастеризуемое
func rast_line(hex1, hex2):var N = hex_distance(hex1, hex2)if N == 0: return PoolVector2Array([hex1])var res = PoolVector2Array()for i in range(N+1):res.append(round_hex(lerp(hex1, hex2, i/N)))return res

Вот так это выглядит:

Пару слов в завершение

Вот и подошел столь запутанный рассказ к концу. Я постарался объяснить все максимально подробно и вставлял как можно больше картинок, надеюсь не зря. Никакую маленькую игру я делать не стал, ибо тут и так хаватаеn над чем подумать, поэтому просто оставлю код получившегося класса на почти 500 строк. Я подразумевал его использование через автозагрузку, как я собственно и делал во время работы над ним.

Если я забыл про что рассказать или упустил какие то важные моменты, или же просто ошибаюсь, напишете об этом в комментарии.

Я надеюсь эта статья позволит вам полностью реализовать давние мечты по созданию "убийы героев" или что она позволила просто интересно провести вечер. До скорого!

Подробнее..

Гексагональные тайловые миры

23.05.2021 22:14:34 | Автор: admin

Тайловость в играх очень распространенное явление, особенно в играх инди сегмента. Чаще всего используют квадратные тайлы в них проще всего задать необходимые данные, будь то карта уровня или инвентарь. Однако на квадратных и прямоугольных формах возможности подобной системы не ограничиваются.

В топовых играх конца девяностых - начала нулевых часто можно увидеть шестиугольную сетку заместо квадратной в то время это смотрелось очень интересно, в особенности в сочетании с изометрией. Именно о работе с такими сетками и пойдет речь.

Если вы не читали мою предыдущую статью про прямоугольные сетки, то рекомендую ознакомится, потому как я иногда буду опускать некоторые вещи, ссылаясь именно на нее. Дабы не изобретать велосипед, некоторые алгоритмы я взял с этой статьи на английском. Кто не хочет или не может в английский, есть ее перевод на хабре. Все демки и примеры сделаны на движке Godot Engine v 3.2.3 с использованием его встроенного языка.

Думаю в целом его синтаксис ясен, однако оставлю ссылки на некоторые функции:

Система координат

На протяжении всей статьи мы будем работать только с правильными шестиугольниками, у них все стороны равны. Работа с неправильными шестиугольниками лишена смысла в принципе. Если не брать всякие повороты и искажения, существует два вида шестиугольных сеток, вертикально и горизонтально ориентированных:

  • Такие я буду называть вертикальными (у ячейки есть явный вертикальный сосед):

  • А такие горизонтальными (у ячейки есть явный горизонтальный сосед):

Уже на этапе введения координат могут возникнуть проблемы. Дело в том, что в шестиугольной сетке невозможно ввести типичную декартову систему координат - всегда будет ось, вдоль которой у ячейки не будет явного соседа. На самом деле существует огромное количество систем координат для таких сеток. Более подробно о них рассказано в упомянутых вначале статьях. Я рассказывать про каждую не буду, все таки пост больше про использование сеток, а не их исследование.

Пожалуй первое, что приходит в голову, это таки впихнуть декартовы оси, однако для этого по одному из направлений координаты придется смещать:

Такая система называется координатами смещения. Бывает два вида координат смещения - четные и нечетные. Они отличаются лишь выбором соседа для смещения. В моем примере использованы нечетные координаты смещения, т.е. ячейка смещается к нижней в случае вертикальной ориентации или к правой в случае горизонтальной.

Главная проблема этих координат состоит в выборе базисов. Для разных ячеек базис к следующей ячейке может отличаться от того, по которому мы к ней перешли. Если вы помните из статьи про прямоугольные тайлы, там мы обращали матрицу из базисных векторов и умножали на нее радиус-вектор пикселя, получая координаты ячейки. Здесь так не выйдет, провернув тоже самое мы просто получим квадратную сетку.

Вообще у сетки шестиугольников есть три ярко выраженных оси:

Что то напоминает, не находите? Тут три оси, прям как в пространстве. На самом деле гений тот человек - кто не просто увидел, что если взглянуть на куб под определенным углом, то получится шестиугольник, а еще и додумался использовать трехмерные координаты в двумерной сетке шестиугольников. Правда вот попробовав посчитать координаты на двумерной сетке, могут вскипеть мозги, ведь третья ось тут кажется лишней и ее использование будто только мешает. Для разрешения данной ситуации просто посмотрим откуда взялись кубы:

Для получения сетки шестиугольников надо взглянуть в изометрии на пирамидку, на каждом уменьшении высоты которой увеличивается количество кубиков в ряду на один. Включив фантазию, можно увидеть в каждом кубе шестиугольник. Включив внимательность, можно увидеть в левом нижнем углу координаты. Включив логику, можно увидеть, что сумма этих самых координат всегда равна некоторому числу, которое, кстати говоря, может быть любым, ведь мы сами решаем, откуда начнется система координат. В моем случае это 15, просто потому, что система отсчета в этом редакторе начинается с нижнего дальнего угла (в случае изометрического вида). Нам незачем таскать за собой лишнюю константу, поэтому возьмем ее за ноль. Таким образом, сумма трех координат всегда и везде равна нулю, поэтому третья нам попросту не нужна, ведь мы можем получить ее из двух других. Теперь и получается, что "мешающая" третья ось уходит. Наконец то мы можем спокойно направить базисы и у каждой ячейки всегда будет точный сосед, находящийся вдоль оси:

Т.к. у шестиугольника нет левого верхнего угла, мы можем поместить начало координат по сути в любую точку. Самым оптимальным мне показался центр фигуры, ведь относительно него она симметрична.

Преобразование координат

Пожалуй это то, на чем запарываются многие при попытке сделать нечто шестиугольное. Я слышал множество способов, порой они были очень забавные. Например, мне больше всего запомнился способ, где предлагалось сделать невидимую маску с такой же сеткой, где каждая ячейка окрашена в свой цвет, а каждому цвету соответствуют координаты. При смещении курсора смотрим в маску и по цвету определяем координаты. Сложно, с костылями, но работать может. А если мы захотим другой размер? Перерисовывать? Вы тут явно не за этим.

Вообще работать с шестиугольниками неудобно, ведь пиксели то квадратные, поэтому лучше все как то привести к прямоугольникам, что бы можно было использовать типичные матричные преобразования. Для этого найдем диагонали шестиугольника (а - сторона):

Оранжевые (маленькие) диагонали делятся пополам зелеными (большими), а зеленые оранжевыми, если последние провести из середины стороны. Уже получается, что мы можем разделить шестиугольник на 4 прямоугольника. Однако некоторые вершины в таком случае будут лежать где то между углами сетки, а ведь нам хотелось бы, чтобы все они попадали ровно в углы. На самом деле "где то", это ровно по серединке, поэтому разделим большие ячейки еще на пополам, тогда все вершины шестиугольника будут ложиться точно в углы прямоугольной сетки:

Желтую сетку в дальнейшем я буду называть вспомогательной. Для задания ее базисов будем использовать такие значения:

# Для горизонтальных шестиугольниковvar hex_size = 32var short = int(size*sqrt(3)/2) # 1/2 from short hex diagonalvar long = int(size/2) # 1/4 from long hex diagonal

Теперь мы можем выразить базисы шестиугольной сетки, используя базисы вспомогательной сетки:

Запишем все базисы в коде:

...# Transorm2D в godot - это матрица 3x2, где последняя строка указыает# смещение объекта, в дальнейшем она не будет использоваться совсем, # поэтому считайте это просто матрицей 2x2. Сделано это для удобства,# на объяснения никак не повлияет.# У нее есть два атрибута - x и y. Каждый из них это вектор. X - представляет# первый столбец матрицы 2x2 (крайняя строка не учитывается), Y - второй столбец.  var grid_basis = Transform2D() # Матрица базисов вспомогательной сеткиvar hex_basis = Transform2D() # Матрица базисов гексагональной сетки...  # Для вертикальной сеткиgrid_basis.x = Vector2(long, 0)grid_basis.y = Vector2(0, short)hex_basis.x = grid_basis.x*3 + grid_basis.yhex_basis.y = grid_basis.y*2# Для горизонтальной сеткиgrid_basis.x = Vector2(short, 0)grid_basis.y = Vector2(0, long)hex_basis.x = grid_basis.x*2hex_basis.y = grid_basis.x+grid_basis.y*3

Я пользуюсь именно встроенными средствами Godot для упрощения работы в целом. Все подобные места будут поясняться в общем виде, как бы это делалось без встроенных возможностей.

Шестиугольник в пиксель

Вот за что я люблю математику, так это за то, что если она работает, то работает везде. Так что для получения центра шестиугольника в пикселях из его координат на сетке надо просто умножить базисы на координаты:

func hex2pixel(hex):return hex.x*hex_basis.x + hex.y*hex_basis.y

Для получения каждой вершины просто прибавляем по нужным базисам:

Тогда для получения вершины в коде прибавляем нужный вектор (см. картинку выше) к центру шестиугольника. Я написал только функцию получения массива вершин, ибо по отдельности они почти никогда не нужны.

Для вертикальных шестиугольников:

func _get_vert_hex_vertices(hex):var pixel = hex2pixel(hex)return PoolVector2Array([pixel+2*grid_basis.x,pixel+grid_basis.x+grid_basis.y,pixel-grid_basis.x+grid_basis.y,pixel-2*grid_basis.x,pixel-grid_basis.x-grid_basis.y,pixel+grid_basis.x-grid_basis.y])

Для горизонтальных шестиугольников:

func _get_hor_hex_vertices(hex):var pixel = hex2pixel(hex)return PoolVector2Array([pixel+grid_basis.x-grid_basis.y,pixel+grid_basis.x+grid_basis.y,pixel+2*grid_basis.y,pixel-grid_basis.x+grid_basis.y,pixel-grid_basis.x-grid_basis.y,pixel-2*grid_basis.y,])

Пиксель в шестиугольник

Наверно самая интригующая часть поста. На самом деле ничего нового почти не будет, ведь для получения вещественных координат ячейки все также обращаем матрицу и умножаем на нее радиус-вектор пикселя:

Для горизонтальной ориентации

В коде это записывается так:

func pixel2hex(pixel):var x = pixel.x/(2*cw) - pixel.y/(6*ch)var y = pixel.y/(3*ch)return round_hex(Vector2(x, y))
Для вертикальной ориентации

В коде это записывается так:

func pixel2hex(pixel):var x = pixel.x/(3*cw)var y = pixel.y/(2*ch) - pixel.x/(6*cw)return round_hex(Vector2(x, y))

Однако я буду пользоваться функцией affine_inverse у Transform2D, для того, что бы при изменении базисных векторов постоянно не менять функции преобразований, позже увидите зачем это надо. Вы скорее всего работаете в другой среде (и зря), поэтому вам придется писать обращение матрицы самостоятельно. Кто не знает как это делается, или забыл, может почитать тут, или переписать следующие функции в свой язык:

Функции
func invert_basis(basis:Transform2D): # обращение матрицыvar det = basis.x.x*basis.y.y - basis.y.x*basis.x.yvar idet = 1.0/det# Я не уверен что Transform2D передается по значению, по этому# копирую данные в новый объектvar res = basisres.y.y = basis.x.x*idetres.x.x = basis.y.y*idetres.x.y = -basis.x.y*idetres.y.x = -basis.y.x*idetreturn resfunc vec_mul_basis(vec:Vector2, basis:Transform2D): # умножение вектора на матрицуvar x = vec.x*basis.x.x + vec.y*basis.y.xvar y = vec.x*basis.x.y + vec.y*basis.y.yreturn Vector2(x, y)func pixel2hex(pixel):return round_hex(vec_mul_basis(pixel, invert_basis(hex_basis)))

Средствами Godot это можно записать всего в одну строчку:

func pixel2hex(pixel):return round_hex(hex_basis.affine_inverse().xform(pixel))

Тут .xform(Vector2) - это метод для умножения матрицы на переданный в него вектор, аналог vec_mul_basis из моего кода. Такой код работает для обеих ориентаций.

Если вы хотя бы бегло прочитали вышеприведенный код, то наверняка заметили функцию round_hex вместо типичных приведений к int. Дело в том, что полных координат у шестиугольника 3, и они обладают условием x + y + z = 0, а после округления каждой из них равенство может нарушиться. Поэтому необходимо задать координату с наибольшей ошибкой округления через две другие, тогда условие выполнится. Да, данный метод полностью слизан отсюда, однако зачем придумывать велосипед, если можно взять готовый? Так же тут используется именно round, а не приведение к int, ведь основание каждой ячейки находится в ее центре, а не в левом верхнем углу, как в случае с прямоугольными сетками:

func round_hex(hex:Vector2):var rx = round(hex.x)var ry = round(hex.y)var rz = round(-hex.x-hex.y) # z = -x-yvar x_diff = abs(hex.x-rx) # Ошибка округления xvar y_diff = abs(hex.y-ry) # Ошибка округления yvar z_diff = abs(-hex.x-hex.y-rz) # Ошибка округления zif x_diff > y_diff and x_diff > z_diff:rx = -ry-rz # Приведение под равенствоelif y_diff > z_diff:ry = -rx-rz # Приведение под равенствоreturn Vector2(rx, ry)

Работает все замечательно:

Вертикальная ориентация
Горизонтальная ориентация

Однако я надеюсь вы не думаете, что сетки, это вручную нарисованные текстуры. Я не самоубийца.

Рисование сеток

Все примеры и объяснения я буду приводить на горизонтальной сетке, ведь для вертикальной они аналогичны. Для рисования последних я просто оставлю готовую функцию.

Для рисования сетки необходимо знать ее размеры. Размеры шестиугольной сетки будем задавать в координатах смещения, так просто понятнее. Тогда по горизонтали будет в два раза больше ячеек вспомогательной сетки, чем шестиугольников, ведь по горизонтали у шестиугольника 2 ячейки. Для нахождения вертикальных размеров заметим, что для перехода к нижнему шестиугольнику мы вниз проходим три вертикальных базиса, однако для крайнего шестиугольника соседа снизу нет, поэтому самая нижняя чать остается неучтенной, так что нужно прибавить единицу:

const hex_map_size = Vector2(7, 7) # размер сетки шестиугольниковvar grid_map_size:Vector2 # размер вспомогательной сетки...grid_map_size.x = hex_map_size.x*2grid_map_size.y = hex_map_size.y*3+1

Для вертикальных шестиугольников все аналогично, только формулы для вычисления ширины и высоты меняются местами:

...grid_map_size.x = hex_map_size.x*3+1grid_map_size.y = hex_map_size.y*2

Сетку из шестиугольников можно разбить на две части, на вертикальные линии и на паттерн вершин:

Будем рисовать каждую составляющую по отдельности. Начнем с вертикальных линий. Можно заметить, что в каждом ряду линии рисуются с интервалом в 2 ячейки, а каждый четный по счету ряд начинается со второй, а не с первой ячейки. Также увидим то, что первый ряд начинается со со смещением в одну ячейку относительно верхей границы, а ряды разделяет одна ячейка. С учетом того, что длина штриха в две ячейки, между верхними концами отрезков находятся три ячейки. Тогда в цикле начинаем с единицы и идем до нижнего края карты с шагом 3, а во втором цикле начинаем со столбца, индекс которого обратен четности ряда, проще говоря 1-i%2, и идем до правого края карты, но на единицу больше, чтобы нарисовать таки крайние линии, с шагом в две ячейки. В кадой итерации второго цикла просто рисуем отрезок высотой две ячейки:

for i in range(1, grid_map_size.y, 3):for j in range(1-i%2, grid_map_size.x+1, 2):VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i, grid_basis.x*j+grid_basis.y*(i+2), color, width, antialiasing)

Этот код будет рисовать только вертикальные линии. Теперь нужно нарисовать паттерн вершин. Есть всего два вида наклонных линий, от нижнего левого угла к верхнему правому (их я буду называть нижними диагоналями), или от верхнего левого к нижнему правому (их я буду называть верхними диагоналями), причем в одной строке они чередуются, а в следующей строке паттерн меняет четность. Четным я буду называть паттерн, начинающийся с нижней диагонали, нечетным - начинающийся в верхней диагонали.

Каждые две строки паттерна разделяют две ячейки, поэтому чтобы перейти от одной к следующей, необходимо сдвинуться на 3 строки вниз. Как я уже говорил, каждую строку паттерн меняет четность, и так совпало, что при переходе к следующей строке ее индекс тоже меняет четность.

Для рисования паттернов пробегаем каждую третью строку, начиная с нулевой, а в каждой строке пробегаемся по столбцам. Тогда для выбора нужной линии сравниваем четности строки и столбца, если они совпадают, то рисуем нижнюю диагональ, иначе верхнюю. Тут я считаю нужным показать, как задается каждый угол ячейки с координатами {j, i} , где j - столбец (как бы x), i - строка (как бы y). Размер ячейки увеличен только для демонстрации:

В коде этот алгоритм выглядит так:

# Drawing verticesfor i in range(0, grid_map_size.y, 3): # рисуем на каждой третьей строкеfor j in range(grid_map_size.x): # крайний столбец не захватываем, т.к. в коде прибавляется единицаif i%2 == j%2: # нижняя диагональCanvas.line(surf, grid_basis.x*j+grid_basis.y*(i+1), grid_basis.x*(j+1)+grid_basis.y*i, color, width, antialiasing)else: # верхняя диагональCanvas.line(surf, grid_basis.x*j+grid_basis.y*i-offset, grid_basis.x*(j+1)+grid_basis.y*(i+1), color, width, antialiasing)

Однако просто нарисовав на холсте сетку, получатся непонятки с координатами:

Дело все в том, что начало координат находится в центре шестиугольника, а начинаем рисовать мы с левого верхнего угла вспомогательной сетки, также как мы это делали с обычными сетками. Для рисования сетки правильно, т.е. из начала координат, необходимо сдвинуть рисование на одну ячейку влево и на две вверх, ведь именно под таким смещением находится начало координат.

Однако и на этом не все. Если просто объеденить весь код выше в одну функцию, то при четных высотах она будет рисовать ненужные хвосты:

Эти хвосты рисуются прямо в углах вспомогательной сетки, поэтому просто добавим уловие, что мы в них не находимся, иначе просто не рисуем тут диагональ.

Соеденив все вместе, получим такую функцию:

func _draw_hor_rect_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var offset = grid_basis.x+grid_basis.y*2# Drawing vertical linesfor i in range(1, grid_map_size.y, 3):for j in range(1-i%2, grid_map_size.x+1, 2):VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i-offset, grid_basis.x*j+grid_basis.y*(i+2)-offset, color, width, antialiasing)# Drawing verticesfor i in range(0, grid_map_size.y, 3):for j in range(grid_map_size.x):if int(hex_map_size.y)%2 == 1 or not (i == grid_map_size.y-1 and (j == 0 or j == grid_map_size.x-1)):if i%2 == j%2:VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(i+1)-offset, grid_basis.x*(j+1)+grid_basis.y*i-offset, color, width, antialiasing)else:VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i-offset, grid_basis.x*(j+1)+grid_basis.y*(i+1)-offset, color, width, antialiasing)

При рисовании вспомогательной сетки кстати тоже используем смещение. На всякий случай оставлю тут и ее рисование, хотя это есть в моей статье про прямоугольные сетки:

func draw_auxiliary_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var offset = grid_basis.x+grid_basis.y*2for i in grid_map_size.x+1:Canvas.line(surf, grid_basis.x*i-offset, grid_basis.x*i+grid_basis.y*grid_map_size.y-offset, color, width, antialiasing)for i in grid_map_size.y+1:Canvas.line(surf, grid_basis.y*i-offset, grid_basis.x*grid_map_size.x+grid_basis.y*i-offset, color, width, antialiasing)

И, как и обещал, функция для рисования вертикально-ориентированной сетки:

func _draw_vert_rect_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var offset = grid_basis.x*2+grid_basis.y# Drawing horizontal linesfor i in range(1, grid_map_size.x, 3):for j in range(1-i%2, grid_map_size.y+1, 2):VisualServer.canvas_item_add_line(surf, grid_basis.x*i+grid_basis.y*j-offset, grid_basis.x*(i+2)+grid_basis.y*j-offset, color, width, antialiasing)# Drawing verticesfor i in range(0, grid_map_size.x, 3):for j in range(grid_map_size.y):if int(hex_map_size.x)%2 == 1 or not(i == grid_map_size.x-1 and (j == 0 or j == grid_map_size.y-1)):if j%2 == i%2:VisualServer.canvas_item_add_line(surf, grid_basis.x*(i+1)+grid_basis.y*j-offset, grid_basis.x*i+grid_basis.y*(j+1)-offset, color, width, antialiasing)else:VisualServer.canvas_item_add_line(surf, grid_basis.x*i+grid_basis.y*j-offset, grid_basis.x*(i+1)+grid_basis.y*(j+1)-offset, color, width, antialiasing)

Результат вполне неплох, нигде линии не рисуются дважды (сетка рисовалась немного прозрачной на черном фоне, а яркость линий везде одинакова):

Сетка вертикальных шестиугольников
Сетка горизонтальных шестиугольников

Однако рендерить такие сетки в реальном времени довольно затратно, тут рисуется множетсво отдельных отрезков, что сильно замедляет работу. Просто для примера, пустое черно окно у меня имеет fps около 950, а при рисовании белым цветом Color8(255, 255, 255, 200) шестиугольной сетки размера 10x10 и размером шестиугольнкиа 32 пикселя, fps примерно 260. Так что рисовать сетки процедурно резонно только на начальном этапе разработки, потом лучше отрендерить ее заранее и использовать как текстуру.

Рисование шестиугольной сетки шестиугольников

Сетки шестиугольников конечно здорово, но иногда хочется чего то большего. Например больше шестиугольников, поэтому сделаем большой шестиугольник из маленьких. Такая сетка может пригодиться, если мы, например, делаем шестиугольные шахматы.

Рисование этой сетки лишь немного сложнее рисования обычной, хотя на первый взгляд мой код похож на код сатаны. Поробую объяснить что откуда взялось. Результат будет примерно таков:

Для начала нам конечно же нужны размеры сеток. Т.к. мы рисуем сетку в виде правильного шестиугольника, ее размер можно задать одним значением. В коде я использую тип Vector2 только для совмещения этой переменной с прямоугольнйо сеткой, при рисовании будет использоваться только X координата. Тогда для задания размеров вспомогательной сетки нужно найти диагональ большого шестиугольника. Для этого вспомним, что бОльшая диагональ шестиугольника в два раза больше его стороны. В нашем случае шестиугольник состоит из маленьких таких же. В таком случае центр будет учитываться два раза, поэтому вычтем единицу:

var hex_map_size = Vector2(5, <не имеет значения>)...var diagonal = hex_map_size.x*2-1

Размеры вспомогательной сетки задаются аналогично тому, что мы делали ранее. Для горизонтальной ориентации ширина будет в два раза больше диагонали, а высота в три раза и еще на единицу больше:

...grid_map_size.x = diagonal*2grid_map_size.y = diagonal*3+1

Для вертикальных значения меняются местами:

grid_map_size.x = diagonal*3+1grid_map_size.y = diagonal*2

Шестиугольную сетку можно точно также разбить на две части, на паттерн вершин и вертикальные линии:

Начнем с рисования вершин. Рисовать каждый слой по-отдельности не имеет смысла, ведь фигура симметрична. Мы можем разделить всю вспомогательную сетку на четыре части и, нарисовав одну четверть, отобразить ее зеркально на все остальные. Сетка кстати всегда будет делиться ровно, и вот почему. По горизонтали понятно, ведь в формуле ширины мы удваиваем диагональ шестиугольной карты. А эта самая диагональ будет всегда нечетна, ведь мы от четного числа отнимаем единицу (hex_map_size.x*2-1). В формуле высоты вспомогательной сетки мы умножаем эту диагональ на 3, и результат получится тоже нечетным, а после прибавления единицы все выражение становится четным. Таким образом ширина и высота вспомогательной сетки всегда четны, и как следствие, ее можно всегда разделить на четыре одинаковые части:

Тогда мы можем пробегать в циклах только до половин размеров вспомогательной сетки, а для рисования в других частях будем просто отражать точки рисования.

При такой форме сетки рисование вершин начинается не с самой левой колонки и паттерн всегда четный (при рассмотрении одной четверти). При увеличении размера сетки на единицу, первый шестиугольник в самом верхем ряду сдвигается на одну ячейку вспомогательной сетки, т.к. мы увеличиваем в том числе и размер левой грани, в которой под каждым шестиугольником следующий находится не только ниже, но и левее на половину шестиугольника, т.е. на одну ячейку. Тогда каждый следующий паттерн начинает рисоватся на ячейку ближе к левому краю, а самый первый ряд имеет смещение на единицу меньшее, чем размер шестиугольной карты, т.к. первый шестиугольник в нем тоже является частью левой грани, так что под ним шестиугольников меньше на эту самую единицу, чем размер карты.

Также вспомним, что каждый следующий паттерн рисуется со смещением в три ячейки от предыдущего, поэтому в цикле идем от нуля до половины высоты вспомогательной сетки с шагом в три, попутно вычисляя смещение для каждого ряда:

for i in range(0, grid_map_size.y/2, 3): # Drawing vertices  # тут i/3 потому что мы идем со смещением 3, а при расчетах нужен индекс  start = hex_map_size.x-1 - i/3  

Проходить по ширине будем также до середины вспомогательной сетки, начиная с выщитанного ранее смщения:

for i in range(0, grid_map_size.y/2, 3): # Drawing vertices  # тут i/3 потому что мы идем со смещением 3, у при расчетах нужен индекс паттерна  start = hex_map_size.x-1 - i/3    for j in range(start, grid_map_size.x/2):  pass # Пока ничего не делаем

Каждый паттерн при рисовании шестиугольной карты четный, а вот смещение чередует свою четность. Четность начального смещения напрямую зависит от четности размера карты - они противоположны. Двигаясь вниз по рядам паттерна, индекс ряда меняет четность, как и смещение для этого ряда. Если помните, для выбора диагонали при рисовании прямоугольной сетки мы сравнивали четность ряда и колонки. Тут же меняются обе четности, и при разных раземрах карты они будут то совпадать при начальных значениях, то нет.

Приведу пример. Мы рисуем нижнюю диагональ, если индексы ряда и колонки совпадают, иначе верхнюю. Поставим размер карты 5. Тогда начальное смещение будет четным, как и индекс первого ряда (i=0). Исходя из условия, рисуем нижнюю диагональ, как и должно быть. Однако поставив четный размер, скажем, 4, начальное смещение будет нечетным, а вот индекс первого ряда по прежнему четным. Тогда взглянув на условие компьютер выберет верхюю диагональ, а ведь нам все еще для начала нужна нижняя. Вот как это будет выглядеть:

Тут на самом деле всего лишь надо поменять четность паттерна, тогда все встанет на свои места. Получается, выбор условия рисвания нижней диагонали зависит от четности самого размера карты. Тут можно заметить, что разница четностей столбца и ряда в каждой первой диагонали ряда паттерна обратна четности размера карты. А при рисовании паттерна диагонали просто чередуются, как и чередуется четность столбца, и как следствие чередуется равенство разностей четностей ряда и столбца и четности размера карты. Поэтому для выбора диагонали используем равентво abs(i%2 - j%2) != parity, где parity - это остаток от деления размера карты на два. Если это условие верно, рисуем нижнюю диагональ, иначе верхнюю. Получим то что нужно, осталось отразить по красным линиям:

Код рисования четверти всего паттерна
func _draw_hor_hex_grid(surf:RID, color:Color):var parity = int(hex_map_size.x)%2var startfor i in range(0, grid_map_size.y/2, 3): # Drawing verticesstart = hex_map_size.x - i/3 - 1for j in range(start, grid_map_size.x/2):if abs(i%2 - j%2) != parity:# Down diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(i+1), grid_basis.x*(j+1)+grid_basis.y*i, color)      else:# Top diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(i), grid_basis.x*(j+1)+grid_basis.y*(i+1), color)

Для отражения точек рисования отнимаем от края вспомогательной сетки индекс точки, ничего сложного. А вот в коде это выглядит громоздко. Взгляните сами:

func _draw_hor_hex_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var parity = int(hex_map_size.x)%2var startfor i in range(0, grid_map_size.y/2, 3): # Drawing verticesstart = hex_map_size.x - i/3 - 1for j in range(start, grid_map_size.x/2):if abs(i%2 - j%2) != parity:# Down diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(i+1), grid_basis.x*(j+1)+grid_basis.y*i, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i+1), grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*i, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(grid_map_size.y-i-1), grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i), color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(grid_map_size.y-i-1), grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(grid_map_size.y-i), color)else:# Top diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(i), grid_basis.x*(j+1)+grid_basis.y*(i+1), color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i), grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(i+1), color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(grid_map_size.y-i), grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i-1), color)VisualServer.ca

Но ничего страшного, ковид пережили - переживем и это. Зато получаем правильный паттерн для сеток с четными и нечетным размером:

Если вы что то поняли во всей этой мешанине четностей, то либо вы гений, либо у меня получилось что то объяснить. Однако дальше не легче, но радует то, что мы почти нарисовали сетку. Осталось добавить вертикальные линии - это будет финальным боссом в рассказе о рисовании сеток.

Тут я не стал ничего придумывать с отражениями, ведь отрезки рисуются в две ячейки и при отражении некоторые места будут рисоваться два раза, а обрабатывать кучу исключений отдельно не очень хочется. Самым простым решение мне показалось рисовать вертикальные линии также, как мы это делали с прямоугольной сеткой, только отбрасывать линии в углах. Напомню код рисования линий в простой прямоугольной сетке:

for i in range(1, grid_map_size.y, 3):for j in range(1-i%2, grid_map_size.x+1, 2):VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i, grid_basis.x*j+grid_basis.y*(i+2), color, width, antialiasing)

Однако просто скопипастив его в нашу функцию, получим кривое рисование при четных размерах карты, ведь при них первый ряд должен иметь смещение в единицу, а при нечетных этого смещения быть не должно. Это вытекает из смещения первого шестиугольника в первом ряду, при четных значения оно нечетно поэтому и рисуем со смещением, и наоборот. Для выбора смещения сравним четности размера карты и ряда, если они отличаются, то рисуем без смещения, иначе со смещением. Пихать сюда условие не имеет смысла, ведь мы можем выбрать смещение через отличие четности карты и четности столбца конструкцией abs(parity-i%2). Просто напомню - parity это остаток от деления размера карты на два. Проверьте сами, при четных столбцах и нечетных размерах карты получается единица - то самое смещение. Запишем это выражение в смещение в цикле:

for i in range(1, grid_map_size.y, 3):for j in range(abs(parity-i%2), grid_map_size.x+1, 2):VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i, grid_basis.x*j+grid_basis.y*(i+2), color, width, antialiasing)

Цель почти достигнута, осталось избавиться от лишних линий по углам:

Для этого при рисовании линий добавим некоторое условие, что мы хотим нарисовать линию в пределах каких-то границ. Для обозначения границ заметим, что с каждым рядом мы начинаем рисовать на ячейку ближе к левой границе, поэтому границу можно задать как смещение первого ряда минус индекс ряда:

...start = hex_map_size.x-1 - i/3

Однако в нижней половине шестиугольника смещение начинает идти обратно, а индекс ряда только возрастает. Поэтому будем смотерть, в какой половине мы находимся, и выбирать нужную формулу для расчета левой границы. Для нижней части карты используем положение ряда относительно центра карты, просто отняв от его индекса половину ее размера:

...start = (i-grid_map_size.y/2)/3

Это мы задали левые границы. Для правых просто отразим левые в силу четности размеров вспомогательной сетки:

for i in range(1, grid_map_size.y, 3):if i <= grid_map_size.y/2:start = hex_map_size.x-1 - i/3else:start = (i-grid_map_size.y/2)/3for j in range(abs(parity-i%2), grid_map_size.x+1, 2):if j >= start and j <= grid_map_size.x-start: # избавляемся от лишних линийVisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i, grid_basis.x*j+grid_basis.y*(i+2), color, width, antialiasing)

Вот и все - финальный босс побежден. Осталось только добавить смещение для расположения сетки в начало координат, offset = grid_basis.x+grid_basis.y*2. Однако тут опять играет роль четность размера карты, так что когда она четна прибавляем к смещению горизонтальный базис ячейки.

Босса то убили, а вот лут забыли. С него мы получили рисование шестиугольных сеток шестиугольников:

Горизонтальная ориентация
func _draw_hor_hex_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var parity = int(hex_map_size.x)%2var offset = grid_basis.x+grid_basis.y*2 + grid_basis.x*(1-parity)var startfor i in range(0, grid_map_size.y/2, 3): # Drawing verticesstart = hex_map_size.x - i/3 - 1for j in range(start, grid_map_size.x/2):if abs(i%2 - j%2) != parity:# Down diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(i+1)-offset, grid_basis.x*(j+1)+grid_basis.y*i-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i+1)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*i-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*(grid_map_size.y-i-1)-offset, grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(grid_map_size.y-i-1)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(grid_map_size.y-i)-offset, color)else:# Top diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(i)-offset, grid_basis.x*(j+1)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)for i in range(1, grid_map_size.y, 3):if i <= grid_map_size.y/2:start = hex_map_size.x-1 - i/3else:start = (i-grid_map_size.y/2)/3for j in range(abs(parity-i%2), grid_map_size.x+1, 2):if j >= start and j <= grid_map_size.x-start:VisualServer.canvas_item_add_line(surf, grid_basis.x*j+grid_basis.y*i-offset, grid_basis.x*j+grid_basis.y*(i+2)-offset, color, width, antialiasing)

Пример:

Вертикальная ориентация
func _draw_vert_hex_grid(surf:RID, color:Color, width=1.0, antialiasing=false):var parity = int(hex_map_size.x)%2var offset = grid_basis.x*2+grid_basis.y + (1-parity)*grid_basis.yvar startfor j in range(0, grid_map_size.x/2, 3): # Drawing verticesstart = hex_map_size.x - j/3 - 1for i in range(start, grid_map_size.y/2):if abs(i%2 - j%2) != parity:# Down diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*(j+1)+grid_basis.y*(i)-offset, grid_basis.x*(j)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(i)-offset, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(j)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)else:# Top diagonalVisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(i)-offset, grid_basis.x*(j+1)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(i)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(i+1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(j)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(j+1)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)VisualServer.canvas_item_add_line(surf, grid_basis.x*(grid_map_size.x-j)+grid_basis.y*(grid_map_size.y-i)-offset, grid_basis.x*(grid_map_size.x-j-1)+grid_basis.y*(grid_map_size.y-i-1)-offset, color)for i in range(1, grid_map_size.x, 3):if i <= grid_map_size.x/2:start = hex_map_size.x-1 - i/3else:start = (i-grid_map_size.x/2)/3for j in range(abs(parity-i%2), grid_map_size.y+1, 2):if j >= start and j <= grid_map_size.y-start:VisualServer.canvas_item_add_line(surf, grid_basis.x*i+grid_basis.y*j-offset, grid_basis.x*(i+2)+grid_basis.y*(j)-offset, color, width, antialiasing)

Пример:

Рисование шестиугольников

Тут на самом деле все просто, можете расслабиться. После этой жести с четностями ничего хуже уже не будет. Для рисования шестиугольников вспомним функции для получения вершин, которые я приводил выше и просто соеденим массив вершин шестиугольника линиями:

Функции для получения вершин, если лень мотать неаверх
func _get_vert_hex_vertices(hex):var pixel = hex2pixel(hex)return PoolVector2Array([pixel+2*grid_basis.x,pixel+grid_basis.x+grid_basis.y,pixel-grid_basis.x+grid_basis.y,pixel-2*grid_basis.x,pixel-grid_basis.x-grid_basis.y,pixel+grid_basis.x-grid_basis.y])func _get_hor_hex_vertices(hex):var pixel = hex2pixel(hex)return PoolVector2Array([pixel+grid_basis.x-grid_basis.y,pixel+grid_basis.x+grid_basis.y,pixel+2*grid_basis.y,pixel-grid_basis.x+grid_basis.y,pixel-grid_basis.x-grid_basis.y,pixel-2*grid_basis.y,])

И рисуем множество линий между точками, не забыв замкнуть цепь:

func _draw_hor_hex(hex, surf, color, width=1.0, antialiasing=false):var points = _get_hor_hex_vertices(hex)points.append(points[0]) # замыкаемVisualServer.canvas_item_add_polyline(surf, points, [color], width, antialiasing)func _draw_vert_hex(hex, surf, color, width=1.0, antialiasing=false):var points = _get_vert_hex_vertices(hex)points.append(points[0]) # замыкаемVisualServer.canvas_item_add_polyline(surf, points, [color], width, antialiasing)

Для заливки шестиугольника, по аналогии с прямоугольником, рисуем полигон:

func _fill_hor_hex(hex, surf, color, antialiasing=false):var points = _get_hor_hex_vertices(hex)VisualServer.canvas_item_add_polygon(surf, points, [color], [], RID(), RID(), antialiasing)func _fill_vert_hex(hex, surf, color, antialiasing=false):var points = _get_vert_hex_vertices(hex)VisualServer.canvas_item_add_polygon(surf, points, [color], [], RID(), RID(), antialiasing)

Выгялдит все это как то так:

Шестиугольные сетки в изометрии

Что может быть лучше сетки шестиугольников? Правильно, сетка шестиугольников в изометрии. Вы могли заметить, что ни в одной функции я не использовал числа - везде я работал с векторами. А это значит, что поменяв базис, автоматически поменяются функции - так и должно работать программирование. Помните, в части про преобразование координат я все вычисления автоматизировал? Так вот, наконец то нам это пригодится.

Как вы уже наверняка поняли, шестиугольная сетка это лишь обертка над обычной прямоугольной, ведь все функции рано или поздно сходятся к работе с базисами вспомогательной сетки. Поэтому для создания изометрии не будем придумывать велосипед, просто зададим ее переменной, отвечающей за искажение отношений горизонтальных размеров к вертикальным:

...const iso_scale = 2.0

Тогда для изменения вида делим y-координату каждого базиса вспомогательной сетки на это искажение:

# Вертикальная ориентацияgrid_basis.x = Vector2(long, 0)grid_basis.y = Vector2(0, short/iso_scale)# Горизонтальная ориентацияgrid_basis.x = Vector2(short, 0)grid_basis.y = Vector2(0, long/iso_scale)

И все, даже не нужно менять базисы шестиугольной сетки, ведь мы их задавали через базисы вспомогательной. Как же хороша эта ваша математика... Вот пример:

На самом деле, благодаря векторным преобразованиям мы можем делать с базисами вспомогательной сетки все что угодно, и все функции все равно будут работать. Поэтому давайте сделаем сетку не просто в изометрии, а еще и повернем ее на 45, также, как мы это делали в статье про прямоугольные сетки:

# для вертикальныхvar pw = int(long*cos(PI/4))var ph = int(short*cos(PI/4))grid_basis.x = Vector2(pw, pw/iso_scale)grid_basis.y = Vector2(-ph, ph/iso_scale)# для горизонтальныхvar pw = int(short*cos(PI/4))var ph = int(long*cos(PI/4))grid_basis.x = Vector2(pw, pw/iso_scale)grid_basis.y = Vector2(-ph, ph/iso_scale)

Напомню, что базисы шестиугольной сетки мы не трогаем, ведь они все так же заданы через базисы вспомогательной. Выглядит вся эта магия как то так:

Красиво, конечно, но игру на этом не сделать. Нужно также уметь что то на этих сетках делать.

Изометрические преобразования

С преобразованиями тоже мудрить ничего не стоит, ведь, напомню, шестиугольная сетка - это только обертка над обычной, поэтому все функции будут работать в штатном режиме. Единственное, что наверно стоит рассмотреть, это получение ячейки вспомогательной сетки, левый верхний угол которой находится в центре шестиугольника.

Для этого вспомним то, как мы направляли базисы для различных ориентаций шестиугольников. Вот картинка из почти самого начала моего рассказа:

Посмотрев на нее, все сразу становится ясно. В случае горизонтальной ориентации при каждом перемещении по x на шестигольной сетке мы двигаемся на две ячейки вспомогательной, а при движении по y мы движемся на одну ячейку вправо и на три вниз. Для вертикальных применима эта же логика. По этим формулам написать функции можно проще простого:

# Для вертикальныхfunc get_center_cell(hex:Vector2):return Vector2(hex.x*3, hex.y*2+hex.x)# для горизонтальныхfunc get_center_cell(hex:Vector2):return Vector2(hex.x*2+hex.y, hex.y*3)

В изометрии ближние объекты должны рисоваться раньше дальних, и, если помните, в пямоугольных изометрических сетках мы использовали сумму координат. Здесь делаем тоже самое, только находим сумму координат центральной ячейки в шестиугольнике, получаемую по алгоритму выше.

Расстояние на сетке

Часто бывает нужно найти расстояние между двумя шестиугольниками. Для этого заметим, что при перемещении в любой из соседних шестиугольников меняются сразу две координаты из трех, причем не единицу. Тогда сумма модулей всех трех координат либо меняется на два, либо не изменятся вовсе. В таком случае сеточное расстояние от начала координат можно найти как половину суммы модулей трех координат шетиугольника, а для нахождения расстояния между двумя шестиугольниками можно просто найти смещение одного относительно другого через разность. Получается вот такая небольшая функция:

func hex_distance(hex1:Vector2, hex2:Vector2):var dif = (hex2-hex1)return (abs(dif.x) + abs(dif.y) + abs(-dif.x-dif.y))/2 # z = -x-y

Сеточное направление

Начнем с самого простого - выбора направляющего шестиугольника. Кто не понимает о чем речь, заглянет в статью о прямоугольных тайловых мирах. Это один из немногих алгоритмов, где нам понадобится третья координата.

Для нахождения направляющей разделим сетку по трем осям и заметим, что в каждой части получившейся сетки одна из трех координат максимальна по модулю:

Теперь все, что нам нужно, это выбрать нужную часть и, сравнив модули не наибольших координат, выдать одно из осевых направлений, представленное в виде направляющей ячейки. Прямо на осях одна из координат всегда равна нулю, поэтому просто перехватим их как особые случаи. Для указания вдоль оси будем использовать знак разности конечного и начального шестиугольников. Также заметим, что на диагональных ячейках модули не наибольших координат равны, поэтому мы можем смещаться в любую из двух осей. Я выбрал смещение в сторону оси по часовой стрелке, в коде это выражается строгостью знаком сравнения. Для смещения против часовой стоит допустить равентсво. Так выглядит этот алгоритм в коде:

func direct_hex(hex1:Vector2, hex2:Vector2):var dx = hex2.x - hex1.xvar dy = hex2.y - hex1.yvar dz = -hex2.x-hex2.y + hex1.x+hex1.yif dx == 0: # Ось yreturn Vector2(0, sign(dy)) # Возвращаем ось yelif dy == 0: # Ось xreturn Vector2(sign(dx), 0) # Возвращаем ось xelif dz == 0: # Ось zreturn Vector2(sign(dx), sign(dy)) # Возвращаем ось zelse:if abs(dz) > abs(dx) and abs(dz) > abs(dy): # модуль разности по z оказался наибольшимif abs(dx) > abs(dy): # т.к. разность по x больше, значит мы отошли по x дальше, чем по y, значит выдаем ось xreturn Vector2(sign(dx), 0) # возвращаем ось xelse: # т.к. разность по y больше, значит мы отошли по y дальше, чем по x, значит выдаем ось yreturn Vector2(0, sign(dy)) # возвращаем ось y        elif abs(dy) > abs(dx): # модуль разности по y оказался наибольшимif abs(dz) > abs(dx): # по аналогииreturn Vector2(0, sign(dy)) # возвращаем y. Это связанно с представлением z-координаты через две другиеelse: # по аналогииreturn Vector2(sign(dx), sign(dy)) # возвращаем z        else: # модуль разности по x оказался наибольшимif abs(dy) > abs(dz): # по аналогииreturn Vector2(sign(dx), sign(dy)) # возвращаем zelse: # по аналогииreturn Vector2(sign(dx), 0) # возвращаем x

Опять же, тому кто читал мою статью про прямоугольные сетки, понять все это будет проще, ведь в ней я разбирал подобный алгоритм подробнее, однако, я надеюсь, что по комментариям принцип работы алгоритма понятен. Как мы видим, все рабоатет:

На всякий случай скажу, что этот алгоритм не зависит от ориентации шестиугольников, ведь работа идет с их координатами, а координатм внутри сетки вообще плевать на положение шестиугольников в пространстве.

Поиск пути

Основной алгоритм поиска пути тот же, что и у обычной прямоугольной сетки, отличаются только соседи и проверки на нахождение точки внутри карты. Главный алгоритм - A*, его не трогаем совсем.

Соседи у шестиугольника выглядят как то так:

Можно заметить, что они также не зависят от ориентации шестиугольников, поэтому в будущем будем пользоваться одной функцией для обоих случаев.

Также у разных видов карты отличаются проверки на принадлежность шестиугольниа им. Алгоритмы для разных ориентаций шестиугольников немного отличаеются, но в целом они похожи, поэтому пояснять я буду только на примере горизонтальных, а для вертикальных оставлю уже готовые функции.

Начнем с прямоугольной карты. Для наглядности напомню как она выглядит:

Синим обозначены границы карты. Оси в такой сетке идут не параллельно сторонам прямоугольника, поэтому просто ограничить их нулем и границей карты не выйдет. Так сработает только для Y оси сетки, а горизонтальные границы зависят от смещения по Y. Перемещаясь вдоль оси Y, расстояние до левой границы в ячейках вспомогательной сетки увеличивается на единицу, значит на половину шестиугольника. Аналогично с правой границей, тоолько до нее расттояние уменьшается. При округлении левой границы используем floor, т.к. когда граница проходит ровно между шестиугольниками, мы вмыбираем тот, что внутри. По аналогии используем ceil для правой границы:

func _in_rect_grid_hor(hex):return hex.x >= -floor(hex.y/2) and hex.x < hex_map_size.x-ceil(hex.y/2) and hex.y < hex_map_size.y and hex.y >= 0

Для вертикальной ориентации логика точно такая же. Вот функция для нее:

func _in_rect_grid_vert(hex):return hex.x >= 0 and hex.x < hex_map_size.x and hex.y >= -floor(hex.x/2) and hex.y < hex_map_size.y-ceil(hex.x/2)

Теперь про шестиугольную карту. Ее вид:

Для простоты вычислений будем считать границы от центра карты. Просто потыкав и посмотрев на координаты я пришел к следующим формулам центров:

# для горизонтальныхfunc _get_hor_hex_map_center():return Vector2(int((hex_map_size.x-1)/2), hex_map_size.x-1)# для вертикальныхfunc _get_vert_hex_map_center():return Vector2(hex_map_size.x-1, int((hex_map_size.x-1)/2))

Каждому смещению по Y соответствует уменьшение длины ряда на единицу, так и будем задавать границы по x. В качестве размеров, ограничивающих карту, возьмем диагональ. Как ее вычислять я рассказывал ранее. Тогда по Y границами будут просто половины этих диагоналей, а по X одна из граней всегда параллельна оси Y, поэтому уменьшаться будет либо правая либо левая граница. Какая именно можно понять по вертикальной половине шестиугольника. Если мы находимся в верхней, то уменьшается левая граница (т.к. правая параллельна оси Y), если в нижней то уменьшается правая граница (т.к. левая паралельна оси Y). А если мы находимся прямо на горизонтальной диагонали то нам плевать, ведь на ней смещение по Y равно нулю.

Вот функции, реализующие данную логику для обеих ориентаций:

# для горизонтальныхfunc _in_hex_grid_hor(hex):    var center = _get_hor_hex_map_center()    var diag = int(hex_map_size.x*2 - 1)    hex -= center # Vector2 passed by value; getting hex regarding map center    if hex.y < 0:        return hex.x >= -diag/2+abs(hex.y) and hex.x <= diag/2 and hex.y >= -diag/2 and hex.y <= diag/2    else:        return hex.x >= -diag/2 and hex.x <= diag/2-abs(hex.y) and hex.y >= -diag/2 and hex.y <= diag/2# для вертикальныхfunc _in_hex_grid_vert(hex):    var center = _get_vert_hex_map_center()    var diag = int(hex_map_size.x*2 - 1)    hex -= center # Vector2 passed by value; getting hex regarding map center    if hex.x < 0:        return hex.y >= -diag/2+abs(hex.x) and hex.y <= diag/2 and hex.x >= -diag/2 and hex.x <= diag/2    else:        return hex.y >= -diag/2 and hex.y <= diag/2-abs(hex.x) and hex.x >= -diag/2 and hex.x <= diag/2

Для проверки поставим условие, что для рисования шестиугольника под курсором он должен быть внутри сетки:

Отлично, теперь можно спокойно реализовывать алгоритм поиска пути:

Ищем путь истинный
class PriorityStack:var items:Arrayfunc _init():items = Array()func empty() -> bool:return items.size() == 0func put(item, priority:int) -> void:if empty():items.append([item, priority])elif priority <= items[0][1]:items.insert(0, [item, priority])elif priority > items[-1][1]:items.append([item, priority])else:for i in range(len(items)):if priority <= items[i][1]:items.insert(i, [item, priority])breakfunc take():return items.pop_front()[0]func in_map(hex):match grid_type:GridTypes.hex:if hex_type == HexTypes.hor:return _in_hex_grid_hor(hex)else: # Verticalreturn _in_hex_grid_vert(hex)GridTypes.rect:if hex_type == HexTypes.vert:return _in_rect_grid_vert(hex)else: # Hor orientationreturn _in_rect_grid_hor(hex)func can_stand(hex:Vector2, obsts:PoolVector2Array):return in_map(hex) and not (hex in obsts)func neighbors(hex_pos:Vector2, obsts:PoolVector2Array):var res:PoolVector2Array = []var _neighbors = PoolVector2Array([Vector2(-1, 0), Vector2(1, -1), Vector2(0, -1), Vector2(1, 0), Vector2(0, 1), Vector2(-1, 1)])for i in _neighbors:if can_stand(i+hex_pos, obsts):res.append(i+hex_pos)return resfunc find_path(start:Vector2, goal:Vector2, obsts:PoolVector2Array):var frontier = PriorityStack.new()frontier.put(start, 0)var came_from = {}var cost_so_far = {}came_from[start] = startcost_so_far[start] = 0var current:Vector2var new_cost:intif not can_stand(goal, obsts):return PoolVector2Array()while not frontier.empty():current = frontier.take()if current == goal:breakfor next in neighbors(current, obsts):new_cost = cost_so_far[current] + 1if not (next in cost_so_far) or new_cost < cost_so_far[next]:cost_so_far[next] = new_costfrontier.put(next, new_cost+hex_distance(goal, next))came_from[next] = currentif frontier.empty() and current != goal:return PoolVector2Array()current = goalvar path = PoolVector2Array([current])while current != start:current = came_from[current]path.append(current)path.invert()path.remove(0) # removes first positionreturn pathfunc hex_distance(hex1:Vector2, hex2:Vector2):var dif = (hex2-hex1)return (abs(dif.x) + abs(dif.y) + abs(-dif.x-dif.y))/2

Данный код я взял напрямую из своей реализации, так что некоторые моменты не освещены, за ненадобностью. Поглазеть на полный код сможете кликнув по ссылке в конце статьи. Так это выглядит:

Растеризация отрезка

Вот с растеризацией у шестиугольной сетки большие проблемы. Можно, конечно, придумать что нибудь с алгоритмом брезенхема для растеризации отрезков, однако я не думаю что вам нужно растеризовывать по 1000 отрезков за кадр, поэтому на оптимизацию позволим себе немного подзабить и воспользуемся линейной интерполяцией, которую, кстати, и предлагает автор популярной англоязычной статьи. Думаю почти все знают что такое линейная интерполяция, поэтому просто оставлю тут рализацию алгоритма:

Растеризуем нерастеризуемое
func rast_line(hex1, hex2):var N = hex_distance(hex1, hex2)if N == 0: return PoolVector2Array([hex1])var res = PoolVector2Array()for i in range(N+1):res.append(round_hex(lerp(hex1, hex2, i/N)))return res

Вот так это выглядит:

Пару слов в завершение

Вот и подошел столь запутанный рассказ к концу. Я постарался объяснить все максимально подробно и вставлял как можно больше картинок, надеюсь не зря. Никакую маленькую игру я делать не стал, ибо тут и так хаватаеn над чем подумать, поэтому просто оставлю код получившегося класса на почти 500 строк. Я подразумеваю его использование через автозагрузку, как собственно я и делал во время работы над ним.

Если я забыл про что рассказать или упустил какие то важные моменты, или же просто ошибаюсь, напишете об этом в комментарии.

Я надеюсь эта статья позволит вам полностью реализовать давние мечты по созданию "убийы героев" или что она позволила просто интересно провести вечер. До скорого!

Подробнее..

Recovery mode Задача о рюкзаке (Knapsack problem) простыми словами

05.06.2021 00:21:43 | Автор: admin

Пару лет назад столкнулся с так называемой задачей о рюкзаке на одном из собеседований, нашел быстренько решение в интернете. Попытался разобрать и.... ничего не понял. Кое как поменял названия переменных, а кто так не делает когда находит готовое решение для home таски? Отправил и забыл как страшный сон. Недавно друг скинул подобную задачу про монеты и в этот раз я уже быстренько разобрался с этой когда то, как казалось мне неподъемной задачкой.

Хотел бы отметить книгу Grokking Algorithms автора Aditya Bhargava. У нее прям максимально простым языком расписаны основы алгоритмов. Так что если, вы как и я в универе думали что алгоритмы вам никогда не пригодятся, потому что FAANG это не для вас. То я вас и разочарую и обрадую, попасть туда может каждый, если конечно приложит достаточно усилий, ну а разочарую тем что вам конечно придется поднапрячься и осилить алгоритмы и чем раньше вы начнете это делать, тем лучше.

На хабре, уже есть одна статья на эту тему: Алгоритм решения задачи о рюкзаке ( версия 2, исправленная) / Хабр (habr.com) . Но, да простит меня автор, на мой взгляд она совершенно непонятная.

И так, перейду к делу. Сначала расскажу обо всем на пальцах, а потом мы рассмотрим решение на нашем любимом C#.

Собственно задача, одна из популярных её вариаций. Вор пробрался в ювелирный магазин, у него есть рюкзак объемом 4 единицы. В магазине, он увидел три вещи:

Вещи которые есть в магазинеВещи которые есть в магазине

Его задача оптимально уместить эти вещи в рюкзаке так что бы он унес драгоценностей на максимальную стоимость.

Есть несколько способов решения. Один из них это перебор всех вариантов.

Для простоты, предмета будет только три, поскольку количество различных комбинаций в которых их можно унести растет очень быстро и даже для 3 предметов уже будет равно 8. Оно вычисляется по формуле 2n где n - количество предметов, то есть если предмета будет 4, то количество возможных комбинаций достигнет уже 16 и так далее. Такой вариант нас не устроит поскольку решая эту задачу онлайн на каком-нибудь Codility ваше решение зарубят с Timeout Exceeded. Нужно что-то получше.

Мы будем решать эту задачу методом динамического программирования

Задача является одной из базовых в этой области и понимание её решения откроет вам дорогу к более сложным задачам. В динамическом программировании мы разбиваем базовую задачу на более простые и постепенно решая их все, в итоге находим решение основной.

Заполним небольшую табличку:

1

2

3

4

Ожерелье / 4000 / 4 ед

Кольцо / 2500 / 1 ед

Подвеска / 2000 / 3 ед

С левой стороны у нас будут все вещи. При этом порядок в котором они расположены, в данной задаче нас не интересует. Количество колонок равно количеству потенциальных рюкзаков размером от 1, минимально возможного целого положительного числа, до размера нашего рюкзака, с шагом 1. Таким образом мы пытаемся решить ряд более мелких задач, для рюкзаков размером 1, 2, 3 и 4. Всегда ведь проще начинать с малого?)

1

2

3

4

Ожерелье / 4000 / 4 ед

0

0

0

4000

Сверху у нас заполненный первый ряд. Мы можем использовать в каждом ряду, только вещь из этого ряда или вещи из верхних рядов.

Рюкзак размером 1: Ожерелье не влезет в рюкзак, значит стоимость того что мы можем унести равна 0.

Рюкзак размером 2: Ожерелье не влезет в рюкзак, значит стоимость того что мы можем унести равна 0.

Рюкзак размером 3: Ожерелье не влезет в рюкзак, значит стоимость того что мы можем унести равна 0.

Рюкзак размером 4: Здесь все становится немного интересней, вес ожерелья 4 и размер рюкзака 4. Ура, наконец то успех, мы не зря ворвались в магазин, кладем ожерелье в большой рюкзак и убегаем.

Немного усложним задачу и добавим еще одну вещь которая потенциально попадет в наш рюкзак. То что подсчитано мы не трогаем, оно нам потом пригодится.

1

2

3

4

Ожерелье / 4000 / 4 ед

0

0

0

4000

Кольцо / 2500 / 1 ед

2500

2500

2500

4000

Добавилось кольцо. Делаем подсчеты для второго ряда:

Рюкзак размером 1: У нас добавилось кольцо и его размер как раз равен размеру даже самого маленького рюкзака. Но у нас ведь еще есть и ожерелье, мы уже проверили, оно не влезет. Кладем только кольцо.

Рюкзак размером 2: То же что и для размера 1. Кладем только кольцо.

Рюкзак размером 3: То же что и для размера 1. Кладем только кольцо.

Рюкзак размером 4: Здесь у нас есть выбор, либо положить только одно маленькое кольцо, либо взять ожерелье, которое тяжелее, но и стоит дороже. Забываем про кольцо, и возвращаемся за ожерельем!

Так, наконец добавим третий ряд

1

2

3

4

Ожерелье / 4000 / 4 ед

0

0

0

4000

Кольцо / 2500 / 1 ед

2500

2500

2500

4000

Подвеска / 2000 / 3 ед

2500

2500

2500

4500

Рюкзак размером 1: Кольцо дороже подвески, да и подвеска не влезет, она по всем параметрам проигрывает вещам выше, берем кольцо размером 1.

Рюкзак размером 2: Тоже самое что и для размера 1.

Рюкзак размером 3: Несмотря на то что мы можем здесь взять подвеску, кольцо выигрывает ее по параметрам, снова кладем ее.

Рюкзак размером 4: А вот тут у нас, весь рюкзак, и все возможные вещи. И мы видим что кольцо и подвеска вместе стоят на 500 долларов дороже ожерелья и при этом все так же влезут в рюкзак. Значит мы возьмем и кольцо и подвеску стоимостью 4500 и весом как раз 4 единицы.

В правом нижнем углу у нас верный результат.

Ну и где же здесь пере использование спросите вы? Да, мы им не пользовались, потому что таблица была сравнительно простая. Но, если присмотреться то можно заметить закономерность!

Представим что для количества вещей у нас счетчик i, а для рюкзаков j.

На примере последней ячейки рассмотрим формулу в действии

Зеленым выделена первая опция, красным вторая. Как видим стоимость в красном круге перевешивает стоимость в зеленомЗеленым выделена первая опция, красным вторая. Как видим стоимость в красном круге перевешивает стоимость в зеленом

Это работает с любой ячейкой, даже в первом ряду. Просто представьте что у нас есть воображаемый нулевой ряд с нулевыми значениями.

И собственно алгоритм задачи на языке C#:

public static int[] weights = { 4, 1, 3 };public static int[] values = { 4000, 2500, 2000 };public static int CountMax(int[] weights, int[] values, int maxCapacity){    //строим массив и закладываем место на ячейки пустышки     //выходящие из левого верхнего угла    int[,] arr = new int[weights.Length + 1, maxCapacity + 1];    //проходим по всем вещам    for (int i = 0; i <= weights.Length; i++)    {        //проходим по всем рюкзакам        for (int j = 0; j <= maxCapacity; j++)        {            //попадаем в ячейку пустышку            if (i == 0 || j == 0)            {                arr[i, j] = 0;            }            else            {                   //если вес текущей вещи больше размера рюкзака                //казалось бы откуда значение возьмется для первой вещи                 //при таком условии. А оно возьмется из ряда пустышки                if (weights[i - 1] > j)                {                    arr[i, j] = arr[i - 1, j];                }                else                {                    //здесь по формуле. Значение над текущей ячейкой                    var prev = arr[i - 1, j];                    //Значение по вертикали: ряд вверх                    //и по горизонтали: вес рюкзака - вес текущей вещи                    var byFormula = values[i - 1] + arr[i - 1, j - weights[i - 1]];                    arr[i, j] = Math.Max(prev, byFormula);                }            }        }    }    // возвращаем правую нижнюю ячейку    return arr[weights.Length, maxCapacity];}

Всем побед и удачных собесов!

Подробнее..
Категории: Алгоритмы , C , Net , Algorithms , Knapsack problem

Перевод Распознавание мелодии путем изучения языка тела музыканта

07.09.2020 16:04:06 | Автор: admin
Перевод статьи подготовлен в преддверии старта нового набора на курс Computer vision.




Инструмент распознавания музыкальных жестов на основе искусственного интеллекта, разработанный в MIT-IBM Watson AI Lab, использует движения тела, чтобы различать звуки отдельных музыкальных инструментов.


Image courtesy of the researchers.
Исследователи используют данные о ключевых точках скелета, чтобы сопоставлять движения музыкантов с темпом их партии, что позволяет слушателям изолировать инструменты с одинаковым звучанием.
Изображение предоставлено исследователями.


Мы наслаждаемся музыкой не только ушами, но также и глазами, с признательностью наблюдая, как пальцы пианиста летают по клавишам, а смычок скрипача качается на гребне струн. Когда ухо не в состоянии разделить два музыкальных инструмента, нам помогают наши глаза, сопоставляя движения каждого музыканта с ритмом каждой партии.

Новый инструмент на основе искусственного интеллекта разработанный MIT-IBM Watson AI Lab использует виртуальные глаза и уши компьютера, чтобы отделить друг от друга звуки схожие настолько, что человеку сложно их дифференцировать. Инструмент улучшен относительно предыдущих итераций путем согласования движений отдельных музыкантов с помощью ключевых точек их скелета с темпом отдельных партий, что позволяет слушателям изолировать звучание отдельной флейты или скрипки среди нескольких таких же инструментов.

Возможные применения для работы варьируются от микширования звука и увеличения громкости инструмента в записи до уменьшения путаницы, которая заставляет людей перебивать друг друга во время видеоконференций. Работа будет представлена на конференции Computer Vision Pattern Recognition в этом месяце.

Ключевые точки тела предоставляют мощную структурную информацию, говорит ведущий автор исследования Чуанг Ган, исследователь в лаборатории IBM. Мы используем их здесь, чтобы улучшить способность ИИ слушать и отделять звук.

В этом и других подобных проектах исследователи использовали синхронизированные аудио-видео треки, чтобы воссоздать способ обучения людей. Система искусственного интеллекта, которая обучается с помощью нескольких сенсорных модальностей, может учиться быстрее, с меньшим количеством данных и без необходимости вручную добавлять надоедливые ярлыки к каждому реальному представлению. Мы учимся на основе всех наших органов чувств, говорит Антонио Торральба, профессор MIT и соавтор исследования. Мультисенсорная обработка это предшественник воплощенного интеллекта и систем искусственного интеллекта, которые могут выполнять более сложные задачи.

Данный инструмент, который использует язык тела для разделения звуков, основан на более ранней работе, в которой сигналы движения использовались в последовательностях изображений. Его самое раннее воплощение, PixelPlayer, позволял кликнуть по инструменту в концертном видео, чтобы сделать его громче или тише. Обновление PixelPlayer позволяет вам провести различие между двумя скрипками в дуэте путем сопоставления движений каждого музыканта с темпом их партии. Эта последняя версия добавляет данные о ключевых точках (которые используют спортивные аналитики для отслеживания результатов спортсменов, для извлечения более детализированных данных о движении), чтобы различать почти идентичные звуки.

Работа подчеркивает важность визуальных подсказок в обучении компьютеров, чтобы они могли лучше слышать, и использование звуковых подсказок, чтобы дать им более острое зрение. Точно так же, как текущее исследование использует визуальную информацию о движениях музыканта для разделения партий музыкальных инструментов с похожим звучанием, в предыдущей работе использовались звуки для разделения похожих объектов и животных одного вида.

Торральба и его коллеги показали, что модели глубокого обучения, обученные на парных аудио-видео данных, могут научиться распознавать естественные звуки, такие как пение птиц или удары волн о берег. Они также могут определять географические координаты движущегося автомобиля по звуку его двигателя и колес, движущихся к микрофону или от него.

Последнее исследование предполагает, что инструменты отслеживания звука могут быть полезным дополнением к беспилотным автомобилям, помогая их камерам в условиях плохой видимости. Звуковые трекеры могут быть особенно полезны ночью или в плохую погоду, помогая отмечать автомобили, которые в противном случае могли бы быть пропущены, говорит Ханг Чжао, доктор философии '19, который участвовал в исследованиях касательно отслеживания движения и звука.

Другими авторами исследования музыкальных жестов CVPR являются Дэн Хуанг и Джошуа Тененбаум из MIT.

На этом все. Чтоб узнать о курсе подробнее, приглашаем вас записаться на день открытых дверей по ссылке ниже:


Читать ещё:


Как я научила свой компьютер играть в Доббль с помощью OpenCV и Deep Learning
Подробнее..

Перевод Что такое фильтр Блума?

09.02.2021 02:22:17 | Автор: admin

Всем привет! В этой статье я постараюсь описать, что такое фильтр Блума, рассказать о его назначении и показать сценарии, в которых его можно использовать. Я также реализую фильтр Блума на Python с нуля в целях облегчения понимания его внутреннего устройства.

Назначение фильтра Блума

Фильтр Блума это структура данных, цель которой быстро проверить, что элемент НЕ входит в множество (для тех, кто знаком с нотацией O большое, сложность вставки и проверки принадлежности элемента к множеству с помощью фильтра Блума O(1)). Он может быть очень полезен для предотвращения излишнего выполнения задач, требующих интенсивных вычислений, просто проверяя, что элемент совершенно точно не входит в множество. Важно понимать, что фильтр Блума это вероятностная структура данных: он может сказать вам со 100% вероятностью, что элемент отсутствует в наборе данных, но сказать со 100% вероятностью, что элемент находится в наборе, он не может (возможны ложно положительные результаты). Давайте же поговорим о сценариях, в которых можно использовать фильтр Блума с подробным объяснением его внутреннего устройства и реализацией на Python, и позже вы поймете, откуда фильтр Блума имеет такие показатели!

Фильтр Блума обычно используется перед поиском в множестве с достаточно медленным доступом к элементам. За счет его использования может быть уменьшено как количество поисковых операций над множеством, так и время поиска в целом.

Сценарии использования

Давайте поразмыслим о сценариях, в которых для ускорения вычисления некоторых задач такая структура данных могла бы оказаться очень полезной. Например, мы можем начать с маршрутизатора опорной сети (не такого, который вы можете найти у себя дома). От таких маршрутизаторов может требоваться скорость в uplink более 100 Гбит/с. Администратору может понадобиться создать черный список IP-адресов, чтобы заблокировать им доступ в сеть. Это означает, что каждый раз, когда маршрутизатор получает пакет на скорости более 100 Гбит/с, он должен обращаться к своей памяти и выполнять в лучшем случае логарифмический поиск (O(log(n))), чтобы проверить, заблокирован ли IP-адрес, учитывая, что большинство IP-адресов не заблокированы и что поиск не даст результатов для большинства пакетов. В этом случае фильтр Блума может быть реализован как раз перед доступом к памяти, чтобы гарантировать, что большинству пакетов не нужно дожидаться поиска IP-адреса для отправки в сеть.

Еще один сценарий это базы данных. Когда к базе данных происходят миллионы обращений в секунду, и большинство обращений представляют из себя поиск по ключу, которого в базе данных нет, максимально уменьшить нагрузку таких обращений на базу данных может быть важно по двум причинам: если сократить количество поисков, ядро базы данных будет быстрее отвечать на другие обращения; если клиент может не дожидаться поиска по базе данных и получить результат (например, не из памяти) без необходимости доступа к базе данных, достигнутое ускорение может быть весьма существенным.

Наконец, чтобы ускорить процесс поиска файла в папке с большим количеством файлов, можно использовать фильтр Блума, чтобы сначала проверить, отсутствует ли файл в этой папке.

Более типичные сценарии использования фильтра Блума можно найти здесь.

Что из себя представляет фильтр Блума?

Чтобы проиллюстрировать устройство фильтра Блума, мы будем использовать первый сценарий. Представьте, что вы внесли в черный список 100 IP-адресов. Самый простой способ пометить, есть ли IP-адрес в черном списке или нет, создать список из 100 бит, где каждый бит это один IP. Если IP-адрес занесен в черный список, мы отмечаем его позицию как 1, в противном случае 0.

В этом фильтре Блума 4-й IP-адрес занесен в черный список, а все остальные нет.

Сколько всего IP-адресов?

Эта реализация работает, если используются только 100 IP. В реальности же каждый IPv4-адрес имеет 32 бита, что означает, что существует 4 294 967 296 (2^32) возможных адресов (некоторые из них зарезервированы для приватных, бродкастных, мультикастных и других специальных сетей, но оставшихся адресов все еще огромное количество)! И количество IP-адресов в черном списке, вероятно, не превысит нескольких сотен в самом крайнем случае. Мы не можем позволить себе составлять такой большой список, чтобы использовать его для такого относительно небольшого количества записей. Нам нужно найти способ сопоставления IP-адреса и записей в списке. И вот тут-то и приходят на помощь хеш-функции.

Хеш-функция

Хеш-функция это функция, которая преобразует вход произвольной длины в значение фиксированного размера. Таким образом, мы можем создать массив фиксированного размера и вычислить результат хеш-функции по конкретному IP-адресу, и он всегда будет генерировать число, меньшее или равное размеру массива. Хеш-функция не является случайной функцией, что означает, что для одного и того же ввода вывод всегда будет одинаковым.

Хеш-функция получает ввод, который может быть любой строкой (в данном случае IP), и вычисляет числовое представление. В этом случае числовое представление будет позицией в фильтре Блума, соответствующей входным данным.

Но подождите Что-то не так. Вернемся к нашему сценарию. Представьте, что мы занесли в черный список 100 IP-адресов. Как хеш-функция точно сопоставит наши 100 из возможных 2^32 IP-адресов на 100 различных значений без сохранения какой-либо информации о них? Правда в том, что никак. Будут коллизии. Хэш-функция гарантирует, что каждый IP-адрес будет иметь собственное сопоставление с числом, но, поскольку может быть 4 294 967 296 (2^32) возможных IP-адресов, невозможно сопоставить их все с всего лишь сотней различных значений. Все, что может гарантировать хеш-функция, это то, что она скремблирует биты входных данных так, чтобы выходные данные согласовались с равномерным распределением. Это означает, что если вы измените ввод хеш-функции с 192.168.1.1 на 192.168.1.2, вывод, вероятно, будет совершенно другим, кажущимся случайным (но в действительности не случайным, поскольку каждому вводу всегда будет соответствовать один и тот же вывод).

Пример коллизии. Два разных IP-адреса имеют одинаковый хеш, а это означает, что их индекс в фильтре Блума будет одинаковым.

Хорошо, теперь с самого начала: мы заносим в черный список 100 IP-адресов. Каждый IP-адрес будет проходить через хеш-функцию, и результат хеш-функции вернет число, меньшее или равное размеру массива. Это число будет индексом массива, который отмечает, был ли IP-адрес в черном списке или нет. Но будут коллизии как нам с этим справиться?

Предположим, что IP-адреса 178.23.12.63 и 112.64.90.12 имеют одинаковый хеш. Первый IP попал в черный список, второй нет. Когда мы проверяем, находится ли хеш второго IP-адреса в фильтре Блума, мы его там найдем, даже если этот IP-адрес никогда не попадал в черный список. Означает ли это, что у нас есть ошибка?

Помните, что в начале я предупреждал, что цель фильтра Блума проверить, что элемент НЕ входит в набор данных. Если позиция элемента в фильтре Блума равна 0, этот элемент определенно НЕ входит в набор. Однако, если позиция элемента в фильтре Блума равна 1, то либо этот элемент может все-таки быть в наборе, либо это просто коллизия. Все, что мы можем сделать, это уменьшить вероятность коллизии, чтобы уменьшить количество обращений к памяти, необходимых для проверки, действительно ли IP находится в черном списке.

Снижение вероятности коллизий

Есть два основных способа снизить вероятность коллизий, и оба с нюансами. Одна из возможностей увеличить размер массива. Если мы увеличим размер массива (и, следовательно, заставим хеш-функцию возвращать число меньше или того же размера, что и новый размер массива), вероятность коллизий уменьшается. В частности, вероятность ложного срабатывания (фильтр Блума возвращает 1, когда элемент отсутствует в наборе) составляет (1-e^(m / n)), где m количество элементов, которые предполагается внести в фильтр, а n размер фильтра.

Другой способ уменьшить вероятность коллизии увеличить количество хеш-функций. Это означает, что в нашем сценарии для одного IP-адреса будет использоваться несколько различных хеш-функций, т.е. несколько различных мест в массиве будет помечаться как 1. Если мы используем k хеш-функций, вероятность ложного срабатывания теперь (1-e^(mk/n))^k, что означает, что оптимальное количество хеш-функций равно (n/m)*ln(2) (подробнее об этих уравнениях можно почитать здесь).

Пример фильтра Блума с двумя хеш-функциями. В одном из хешей этих IP-адресов мы наблюдаем коллизию, но все-равно можно проверить, что IP 112.64.90.12 не входит в набор, потому что одна из его позиций фильтра Блума не равна 1.

Ну что ж, а теперь давайте реализуем фильтр Блума в Python и посмотрим на результат! Это займет у нас всего около 50 строк кода.

Давайте начнем с создания класса BloomFilter (в следующем фрагменте кода). Конструктор получает размер фильтра Блума и (это опционально) количество ожидаемых элементов, которые будет хранить этот фильтр Блума. Для создания массива из битов мы будем использовать библиотеку bitarray, и мы установим их все в ноль. Наконец, мы устанавливаем количество хеш-функций в уравнение, которое возвращает оптимальное количество хеш-функций, учитывая размер фильтра Блума и количество ожидаемых элементов.

import mathfrom bitarray import bitarrayclass BloomFilter(object):    def __init__(self, size, number_expected_elements=100000):        self.size = size        self.number_expected_elements = number_expected_elements        self.bloom_filter = bitarray(self.size)        self.bloom_filter.setall(0)        self.number_hash_functions = round((self.size / self.number_expected_elements) * math.log(2))

Теперь давайте определим хеш-функцию для фильтра Блума. Используемая реализация (взятая отсюда) реализует алгоритм DJB2. Сейчас мы будем использовать его как черный ящик, поскольку объяснение это алгоритма выходит за рамки темы этой статьи.

def _hash_djb2(self, s):        hash = 5381        for x in s:            hash = ((hash << 5) + hash) + ord(x)        return hash % self.size

Теперь у нас есть хеш-функция, но как нам создать K хеш-функций? Мы можем сделать один простой фокус. Вместо того, чтобы создавать разные хеш-функции, мы просто будем добавлять число к каждому вводу в хеш-функцию. Число будет представлять из себя номер вызываемой хэш-функции. Поскольку любая небольшая разница во вводе хеш-функции результирует в совершенно другом хеше, результат можно рассматривать как другую хеш-функцию. Круто, правда?

def _hash(self, item, K):        return self._hash_djb2(str(K) + item)

Теперь давайте создадим функцию для добавления элемента в фильтр Блума. Для этого давайте проитерируем все хеш-функции, вычисляя хеш для элемента и, наконец, помещая 1 (или True) в индекс хеша.

def add_to_filter(self, item):        for i in range(self.number_hash_functions):            self.bloom_filter[self._hash(item, i)] = 1

Осталось только создать функцию, которая проверяет, что элемент НЕ находится в фильтре Блума. Для этого давайте еще раз проитерируем по всем хеш-функциям. Если какая-либо из позиций фильтра Блума имеет 0, мы можем сказать, что элемент определенно отсутствует в наборе. В противном случае, если все позиции имеют 1, мы не можем сказать, что элемента нет в наборе.

 def check_is_not_in_filter(self, item):        for i in range(self.number_hash_functions):            if self.bloom_filter[self._hash(item, i)] == 0:                return True        return False

И все! Мы реализовали наш фильтр Блума. Давай протестируем его!

Мы создадим простой тест, чтобы проверить, работает ли он. Давайте создадим фильтр Блума с 1 миллионом записей, а затем установим ожидаемое количество элементов равным 100 000. Мы собираемся добавить элемент 192.168.1.1 в наш фильтр Блума в качестве заблокированного IP-адреса.

bloom_filter = BloomFilter(1000000, 100000)base_ip = "192.168.1."bloom_filter.add_to_filter(base_ip + str(1))

Чтобы проверить это, мы будем итерировать i от 1 до 100 000 и проверять, находится ли IP 192.168.1.i в фильтре Блума (нет таких IP-адресов, где i>254, например 192.168.289, но в данном случае мы просто проводим тест). Мы выведем элементы, о которых мы не знаем, входят ли они в набор; все остальные элементы, которые не будут напечатаны, точно не входят в набор.

for i in range(1, 100000):    if not bloom_filter.check_is_not_in_filter(base_ip + str(i)):        print(base_ip+str(i))

192.168.1.1

Да! Наш фильтр Блума говорит, что из 100 000 IP-адресов единственный элемент, который может быть заблокированным, это действительно наш заблокированный IP-адрес. Никаких ложноположительных результатов!

Вот полный код нашего фильтра Блума:

import mathfrom bitarray import bitarrayclass BloomFilter(object):    def __init__(self, size, number_expected_elements=100000):        self.size = size        self.number_expected_elements = number_expected_elements        self.bloom_filter = bitarray(self.size)        self.bloom_filter.setall(0)        self.number_hash_functions = round((self.size / self.number_expected_elements) * math.log(2))    def _hash_djb2(self, s):        hash = 5381        for x in s:            hash = ((hash << 5) + hash) + ord(x)        return hash % self.size    def _hash(self, item, K):        return self._hash_djb2(str(K) + item)    def add_to_filter(self, item):        for i in range(self.number_hash_functions):            self.bloom_filter[self._hash(item, i)] = 1    def check_is_not_in_filter(self, item):        for i in range(self.number_hash_functions):            if self.bloom_filter[self._hash(item, i)] == 0:                return True        return Falsebloom_filter = BloomFilter(1000000, 100000)base_ip = "192.168.1."bloom_filter.add_to_filter(base_ip + str(1))for i in range(1, 100000):    if not bloom_filter.check_is_not_in_filter(base_ip + str(i)):        print(base_ip+str(i))

Вот и все, что касается фильтров Блума. Я надеюсь, что вам было интересно узнать, что такое фильтр Блума и как его реализовать. Спасибо за внимание!


Перевод статьи подготовлен в преддверии старта курса Data Engineer.

Также приглашаем всех желающих на бесплатный демо-урок по теме ML в Spark. На занятии участники вместе с экспертом узнают об особенностях ML в Spark, рассмотрят процесс разработки моделей и научатся переводить обученные модели в production

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru