Прямоугольные тайловые миры04.05.2021 06:03

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

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

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

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

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

Прямоугольные сетки

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

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

Для понимания игрового мира необходима система коорднат. Обычно она состоит из двух осей (для двумерного мира) — X и Y. Внутри самой сетки направим оси как экранные — ось X вправо, ось Y вниз. Единичные отрезки представляют ячейки. Для связи сеточной системы отсчета с экранной необходимы базисные векторы, которые будут направлены вдоль осей сетки. Длины таких векторов будут равны размерам ячейки в пикселях, а начало системы отсчета, аналогично экранной, поместим в левый верхний угол:

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

const cell_width = 48 # width of cell in pixels
const cell_height = 32 # height of cell in pixels
# Basis vectors
var srv = Vector2(cell_width, 0) # screen-right-vector
var sdv = Vector2(0, cell_height) # screen-down-vector

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

С преобразованием ячейки в пиксель проблем возникнуть не должно. Если клетка имеет координаты {x; y}, это значит, что на экране она находится на x горизонтальных и на y вертикальных базисов от начала координат:

func cell2pixel(cell:Vector2) -> Vector2:
	return srv*cell.x + sdv*cell.y

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

func cell2pixel_center(cell:Vector2) -> Vector2: # To cell center
	return cell2pixel(cell)+srv/2+sdv/2 # cell2pixel returns left-top corner

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

А как из пикселя получить ячейку? Если говорить простым языком, точка лежит в ячейке, пока она находится в пределах ее длины и высоты. Это означает, что для смещения к следующей ячейке необходимо переместится на ее размер на экране. Тогда точные координаты в сеточной системе отсчета можно найти через деление каждой координаты пикселя на соответствующий ей размер ячейки. В результате деления получится дробное число, вещественная часть которого показывает смещение пикселя внутри клетки относительно ее верхнего угла. Т.к. нас интересует только ячейка, округлим к ближайшему меньшему целому. Это важно, ведь при маленьких дробных отрицательных значениях (по модулю <1) приведение к int все равно покажет 0, хотя это уже отрицательная часть:

func pixel2cell(pixel:Vector2) -> Vector2:
	var x = floor(pixel.x/cell_width)
	var y = floor(pixel.y/cell_height)
	return Vector2(x, y)

Однако такие преобразования можно описать более точно, с помощью математики. Мы имеем базис из векторов srv{cell_width; 0} и sdv{0; cell_height}. Представив его в виде матрицы запишем преобразование координат ячейки в координаты пикселя как произведение матрицы и вектора:

А для нахождения отсюда pixel нужно обратить матрицу:

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

Как видим, все прекрасно работает:

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

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

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

const map_width = 5
const map_height = 5

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

func draw_grid(surf:RID, color:Color, width=1.0, antialiasing=false) -> void:
	for i in range(map_width+1):
		VisualServer.canvas_item_add_line(surf, cell2pixel(Vector2(i, 0)), cell2pixel(Vector2(i, map_height)), color, width, antialiasing)
	for i in range(map_height+1):
		VisualServer.canvas_item_add_line(surf, cell2pixel(Vector2(0, i)), cell2pixel(Vector2(map_width, i)), color, width, antialiasing)

Получаем обычную прямоугольную сетку, то что нужно:

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

func draw_open_grid(surf:RID, color:Color, width=1.0, antialiasing=false) -> void:
	for i in range(1, map_width):
		VisualServer.canvas_item_add_line(surf, cell2pixel(Vector2(i, 0)), cell2pixel(Vector2(i, map_height)), color, width, antialiasing)
	for i in range(1, map_height):
		VisualServer.canvas_item_add_line(surf, cell2pixel(Vector2(0, i)), cell2pixel(Vector2(map_width, i)), color, width, antialiasing)

Рисование ячейки

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

func draw_cell(cell:Vector2, surf:RID, color:Color, width=1.0, antialiasing=false):
	var points = PoolVector2Array([
		cell2pixel(cell), # Левый верхний угол
		cell2pixel(cell)+srv, # Прибавили правый базис, правый верхний угол
		cell2pixel(cell)+srv+sdv, # Прибавили оба базиса, правый нижний угол
		cell2pixel(cell)+sdv, # Прибавили нижний базис, левый нижний угол
		cell2pixel(cell) # Замыкаем цепочку
	])
	VisualServer.canvas_item_add_polyline(surf, points, [color], width, antialiasing) 

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

