Pull to refresh

Comments 24

UFO just landed and posted this here
Этот рисунок аппроксимирует нарисованное на сетку, судя по всему
К слову сказать вы правы, это был баг в оптимизации(точнее в предположении), что я могу помещать посещаемую точку сразу в список закрытых(даже еще не обработав её).
UFO just landed and posted this here
Потому что поверху он считается заблокированным, почему сверху посчитался заблокированным а снизу такая же клетка — нет, думаю проблема где-то с округлением просто
Периодически создаётся ощущение, что написание всяческого рода костылей и велосипедов программисту доставляет гораздо больше, чем использование кладезя человеческой мудрости, накопленной за года придумывания алгоритмов людьми.
Написание своих велосипедов лично мне помогает разобраться и понять эти самые кладези. Плюс, судя потому что видел много разных представлений и трансформаций, единой общепринятой практики нету для этого случая(возможно ошибаюсь и сходу не распознал общей простой идеи, тогда буду благодарен за разъяснения на пальцах).
А в этом велосипеде мне нравится, что он получился локальным(все изменения, не выходят далеко за пределы клетки) и простым (минимум лишнего умножения и деления на что-то, отличное от 2)
Я конечно рискую схватить минусов, но вы пробовали к примеру узнать об A*? В своё время я, разрабатывая поиск пути для Pocket Fallout, переизобрёл этот алгоритм и несколько жалел о потраченном времени, которое могло бы быть потрачено на более полезные штуки.
И не надо заводить речь про «сложную математику», ибо при желании этот алгоритм разбирается на ура, даже не очень сведущими в теории графов людьми.
Так именно A* и использовался здесь, поэтому в конце и написано:
«Теперь осталось натравить A* на это все, например как я это сделал тут...»
Статья вообще о том как легко привести обычную сетку к гексагональной, как раз в контексте использования её A*. Ведь все что требуется алгоритму поиску пути на основании алг. Дейкстры, если задуматься, это: перевод координаты в вершину, вершину в координаты, взять все дуги конкретной вершины, плюс для A* еще эстимация расстояния между двумя врешинами. Вот как раз один из способов реализация этих методов и расписан.
Ясно, просто после диагонального прочтения мне показалось, что вы сделали свой алгоритмический велосипед для поиска пути на гексагональной сетке.

P.S.: Всё-таки, на мой взгляд, удобнее производить преобразование по наклонённым осям (т.е. квадратная по координатам карта будет рисоваться не квадратом, а ромбом), в общем, смотрите классику в виде первого и второго Fallout'а.
Вот этот кстати пункт, что квадратная карта будет рисоваться ромбом, меня тоже насторожил, во первых уж сильно все преобразуется, а во-вторых, адресация памяти может стать сложнее (так двумерном массиве x+y*width вот тебе и элемент в массиве, а как там надо еще смотреть). Возможно зря боюсь, надо просто сесть и разобраться, но у меня был на руках поиск по обычной сетке, и пришла идея как быстро и просто сделать из него поиск по гексагнальной… попробовал, получилось, вот и решил поделится.
А всего напросто, достаточно было изменить функцию поиска соседей (которая кстати простейшая) в любом из алгоритмов поиска пути, и не придумывать никакие отображения гексагонов в параллелепипеды… Вычисление расстояний между клетками вообще ужас, так как расстояние между соседними гексоганальными клетками одинаковое
Пардон, конечно, параллелограммы
Уф. Пойдем по порядку:
Функция поиска соседей вообще-то зависит от представления данных, и для конкретного этого случая она действительно простейшая (и была приведена);
Отображение гексагонов было в прямоугольники(тоже простейшие) и нужно было именно для того, чтобы могли перевести обычные координаты в конкретный гексагон и обратно (а иначе пользы от всего этого, если даже не можем определить по какому из них только что мышкой тыкнули?)
Про одинаковое расстояние между соседями согласен, вот только расстояния мы измеряем не между соседями, а между любыми двумя гексами (это опять же, потому что используем A*, где необходима нижняя оценка оставшегося пути до цели, а не просто Дейкстру)
1 В данном случае речь идет о двумерном массиве.
2 Вычислить клетку, на которую кликнул пользователь не составляет особого труда даже без представления клетки, как прямоугольника, что кстати является крайне не точной аппроксимацией, для этого достаточно знать ширину и длину клетки.
3 Для А* достаточно знать расстояние между двумя соседними клетками (и то это в том случае если у вас переход между клетками не равен 1)
1. И все же, я так и не понял что именно в поиске соседей описанном мною, вам не понравилось? И что можно было сделать в нем еще проще?
2. Но наличие ширины и длины у клетки, как раз и делает ее прямоугольником, опять же, если я что-то перемудрил с представлением клетки, буду рад услышать как можно проще вычислить клетку на которую кликнули.
3. Мне кажется, вы путаете A* с алгоритмом Дейкстры, знать расстояние между соседними достаточно только для оригинального алгоритма Дейкстры, для A* нам нужно еще уметь ранжировать текущие открытые вершины. Чаще всего для этого используется f(x) = g(x) + h(x), где g(x) длина пройденного пути, h(x)- оптимистичная оценка оставшегося пути. Вот именно для h(x) — и нужно знать расстояния между не соседними клетками.
1 Изначально я написал, что мне не понравилось представление гексагональной сетки в виде прямоугольной.
2 Наличие ширины и длины не делает клетку прямоугольной, так как она гексагональная изначально. И как мне кажется, x/w не даст правильную координату х, потому что при клике в крайние «треугольные области» клетки точно нельзя сказать куда кликнул пользователь.
1. Изначально написали% «достаточно было изменить функцию поиска соседей (которая кстати простейшая) в любом из алгоритмов поиска пути»- но как сделать легко и просто в вашем понимании я пока так и не понял.
2. Да, я прекрасно понимаю, что это только аппроксимация, но если учесть на сколько она проста, и какая у нее ошибка, то компромисс как по мне достаточно хорош, чтобы иметь право на жизнь.

Вообще(по моему личному убеждению) одно из главных качеств ориентированных на игры программистов- это как раз уметь увидеть и сделать адекватную аппроксимацию какой-либо модели
1 Ну с описанным вами способом я согласен.
2 С учетом того, что эти области занимают чуть ли не четверть клетки, я бы не назвал это удачной аппроксимацией.
2. В вас говорит или заядлый математик, или идеалист-программист:-)
Да, погрешность 1/8 клетки в сумме получается, может это и много (особенно если гексы большие), но именно свойство локальности изменений, позволяет при необходимости большей точности, дописать к ней дополнения, учитывающие и эти крайние треугольники.
На мой взгляд, это не настолько сложная задача, что бы сразу ее сделать правильно, что даст максимальный комфорт пользователю, так как он будет тыкать куда считает нужным и точно знать, что при этом произойдет. И идеализм тут не причем, это обычное юзабилити. Т.к. я с 100% уверенностью могу сказать, что после 5-10 кликов после, которых следует неверное поведение, пользователь просто забьет.
К слову сказать, такую аппроксимацию (или похожую на эту) тоже достаточно много описывают, например даже тут:
www-cs-students.stanford.edu/~amitp/game-programming/grids/
Но вообщем то, каждый сам решает какая ему точность нужна :-)
А чистый алгоритм Дейкстры вам чем не угодил?
A* -это расширение над над алгоритмом Дейкстры, и позволяет достичь в общем случае лучшей производительности и (при правильной эвристике) сделать это без потери качества.
Sign up to leave a comment.

Articles