Заказ №30: "Маршрутизация метро"

[Admin 455]

Основное направление разработки на данный момент:

Описание на GitHub | Вспомогательная таблица

 

 

---

 

 

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

 

Оплата за схему развязок = 6 стеков изумрудных блоков

Оплата за подготовку отдельной развязки = 1 стек изумрудных блоков

 

Список станций тут.

 

В качестве награды, как минимум - 

 

Схема линий, станций и развязок:

 

 

Развязки, маршруты, команды:

Спойлер

 

При текущем подходе [для экономии командных блоков при проверке проезжающего игрока] используется "маршрут по умолчанию = на спаун": это означает, что все стрелки по умолчанию ведут на спаун.

Из-за этого необходимо выполнять сброс стрелки после проезда игрока.

 

 

При подготовке команд:

• сначала идут команды в командных блоках: последовательность - сверху (от нажимных рельс) вниз
• в конце должна быть команда сброса конкретной стрелки в исходное положение

 

Коды направлений рельс:

• 0: Север-Юг (Юг-Север)
• 1: Запад-Восток (Восток-Запад).
• 6: Юг-Восток (Восток-Юг).
• 7: Юг-Запад (Запад-Юг).
• 8: Север-Запад (Запад-Север).
• 9: Север-Восток (Восток-Север).

 

Последний вариант с деревом квадрантов

Спойлер

 

Про КБ выдачи названия станции в чат и ассоциации номер -> адрес в отдельную группу КБ  тут

Список развязок и станций с адресами  тут

Схема дерева квадрантов и станций и развязок на нем  тут

 

У нас 61 развязка и 43 станции (не считая новый спаун)

Глубина вложенности дерева - 5 уровней.

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

 

Описание команд развязки тут

 

 

 

 

Старый вариант

Спойлер

 

 

 

Стрелка 1

/execute @p[r=20,score_MetroSt_min=2,score_MetroSt=2] ~ ~ ~ /setblock 44 33 -100 rail 0
/execute @p[r=20,score_MetroSt_min=7,score_MetroSt=15] ~ ~ ~ /setblock 44 33 -100 rail 0
/execute @p[r=20,score_MetroSt_min=24,score_MetroSt=26] ~ ~ ~ /setblock 44 33 -100 rail 0
/execute @p[r=20,score_MetroSt_min=32,score_MetroSt=42] ~ ~ ~ /setblock 44 33 -100 rail 0

/setblock 44 33 -100 rail 7 

Стрелка 3

/execute @p[r=20,score_MetroSt_min=1,score_MetroSt=43] ~ ~ ~ /setblock 41 33 -91 rail 9

/setblock 41 33 -91 rail 0 

 

Стрелка 2

/execute @p[r=20,score_MetroSt_min=1,score_MetroSt=1] ~ ~ ~ /setblock 41 33 -96 rail 8
/execute @p[r=20,score_MetroSt_min=3,score_MetroSt=6] ~ ~ ~ /setblock 41 33 -96 rail 8
/execute @p[r=20,score_MetroSt_min=16,score_MetroSt=23] ~ ~ ~ /setblock 41 33 -96 rail 8
/execute @p[r=20,score_MetroSt_min=27,score_MetroSt=31] ~ ~ ~ /setblock 41 33 -96 rail 8
/execute @p[r=20,score_MetroSt_min=43,score_MetroSt=43] ~ ~ ~ /setblock 41 33 -96 rail 8

/setblock 41 33 -96 rail 0  

 

 

[RedTeapot 155]

Итак. Кажется, я понял, в чем проблема. Осталось придумать, как ее поправить.

 

Рассмотрим путь от станции 43 до станции 42. Развязка номер 7.

 

Станция 42 находится по адресу 0 (уровни кроме нулевого нас не интересуют, поскольку станция отправления находится в другом квадранте нулевого уровня). В квадрант 0 можно попасть, уехав на север (кратчайший путь до станции 42) или на юг (кратчайший путь до станции 27). Таким образом, возникает конфликт: куда ехать? Сейчас вышло так, что вагонетка будет отправлена на юг. Но на развязке 23 возникает петля: вагонетка отправляется назад на развязку 24. Потом снова на 23, и цикл повторяется.

 

