Поиск пути в ширину.

    Однако как-то прошел мимо меня алгоритм поиска пути в ширину, как бы знал о нем, но совершенно не интересовался, есть такой и ладно. А вот на днях заинтересовался, оказывается незаменимая вещь для игр жанра Tower Defense или даже для шутеров, везде где враги должны набегать на одинокую цель, или небольшое количество целей. И главное - простая. Причем, в силу своей простоты исполняется один раз, а дальше результатами может пользоваться куча юнитов, во всяком случае, пока цель не сдвинется с места. А ведь делал что-то подобное - генератор регионов для навигационных карт и даже не сообразил, вот что значит лень и отсутствие специализированного образования.

Отвлекся.

Пришло в голову проверить простейший алгоритм обхода препятствий. Сделал. Результат - как сказал Винни-Пух Пятачку: "Не то что бы совсем не попал..." Иной раз удивительным образом обходит все препятствия, прямо гордость берет, а иной раз упрется как баран в новые ворота.  Но похоже на движения юнитов в DuneII, аж ностальгия пробивает, кто играл, тот поймет. Коротенькое видео:

Немного переписал генератор регионов.

А то совсем странно выглядело. Сейчас оно сделано так:

def genRegions(self):

        tempRegionList = []

        for currentBrick in self.brickList:

            if currentBrick.regions == []:

                relList = []

                tempList = list(currentBrick.relatedList)

                for i in tempList:

                    brick = self.brickList[i]

                    #print(brick.h - currentBrick.h)

                    if (brick.regions != [] or 

                    brick.h - currentBrick.h > self.maxH or 

                    self.getDistTo2(currentBrick.position, brick.position) > self.regionDist):

                        brick.regions.append(currentBrick.index)

                        relList.append(brick.index)

                    else:

                        brick.regions.append(currentBrick.index)

                        relList.append(brick.index)

                        #print(brick.relatedList)

                        for appB in brick.relatedList:

                            if appB not in tempList:

                                tempList.append(appB)

                            

                        

                #print(currentBrick.index, relList)

                newRegion = landRegion.landRegion(currentBrick.index, relList)

                tempRegionList.append(newRegion)

                        

        print(tempRegionList)                 

        return 0

Еще надо дописать определение соседних регионов и списка общих точек. И как сделать определение высоты точки, вот в чем вопрос, ведь один блок ландшафта может содержать в себе все уровни высоты...

Начал набрасывать генератор регионов.

   Зато пока сообразил, как сделать, чуть мозг не поломал, но вроде сдвинулось с мертвой точки, тьфу-тьфу-тьфу... Здорово помог MyPaint - редактор графический. Рисовал вручную точки, соединял их линиями, пытался прикинуть, как оно должно работать. Немножко отвлекся, нарисовал картинку, смотрите ниже. Код пока еще страшный, состоит только из генератора списка блоков. Наверное вынесу его в отдельную функцию - пригодится для расчета полей зрения и вообще... Сам класс региона я написал аж в двух вариантах, и оба пойдут в утиль. Еще надо написать определение связанных регионов. Код ниже:

Хвастать вредно. Юбилей.

    Сперва о плохом. Не писал потому, что во-первых, был несколько занят, и занятость эта в ближайшее время будет увеличиваться до зимы, во-вторых, создание миникарты с помощью модуля видеотекстуры потерпело крах. Почему-то плоттер видеобуфера вешается, при слишком частых обращениях. И фиг бы с ним, но и Блендер тоже подвешивается намертво, приходится вырубать консоль, с которой он запущен. Пришлось подключать bgl,  в котором я ни в зуб ногой. Спасибо пользователю dron, который когда-то давно, еще в далекой-далекой галактике  на БУ, сделал пример использования этого самого бгл. Потихоньку ковыряюсь.

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

    Дальше - у моего WIP на момент написания сообщения 999 просмотров. Ура-ура, юбилей прямо вот-вот. 

Накатал скриптец генератора имен.

Ничего сложного, просто куча вложенных циклов. Подробнее:

Добавил промежуточный уровень.

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

Все получилось.

 Алгоритм оказался ОЧЕНЬ удачным.

Прогресс есть.

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

Мне еще добавлять промежуточный уровень, для плавных спусков.

А так, все работает, как надо.

Похвастаюсь.

    Работа над редактором блочного ландшафта медленно, но неуклонно движется в перед. "Наше дело правое и мы победим". Благодаря Flogger-K, который натолкнул на мысль, удалось разобраться с определением типа блока по соседним, без всяких "если блок выше такой-то, и блок правее такой-то, а блок левее совсем не такой, то..." Алгоритм более тормозной, но многообещающий. Если получится все правильно оформить, то распишу подробнее.

Пока хвастать нечем #2

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

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

Пока хвастать нечем.

Для редактора блочного ландшафта сделал визуализацию, хотя пока и "не фонтан".  Надо еще поправлять. Уже тестил на карте 1024Х блоков, тормоза есть, но небольшие. Еще нужно запилить изменение соседних блоков от изменяемого и повыкидывать лишнее.

Делаю редактор блочного ландшафта.

Пока упрощенный - надо еще понять, как правильно все сделать. Есть успехи:
1) Уже генерируется базовый ландшафт, состоящий из блоков с высотой 0. То есть "чистое поле". Размер произвольный, тестировал от 8Х8 до 256Х256 блоков.
2) Вроде окончательно решен вопрос с определением индекса блока ландшафта, на который указывает курсор мыши. Да и вообще любой объект, имеющий координаты.
3) Выборочно заменяются блоки ландшафта на другие.

Похоже, что домучал класс навигационного узла окончательно.

Когда список атрибутов стал угрожать перевалить за второй десяток, понял, что оно будет жрать непомерно памяти, особенно при копировании списка узлов. Выкинул половину атрибутов, оставив только нужные для расчета пути. Оставил десяток - авось хватит )))). Написал ему функцию рассчета расстояния, сейчас думаю, может лучше выкинуть на мороз в отдельный класс отправить? Этакий mathutils. Дописал также парсер прямо в __init__() ,пускай сам читает данные, не маленький уже. Пока пишу документацию к классу.

Трайк

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

Пилю навигационную систему 2

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

Всех с Пятницей!

Пилю навигационную систему.

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

Пример реализации алгоритма поиска пути А.

#!/usr/bin/python
# -*- coding: UTF - 8 -*-
#Поиск пути по алгоритму Дейкстры, как я его понимаю №3
#denis8424