StarCraft FOREVER - Тема для волосатых мужиков (задача с графом)

Страница 1 из 2

Показывать 40 сообщений этой темы на одной странице

StarCraft FOREVER (http://www.forum.7x.ru/index.php)

- Общий форум (http://www.forum.7x.ru/forumdisplay.php?f=60)

- - Тема для волосатых мужиков (задача с графом) (http://www.forum.7x.ru/showthread.php?t=659)

uti	19.07.2011 11:22

Тема для волосатых мужиков (задача с графом)

Пишу свою браузерную игру с маджонгом и гейшами. Возникла следующая проблема.

Есть поле из гексов и некий источник энергии, от которого она может распространяться по всем ячейкам. При этом поток может разделяться и объединяться сколь угодно раз. Но в нём не должно быть циклов. Проще говоря, если двигаться по любым энергетическим веткам вдоль "течения", то никогда нельзя оказаться в одной ячейке более одного раза, то есть нельзя сделать петлю.
Как детектить такое замыкание?
Зелёный - как можно. Красный - как нельзя.

p.s. На одном форуме порекомендовали топологическую сортировку, но я что-то не понял, как её тут применить.

http://img171.imageshack.us/img171/712/screenmy.jpg

[7x]Злобный Head

19.07.2011 15:47

Полярные координаты, проверка списка точек на существующие и если совпадает, то запрещать.

Dyavol

19.07.2011 16:27

Хотел предложить один способ, но он разрешает стрелку из клетки 3.0 в 2.1
Так что надо ещё подумать.

Добавлено через 4 минуты
А хотя это ж и не проблема. Цикла то не будет.
Короче вот:

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

Если хочется сделать затухание энергии, то можно начинать не с единицы, а с максимальной дальности распространения энергии, и отнимать по единице.

Dyavol

19.07.2011 18:27

К цикличности поидее будут приводить только стрелки, в которых от большего к меньшему идёт. Если от меньшего к большего или даже между одинаковыми, то циклов не будет.

uti	19.07.2011 18:41

Но "от большего к меньшему" - недостаточное условие для зацикливания.

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

код javascript:

Код:

var edges = [

  [1],        // из 0

  [2],        // из 1

  [3],        // из 2

  [4,15],     // из 3

  [],         // из 4

  [8],        // из 5

  [7],        // из 6

  [10],       // из 7

  [10],       // из 8

  [],         // из 9

  [9],        // из 10

  [5,12],     // из 11

  [1],        // из 12 (!)

  [11],       // из 13

  [6],        // из 14

  [13,14]     // из 15

];



// true если петель нет, false если есть

alert(checkGraph(edges));



function checkGraph(edges) {

  var n = edges.length;

  var clr = new Array(n);

  var dfs = function(v) {

    if (clr[v] == 1) return true;

    if (clr[v] == 2) return false;

    clr[v] = 1;

    for (var i = 0; i < edges[v].length; i++) {

      if (dfs(edges[v][i])) return true;

    }

    clr[v] = 2;

    return false;

  };

  for (var i = 0; i < n; i++) {

    if (dfs(i)) return false;

  }

  return true;

}

А вот картинка, по которой я вершины нумеровал. Можно поэкспериментировать.

http://img198.imageshack.us/img198/3251/screenbw.jpg

Dyavol

19.07.2011 18:49

А придумаешь конфигурацию при которой от меньшего к большему идёт, но при этом зациклено?

uti	20.07.2011 10:18

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

[7x]Злобный Head

20.07.2011 11:04

Мега, объясни, почему незаюзать просто проверку на присутствие стрелки.

uti	20.07.2011 11:57

Что значит "проверка на присутствие стрелки"? Давай не будем говорить на языке гуманитариев. Напиши по пунктам алгоритм, который ты предлагаешь, и я поищу в нём ошибку (но, скорее всего, ты сам её найдешь, когда займёшься этим).

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

[7x]Злобный Head

20.07.2011 14:32

У тебя поле, представляем как массив. Как предлагал дъявол сначала все 0, потом забиваем цифры в клетки куда идём. Когда делаем новую стрелку определяем куда она делается и проверяем наш элемент массива на число.

Это же старо как мир всё.

Добавлено через 3 минуты
Как раз таки как я предлагаю случая как в клетке 10 не будет, всё что отлично от заданой константы запрещает установку стрелки.

Добавлено через 3 минуты
к примеру есть поле 10*15
это массив двойной [10][15]
изначально где-то есть наш "источник добра", в массиве его положение соответствует строке и столбцу нашего массива, и значится например как - 1000, всё остально - 0
начинаем строить стрелки, если надо можно нумеровать их, и в массив заносить их порядковый номер. Если клетка массива,куда ставим новую стрелку, равна 0 то стрелка ставиться, если не равно 0, то всё стрелку ставить нельзя.

Так понятней?

Текущее время: 22:31. Часовой пояс GMT +4.

Страница 1 из 2

Показывать 40 сообщений этой темы на одной странице