Вот, попробовал картинку накалякать, чтобы понятнее было (ха, если это помогло хоть как-то).

 

Спойлер

 

-------------------------------------------

 

UPD: Собственно, переписал маршрутизацию.

 

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

 

Не помогло.

 

В общем, вот эта проблема (описанная выше) оказывается куда фатальнее, чем я представлял.

 

У меня уже возникают сомнения в возможности решения задачи таким способом.

 

-------------------------------------------

 

UPD2:

 

Вообще, сильно портят ситуацию, на мой взгляд, станции типа седьмой или восьмой. Расположены в нулевом квадранте, но, например, чтобы попасть на них с нулевого же квадранта (рассматриваем пока нулевой уровень вложенности), необходимо сначала проехать в первый квадрант, а потом вернуться в нулевой на развязку 36 (с развязки 37). Вот такие случаи к чертям собачьим ломают примерно все.

Изменено 24 февраля, 2017 пользователем RedTeapot

[Admin 455]

13 часов назад, RedTeapot сказал:

Вот, попробовал картинку накалякать, чтобы понятнее было (ха, если это помогло хоть как-то).

Да - с помощью списка станций можно вкурить )

 

Думаю...

 

 

---

 

 

UPD:
@RedTeapot

 

13 часов назад, RedTeapot сказал:

на развязке 23 возникает петля: вагонетка отправляется назад на развязку 24. Потом снова на 23, и цикл повторяется.

Чайник, мы тут с Бориком часик курили эту тему (он лишь понаслышке в курсе того, что мы уже год возимся с этой идеей).

 

Я ему всё объяснил на основе этого примера и мы пришли в итоге вот к чему:

Спойлер

Борик: третий раз читаю, не понимаю                        
Борик: например мы хотим поехать из 1 в 5                        
Борик: куда поедем из 1 сначала? вверх или вниз?                        
Борик: просто это по сути равнозначные пути. как программа выбирает?                        
Я:

1. Каждая станция привязана к той развязке, с которой она соединена. По сути, адрес станции равен адресу развязки, к которой она подключена напрямую.
2. я понял, что не так в примере Чайника - ща отвечу тебе на твои вопросы по твоему примеру                        

программа выбирает по значению переменной - ща всё последовательно распишу                        

Я:

1. мы ручками (во время настройки системы) придаём каждой станции уникальный код = расположению в дереве квадрантов: код состоит из нескольких разрядов = количеству уровней вложенности (metro_st_encoded хранит адрес станции как 1-3-0-2 = у нас 4 уровня вложенности)
2. игрок выбирает станцию из списка = после того, как он выберет нужный пункт назначения, ему присваивается значение переменной = Для станции 1-3-0-2 значение переменной будет 2031 (как видим, порядок цифр инвертирован).
3. Мы ручками кодируем каждую развязку - на основе имеющегося расписанного дерева квадрантов = рассказываем системе, куда направлять вагонетку при определённых значениях переменной.
4. При подъезде к развязке игрок активирует проверку этой переменной: система проверяет нужные разряды = выбирает направление движения
5.  

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

 

Всё. Надеюсь, теперь всё станет понятно                        

 

 

---

 

 

Борик: 3 пункт: куда развязка направит вагонетку, приехавшую из станции 1?                        
Я: По идее, так - как закодируем развязки.

 

Грубо говоря, если мы в развязке 1 напишем, что [в зависимости от значения переменной] вагонетка должна ехать в сторону 0, то она всегда поедет туда.

 

При этом, если нужно будет ехать из 2 в 5, то там тоже будет закодировано ручками, что ехать надо всегда в сторону 3. А, даже, если будет написано, что ехать надо всегда в сторону 1, то, как мы уже написали выше, из развилки 1 она всегда поедет в сторон нуля.

 

Хм...
Получается, что Чайник зря переживает и мы все циклы должны разруливать ручками?

И вот в этом посте ты сам все свои циклы разруливаешь конкретными командами.

Откуда у тебя взялись циклы сейчас?

 

13 часов назад, RedTeapot сказал:

Но на развязке 23 возникает петля: вагонетка отправляется назад на развязку 24.

Я к тому, что мне кажется, что на этой развязке не возникнет конфликта.

