Зона видимости и поведение мобов

Темы, связанные с проектированием и программированием roguelike-игр

Модераторы: Sanja, Максим Кич

Ответить
vapekreng
Сообщения: 63
Зарегистрирован: 22 фев 2016, 22:33

Зона видимости и поведение мобов

Сообщение vapekreng » 22 фев 2016, 22:43

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


каждый тайтл имеет уровень проходимости
0 - свободный тайтл, пройти может любой
1 - закрытая незапертая дверь, открыть можно
2 - вода, можно, если умеешь плавать, но долго
3 - закрытая дверь, некоторые мобы могут выбить
4 - моб

Построение карты дальности.
В начале хода вокруг героя строится карта пути: минимальная дальность пути до каждой достижимой клетки карты.
1. Сначала все смежные точки маркируются 1000 или 1410, всё это кидается в список №1.
2. В списке №1 по циклу проверяется расстояние до смежных точек. Если метки нет, то маркируется и в список №2, если метка есть, то сверяется с новым расстоянием, если оно меньше, то маркируется заново и в список №2.
3. Список №1 удаляется. Если список №2 не пуст, то список №2 переименовывается в список №1. Идем на шаг 2.

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

Свет распространяется по прямой, т.е. по кратчайшему пути. Карта света строится, прокладывая пути игнорируя все препятствия (ренген) на расстояние не превосходящее максимальную дальность зрения мобов на карте (герой тоже моб) т.к. больше не нужно. На соседнюю клетку 1000 энки, наискосок 1415. Если длинна пути до клетки равна длинне прямой, то зона прямой видимости и клетка видна герою при условии, что хватает дальности взгляда. Дальность видимости равна (восприятие+3)*1000. Видимость героя мобу: сравнивается дальность пути с дальностью света: если равны, то проверяется дальность взгляда моба, если не меньше, то заметил. Заметив, моб получает в список сразу весь набор координат для движения на тот случай, если потерят героя из зоны видимости. В этом случае он идет на точку, на которой видел героя последний раз. Флаг поведения меняется с брожения на погоню.

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

1. При заходе перса на уровень создаётся список мобов (включая перса), который упорядочивется по скорости.
2. Первоначальный уровень энергии у каждого моба равен 0
3. При выполении любого действия тратится энергия
4. Первый моб делает ход
5. Далее цикл:
а. Проверяем список мобов с начала, пока не найдем моба с уровнем энергии 0 или выше.
б. Если нашли, то даём ему ход, иначе увеличиваем таймер времени.
в. При увеличении таймера времени каждый моб получает количество энергии, равное его скорости.
г. переходим к а.
При выходе с уровня и переходе на другой список составляется заново.

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: Зона видимости и поведение мобов

Сообщение Максим Кич » 23 фев 2016, 00:25

каждый тайтл имеет уровень проходимости
А потом мы захотим добавить в игру зыбучий песок. А потом у нас появится монстр, который маскируется под запертую дверь (да, запертая дверь тоже появится) и который стоит за зыбучем песке… В общем, гарантированная дорога в ад из слабо связанных «magic numbers», вымощенная каскадами условных переходов.

Я остаюсь сторонником следующего подхода:
Tile — объект у которого есть события:
onCharacterEntryAttempt, onCharacterEntry, onCharacterStand, onCharacterLeaveAttempt, onCharacterLeave — где Character это любой игровой объект, способный перемещаться, будь до моб или герой.
У тайла есть свойства floor, wall, character, loot[] которые отвечают за пол, стену(дверь), ссылку на моба/игрока и стек с лутом, буде там что-то лежит. Соответственно, отрисовка идёт по порядку floor, loot, wall, character. Если это тайловый рогалик, то они перекрываются, если ASCII — рисуется последний в списке.

Если это сильно круто, то для начала можно просто составить индексы для пола (1 — пол, 2 — вода, 3 — лава, и т.д.), стен (0 — нет стены, 1 — камень, 2 — закрытая дверь) и так далее и хранить это в записи или массиве. Тоже будет работать, но не так красиво и с меньшим запасом для расширения.
Построение карты дальности.
Что такое «1000 или 1410» я так и не понял.
Проходить всю карту алгоритмом заливки с пересчётом расстояния до игрока мне кажется сильно расточительным. Но при нынешних машинах, скорее всего, будет работать без проблем. Правда, этот подход сразу обрубает другие тактики кроме как «бежать к игроку/от игрока», потому что для каждой новой точки надо будет пересчитывать карту дальности.
В принципе, можно строить заливку от всех мобов и игрока одновременно — так будет меньше впустую залитых клеток. Но что-то мне подсказывает, что классика вроде А* будет работать лучше.
дополнительная карта дальности создается в начале хода для каждого моба с флагом погоня
Крайне избыточное решение. Моб не может занять клетку уже занятую им, поэтому можно всех мобов считать препятствиями на общей карте. Более быстрые мобы, более медленных будут огибать по той же причине, по которой они будут огибать колонны.
Видимость героя мобу: сравнивается дальность пути с дальностью света
А вот это уже интересная мысль. На самом деле, это может быть очень дешёвый FOV — так же можно сравнивать не только монстров но и стены. Взять предрассчитанную матрицу расстояний от смещения, где Mdist[0][0] = 0 (принимаем координаты игрока за ноль), а Mdist[m][n] = sqrt(m² + n²), вычесть значения из карты дальности по тем же координатам и, чисто теоретически, в видимых тайлах будут нули (чисто практически, скорее всего, у такой проверки будет свой набор артефактов, от которых будет сложно избавиться)
список очередности ходов
Имхо, нормально.
Dump the screen? [y/n]

