amarao (amarao_san) wrote,
amarao
amarao_san

я не забыл про игрушку

Пока что осознал важную вещь: для всяких pathfinding'ов нужно иметь граф. Граф чаще всего хранится в виде списка вершин с прилагающимся к каждой вершине списком граней.

Карта же обычно хранится в виде массива.

Почесав в затылке и пересмотрев MIT'овскую лекцию про BFS (http://www.youtube.com/watch?v=s-CYnVz-uh4) я осознал, что никакой проблемы тут нет. Вместо "хранения граней" должна быть функция "доступные грани", вычисляющая грани, доступные для данной клетки на карте.

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

(напомню суть идеи)
Вместо gods hands мобов, которые всегда прут по кратчайшему пути, я хочу реализовать честный pathfinding пешком, когда моб тыкается в перпятствия, пока не найдёт проход.

Для этого нужно для каждого моба иметь собственное представление о карте, посещённых вершинах и т.д.

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

При pathfinding'е мобов будет предполагаться, что топать можно по свободным и по неизвестным клеткам. В этом случае мы по "субъективной карте мира" моба делаем обычный А*, который пересчитывается каждый раз, когда моб обнаруживает, что на shortest path возникло препятствие. Препятствие, соответственно, будет увидено только на расстоянии не более Х клеток раз, и два, если по прямой между мобом и препятствием нет известных препятствий (то есть закрывшаяся стенка за углом мобом не будет увидена пока он за этот угол не повернёт).

(техническое)
И всё ещё не решены вопросы:

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



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

2) Как рисовать: полный flip на каждом кадре или update c списком rect. Попробую написать какой-нибудь простой тест для определения "что быстрее".

3) Как собирать стек картинок. Каждый раз blit() для всех видимых объектов (читай: карта, башни, мобы, заряды) или какая-нибудь кеширующая эвристика? В принципе, т.к. анимация, я надеюсь, появится для всех (включая фон), то, видимо, blit для всего. Но это очень медленно. Котики у меня по экрану при 50 фпс и честном blit/full update на каждом шагу выжирали 102% CPU...

(фантазируя)
Собирать фон и башни в набор синхронно анимированных больших полотен, на них блитить мобов (в копию) и её отдавать на отрисовку? Поиграться с opengl, чтобы на ходу просто переключать текстуры?
Tags: pygame, sdl
Subscribe

  • Админская мудрость

    Когда вывод strace на башовый скрипт становится понятнее самого скрипта, граница разумности давно пройдена.

  • Rules of internet

    Rule 34. There is porn of it. Rule 35. It's used to mine cryptocurrencies.

  • CI без сервера

    А вот у меня есть такой запрос: я хочу иметь CI-подобный инструмент (задачи/автоматически вычисляемые зависимости порядка выполнения, параметры,…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments

  • Админская мудрость

    Когда вывод strace на башовый скрипт становится понятнее самого скрипта, граница разумности давно пройдена.

  • Rules of internet

    Rule 34. There is porn of it. Rule 35. It's used to mine cryptocurrencies.

  • CI без сервера

    А вот у меня есть такой запрос: я хочу иметь CI-подобный инструмент (задачи/автоматически вычисляемые зависимости порядка выполнения, параметры,…