Тема для волосатых мужиков (задача с графом)
Пишу свою браузерную игру с маджонгом и гейшами. Возникла следующая проблема.
Есть поле из гексов и некий источник энергии, от которого она может распространяться по всем ячейкам. При этом поток может разделяться и объединяться сколь угодно раз. Но в нём не должно быть циклов. Проще говоря, если двигаться по любым энергетическим веткам вдоль "течения", то никогда нельзя оказаться в одной ячейке более одного раза, то есть нельзя сделать петлю. Как детектить такое замыкание? Зелёный - как можно. Красный - как нельзя. p.s. На одном форуме порекомендовали топологическую сортировку, но я что-то не понял, как её тут применить. http://img171.imageshack.us/img171/712/screenmy.jpg |
Полярные координаты, проверка списка точек на существующие и если совпадает, то запрещать.
|
Хотел предложить один способ, но он разрешает стрелку из клетки 3.0 в 2.1
Так что надо ещё подумать. Добавлено через 4 минуты А хотя это ж и не проблема. Цикла то не будет. Короче вот: можно пометить все клетки нулями и клетку с источником в единицу. Потому клетку в которую сделан первый шаг поставить в двойку и так дальше. Таким образом число в клетке будет на единицу больше, чем количество шагов нужное, чтоб туда пройти (за исключением нуля) Во первых при расстановке менять номер можно только если текущий меньше, чем тот, что там стоял (это если хочется лабиринт сделать и зафигачить там поиск крадчайшего пути. Для твоей задачи достаточно просто проверки на ноль) А если есть ещё и стрелки, то правильными считать только те, у которых начало стрелки на единицу меньше конца стрелки. Остальные не правильные. Если хочется сделать затухание энергии, то можно начинать не с единицы, а с максимальной дальности распространения энергии, и отнимать по единице. |
К цикличности поидее будут приводить только стрелки, в которых от большего к меньшему идёт. Если от меньшего к большего или даже между одинаковыми, то циклов не будет.
|
Но "от большего к меньшему" - недостаточное условие для зацикливания.
Короче, вот как я сделал. Нашёл похожий урок на хабре. Не знаю, как быстродействие, но вроде работает. Нужно только пронумеровать все вершины графа в произвольном порядке и для каждой написать, к каким вершинам от неё имеются переходы. Этот массив скармливаем функции и получаем ответ, имеются в графе циклы или нет. код javascript: Код:
var edges = [ http://img198.imageshack.us/img198/3251/screenbw.jpg |
А придумаешь конфигурацию при которой от меньшего к большему идёт, но при этом зациклено?
|
Не думаю, что такое возможно. Для зацикливания "поток" из клетки должен вернуться в неё же. В случае этого поля минимальный цикл может состоять из трёх стрелок, а, значит, замыкающая клетка будет минимум на два уровня выше, чем замыкаемая.
|
Мега, объясни, почему незаюзать просто проверку на присутствие стрелки.
|
Что значит "проверка на присутствие стрелки"? Давай не будем говорить на языке гуманитариев. Напиши по пунктам алгоритм, который ты предлагаешь, и я поищу в нём ошибку (но, скорее всего, ты сам её найдешь, когда займёшься этим).
Если ты имеешь ввиду проверку целевой вершины на наличие исходящего ребра, то ты не учитываешь возможности слияния потоков как, например, в ячейке 10. |
У тебя поле, представляем как массив. Как предлагал дъявол сначала все 0, потом забиваем цифры в клетки куда идём. Когда делаем новую стрелку определяем куда она делается и проверяем наш элемент массива на число.
Это же старо как мир всё. Добавлено через 3 минуты Как раз таки как я предлагаю случая как в клетке 10 не будет, всё что отлично от заданой константы запрещает установку стрелки. Добавлено через 3 минуты к примеру есть поле 10*15 это массив двойной [10][15] изначально где-то есть наш "источник добра", в массиве его положение соответствует строке и столбцу нашего массива, и значится например как - 1000, всё остально - 0 начинаем строить стрелки, если надо можно нумеровать их, и в массив заносить их порядковый номер. Если клетка массива,куда ставим новую стрелку, равна 0 то стрелка ставиться, если не равно 0, то всё стрелку ставить нельзя. Так понятней? |
Текущее время: 12:32. Часовой пояс GMT +4. |
Powered by vBulletin® Version 7.7.7
Copyright ©2002 - 2024, 7x.ru information site edition. Перевод:
Копирование информации сайта без разрешения администрации преследуется по понятиям.