func fill_cell(cell:Vector2, surf:RID, color:Color) -> void:
	VisualServer.canvas_item_add_rect(surf, Rect2(cell2pixel(cell), Vector2(cw, ch)), color)

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

Изометрические сетки

Если вы промотали часть про прямоугольные сетки досюда — я не удивлен. Во всяком случае они выглядят не так красиво, как изометрические. Вообще такой стиль в свое время опередил технологии — он создал объем тогда, когда это еще не было доступно в виду ограниченности технологических ресурсов. Типичным представителем являются в свое время очень популярные казаки:

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

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

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

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

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

Зададим размер ячейки и два значения — cw как половина горизонтальной диагонали и ch как половина вертикальной. Как упоминалось ранее, сетка сжимается по вертикали вдвое, значит вертикальная диагональ, изначально равная горизонтальной, тоже уменьшилась вдвое:

const cell_size = 60
# работать с int гораздо проще, поэтому убираем вещ. часть,
# от этого сильно ничего не поменяется.
cw = int(cell_size/2) # cell-width
ch = int(cw/2) # cell-height

Через эти значения базисные векторы можно задать проще простого:

...
right_basis = Vector2(cw, ch) # вектор по X
left_basis = Vector2(-cw, ch) # вектор по Y

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

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

func cell2pixel(cell:Vector2) -> Vector2:
	return cell.x*right_basis + cell.y*left_basis

Для получения центра ячейки аналогично прямоугольной сетке прибавляем по половинке базисов:

func cell2pixel_center(cell:Vector2) -> Vector2:
	return cell2pixel(cell)+right_basis/2+left_basis/2

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

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

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

func pixel2cell(pixel:Vector2) -> Vector2:
	var x = pixel.x/cw + pixel.y/ch
	var y = pixel.y/ch - pixel.x/cw
	return Vector2(floor(x/2), floor(y/2))

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

Преобразование угла

Как найти угол между двумя ячейками понятно — находим соединяющий их вектор через разность, потом определяем его угол. Но могут возникнуть проблемы когда нам известен только угол. Например, корабль хочет выстрелить вправо, т.е. под 0° относительно себя. Такое направление указывает вдоль горизонтальной оси, но мы знаем, что изометрическая ось не особенно то и совпадает с экранной. Как перевести одно в другое мы уже выяснили, а если угол произвольный? Тут тоже пригодятся описанные выше преобразования. Представим угол через вектор с координатами {cos a; sin a} и прогоним его через ту же функцию, после чего найдем угол вектора с преобразованными координатами:

func iso2linear(angle:float) -> float:
	var x = cos(angle)
	var y = sin(angle)
	return cell2pixel(Vector2(x, y)).angle()

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

func linear2iso(angle:float) -> float:
	var x = cos(angle)
	var y = sin(angle)
	var x1 = x/cw + y/ch
	var y1 = y/ch - x/cw
	return Vector2(x1, y1).angle()

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

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

Произвольное изометрическое искажение

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

var iso_scale = 2.0

Тогда единственное, что нужно поменять, это значение переменной ch:

...
ch = int(cw/iso_scale)
...

И все. Все предыдущие функции будут работать как прежде. Вот, например, соотношение 1 к 1.43:

Порядок рисования объектов

Вряд ли вы хотите увидеть в своей игре что такое:

Те блоки, которые ближе к нам, перекрываются дальними, поэтому создается впечатление что мы строим в высоту, хотя это не так. Если в простой прямоугольной сетке мы можем определять порядок отрисовки по Y координате, то здесь оба базиса смотрят вниз и определить по одному из них порядок рисования не выйдет. В изометрии мы можем сортировать объекты по диагоналям, потому как их ряды идут точно вниз. Каждая ячейка в ряду имеет одну и ту же сумму координат, поэтому именно эту сумму мы и будем использовать как z_index объекта (в godot эта переменная у двумерных объектов обозначает порядок их рендера. Чем этот индекс выше, тем позже рисуется объект):

