Тема: Rooftop
Показать сообщение отдельно
Старый 05.04.2014, 11:23   #3
Taugeshtu
scientist.alien
 
Аватар для Taugeshtu
 
Регистрация: 12.02.2007
Сообщений: 2,098
Написано 1,030 полезных сообщений
(для 2,593 пользователей)
Плохо Ответ: Rooftop

Всем привет

Состояние на утро субботы, 5 апреля 2014:
Размер скриптов раздулся до 82 килобайт, из которых порядка 6 - .ToString() методы для дебага
Остальное - фиксы, доработки, методы для установки тестовых условий ииии...
  • Относительно работающий генератор зданий;
  • Почти законченный путенах.

Собственно, всё. Пятница ушла на то, чтобы отдебажить мой "тёмный" код, который почти весь перешёл на светлую сторону силы. Оставшиеся ситхи прячутся в коде присоединения к семье/покидания семьи и выбора задания поселенцем. Задания кстати генерятся нормально, проверил

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

Поиск пути выродился в почти классический поиск кратчайшего маршрута по графу. Тут есть маленькая хитрость в том, что я пошёл на допущение: в пределах одного этажа никаких перегородок и препятствий нет. Там персонажи будут ходить по прямой до следующей точки в их маршруте.
Другая хитрость заключается в том, что я разбиваю здания не просто на этажи, а на группы этажей. Если что-то сломало лестницу между этажами - группа разбивается на две; если игрок построил лестницу между этажами, которые принадлежали разным группам - они сливаются в одну. Причём разделение группы, при всей неоптимальности алгоритма, стоит всего-то O(n), где n < 100 (максимум этажей пока что). По-хорошему надо со списков переписать в массивы, тогда вообще почти бесплатным будет.

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

В заключение, по традиции, маленькая няшка - эмбрион генератора зданий. Просто для оценки масштабов в игре:
Миниатюры
Нажмите на изображение для увеличения
Название: Skyrapers.png
Просмотров: 957
Размер:	33.9 Кб
ID:	20331  
__________________
Public service announcement: вы можете заблокировать отображение сообщений определённого пользователя, добавив его ник в список игнорируемых.
Tau lab.
We LOVE you. We MADE you.

Последний раз редактировалось Taugeshtu, 13.04.2014 в 13:56.
(Offline)
 
Ответить с цитированием
Эти 12 пользователя(ей) сказали Спасибо Taugeshtu за это полезное сообщение:
Adrax (05.04.2014), Кирпи4 (05.04.2014), Fatalix3d (11.04.2014), Harter (08.04.2014), impersonalis (05.04.2014), KCEPOKC (05.04.2014), mr.DIMAS (11.04.2014), Nex (05.04.2014), Randomize (05.04.2014), St_AnGer (07.04.2014), tirarex (13.04.2014), Wegox (06.04.2014)