Добавлено: Пт Янв 08, 2010 1:13
Заголовок сообщения:
Подумал-подумал и решил раскрытия Алексеем секретов не ждать. Получилось примерно вот так.
Исходно дано:
* разведанная часть карты
* начальная провинция S
* конечная провинция F
* отряд под чутким руководством героя
Нужно построить скорейший для данного отряда маршрут-цепочку из провинций, начиная с начальной точки и завершая конечной.
Решение гремлинское "от Зарра":
1)
Правильная подготовка, Босс, это залог успеха: посадить за исследование пару-тройку монахов поопытней, картами их снабдить...
* строится список своих провинций, которые доступны для прохождения, то есть не осаждены, не ограждены и т.п.
* в список добавляются (если не было) исходная и целевая провинции
* для каждой провинции из списка нужно выяснить перечень выходов, то есть приграничных с ней провинций и провинций, куда можно непосредственно попасть из верфи/порта
* для каждой провинции из списка определить время преодоления с учётом ей особенностей (вид, постройки, эффекты обрядов и тп), и возможностей нашего отряда
2) Гоблиниада 2010 (
гоблинишек, Босс, на эстафету советую скликать помельче и пошустрее):
*
даём орку посмышлёней свиток, на который монахи список записали и карандаш... хотя, если герой командир или маг, то орка нафиг - сам справится! гоблинишек надо распределить по провинциям по списку. сколько выходов в провинции, столько и бегунов
* помещаем в FIFO провинцию S (
не понятно, босс? стартуем, то есть, из начальной провинции!)
* из очереди FIFO изымаем очередную провинцию X и сверяемся со орочьим списком - прибегал ли уже кто-то из гоблиниадцев в эту провинцию?
** если нет, то пусть орчище запишет теперь напротив этой провинции X в своём свитке "да, прибегали", а время в пути - время, которое скажет прибежавший гоблин. и дорогу пропишет, что гоблин скажет (у него с собой, на бумажке-шпаргалке записано).
(
что, Босс? говорите что в начальную провинцию никто изначально не прибегал? значит всё равно писать "да, прибегали", а время - ноль! что такое ноль?... мда, Босс... как-нибудь в другой раз объясню...)
** если уже стоит пометка "да, прибегали", то сравниваем время нового бегуна с записанным.
*** если дольше или совпало, то пусть гоблинишка прочь пойдёт. может, в следующий раз повезёт...
*** если быстрее, то гоблина наградить, исправляем в орочьем списке "время в пути до провинции X", а также переписываем из гоблинской шпаргалки новый быстрейший маршрут до неё. и надо у всех остальных гоблинов в шпаргалках старый вариант маршрута на новый заменить!
как, Босс? ну придумайте сами или магов попросите.
* смотрим, есть ли в списке напротив провинции X пометка "старт дан", если нету, то
** ставим пометку "старт дан"
** если "время до провинции X" лучше, чем текущее "лучшее время до финиша", то вручаем каждому из гоблинов на старте эстафетную шпаргалку - копию маршрута до провинции X с добавленным индивидуально пунктом назначения, указываем время = времени до X + время преодоления её же отрядом и выпихиваем бегунов через все выходы. записываем все выходные провинции в FIFO.
(
если "время до провинции X" не лучше, чем текущее "лучшее время до финиша", то нечего гоблинов зря гонять, на дракона их послать и то будет полезней...)
* если провинция X оказалась по совместительству конечной провинцией F, то отмечаем новое "лучшее время до финиша" в орочьем свитке.
* пока в очереди есть что-нибудь (кто-то ещё бежит...) продолжаем извлекать очередной X и т.д.
Всё, Босс!!
Работать будет и для соседней клетки, и для пути по периметру или зигзагом через большую карту. Если памяти сильно жалко на гоблинские шпаргалки тратить, то можно поманьячить с обратными ссылками в орочьем свитке (на то откуда самый шустрый прибежал), да с динамическим расчётом текущего наилучшего времени, но это уже бантики.
Плюс, чтоб путь не перелопачивать каждый раз при выборе отряда, можно для отряда его запомнить, а сбрасывать его всем отрядам с заданием "идти в ...", если построили или скастовали где-то что-то влияющее на проходимость. Тогда пересчитывать маршрут надо будет только если он новый или если транспортная ситуация изменилась.
Кстати, так как ситуации с мобильностью больше 5 это в нормальной игре роскошь, а провинций - несколько десятков, то монахов можно грузить работой постепенно - сначала сверстать просто список "своих доступных" провинций, а связность с соседними и время преодоления определять по ходу расширения круга гоблинской эстафеты.
что делать чтобы ускорить раздумья компа?????
Великая Кузня