При изменении позиции приравниваем z_index к pos.x+pos.y (pos — позиция объекта на сетке):

func set_pos(cell):
	pos = cell # сохраняем значение в свою локальную переменную
	position = Grid.cell2pixel(pos) # ставим объект на экране в нужную точку
	z_index = pos.x+pos.y # устанавливаем порядок отрисовки

Теперь все рисуется как надо и создается необходимая иллюзия объема:

Прямоугольные изометрические сетки

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

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

Система координат внутри сетки все остается прежней, потому как, напоминаю, мы меняем только вид на нее. Базисы точно также будут направлены вдоль изометрических осей, а вот для задания их координат необходимо повозиться. Дело в том, что у таких ячеек нет размеров, независящих от вертикальных преобразований, все стороны и диагонали будут менять свои размеры. Но мы же знаем, что при вертикальных преобразованиях точки не перемещаются по X, а это значит что проекции всех величин на эту ось тоже сохраняются. В качестве размеров можно взять просто длину и высоту, как в случае с обычными прямоугольными сетками. Это будут размеры в натуральную величину, т.е. при отсутствии изометрических искажений, и именно при таком виде можно и найти проекции. Без искажений угол между экранной горизонтальной осью и обеими изометрическими будет 45°. Используя его, найдем проекции:

const cell_width = 93 # Real cell width
const cell_height = 67 # Real cell height

pw = int(round(cell_width*cos(PI/4))) # Проекция длины
ph = int(round(cell_height*cos(PI/4))) #  Проекция высоты

Тогда синий вектор будет иметь координаты {pw; pw}, а красный {-ph; ph}. Для создания изометрического искажения просто делим Y-компоненту каждого базиса на коэффицент этого искажения:

const iso_scale:float = 2.0
...
srd = Vector2(pw, pw/iso_scale) # screen-right-down
sld = Vector2(-ph, ph/iso_scale) # screen-left-down

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

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

func cell2pixel(cell):
	return cell.x*srd+cell.y*sld

И с получением центра ничего не поменялось (да ладно):

func cell2pixel_center(cell): # To cell center
	return cell2pixel(cell)+srd/2+sld/2

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

Выносим двойку и округляем:

func pixel2cell(pixel):
	var x = pixel.x/pw + iso_scale*pixel.y/pw
	var y = iso_scale*pixel.y/ph-pixel.x/ph
	return Vector2(floor(x/2), floor(y/2))

Ну и куда же без визуализации:

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

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

func draw_grid(surf, color, width=1.0, antialiasing=false):
	for i in range(map_width+1):
		VisualServer.canvas_item_add_line(surf, cell2pixel(Vector2(i, 0)), cell2pixel(Vector2(i, map_height)), color, width, antialiasing)
	for i in range(map_height+1):
		VisualServer.canvas_item_add_line(surf, cell2pixel(Vector2(0, i)), cell2pixel(Vector2(map_width, i)), color, width, antialiasing)

И рисование ячейки не тоже изменилось:

func draw_cell(cell, surf, color, width=1.0, antialiasing=false):
	var points = PoolVector2Array([
		cell2pixel(cell),
		cell2pixel(cell)+srd,
		cell2pixel(cell)+srd+sld,
		cell2pixel(cell)+sld,
		cell2pixel(cell),
	])
	VisualServer.canvas_item_add_polyline(surf, points, [color], width, antialiasing)

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

func fill_cell(cell, surf, color):
	var points = PoolVector2Array([
		cell2pixel(cell),
		cell2pixel(cell)+srd,
		cell2pixel(cell)+srd+sld,
		cell2pixel(cell)+sld
	])
	VisualServer.canvas_item_add_polygon(surf, points, [color])

Алгоритмы на сетках

Рисовать сетки конечно здорово, но на этом далеко не уедешь. В игре должны быть какие то механики, какое то движение и интерактивность, без этого это просто приложение, рисующее красивые (или не очень) каринки.

Поворот изометрического объекта

В играх часто нужно направить объект на курсор. В случае top-down вида это делается поворотом самого спрайта объекта, а вот в псевдо 3d вращать спрайт не очень хорошая затея:

Для создания объема необходимо несколько спрайтов, по одному на каждое направление. Для выбора нужного спрайта необходимо понять, какое из 8-ми направлений наиболее близко к направлению до курсора. Каждое из них можно задать относительную ячейку, ({-1; 0} — влево, {-1, -1} — влево вверх и т.д.) и искать направление до клетки через направляющие. Звучит немного непонятно, поэтому поясню. Чтобы перейти из ячейки {1, 2} в ячейку {5, 2} нам необходимо передвинутся вправо 4 раза. Понять мы это можем вычитаением из конечной ячейки начальной (5–1 = 4). Сколько именно раз надо передвинутся нам не важно, нас интересует направление. В данном случае разница между координатами положительна, значит двигаемя вдоль оси X. Тоже самое и с вертикальными координатами. Однако если мы просто запишем знаки разностей в координаты направляющего вектора, получится неравномерное распределение, ведь достаточно разности в единицу, чтобы вектор указывал на это направление. Тут лучше показать:

Как мы видим, кораблик смотрит вдоль осей только тогда, когда мы указываем прямо на них, а в остальных случаях он смотрит в какой то из углов. Так дело не пойдет, надо как то расширять углы осевых направлений. Для начала мы можем ограничить угловые направления посредством введения условия, что разность между разностями координат (WAT) будет менее какого то числа. Чем это число больше, тем больше область у угловых направлений. Если же эта разность больше этого числа, значит это одно из осевых направлений. Какое именно можно узнать, сравнив модули разностей кординат. Если разность больше по X, значит это горизонтальное направление, иначе вертикальное. Возможно звучит непонятно, но в коде должно быть яснее:

func direct_cell(cell1, cell2):
	var res = cell2-cell1 # вектор разности
  # В качестве этой константы я выбрал 4, она показалась мне наиболее 
  # правдоподобной
	if abs(abs(res.x)-abs(res.y)) > 4: # Проверяем, осевое ли это направление
		if abs(res.x) > abs(res.y): # Если да, то смотрим какое именно
			return Vector2(sign(res.x), 0) # Разница по x больше, значит горизонтальное
		else:
			return Vector2(0, sign(res.y)) # Разница по y боьше, значит вертикальное
	else:
		return Vector2(sign(res.x), sign(res.y)) # Угловове направление

Для удобной работы со спрайтами их можно разместить кругом:

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

Поиск пути

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

class PriorityStack:
	
	var items:Array
	
	func _init():
		items = Array()
		
	func empty() -> bool:
		return items.size() == 0
		
	func 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])
					break
					
	func take(): # "get" name already taken by Variant
		return items.pop_front()[0]

func in_map(grid_pos:Vector2, map_size:Vector2) -> bool:
	return grid_pos.x < map_size.x and grid_pos.x >= 0 and grid_pos.y >= 0 and grid_pos.y < map_size.y

func can_stand(grid_pos:Vector2, obsts:PoolVector2Array, map_size:Vector2) -> bool:
	return not (grid_pos in obsts) and in_map(grid_pos, map_size)

func neighbors(grid_pos:Vector2,  obsts:PoolVector2Array, map_size:Vector2) -> PoolVector2Array:
	var res:PoolVector2Array = []
	var _neighbors = PoolVector2Array([grid_pos+Vector2(-1, 0), grid_pos+Vector2(1, 0), 
		grid_pos+Vector2(0, -1), grid_pos+Vector2(0, 1)])
	for neigh in _neighbors:
		if can_stand(neigh, obsts, map_size):
			res.append(neigh)
	return res

func heuristic(a:Vector2, b:Vector2) -> int:
	return int(abs(a.x-b.x)+abs(a.y-b.y))