vapekreng
Сообщения: 63
Зарегистрирован: 22 фев 2016, 22:33

Re: Зона видимости и поведение мобов

Сообщение vapekreng » 23 фев 2016, 01:06

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

1.
У тайла есть свойства floor, wall, character, loot[] которые отвечают за пол, стену(дверь), ссылку на моба/игрока и стек с лутом, буде там что-то лежит. Соответственно, отрисовка идёт по порядку floor, loot, wall, character. Если это тайловый рогалик, то они перекрываются, если ASCII — рисуется последний в списке.
Согласен, но пока не особо представляю, как реализовать, т.к. пишу на FPC для консоли

2.
Что такое «1000 или 1410» я так и не понял.
Проходить всю карту алгоритмом заливки с пересчётом расстояния до игрока мне кажется сильно расточительным. Но при нынешних машинах, скорее всего, будет работать без проблем. Правда, этот подход сразу обрубает другие тактики кроме как «бежать к игроку/от игрока», потому что для каждой новой точки надо будет пересчитывать карту дальности.
В принципе, можно строить заливку от всех мобов и игрока одновременно — так будет меньше впустую залитых клеток. Но что-то мне подсказывает, что классика вроде А* будет работать лучше.
1000 - базовая стоимость перемещения (любого действия, в принципе тоже) на одну клетку по прямой. если перемещаемся наискосок, то затраты энергии выше :изменение координаты по двум осям) и равны корню из 2, т.е. 1.41
пересчет карты дальности для моба (при условии, что атакуют-догоняют 2 и боле мобов) задумал, чтобы более быстрые мобы не ждали медленных, а медленные или подходили другим путем или ждали рядом, пока не освободится место для атаки
Крайне избыточное решение. Моб не может занять клетку уже занятую им, поэтому можно всех мобов считать препятствиями на общей карте. Более быстрые мобы, более медленных будут огибать по той же причине, по которой они будут огибать колонны.
идея в том, чтобы моб менялся местами с более медленным. но не мешал боле быстрым. карта делается для каждого моба отдельно. но переменная одна и та же для всех, т.к. после хода нет смысла её помнить. в итоге, более быстрый моб для более медленного - помеха, а более медленный для более быстрого - нет


А вот это уже интересная мысль. На самом деле, это может быть очень дешёвый FOV — так же можно сравнивать не только монстров но и стены. Взять предрассчитанную матрицу расстояний от смещения, где Mdist[0][0] = 0 (принимаем координаты игрока за ноль), а Mdist[m][n] = sqrt(m² + n²), вычесть значения из карты дальности по тем же координатам и, чисто теоретически, в видимых тайлах будут нули (чисто практически, скорее всего, у такой проверки будет свой набор артефактов, от которых будет сложно избавиться)

Mdist[0][0] = 0 (принимаем координаты игрока за ноль), а Mdist[m][n] = sqrt(m² + n²)

как раз это и получается, если взять стоимость пути по диагонали за 1410. при этом стоимость пути света и игрока будут равны между собой и при вычитании получим ноль, что вы и писали выше
Mdist[0][0] = 0 (принимаем координаты игрока за ноль), а Mdist[m][n] = sqrt(m² + n²), вычесть значения из карты дальности по тем же координатам и, чисто теоретически, в видимых тайлах будут нули

Большое спасибо за ответ, попробую в ближайшее время реализовать и отписаться, что получилось

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: Зона видимости и поведение мобов

Сообщение Максим Кич » 23 фев 2016, 10:25

Согласен, но пока не особо представляю, как реализовать, т.к. пишу на FPC для консоли
Я на FPC давно ничего не писал, но классы же из него не исчезли же. Соответственно, у нас есть TTile — который клетка карты. У TTile есть свойства (например). За синтаксис не ручаюсь, я по существу.

Код: Выделить всё