Если ты считаешь, что он всё же возникнет, то распиши плиз более чётко - почему вагонетка не должна будет поехать с кодом определённой станции - к этой станции?

Почему она поедет в другое место?

 

 

---

 

 

13 часов назад, RedTeapot сказал:

Вообще, сильно портят ситуацию, на мой взгляд, станции типа седьмой или восьмой. Расположены в нулевом квадранте, но, например, чтобы попасть на них с нулевого же квадранта (рассматриваем пока нулевой уровень вложенности), необходимо сначала проехать в первый квадрант, а потом вернуться в нулевой на развязку 36 (с развязки 37). Вот такие случаи к чертям собачьим ломают примерно все.

Тупой вариант - делать нечто вроде... "дерева кривантов"??

Моё личное изобретение - только что придумал!!!

 

Что такое "дерево кривантов"?
Это дерево с четырьмя потомками, но форма которых не - 4 одинаковых квадранта, а 4 соврешненно любой формы фигуры )))))))

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

 

* хотя, Борик говорит, что эта идея с "кривантами" - похожа на К-мерное дерево, а возможно ещё и на B-дерево или R-дерево... Может, есть ещё какие-гениальные идеи математиков... Попросил Борика курнуть эту тему в контексте нашей задачи. Но сейчас он говорит, что проблема не в структуре хранения данных, а в алгоритме... Хз - имхо, "дерево кривантов" поможет нам ))))))

 

+ немного маразма )))))

Спойлер

 

В 6/16/2016 в 20:56, Admin сказал:

Скука, я гениален

 

В 8/31/2015 в 16:09, Admin сказал:

Сука, я гениален

 

Я гениален!

 

Я гениален!

 

 

 

 

[Admin 455]

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

 

1. прокоадывать маршруты длиннее и так, чтобы не уезжать из текущего квадранта, когда это не нужно
2. можно капнуть дополнительные тоннели

 

Главное - это система, позволяющая апгрейдить метро (которой мы сейчас и занимаемся). Всё остальное - мелочи )

[Admin 455]

Вроде, выявили сложности и нашли решение:

1. скорректировать исходные данные так, чтобы не было станций, въезд в которые только через другие квадранты = приписать их к квадранту въезда (вариация "дерева кривантов")
2. обязательно проводить маршруты только внутри квадранта, если станции отправления и назначения в одном квадранте
3. если пункт 2 невозможно выполнить - капнуть пару тоннелей по гос.зазказу, чтобы обязательно был хотя бы 1 маршрут внутри квадранта
   • сразу помечать маршруты, которые нужно построить, но внутри квадранта нет маршрута - только через други = поймём масштаб проблемы

 

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

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

 

---

 

Естественно, вбивать команды и ставить кб нужно будет ручками для каждой развязки.

Хотя, можно покурить мкросы и закодить последовательность действий для однотипных развязок - на основе сгенерированных команд

[JinenryokuFu 278]

12 часов назад, Admin сказал:

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

можно я тебя стукну? Между прочим, команды были наполовину готовы, но идея сделать так, чтобы потом не править все развязки, была настолько хороша, что от команд ручками отказались.

[Admin 455]

11 часов назад, JinenryokuFu сказал:

можно я тебя стукну? Между прочим, команды были наполовину готовы, но идея сделать так, чтобы потом не править все развязки, была настолько хороша, что от команд ручками отказались.

Можно )
Возможно, всё именно так и было. Если не сложно, можешь не только стукнуть, но тыкнуть носом в пост, где приняли это решение?

[JinenryokuFu 278]

В 26.02.2017 в 12:14, Admin сказал:

Можно )

у меня теперь скрин есть))), для истории.

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

[Admin 455]

В 2/26/2017 в 02:22, JinenryokuFu сказал:

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

 

1 час назад, JinenryokuFu сказал:

но в середине твое про то, что надо остановиться пока с командами. Тогда система Чайника казалось близкой завершению.

И за что ты меня хочешь стукнуть (понял - объяснил в конце поста)?

Именно в тот момент мы полностью отказались от обычной маршрутизации, подразумевающей переделку всего и вся при добавлении новой станции.
Далее работу продолжили только над идеей Чайника. Это был только май 2016 года.

Весь июнь работа также продолжалась.

 

