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

(Reply to this) (Thread)

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

(Reply to this) (Parent) (Thread)

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

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

(Reply to this) (Parent) (Thread)

Короче, смотри :)
Смысл в том, что задача собственно поиска пути в этом посте не решается. Здесь решается задача перебора направлений, и только :)
Ну представь себе, что у тебя есть клетка. Вокруг нее восемь других клеток. Тебе нужно их проверить по очереди. Проверить по некоему условию, которое тебя не волнует. Каждая из этих клеток кодируется двумя числами, каждое из которых может принимать значение -1, 0, 1. Вот их нужно перебрать.
Если бы нужен был просто тупой перебор, я бы делал так:

for (int i=-1; i<2; i++) {
for (int j=-1; j<2; j++) {
check (i, j);
}
}

Но! Мне нужен не простой перебор. Мне нужен перебор, начинающийся от определенных значений i и j и заканчивающийся значениями -i, -j.
Искать путь не надо, это я так, в качестве лирического отступления упомянул :).

(Reply to this) (Parent) (Thread)

Хм? Типа,

Дано: восемь значений.
Задача: невозбранно проверить их!

Как-то непохоже на задачу, достойную поста в жж.

Ты говоришь "Мне нужен перебор, начинающийся от определенных значений i и j и заканчивающийся значениями -i, -j"

под i,j имеются в виду координаты клеток, так? Типа, i = количество горизонтальных, а j = вертикальных шагов от Здесь? Ну значит если тебе нужен не простой перебор, а от сих и до сих, так и пиши не for i = -1; i< 2, а пиши for i = от_сих; i< до_сих

хотя для задачи размеров в 8 простой перебор наверное таки лучше =)

или я реально туплю и не понимаю чего-то, что тут тебя заинтересовало?

(Reply to this) (Parent) (Thread)

пиши не for i = -1; i< 2, а пиши for i = от_сих; i< до_сих

От сих до сих - это от каких до каких? :)
Нет, проблема в том, что интервалы по-любому будут от -1 до +1 включительно. Но порядок перебора не линейный "от сих до сих", а по окружности. Представь себе такое обтекание окружности с двух сторон. А там получаются очереди, которые тупо циклом не переберешь. Ну я же в посте привел пример перебора, начинающегося от 0, -1 и заканчивающегося 0, 1:

dC = 0, dR = -1
dC = -1, dR = -1
dC = 1, dR = -1
dC = -1, dR = 0
dC = 1, dR = 0
dC = -1, dR = 1,
dC = 1, dR = 1
dC = 0, dR = 1

А, допустим, если начинать с -1, -1, то получится вот такое:

-1, -1
-1, 0
0, -1
-1, 1
1, -1
0, 1
1, 0
1, 1

Какие ты тут "от сих до сих" будешь подставлять? :)

(Reply to this) (Parent) (Thread)

хм, я что-то не понимаю вопроса. Если ты говоришь о порядке, то это значит, что у тебя есть понятие, ну, порядка, в математическом смысле. То есть, все пары элементов твоего множества могут быть скормлены оператору "<" и дадут ответ "да" или "нет". Значит можно задать диапазон "от сих до сих", математически осмысленный. То есть, напиши тупо оператор "<" для своего класса или что там в си, стракты? И задавай =)

о, и ещё - что означают твои имена dC, dR? я бы назвал dH, dV, хоризонтал и вертикал )

(Reply to this) (Parent) (Thread)

dC и dR генетически восходят к dCol и dRow :)

То есть, все пары элементов твоего множества могут быть скормлены оператору "<" и дадут ответ "да" или "нет". Значит можно задать диапазон "от сих до сих", математически осмысленный. То есть, напиши тупо оператор "<" для своего класса или что там в си, стракты? И задавай =)

Так нет, в том-то и дело! На окружности нет отношения больше-меньше. Вправо-влево есть, но это не совсем то. Давай на пальцах. Вот девять клеток:

A B C
D E F
G H I

Тебе из клетки E нужно заглянуь в каждую из соседних букв. Причем тебе дается начальная буква. Допустим, это буква F. Сначала ты проверяешь F, затем соседние - C и I, затем их соседей B и H, потом A и G, потом D.
Как ты на множестве ABCFIHGD введешь операцию сравнения, если ты не знаешь, начнешь ты обход с точки F или, к примеру, с точки A?

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

static int circle[] = {0, 10, 20, 21, 22, 12, 2, 1};

каждое число в этом массиве получено следующим образом: 10*(dC+1) + dR + 1

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

(Reply to this) (Parent) (Thread)

ну чисто _формально_ - да, массив не нужен... задай пару функций, описывающих биекцию из твоих восьми клеток в Z8 и обратно, и вызывай "следующую" клетку операцией "плюсадин" =)

(Reply to this) (Parent) (Thread)

Уж все-таки лучше один массив, чем восемь ифов :)

(Reply to this) (Parent) (Thread)

ну, да, и памяти съест столько же )

(Reply to this) (Parent)

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

(Reply to this) (Parent) (Thread)

imho она несложно формализуется - трабл в другом - с 8 клетками проще захардкодить значительную часть логики, чем писать ее "по уму" - в результате чего и получается то, что получается. Но короче всего делается как-то так:

static int dirs [] [2] =  { 0,1,   1,1,  1,0,    1,-1,  0,-1,  -1,-1,  -1,0,  -1,1 };
static int order [] = {0, 1,-1,  2,-2, 3,-3, 4};
void scan (int dir) {
  for (int i = 0; i != 8; ++ i)
    {
      int const * d = dirs [(order [i] + dir + 8) % 8];
      printf ("<%d,%d>  ",  d [0], d [1]);
    }
   printf ("\n");
}

(Reply to this) (Parent) (Thread)

О, симпатично, кстати.

(Reply to this) (Parent)

Вернее вот так:

for (int i=-1; i<2; i++) {
for (int j=-1; j<2; j++) {
if (i!=0||j!=0) check (i, j);
}
}

Но это не принципиально :)

(Reply to this) (Parent)

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

(Reply to this) (Thread)

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

(Reply to this) (Parent)