а мы у пассажиров спрашиваем, куда они хотят ехать?

[Pk]

Ладно, развёрнуто:
Ты саму задачу представляешь, имхо, некорректно. ИИ не будет взаимодействовать с картой (в идеале вообще)
Задача ИИ создать "мозайку" из точки А в В через иные точки. При этом совершенно не важна карта, но важна альтернатива.
У меня дома просто нет места чтобы нормально порисовать блоксхемы и прописать алгоритмику (EAI тому пример)

По этой причине у меня нету рабочих вещей. Хотя...
Если это именно так, а не просто у меня мысль спараллелилась с чьей-то, то автобусные остановки на дороге сначала появились в теме "предложения", а потом - в Mini IN (хотя х/з и без гарантий).

*начинаю ставить себя на место пассажира на неизвестном маршруте*

[George]

Ладно, развёрнуто:

Жаль, не получилось

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

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

Задача ИИ создать "мозайку" из точки А в В через иные точки.

На графе это называется путь. Только вот перебором решать эту задачу для каждого отдельного пассажира при прибытии транспорта на остановку, где этот пассажир стоит, процессорных мощностей не хватит. Ведь на каждой остановке 2-3 сотни пассажиров, на карте 256х256 полсотни городов, в городе с десяток остановок - это песец даже если задачу решать для всей партии пассажиров с одной точкой назначения. Даже если считать, что назначение это город, и любая остановка в городе подходит, простейшая задача доехать до самолёта на автобусе, пересесть на самолёт и долететь не такая простая задача. А уж что делать в случае, если для того, чтобы проехать из города 1 в город 3 надо приехать в город 2, проехать по городу 2 на другую остановку, и оттуда ехать в город 3? Тогда расчёт по годам вести не получится, придётся по остановкам. А ежесекундный расчёт 1000 кратчайших путей на графе в 1000 узлов мне кажется очень сложной задачей. Хотя может я перегибаю палку. Давайте оценим, сколько единиц транспортных средств прибывает на все станции всех игроков в секунду (в среднем)? Кто может дать оценку?
Да, и ещё меня вот что смущает. Если мы считаем по-остановочно, то попав на остановку одного игрока, на остановки других он попасть не может. Но явно в перспективе будет кооперативная игра и общие остановки. Тогда граф существенно расшириться. Надо ли считать, что пассажир приехал, если он попал в готод назначения на транспорте другой компании, а не той, с которой он стартовал?

У меня дома просто нет места чтобы нормально порисовать блоксхемы и прописать алгоритмику (EAI тому пример)

Схемы лучше рисуй в Visio

По этой причине у меня нету рабочих вещей.

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

Если это именно так, а не просто у меня мысль спараллелилась с чьей-то, то автобусные остановки на дороге сначала появились в теме "предложения", а потом - в Mini IN (хотя х/з и без гарантий).

О существовании TTDP аккуратно умолчим. А можно было Oskar'у сказать спасибо. Если я не ошибаюсь, первым был он.

Ладно, Вань, в 20 лет ещё столько всего впереди, глядишь чему-то научишься

[Killen]

А зачем для каждого пассажира? Может быть не создавать слишком сложных схем и направлять пассажиров только по имеющимся маршрутам. Допустим так: попав на остановку, груз (пассажир) смотрит список транспорта, отбывающего отсюда, и их маршруты. Если без усложнения алгоритмов погрузки/разгрузки, то смотреть только следующие пункты назначения после текущего. Если же усложнять, то в "поле зрения" попадают все станции в списке (перед станцией с полной разгрузкой включительно) и на нужной он выходит. Далее случайным образом выбирается один из пунктов назначения.
Сначала использовать этот алгоритм, а затем усовершенствовать так, чтобы в поиск попадали и пункты назначения, до которых можно добраться с пересадками. Только в этом случае уже нужно будет усовершенствовать и алгоритм погрузки/разгрузки.

[Enlightened]

Где ты там нашёл что-то сложнее деления!?

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

ЗЫ. Ушел решать задачке. вернусь недель через пару. А вы пока обсуждайте.

ЗЗЫ. Идея желто-зедено-красных пассенгеров мне понравилась. Но это в лучшем случае вторая очередь.

[George]

Где ты там нашёл что-то сложнее деления!?

Есть такой раздел высшей математики. Называется математические методы. Так вот. там есть так называемая транспортная задача. Программный метод ее решения когда-то был темой моемй курсовой.