С июля работа прекратилась и продолжается лишь изредка:

• в августе Чайник подготовил описание системы
• в октябре Чайник понял, что система с косяками
• в ноябре Чайник продолжил работу над исправлением проблемы
• в декабре система была полностью переписана Чайником, но ошибки остались
• и только сейчас в феврале - были окончательно локализованы косяки и мы поняли, как это исправить

 

В 2/25/2017 в 13:31, Admin сказал:

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

К сожалению, я не очень корректно выразился тут.

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

Эта фраза означает только то, что можно было взять сырую идею Чайника и начать кодить развязки ручками без тестов.

Но систему Чайника никто не вкуривает (никто, кроме Чайника, не знает, какие команды вписывать в кб на стрелках) = отсюда и взялась фраза "но делать было некому", т.к. единственный знающий человек (Чайник) понимал, что кодировать развязки ручками - это ад!

 

Тут даже проблема не в том, что только Чайник всё это понимает.

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

 

Это тупо сложно и геморно делать ручками и мозгом.

С точки зрения сохранения мотивации [и избавления от рутины] проще - много недель и месяцев, время от времени мозговать эту тему и продумывать автоматизированную систему составления команд для командных блоков.

А это уже то, что я выразил фразой - "лучше всё же заморачиваться на автомазацию составления команд и автоматическое тестирование".

 

 

---

 

 

@JinenryokuFu, если ты вкуриваешь систему Чайника и готов помочь с командами для кб по его системе, то я с удовольствием готов как-то совместными усилиями попробовать подключать станции постепенно.

Лично я понял, что нужно доработать Чайнику, чтобы команды в кб генерировались его программой. Но до сих пор не могу осознать - как же именно надо составлять команды в ручную для каждого кб каждой стрелки на развязке (с учётом всех четырёх уровней вложенности): я пока могу направить вагонетку только на нулевом уровне вложенности - далее мозга пока не хватает...

 

В общем, я готов потеоретизировать на эту тему на бумаге, пока Чайник вносит финальные правки в автоматическую систему генерации команд для кб

[JinenryokuFu 278]

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

[Admin 455]

Думаю, что лучше ждать окончания работ над автоматизацией. И да - это риск

[RedTeapot 155]

Возникает ощущение, что довести дело до конца я не в состоянии. Простите меня.

[Admin 455]

1 час назад, RedTeapot сказал:

Возникает ощущение, что довести дело до конца я не в состоянии. Простите меня.

Можешь передать мне этот репозиторий с вики на гитхабе?
А то вики не получается клонировать: есть только мануал, как скачать её локально, не очень пойму - как загрузить её в репозиторий на гитхабе.

[RedTeapot 155]

13 часов назад, Admin сказал:

Можешь передать мне этот репозиторий с вики на гитхабе?
А то вики не получается клонировать: есть только мануал, как скачать её локально, не очень пойму - как загрузить её в репозиторий на гитхабе.

 

Не могу, ибо репозиторий minecraft-metro у юзера VELLEVET уже существует. Мне Гитхаб так и написал. Надо либо выпилить ваш репо, либо переименовать.

 

UPD: А вообще, работа с wiki ведется так же, как и с любыми другими репозиториями, ибо wiki - это кучка md-файлов. Изменил/добавил - закоммитил - запушил.

Изменено 24 марта, 2017 пользователем RedTeapot

[Admin 455]

57 минут назад, RedTeapot сказал:

UPD: А вообще, работа с wiki ведется так же, как и с любыми другими репозиториями, ибо wiki - это кучка md-файлов. Изменил/добавил - закоммитил - запушил.

Вообще, понятно, что всё более менее как-то работает.
Только точно также, в общем, это далеко не у всех получается. Иначе программеры - не были бы такими нужными специалистами )

 

58 минут назад, RedTeapot сказал:

Не могу, ибо репозиторий minecraft-metro у юзера VELLEVET уже существует. Мне Гитхаб так и написал. Надо либо выпилить ваш репо, либо переименовать.

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

 

---

 

Удалил этот форк.
Передай плиз права на эти наработки по метро - попробую, может, с Бориком докурить алгоритм ))))

[Admin 455]

Давайте скинемся на пиво (или сок) Чайнику, чтобы он домозговал автоматизацию метро? )))

