|
| Опубликовано 08.02.2012 19:43 (13 лет назад) # |
Malcolm написал:
Нельзя ли как это один раз утвердить, Что утвердить то? о_О
Условия не создавать свою мморпг. |
|
|
|
|
| Опубликовано 09.02.2012 02:47 (13 лет назад) # |
bsivko написал:
Заливка и поиск пути - это разные задачи.
Да по-банану, какие это задачи. Речь идёт про алгоритм.
Поэтому прежде чем писать фасепалмы, следует разобраться в матчасти.
Это умиляло, если бы не достовало. С какого рожна нужо переходить на личности в совсершенно не способствующем для этого постебушном споре? Тебе матчасть сейчас объяснить? Без мягких выражений, не напрягаясь.
Каким хером тут муравьи приплелись? Они, что, запрограммированы человеком? Тогда какого хера они в этой теме делают?
Еще раз, для тех кто посылает учить матчасть, не понимая о чём речь - АЛГОРИТМ поиска пути и АЛГОРИТМ заливки это варианты одного и того же алгоритма посика в графах, с некоторыми дополнениями для выполнения свой задачи. Открой приведенную тобой же ссылку на вики и почитай, что такое алгоритм Дейкстры, что такое А* и чем они отличаются. В той же статье, справа, есть список разновидностей алгоритма по поиску в графах.
В общем говоря, поиск в глубину и поиск в ширину являются двумя частными случаями алгоритма A*. Для поиска в глубину возьмём глобальную переменную-счётчик С, инициализировав её неким большим значением. Всякий раз при раскрытии вершины будем присваивать значение счётчика смежным вершинам, уменьшая его на единицу после каждого присваивания. Таким образом, чем раньше будет открыта вершина, тем большее значение h(x) она получит, а значит, будет просмотрена в последнюю очередь. Если положить h(x) = 0 для всех вершин, то мы получим ещё один специальный случай — алгоритм Дейкстры.
Это та самая матчасть, с которой нужно ознакомиться, прежде чем посылать это делать кого-то другого.
А её реализацию можно посмотреть у меня в 64м конкурсе, где один и тот-же волновой алгоритм используется как для заливки (реализация маршрута к репликатору, из всех валидных точек игрового поля) и как поиск пути, по которому биообразцы гоняются за протагонистом.
В SimCity 1989 для ZX кстати нет полноценной заливки по Дейкстре. Я очень хорошо помню, как у города едет крыша в случае, если мощности электростанции не хватает. Когда свет в домах отключается по всему городу волнами. Динамика хорошо видна на мониторе города, и там оченьвидно, что никакими заливками и не пахнет - реализована какая-то эвристика. Там был четырёх мегагерцовый процессор, который обрабатывал эту заливку в несколько итерраций. И заливка проста и быстра как булыжник в падении. В отличие от эвристик и прочих страшных слов.
Блин, ну вот какого хрена надо было всё портить.
редакция от Shirson, 09.02.2012 03:01 |
|
|
|
Инженер‑космогоник
|
| Опубликовано 09.02.2012 06:56 (13 лет назад) # |
суровый спор:)
Еще переплетаются алгоритм заливки в симсити(не факт, что его корректно так называть, но водопровод, фигли) и алгоритм заливки собственно графа пути
1-ый случай это частный случай задачи поиска пути(очень простой, чего уж там)
2-ой случай - это один из методов решения самой задачи поиска пути - поиск в ширину.
А* - поиск в ширину с оптимизацией.
Дело совершенно не в этом. Для походовой стратегии за раз двигается один юнит и волнового поиска пути хватит выше крыши. А для РТС можно обойтись вообще простейшим поиском пути - просто линией между текущей точкой и точкой назначения, без коллизий.
Проблема в том, что поиск пути - это далеко не самая важная часть стратегии, даже если сделать простейшую вещь в духе nanowars, возникнут куча сложностей с балансом и ИИ.
Я пытаюсь сделать РТС с тех пор, как начал пытаться делать игры, еще ни одной не вышло:)
|
|
|
|
Древний организм
|
| Опубликовано 09.02.2012 07:15 (13 лет назад) # |
bsivko, муравьи тут не при чем. Но коли ты уж завел тему, то у муравьев поиск пути сводится к самой простой эвристике. Проложить прямую до еды. Если на дороге возникло препятствие, попытаться его перелезть, если слишком сложное, то обойти. Пока обходишь потерять из вида еду и тут же про нее забыть, переключившись на другую задачу.
У муравьев НЕТ мозгов в привычном нам понимании. Они НЕ мыслят вообще. А живут только поддаваясь инстинктам. Поэтому и не захватили еще мир до сих пор, а могли бы.
Касательно Дейкстры, волнового алгоритма, А* и иже с ними это всё суть есть одно и тоже.
Mefistofel, понимаешь, я заговорил о поиске пути, как неотъемлемой части РТС игры. Эта часть образует контроллер игры, который непосредственно сказывается на игропроцессе. Если поиск пути реализован плохо (а как следствие кривой контроллер), то игра будет только бесить. ты тыкаешь юнитам перейти на другую сторону моста, один юнит забивает мост пока его переезжает, а все остальные начинают ехать в обход, вместо того чтобы поехать сразу следом за первым по тому же мосту. Ты даешь 10 юнитам одну точку назначения и они начинают виться аки пчелы вокруг этой точки, пока как-то не расставятся, вместо того чтобы просто набиваться в кучу вокруг точки. Все эти вещи бесят, и если не делать обработки этих ситуаций игра будет выглядеть как подавляющее большинство работ на конкурс джампера. Тоесть сделанными на коленке за 1 день.
И поиск пути это только часть проблемы. Есть еще ИИ, который написать нифига не проще. А баланс...уууу про него скромно промолчу.
Лично я (даже при условии что Zbl будет тоже делать со мной) не возьмусь делать стратегию за 10 дней. И за 20 не возьмусь. Был у вас ФПС шутер. Скажите мне, сколько из них играбельны вышли? Дан молодец, ага, но это не игры, это прототипы движков на ранних стадиях. В них попросту неинтересно играть.
Зачем создавать недоделки крутого, если можно сделать что-то простое, но завершенное, самодостаточное? Да научитесь вы наконец делать тетрисы уже, а потом и поговорим о...
редакция от Darthman, 09.02.2012 07:23 |
|
|
|
[35].jpg)
|
| Опубликовано 09.02.2012 07:20 (13 лет назад) # |
ну так что, давайте уже РТС на пару недель?
в ртс поиск пути это на самом деле мелочь, сделать вменяемый ИИ намного сложнее. |
|
|
|
|
| Опубликовано 09.02.2012 08:34 (13 лет назад) # |
| было бы круто |
|
|
|
|
| Опубликовано 09.02.2012 09:27 (13 лет назад) # |
| Тут в соседнем треде идея синхронизации 2х конкурсов пробежала, как вам?) |
|
|
|
|
| Опубликовано 09.02.2012 09:35 (13 лет назад) # |
Shirson написал:
bsivko написал:
Заливка и поиск пути - это разные задачи.
Да по-банану, какие это задачи. Речь идёт про алгоритм.
Речь идет про разные задачи. Изначально рассматривается поиск пути. И для поиска пути используются одни алгоритмы. А для заливки - другие алгоритмы.
Заливка - это обход всех вершин связанного графа. Её задача - как можно быстрее обойти все вершины и использовать минимум памяти, для чего нужно проверять как можно меньше ребер, как можно меньше задействовать стек. Заливке по-банану путь из точки A в точку B. Ей нужно обойти все.
Поиск из точки A в точку B - это поиск маршрута в связанном графе. Если маршрут найден, то поиску пути плевать что в графе не произведен обход всех вершин. Ему важно найти путь, а не обойти все вершины.
Ещё раз, повторяю, это разные задачи, и соответственно, разные алгоритмы.
Shirson написал:
Каким хером тут муравьи приплелись? Они, что, запрограммированы человеком? Тогда какого хера они в этой теме делают?
Еще раз, для тех кто посылает учить матчасть, не понимая о чём речь - АЛГОРИТМ поиска пути и АЛГОРИТМ заливки это варианты одного и того же алгоритма посика в графах, с некоторыми дополнениями для выполнения свой задачи. Открой приведенную тобой же ссылку на вики и почитай, что такое алгоритм Дейкстры, что такое А* и чем они отличаются. В той же статье, справа, есть список разновидностей алгоритма по поиску в графах.
Любой алгоритм характеризуется множествами входных и выходных данных. Входные данные заливки: точка старта и граф. Входные данные поиска пути: две точки и граф. Результат работы заливки: множество найденных вершин. Результат работы поиска пути - последовательность вершин маршрута.
И это млять, базовые понятия. Не понимать их - это поверхностное мышление.
Есть алгоритмы заливки, которые работают намного быстрее и жрут на порядки меньше памяти, чем поиски в ширину, глубину, Дейкстры и прочих. В том же древнем QBasic в операции PAINT использовалась заливка, которая плевать хотела на волну, Дейкстру, ширину и глубину. При этом на порядок меньше требовала памяти и работала в 4-5 раз быстрее. Почему так происходило - достаточно понять как он работает. И если нужно, могу это наглядно продемонстрировать.
А её реализацию можно посмотреть у меня в 64м конкурсе, где один и тот-же волновой алгоритм используется как для заливки (реализация маршрута к репликатору, из всех валидных точек игрового поля) и как поиск пути, по которому биообразцы гоняются за протагонистом.
Алгоритмы заливок и поиска пути я изучал буквально 20 лет назад. И знаю о них намного больше, чем написано в википедиях.
Там был четырёх мегагерцовый процессор, который обрабатывал эту заливку в несколько итерраций. И заливка проста и быстра как булыжник в падении. В отличие от эвристик и прочих страшных слов.
Да плевать какой там был процессор. Maxis тупо не знали эффективных алгоритмов, и исправились только в SC2000. Также, как не знали создатели X-COM 1/2. Аналогично ситуация была с Медноноговым, когда в НЛО-1 он сделал эвристику (с которой пользователи плевались), а в НЛО-2 хвастался, что наконец-таки изобрел велосипед 1959-го года выпуска.
Shirson написал:
Каким хером тут муравьи приплелись? Они, что, запрограммированы человеком? Тогда какого хера они в этой теме делают?
Муравьи - это пример поиска пути для динамических графов. Графов, в которых пока ты идешь из точки A в точку B граф может изменится. И нужно проложенный маршрут исправлять. Именно с такими проблемами сталкиваются разработчики RTS. Когда по карте бегает толпа юнитов и мешает друг другу. Распространенным решением является создание волны/Дейкстры/A*/... с подвешиванием на неё костылей различного вида. Но для решения проблемы есть и другие способы. |
|
|
|
|
| Опубликовано 09.02.2012 11:11 (13 лет назад) # |
| Муравьи-муравьями, но тема как бы для обсуждения темы следующего конкурса, а это может быть и не стратегия вообще. |
|
|
|
|
| Опубликовано 09.02.2012 11:49 (13 лет назад) # |
tl; dr
О чем спор? |
|
|
|
|
| Опубликовано 10.02.2012 02:08 (13 лет назад) # |
| Давайте какую-нибудь полегче тему тогда! В топку эту стратегию!!1 |
|
|
|
|
| Опубликовано 10.02.2012 02:59 (13 лет назад) # |
| Да вроде, у нас будет конкурс смежный с другим ресурсом. Тему выбирают они. Можно дальше обсуждать заливку с муравьями =) |
|
|
|
|
| Опубликовано 10.02.2012 04:49 (13 лет назад) # |
Можно двухдневный на выходные, а дальше ждать смежного. 18-го он стартует.
Хотя бы тот же скроллер.
редакция от Malcolm, 10.02.2012 04:50 |
|
|
|
|
| Опубликовано 10.02.2012 06:45 (13 лет назад) # |
| РТС за выходные! |
|
|
|
|
| Опубликовано 10.02.2012 06:53 (13 лет назад) # |
| Я за. Только тема где? |
|
|
|
Главный Говнюк
|
| Опубликовано 10.02.2012 07:46 (13 лет назад) # |
| Ну если посмотреть на прошлые конкурсы, за те 1.5-2 недели мало кто делал полные играбельные проекты, а вы за 2 дня хотите, кажись не успеете. моё имхо. |
|
|
|
Древний организм
|
| Опубликовано 10.02.2012 08:01 (13 лет назад) # |
РТС за выходные!
Сам вести будешь 8) |
|
|
|
|
| Опубликовано 10.02.2012 08:30 (13 лет назад) # |
| РТС? Неее, без меня... за два дня даже на конструкторе что-то сложнее пакмана/скроллера/арканоида фиг сделаешь. |
|
|
|
Главный Говнюк
|
| Опубликовано 10.02.2012 09:19 (13 лет назад) # |
| За выходные только успеть можно прототип набросать для RTS из ходячих квадратиков разного цвета. строившихся в больших квадратиках и стреляющих маленькими квадратиками )). это максимум, и то если утром в субботу начать и в воскресение вечером закончить. Это не реал сделать всё нормально рабочим. |
|
|
|
|
| Опубликовано 10.02.2012 09:50 (13 лет назад) # |
| Darthman, не красиво будет если я буду ведущим и единственным участником в конкурсе=) |
|
|
|