И моей дипломной.
Так вот, ежесекундный расчёт тысяч маршрутов на ориентированных графах с несколькими тысячами узлов рядовой машине типа селерона 500 даже и не снился. Тогда я выкручивался дополнительными упрощениями вида "магистральная ветвь", когда предполагается, что вместо сотен малых (пропускная способность) ветвей эффективней (что не доказывается, а постулируется, ибо в общем случае неверно) иметь 1 большую (искусственное сокращение размерности графа). В терминах TTD это бы означало, что на расстояние до N клеток надо проехать на автобусе, до M на поезде, до L на самолёте. Неприемлемо! Ибо если на 2-х краях города по аэропорту, а автобусов нет, то пассажир может сесть в самолёт в одном аэропорту, долететь до другого города, там пересесть, и прилететь в свой город, но на другой аэропорт

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

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

А то, что нарисовал George несколькими постами выше - элементарно решающийся граф:) не тот, что с родословной, а тот, что математический.

Не совсем так. Я нарисовал легенду для построения графа. А граф строится из маршрутов, а не дорог. При том граф здесь ориеннтированный. Только PK всего этого, как я понимаю, не знает.

[Pk]

Тебе русским языком написано: я не знаю Cи, я не люблю английский я не знаю визио и принадлежу к тем, кто сначала всё делает на бумажке, а только потом - в комп.

И если ты не читаешь, что я пишу? а как тупая дура передёргиваешь на свой взгляд и вкус - извини. Алгоритм? Пожалуйста. Но не в коде.

Или это что "сначала научись плавать, потом мы нальём воду"?

----=====----

И эти люди называют себя программистами.
Я что впустую пишу пометки!?? Вы хоть читайте что написано.

Подумайте: а как насчёт оптимизации? Где можно уменьшить и что это даст? (я уже продумал и ограничения, и оптимизации, но не скажу. Сами догадаетесь или нет что можно сделать?)

[Enlightened]

1. У меня стоит дома старенький Sempron 2800+. Это - старая развалина. но тем не менее - ее мощностей вполне хватит.

2. Ребят, не ссорьтесь.
2George - Если человек не знает С, и у него нет рабочих вещей, это не значит что он не может помочь проекту. Я при проектировании интерфейсов сайтов сажу за комп жену. Которая вообще не представляет как пишется слово такое чудное - программирование. Понимаешь зачем?

2Pk - Не кипятись. Нарисуй алгоритм, как ты его видишь. это полезнее:)

[Dictu]

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

Вот здесь вот много говорится о пунктах назначения для пассажиров. Что это означает?

Во-первых, пассажиры перестанут быть грузом. Груз - это вещество, которому пофиг как и куда, только побыстрее, пока не протухло. Уголь, сталь, руда, человеческое мясо - вот груз. Умных же пассажиров логичнее обрабатывать отдельно, что повлечёт изменение всей структуры игры. Стоит ли?

Во-вторых, все эти разговоры о пересадках, вершинах и рёбрах графа - попытка ввести в игру непрерывное решение тысяч частных случаев задачи коммивояжера. А эта задача не имеет пока экономного алгоритма решения! Даже если удастся найти экономное решение, сколько задачек разом придётся решать и сколько ресурсов это займёт? Предполагаю, что на настольных компах прокатит, но о порте на КПКшки можно будет забыть.

Да и вообще, в Советском Союзе такой план ставили как минимум на пятилетку, а в Росиийской Федерации такой план не растёт вовсе. Тем более на общественных началах.

Далее конструктив. Возможно, стоит так и оставить пассажиров мясом, но подумать, как это мясо грамотно развозить по стране?

Возьмём обычный вокзал. Жизненный. Там первичен не пассажир и не другой город, а поезд. Пассажиры приходят к конкретному поезду, с билетом в кармане. А не просто бегут на вокзал со смутным желанием уехать в Сызрань.

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

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

А надо сделать так, что пассажир после появления на станции был привязан к имеющемуся поезду, и ждал его. На станции можно расчитывать вес каждого города в пассажиропотоке. Считаем те города, которые фигурируют в расписаниях имеющихся поездов. У города М есть население и расстояние от Питера до города М.

х(М)=(население М в некоторой степени)/(расстояние от М до СПб)

Степень надо будет подобрать экспериментально. Она нужна для того, чтобы привлекательность города возрастала в степени в зависимости от населения и падала линейно от расстояния. Так народ будет стремиться как в Петергоф, так и в Москву, но почти проигнорирует Кудымкар. Кстати, так можно будет поприжать полубаг-полуфичу, когда мы шлём эшелон за эшелоном пассажиров в самую маленькую деревеньку на дальнем конце карты и обогащаемся сказочно. А может, и без степени всё заработает ::)