[JinenryokuFu 278]

Сколько нужно пива/сока)))) и в какие сроки. Где сам "виновник торжества"?)

[Admin 455]

1 час назад, JinenryokuFu сказал:

Сколько нужно пива/сока)))) и в какие сроки. Где сам "виновник торжества"?)

Виновник, как видишь, всё вокруг да около ходит )
По срокам - есть небольшой нюанс в виде выпускных экзаменов + некоторое время на разработку.

 

Пива и сока нужно по факту: главное - желание )

[JinenryokuFu 278]

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

[Ahnaton 101]

+1 помогу чем смогу.

[PAPATAPON 387]

Давайте уже все вместе запрограммируем эту "неведомую хрень" ...
 

[RedTeapot 155]

5 часов назад, Admin сказал:

Виновник, как видишь, всё вокруг да около ходит )
По срокам - есть небольшой нюанс в виде выпускных экзаменов + некоторое время на разработку.

 

Пива и сока нужно по факту: главное - желание )

 

Ну, сомневаюсь, что вы сможете что-то сделать с ЕГЭ. Я же в таком не особо приятном состоянии не способен что-то полезное совершать. 

 

Или ты серьезно думаешь, что я так что-то с вас тут вытянуть пытаюсь? 

 

---

 

3 часа назад, PAPATAPON сказал:

Давайте уже все вместе запрограммируем эту "неведомую хрень" ...
 

 

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

[Admin 455]

8 часов назад, RedTeapot сказал:

у, сомневаюсь, что вы сможете что-то сделать с ЕГЭ. Я же в таком не особо приятном состоянии не способен что-то полезное совершать. 

 

Или ты серьезно думаешь, что я так что-то с вас тут вытянуть пытаюсь? 

Не - всё ок: про экзамены я понимаю = поэтому и написал, что ближайшее время не сделаем.

А само предложение решил написать именно для того, чтобы снова поднять этот вопрос и не забывать о нём.

Вот - даже Тапон изъявил желание чем-то помочь )))

 

11 часов назад, PAPATAPON сказал:

Давайте уже все вместе запрограммируем эту "неведомую хрень" ...
 

 

8 часов назад, RedTeapot сказал:

 

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

 

В 2/25/2017 в 13:31, Admin сказал:

Спойлер

 

Вроде, выявили сложности и нашли решение:

1. скорректировать исходные данные так, чтобы не было станций, въезд в которые только через другие квадранты = приписать их к квадранту въезда (вариация "дерева кривантов")
2. обязательно проводить маршруты только внутри квадранта, если станции отправления и назначения в одном квадранте
3. если пункт 2 невозможно выполнить - капнуть пару тоннелей по гос.зазказу, чтобы обязательно был хотя бы 1 маршрут внутри квадранта
   • сразу помечать маршруты, которые нужно построить, но внутри квадранта нет маршрута - только через други = поймём масштаб проблемы

 

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

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

 

 

---

 

 

Естественно, вбивать команды и ставить кб нужно будет ручками для каждой развязки.

Хотя, можно покурить мкросы и закодить последовательность действий для однотипных развязок - на основе сгенерированных команд

 

 

Тапон, если ты правда чем-то можешь помочь, может, попробуем обсудить?

[Admin 455]

Может, нам как-то поможет направленный ациклический граф?
https://ru.wikipedia.org/wiki/Направленный_ациклический_граф

 

Выглядит красиво, но чё-то как-то есть станции/развязки в начале, которых не достичь.

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

[FoxSus 16]

Меня тут попросили помочь разобраться с маршрутизации метро. пока возникло только несколько вопросов:

1. Есть актуальная разбивка корты на квадраты?

2. Есть ли тестовый мир (чтоб не создавать свой)?

[Admin 455]

25 минут назад, FoxSus сказал:

1. Есть актуальная разбивка корты на квадраты?

Возможно, это делается вручную (на глаз) и представлено в виде таблицы, ссылка на которую в первом посте.

 

25 минут назад, FoxSus сказал:

Есть ли тестовый мир (чтоб не создавать свой)?

Может, у @RedTeapot

 + в принципе, всё это работает на первых 6 станциях в нашем мире = можно его скачать даже самому через какие-то плагины )