func find_path(start:Vector2, goal:Vector2, obsts:PoolVector2Array, map_size:Vector2) -> PoolVector2Array:
	var frontier = PriorityStack.new()
	frontier.put(start, 0)
	var came_from = {}
	var cost_so_far = {}
	came_from[start] = start
	cost_so_far[start] = 0
	
	var current:Vector2
	var new_cost:int
	
	if not can_stand(goal, obsts, map_size):
		return PoolVector2Array()
		
	while not frontier.empty():
		current = frontier.take()
			
		if current == goal:
			break
			
		for next in neighbors(current, obsts, map_size):
			new_cost = cost_so_far[current] + 1
				
			if not (next in cost_so_far) or new_cost < cost_so_far[next]:
				cost_so_far[next] = new_cost
				frontier.put(next, new_cost + heuristic(goal, next))
				came_from[next] = current
				
	if frontier.empty() and current != goal:
		return PoolVector2Array()
		
	current = goal
	var path:PoolVector2Array = PoolVector2Array([current])
	
	while current != start:
		current = came_from[current]
		path.append(current)
	
	path.invert()
	path.remove(0) # removes first position
	return path

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

Растеризация различных фигур

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

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

Тут реализована максимально простая версия алгоритма, опять же не претендующая на максимум производительности:

func rast_line(start:Vector2, goal:Vector2) -> PoolVector2Array:
	var res:PoolVector2Array = []
	var steep = abs(goal.y-start.y) > abs(goal.x-start.x)
	if steep:
		start = Vector2(start.y, start.x)
		goal = Vector2(goal.y, goal.x)
	var reverse = start.x > goal.x
	if reverse:
		var x = start.x
		start.x = goal.x
		goal.x = x
		
		var y = start.y
		start.y = goal.y
		goal.y = y
		
	var dx = goal.x - start.x
	var dy = abs(goal.y - start.y)
	var error = dx/2
	var ystep = 1 if start.y < goal.y else -1
	var y = start.y
	for x in range(start.x, goal.x+1):
		if steep:
			res.append(Vector2(y, x))
		else:
			res.append(Vector2(x, y))
		error -= dy
		if error < 0:
			y += ystep
			error += dx
	if reverse:
		res.invert()
	return res

И вот так это все работает:

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

func rast_circle(center:Vector2, radius:int) -> PoolVector2Array:
	var x:int = 0
	var y:int = radius
	var delta:int = 1-2*radius
	var error:int = 0
	var res:PoolVector2Array = []
	while y >= 0:
		if not center+Vector2(x, -y) in res:
			res.append(center+Vector2(x, -y))
		if not center+Vector2(-x, y) in res:
			res.append(center+Vector2(-x, y))
		if not center+Vector2(-x, -y) in res:
			res.append(center+Vector2(-x, -y))
		if not center+Vector2(x, y) in res:
			res.append(center+Vector2(x, y))
		error = 2*(delta+y)-1
		if delta < 0 and error <= 0:
			x += 1
			delta += 2*x+1
		elif delta > 0 and error > 0:
			y -= 1
			delta -= 2*y+1
		else:
			x += 1
			y -= 1
			delta += 2*(x-y)
	return res

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

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

func rast_ellipse(center:Vector2, size:Vector2):
	var res = PoolVector2Array([])
	var x = 0
	var y = size.y
	var a_sqr = size.x*size.x
	var b_sqr = size.y*size.y
	var delta = 4*b_sqr*(x+1)*(x+1) + a_sqr*(2*y-1)*(2*y-1) - 4*a_sqr*b_sqr
	while (a_sqr*(2*y-1) > 2*b_sqr*(x+1)):
		res.append(center+Vector2(x, y))
		res.append(center+Vector2(-x, y))
		res.append(center+Vector2(x, -y))
		res.append(center+Vector2(-x, -y))
		if delta < 0:
			x += 1
			delta += 4*b_sqr*(2*x+3)
		else:
			x += 1
			delta = delta-8*a_sqr*(y-1)+4*b_sqr*(2*x+3)
			y -= 1
	delta = b_sqr*(2*x+1)*(2*x+1)+4*a_sqr*(y+1)*(y+1)-4*a_sqr*b_sqr
	while y+1 != 0:
		res.append(center+Vector2(x, y))
		res.append(center+Vector2(-x, y))
		res.append(center+Vector2(x, -y))
		res.append(center+Vector2(-x, -y))
		if delta < 0:
			y -= 1
			delta += 4*a_sqr*(2*y+3)
		else:
			y -= 1
			delta -= 8*b_sqr*(x+1) + 4*a_sqr*(2*y+3)
			x += 1
			
	return res

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

Заключение

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

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

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

Я благодарен вам за прочтение и желаю такой удачи, какой не желал еще никто!