К(М)=х(М)/(х(М)+х(П)+х(К))

К(М) - и есть вес города, определяющий, какая часть общего кол-ва пассажиров на станции СПб сядет на поезд до М. Такую таблицу можно составить для каждой станции и обновлять, скажем, раз в месяц или даже реже - население городов не так быстро меняется. Думаю, все таблички для одного игрока займут не больше десяти-пятнадцати килобайт, а мощности проца на расчёты не потребуется вовсе.

Нам же останется только пустить требуемое количество поездов по уже имеющимся маршрутам. И начнётся Жизнь. Конечно, не все моменты я продумал...

ЗЫ: Killen о том же говорит!
PK, ты неправ и неучтив. Нехорошо.

ЗЗЫ: для смазки всего механизма можно долить на станцию полстакана обычных пассажиров, которым вообще всё равно. Чтобы сглаживали всю эту математику.

[KubiR]

Маленько поддержу идею Dictu.
Если продолжать развивать его линию, то на станциях(остановках) вместо общего рейтинка перевозки:
Пассажиры N%
Почта M% и тд, уже следует показывать пасс.Питер A%, пасс.Москва B%, пасс.Кудымкар С%

кажется это уже в самом конце, на этапе исполнения будет)))

[Pk]

А что-то вроде и будет.

Поскольку единица будет работать не с массивом "остановки пассажиры", а с массивом "остановки маршрута пассажиры"

Так же такой вопрос: когда вы едете на работу/учёбу/... вы каждый раз смотрите на карту, сверяете маршрут? Нет.
Итак оптимизация №1: маршрут может быть записан в память как типовой, т.е:
если 2 (и более) пассажира хотят пойти из точки А в точку Б, при этом между ними есть маршрут "АВБ", то скорее всего (95% вероятность), что второй пассажир слепо пойдёт за первым.
Таким образом, к-во операций возрастает не на 2000-5000% в общем объёме, уж никак.
Зачем нужен 5% остаток? Просто это те лемминги, которые будут открывать новые маршруты, сами без ожидания пробок.
Так же этим начинают заниматься те единицы /групп/ пассажиров, которые уже начинают опаздывать (красные).

Оптимизация №2: Если более 4-х единиц (груз, машин и т.п.) идут со сходными свойствами, то: они могут быть объеденены в группу и обрабатываться сходно, т.е.
для маршрута: единицы №№, длина маршрута, время мин. сред., время сред., время макс. сред., средняя нагрузка.
(ещё сыро, возможна большая оптимизация БД + стабильность работы.)
Почему 4? Чтобы была польза в объёме.

>>Dictu

А надо сделать так, что пассажир после появления на станции был привязан к имеющемуся поезду, и ждал его.

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

Насчёт учтивости: человеку говоришь: "ВАЗ - не лучший автомобиль в мире", а в ответ: "Ты хочешь сказать, что самолёты миру не нужны!?"
Задалбывает, знаешь ли.
Сначала Quark, который нежелал читать то, что написано, потом один придурок (полчаса трепал нервы про то, что девушка то ли жива, то ли всё, хотя знал что жива и дома), потом снова (читай цитату "я так не делаю").
"Либо мы работаем по одним инструкциям, либо не жалуемся, что работаем чёрт знает как".

>>George

На графе это называется путь. Только вот перебором решать эту задачу для каждого отдельного пассажира при прибытии транспорта на остановку, где этот пассажир стоит, процессорных мощностей не хватит. Ведь на каждой остановке 2-3 сотни пассажиров, на карте 256х256 полсотни городов, в городе с десяток остановок - это песец даже если задачу решать для всей партии пассажиров с одной точкой назначения. Даже если считать, что назначение это город, и любая остановка в городе подходит, простейшая задача доехать до самолёта на автобусе, пересесть на самолёт и долететь не такая простая задача. А уж что делать в случае, если для того, чтобы проехать из города 1 в город 3 надо приехать в город 2, проехать по городу 2 на другую остановку, и оттуда ехать в город 3? Тогда расчёт по годам вести не получится, придётся по остановкам. А ежесекундный расчёт 1000 кратчайших путей на графе в 1000 узлов мне кажется очень сложной задачей. Хотя может я перегибаю палку. Давайте оценим, сколько единиц транспортных средств прибывает на все станции всех игроков в секунду (в среднем)? Кто может дать оценку?
Да, и ещё меня вот что смущает. Если мы считаем по-остановочно, то попав на остановку одного игрока, на остановки других он попасть не может. Но явно в перспективе будет кооперативная игра и общие остановки. Тогда граф существенно расшириться. Надо ли считать, что пассажир приехал, если он попал в готод назначения на транспорте другой компании, а не той, с которой он стартовал?

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