floor: TFloor;
wall: TWall;
loot: array of TItem;
occupant: TActor;
Причём есть они все в предках имеют какой-нибудь TDrawable, который умеет себя рисовать (в идеале, отдавать данные рендеру для отрисовки)
Дальше TMob(TActor) и TPlayer(TActor) — всё что шевелится, это потомки TActor, соответственно их можно будет присваивать свойству tile.occupant
TDoor(TWall), от базового (возможно, абстрактного) класса TWall наследуется всё, что может быть стеной.

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

Код: Выделить всё

.........
.@..D..r.
.........
Крыса бежит к игроку, догоняя медленного дракона. Для крысы ситуация такая же, как если бы на её пути стоял столб:

Код: Выделить всё

.........
.@..#..r.
.........
Она построит путь вокруг препятствия и добежит до игрока. Второй вариант:

Код: Выделить всё

.........
.@..r..r.
.........
Две крысы бегут к игроку с равной скоростью. Для дальней крысы ближняя является препятствием вокруг которого она строит обходной маршрут. НО. Её ближайший ход остаётся неизменным.

Ещё вариант:

Код: Выделить всё

.........
...###...
.@..D..r.
...###...
.........
Дракон своей тушкой перекрыл ближайший путь к игроку. Крысе надо выбрать другой путь. Разницы между драконом и стеной опять же нет. Самый интересный вариант:

Код: Выделить всё

.........
...###...
.@..r..r.
...###...
.........
Оптимально будет не считать крысу препятствием. НО:

Код: Выделить всё

............
...######...
...@rrrrr.r.
...######...
............
Оптимальность теряется, если игрок блокирует коридор, чтобы получить преимущество. А игрок будет это делать. Решений может быть несколько. Например, выставлять весовые коэффициенты исходя из скорости мобов (быстрый моб быстрее освободит путь). Исходя из здоровья мобов (игрок раньше завалит хилого моба и путь освободится, можно не ждать) и так далее — в идеале разные монстры будут пользоваться разными алгоритмами.
Dump the screen? [y/n]

vapekreng
Сообщения: 63
Зарегистрирован: 22 фев 2016, 22:33

Re: Зона видимости и поведение мобов

Сообщение vapekreng » 23 фев 2016, 12:11

Я в классах полный ноль, всё делаю через функции, процедуры и модули... Не скинете ссылку на самые основы: что это такое, как реализуется и для чего используется? Буду очень благодарен.
Крыса бежит к игроку, догоняя медленного дракона. Для крысы ситуация такая же, как если бы на её пути стоял столб:
В том-то и идея, что для крысы более медленны дракон НЕ является препятствием. Она его догоняет и, когда будет с ним вплотную, на свой ход меняется с ним местами. А вот для дракона крыса, как более быстрая, будет являться препятствием и он будет искать другой путь к герою или, если такого пути нет, подойдет как можно ближе, но крысу сдвинуть не сможет.
Решений может быть несколько. Например, выставлять весовые коэффициенты исходя из скорости мобов (быстрый моб быстрее освободит путь). Исходя из здоровья мобов (игрок раньше завалит хилого моба и путь освободится, можно не ждать) и так далее — в идеале разные монстры будут пользоваться разными алгоритмами.
Я как раз выбрал весовые категории исходя из скорости мобов: медленные мобы уступают путь быстрым. Хотя, насчет низкого хп тоже хорошая идея.

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

Re: Зона видимости и поведение мобов

Сообщение Максим Кич » 23 фев 2016, 13:23

Я в классах полный ноль, всё делаю через функции, процедуры и модули... Не скинете ссылку на самые основы: что это такое, как реализуется и для чего используется? Буду очень благодарен.
Честно говоря, подойдёт любой мануал для Delphi или Free Pascal. Тут пусть лучше кто-нибудь кто сейчас пишет на FPC подскажет.

По поводу остального: если будет работать — отлично. Я бы делал иначе, но не вижу повода не попробовать.

А, да, вот тут есть остатки моего старого проекта: http://rlgclub.ru/forum/viewtopic.php?f ... 0&start=30, кое-что тоже можно подсмотреть, хотя я бы многое сейчас делал по-другому.
Dump the screen? [y/n]

Аватара пользователя
Apromix
Мастер
Сообщения: 1236
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: Зона видимости и поведение мобов

Сообщение Apromix » 24 фев 2016, 09:11

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

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: Зона видимости и поведение мобов

Сообщение kipar » 24 фев 2016, 09:32

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

Код: Выделить всё

##########
@..#######
##.#######
##......##
#######.##
#######...
---
диагонали не учел. Исправил.

vapekreng
Сообщения: 63
Зарегистрирован: 22 фев 2016, 22:33

Re: Зона видимости и поведение мобов

Сообщение vapekreng » 24 фев 2016, 20:32

