Xonix на Javascript с картинками

[saboteur_kiev]

Я не помню на каком дремучем компе в середине 80-х я впервые увидел Xonix. А он УЖЕ чей-то клон…

[DAiMor]

То возможно был Агат, сам впервые играл в Xonix именно на нем, а точнее на Агат-9

[khim]

Причём Агат — это ведь тоже клон!

[srgdmitriy]

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

[khim]

Тут вам не 80е! Тут нельзя просто пару раз по всем точкам пройтись и всё!

А вот зачем ввели «угол в градусах» — этого я уж совсем понять не могу. Разве с заданием движения в виде пары чисел (Δx, Δy) не удобнее работать? Кстати в JavaScript Δx и Δy — валидные называния переменных, так что можно писать что-нибудь типа

direction = { Δx: 1, Δy: 0}

— просто и понятно.

[xmeoff]

Наверное это дело вкуса. Мне лично удобнее работать с градусами. К тому же так легче рассчитывать отскок точек от границ.

[khim]

Это какую же операцию делать легче, я извиняюсь? Рассчёт отскока с парой чисел выглядит так:

if allowed(X + Δx, Y + Δy) return [Δx, Δy] // Движение вперёд
if allowed(X - Δx, Y + Δy) return [-Δx, Δy] // отражение по X
if allowed(X + Δx, Y - Δy) return [Δx, -Δy] // отражение по Y
return [-Δx, -Δy] // возврат

В буквальном смысле четыре строчки. Ну ещё пяток чтобы реально точку передвинуть. Как это делать непосредственно с градусами — я вообще себе представить не могу! Собственно тот алгоритм, что у вас реализован так и работает — с той только разницей, что у вас там есть ещё дополнительная сущность предназначенная «для запутывания противника».

[xmeoff]

Наверное вы этого не знаете, но в HTML5 Canvas заливка работает не так, как во многих (десктопных) графических библиотеках. Здесь не получится просто указать точку «где-то внутри» замкнутой области и цвет заливки. Здесь нужно явно задавать контур заливаемой области (см. описание Canvas.fill). Что возвращает нас к задаче определения контуров.
Но даже если бы в Canvas заливка работала «привычным» способом, это все равно не решило бы всех проблем. Главная (но не единственная) проблема — в том, что заливать нужно не все замкнутые области, а только те, внутри которых нет «морских» точек. Что в итоге опять же возвращает к задаче определения контуров).

[srgdmitriy]

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

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

[Goodkat]

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

[srgdmitriy]

Неверно. В ксониксе захваченная территория всегда та, на которую, после очередного прокладывания следа, не могут попасть «морские» точки-враги. Не важно какая часть больше, а какая меньше. Сам след при этом всегда превращается в захваченную территорию.

А про скриншот-2 перефразирую еще раз: заливкой мы ищем не захваченную территорию, а наоброт, территорию которая осталась за врагами, т.е. заливаем области начиная с «морских» точек-врагов, со всех по очереди. Потом смотрим что осталось незалито — это и есть захваченная территория.

[Goodkat]

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

В таком случае всё как-то слишком уж упрощается. Главное — стек не переполнить при рекурсивной заливке :)

[khim]

Лучше не стек, а очередь. Меньше вероятность переполнения. Обычно там живёт «расширяющийся граница», но изначально туда кладут одну точку. Тут же нужно туда сразу положить сразу все морские точки, а дальше — как обычно.

[xmeoff]

Эти области (с «морскими» точками) и не нужно заливать, они и так уже залиты нужным цветом (черным). Или вы предлагаете заливать их другим цветом? Как это поможет залить (стереть) области без морских точек?
Само собой, рекурсивный алгоритм реализуется гораздо проще. Но лично я предпочитаю не использовать рекурсию там, где можно обойтись без нее.

[khim]

Нужно залить их другим цветом на «теневой» графической странице, а то, что там осталось чёрным нужно на основной странице — перекрасить. Делов-то. Так оно делалось в 80е, когда никаких хитрых библиотек ни у кого не было, а зато пара графических страниц — была (обычно она использовалась чтобы можно было вывести новое изображение, а потом «в один фрейм» сменить новое на старое).

[xmeoff]

Я в курсе про заливку растра. Только вот речь в этой ветке шла о том, чтобы использовать заливку так сказать «из коробки». Если же реализовывать ее самому, то я не вижу никаких преимуществ по сравнению с описанным мной методом. Этот метод, во-первых — не рекурсивный. Во вторых, он не обходит все ячейки внутри области: алгоритм нахождения контуров проверяет только ячейки контура плюс соседние с ними; а алгоритм разбиения на прямоугольники имеет дело с вершинами многоугольника, число которых на порядок меньше даже числа ячеек контура, не говоря уже о всех ячейках области. Ну и в-третьих, этот метод сводит к минимуму число графических операций. Здесь не считывается цвет каждой проверяемой ячейки, и закрашиваются здесь не ячейки, а прямоугольники, из которых состоит область. Сколько прямоугольников, столько и графических операций (вызовов метода clearRect).

[srgdmitriy]

Вы как-то совсем неверно воспринимаете мои слова, или я на столько косноязычен? Про заливку из коробки я ничего не говорил. И при чем тут вообще цвет? При чем тут графические операции? Почему увидев слово «заливка» вы подумали не про алгоритм, а про фукнцию заливки в «десктопных» графических библиотеках?

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

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

[xmeoff]

Я и в самом деле вас неверно понял. Мне почему-то показалось, что вы имели в виду стандартную функцию заливки.
Теперь я понял вашу мысль: не париться по поводу эффективности, а использовать готовый алгоритм. Возможно, я действительно перемудрил и стоило так и сделать.
И все же я считаю проблемой общих алгоритмов заливки то, что они не учитывают особенности данной конкретной задачи — информацию о следе курсора. Поэтому им приходится так или иначе проверять все возможные элементы (все ячейки сетки). К тому же для данной задачи это придется делать два раза: первый раз, чтобы, как вы писали, найти незахваченные территории (отметить их); а второй — чтобы найти оставшиеся, т.е. захваченные. За один заход, мне кажется, вы это сделать не сможете.

Насчет сканирования линий. Этот метод, конечно, не рекурсивный, но он тоже проверяет все элементы. К тому же он не подходит для определения захваченных/незахваченных областей.

[elgordo]

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

Сам пишу сейчас Xonix… И вот идея родилась буквально секунду назад. У нас есть начальная и конечная точки движения игрока. Наша задача — определить кратчайший путь, соединяющий их по суше, исключая точки, нарисованный самим игроком. Вот и всё, контур найден. В качестве алгоритма можно использовать поиск выхода из лабиринта для роботов (тоже рекурсия). Ну а дальше уже алгоритм поиска любой точки внутри контура.