По поводу пересадок: какая хрен разница на что? Да хоть на подводную лодку! Для Лемминга (и нас) никакой разницы, только придётся объединить в правах переменные для самолётов, кораблей, машин и поездов. (хотя, имхо, этот кус в коде вообще надо переделать)

[Dictu]

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

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

А езду с пересадкой АБВ можно реализовать путём трансфера. Все данные из таблицы перевалочной станции Б, отсутствующие в таблице станции А, добавляются в неё, а в знаменатель расчёта их рейтинга на станции А плюсуется расстояние АБ.

Соответственно, тег, о котором ты говоришь - это наличие Б, В или Г в расписании подошедшего поезда.

И чего такого нет в этой простейшей схеме, ради чего стоит придумывать пересадки, да ещё на станции конкурентов, маршрут каждого третьего пассажира от порога до порога дома и прочее, типа расчёта графов?

Кстати, в этой же схеме вид транспорта вообще не играет роли, лишь бы на станцию заходил и пассажиров брал.

Оккам говаривал: "Не следует умножать сущности сверх необходимости". По мне таки старик прав.

[Pk]

А по мне не имеет роли чья техника/терминалы используется (по крайней мере до появления проездных и скидок, да и то - так, фон).

А нафига нам трансфер, если мясо само вылезет там где надо, да и заплатив за проезд? Тем более что у меня по маршруту "грузовик-корабль-грузовик" получалась только отрицательная прибыль.

Тег-то тег... но есть одно но: сколько до этой станции ползти? Если у нас 2 станции в листе - норма, а если 3 (FFF-RH-FFF-MH)? Мой-то довести ещё можно (если потом будет быстрее, то пропустить), а вот твоё мясо...

[Pk]

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

[Dictu]

PK, ты выражаешься осмысленно, но очень туманно, а потом на всех кричишь, что оне невнимательно тебя читают. Чиста по оптимизации лучше будет, если ты один раз потрудишься при написании, чем десятки читателей десятки раз при чтении.

Теперь по сути. Трансферы надо обсчитывать, потому что они должны быть вписаны в систему, иначе всё развалится. Зачем нужны трансферы - это вопрос не про здесь, но поверь, нужны. А обсчитанные они всё украсят, ага.

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

Про тэг - ты вообще непонятно написал. Извини. У меня такое впечатление, что ты постишь не результаты, а сам процесс мышления, причём незавершённый.

Я же постарался написать формулы, о которых говорил выше. получилось довольно похоже на passengers destinations, но сильно попроще. ИМХО, должно работать, хотя некоторые моменты надо додумать. Ну чего я не кодер?

[George]

Кол-во пассажиров, имеющихся на станции А, поделено на части Б, В, Г (это остановки, имеющиеся в расписании пасс. поездов, проходящих через станцию А). Поезд, имеющий в расписании Б или В забирает пассажиров только из этих частей. И скидывает такое же количество на остановках Б и В. Пополняются части путём умножения общего притока пассажиров на рейтинг станции назначения (описанный в предыдущем моём постинге).

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

Давайте вернёмся к постановке вопроса.
Каждый пассажир, сгенерированный зданием (обращаю внимание, что пассажиры генеряться зданииями, а не остановками), случайным образом по некоторым правилам выбирает город назначения (в том числе город, в котором находится здание).
Далее, если рядом с его домом несколько остановок, он должен выбрать остановку (Сейчас выбор в соответсвии с рейтингом станций), с которой он начнёт движение. Остановку он должен выбирать ту, с которой он через пересадки попадёт в город назначения. Если задача не имеет решения, пассажир либо никуда не едет, либо выбирает новую точку назначения. Далее пассажир будет платить за перевозку его до конечной точки по прибытию в эту конечную точку из расчёта затраченного времени и растояния от его дома до точки, в которую его доставили. В качестве расширения можно сделать вариант, что если он выбрал свой город, то он должен попасть в некоторую определённую часть города.
Есть ли возражения к постановке вопроса?