ну да, вот такой коридор будет целиком освещен.
Изображение

Не совсем полностью, но косяк, причем конкретный, налицо... Будем допиливать. Попробую по классической sqrt(dx^2+dy^2 ) сравнивать, глядишь, чего получится))

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

В модуле объявляю процедуру вывода на экран в определенной позицииЖ

Код: Выделить всё

unit RogueModule;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, CRT;
type
Maps = array[1..80,1..20] of char;
TCoord = record
  x_:shortint;
  y_:shortint;
end;
{выводим символ в консоль на определенную позицию, верхние 2 строки оставляем
под текст}
Procedure ConsoleOut(Coord:TCoord;Color:byte;C:Char);
implementation
Procedure ConsoleOut(Coord:TCoord;Color:byte;C:Char);
   begin
      Textcolor(color);
      GotoXY(Coord.x_,coord.y_+2);
      Write(C);
      GotoXY(Coord.x_,Coord.y_+2);
   end;

end.
Далее в основной программе при использовании типа Tcoord имя переменной может быть любое допустимое, это ясно-понятно, а вот имена полей так и будут х_ и у_ или я чего-то не понимаю? Извиняюсь, если что-то непонятно изложил...

PS: язык FPC 3.0.0, Среда разработки - Lazarus IDE v 1.6

vapekreng
Сообщения: 63
Зарегистрирован: 22 фев 2016, 22:33

Re: Зона видимости и поведение мобов

Сообщение vapekreng » 24 фев 2016, 20:42

Изображение, к сожалению, не вставилось.
http://itmages.ru/image/view/3922266/3ac3bd30

Пока покурил решил не выпендриваться со списками в модуле:

Код: Выделить всё

unit RogueModule;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, CRT;

type
Maps = array[1..80,1..20] of char;


Procedure ConsoleOut(x:byte; y:byte; Color:byte; C:Char);
implementation

{выводим символ в консоль на определенную позицию, верхние 2 строки оставляем
под текст}

Procedure ConsoleOut(x:byte; y:byte; Color:byte; C:Char);
   begin
      Textcolor(color);
      GotoXY(x,y+2);
      Write(C);
      GotoXY(x,y+2);
   end;

end.
Но вопрос остаётся в силе 8)

Аватара пользователя
Jesus05
Сообщения: 1840
Зарегистрирован: 02 дек 2009, 07:50
Откуда: Норильск, сейчас Санкт-петербург.
Контактная информация:

Re: Зона видимости и поведение мобов

Сообщение Jesus05 » 24 фев 2016, 21:44

да имена полей так и будут x_ и y_

vapekreng
Сообщения: 63
Зарегистрирован: 22 фев 2016, 22:33

Re: Зона видимости и поведение мобов

Сообщение vapekreng » 24 фев 2016, 21:50

Спасибо за ответ, буду поаккуратнее там

Аватара пользователя
Apromix
Мастер
Сообщения: 1236
Зарегистрирован: 04 июл 2011, 10:44
Откуда: Украина, Черновцы
Контактная информация:

Re: Зона видимости и поведение мобов

Сообщение Apromix » 25 фев 2016, 07:27

Обрати внимание на BeaRLib Terminal. Есть пример на FreePascal.

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

Re: Зона видимости и поведение мобов

Сообщение kipar » 25 фев 2016, 08:15

Я не думаю что какая-то простая формула может решить все косяки. FOV в рогаликах широко известная задача, много алгоритмов придумано. Имхо или взять готовый алгоритм (как минимум ознакомится с ними), или забить на косяки и сделать их "фичей". Например сделать радиус обзора порядка 5-6 (темные подземелья), тогда проблем будет не видно. Или генерировать уровни без зигзагообразных коридоров.

vapekreng
Сообщения: 63
Зарегистрирован: 22 фев 2016, 22:33

Re: Зона видимости и поведение мобов

Сообщение vapekreng » 25 фев 2016, 18:26

Обрати внимание на BeaRLib Terminal. Есть пример на FreePascal.
Спасибо, ознакомлюсь
Я не думаю что какая-то простая формула может решить все косяки. FOV в рогаликах широко известная задача, много алгоритмов придумано. Имхо или взять готовый алгоритм (как минимум ознакомится с ними), или забить на косяки и сделать их "фичей". Например сделать радиус обзора порядка 5-6 (темные подземелья), тогда проблем будет не видно. Или генерировать уровни без зигзагообразных коридоров.
базовый радиус с непрокачанным восприятием будет 3, с учетом предметов, навыков и шмота максимальный - 10. алгоритмы На вашем сайте по ссылкам в основном изучал (так на сайт и наткнулся - тут просто кладзень информации!!) Сам просто по образованию математик, вот пытаюсь улучшить))

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 28 гостей