Линии

← →
anod (2001-11-15 21:54) [0]

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

← →
Дремучий (2001-11-15 22:08) [1]

2anod
вопрос нужно ставить конкретнее

← →
anod (2001-11-15 22:35) [2]

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

← →
Вадим (2001-11-15 22:42) [3]

lines?

← →
Дремучий (2001-11-15 22:58) [4]

мы тут с Китайцем посоветовались -
суть примерно такова 8)

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

;))

← →
anod (2001-11-16 00:33) [5]

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

← →
panov (2001-11-16 08:00) [6]

Катишь мышку по столу, если в нужную точку попал - путь свободен.

← →
Дремучий (2001-11-16 10:01) [7]

2 anod ©
>>У меня для каждой клетки, кроме тех,которые у стеночки, есть 4
>>варианта хода
....постоянно увеличиваешь(или уменьшаешь) свой x,y в направлении к желаемой клетке ....

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

← →
anod (2001-11-16 11:08) [8]

Понял, буду пробовать, спасибо.

← →
Merlin (2001-11-16 11:23) [9]

> нельзя приближаться к объекту удаляясь от него
Запросто! "Назад в будущее" смотрел? :)))

Вот в таком лабиринте
B.... ####. ...#. .#.#. A#...
тебе однозначно придется удаляться от точки "B" некоторое время.

Для поиска кратчайшего пути в любом лабиринте, я бы сделал так:
1. Есть двумерный массив.
2. Исходная точка и конечная точка
3. В массиве преграды как-то помечены
4. В исходную точку ставим воображаемый шарик
5. Каждый воображаемый шарик ставит потомков во все свободные клетки вокруг себя (можно ходить по диаганали или нет, это уж как захочется)
6. Каждый воображаемый шарик имеет порядковый номер. Тот что в исходной точке 0, он поставил вокруг себя 1-е, те вокруг 2-е и т.д.
7. Когда воображаемый шарик ставит вокруг себя потомков, он может заменить какой-то другой воображаемый шарик рядом с собой, если у того, порядковый номер больше, чем у нашего потомка! (если этого не делать, то мы тоже найдем возможный путь, но он не всегда будет кратчайшим)
8. Так в цикле ползем до тех пор, пока какой-то воображаемый шарик не доберется до конечной точки.
9. Получаем кратчайший свободный путь двигаясь от конечной точки по воображаемым шарикам с номером на 1 меньше чем у текущего.

Чтобы стало понятнее, лучше нарисую.
Имеем:

B.... ###.. ...#. .#... A.... #- преграды A- исходная точка B- конечная Для того, чтобы меньше рисовать, допустим, по диагонали ходить можно. Поехали: B.... ###.. ...#. 1#... A1... B.... ###.. 22.#. 1#2.. A12.. B.... ###.. 223#. 1#23. A123. B.... ###4. 223#4 1#234 A1234 B.555 ###45 223#4 1#234 A1234 B6555 ###45 223#4 1#234 A1234
Дошли до конечной. От нее в обратном направлении, топаем по шарикам с меньшим номером на единицу:
Звездочками помечаю:
B**55 ###*5 22*#4 1#*34 A*234
Вот и получили кратчайший путь.
Осталось это реализовать :) Я такое делал еще в школе, но программы не сохранилось... :(

← →
Дремучий (2001-11-16 12:08) [10]

2 anod ©
Метод Merlinа бесспорно красивей и еффективней.
Но это не мешает придумать что-то свое еще более...
;)

← →
Dush (2001-11-16 12:09) [11]

2anod Алгоритм называется "Волновой". Я часто натыкался на описание этого алгоритма написанное Медноноговым. Описание очень хорошее и понятное. Попробуй поискать.
2Merlin В lines, помоему, нельзя прыгать по диагонали.

← →
anod (2001-11-16 12:58) [12]

2Merlin И вправду красивый метод
2Dush Сразу столько статей нашел... Будем читать

← →
anod (2001-11-17 13:26) [13]

Вот! Разобрался.
Вобщем, как я понял, этот алгоритм похож на то, сто предложил Merlin.
Только при попытке нажать в "заперщенную" клетку, программа подвисает.

Tckb rjve bynthtcyj
http://prg.newmail.ru/rus/gamemaker/alg/alg10.html

← →
anod (2001-11-17 20:00) [14]

Подскжите как учесть нажатие на клетку, в которую нельзя ходить.
В описании Медноногова, сказано, что если ni>nk,то ход не возможен,
тогда как определить nk (там не сказанно)

procedure TForm1.Path(nni,nnj,kki,kkj:word);{ввожу начальные и конечные координаты} var i,j,x,y,x1,y1,min:word; ni,nk:word; rp:array [1..4,1..4] of word; begin x:=nni; y:=nnj; ni:=0;{счётчик итерaций} nk:=16;{мaксимaльно возможное число итерaций} for i:= 1 to 4 do for j:= 1 to 4 do if Mpole^[i,j].val=0 then rp[i,j]:=254 else rp[i,j]:=255; rp[x,y]:=253; rp[kki,kkj]:=0; While ni<>nk do begin for i:= 1 to 4 do for j:= 1 to 4 do if rp[i,j]=ni then begin if i<4 then if rp[i+1,j]=254 then rp[i+1,j]:=Ni+1; if i>1 then if rp[i-1,j]=254 then rp[i-1,j]:=Ni+1; if j<4 then if rp[i,j+1]=254 then rp[i,j+1]:=Ni+1; if j>1 then if rp[i,j-1]=254 then rp[i,j-1]:=Ni+1; end; Inc(Ni); end; repeat if x<4 then begin min:=rp[x+1,y]; x1:=x+1; y1:=y; end; if x>1 then if rp[x-1,y]<min then begin min:=rp[x-1,y]; x1:=x-1; y1:=y; end; if y<4 then if rp[x,y+1]<min then begin min:=rp[x,y+1]; x1:=x; y1:=y+1; end; if y>1 then if rp[x,y-1]<min then begin min:=rp[x,y-1]; x1:=x; y1:=y-1; end; Hod(x1,x2); X:=X1; Y:=Y1; until rp[x1,y1]=0; SecondClick(x1,y1); end;

← →
vasco (2001-11-18 14:21) [15]

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

← →
Anatoly Podgoretsky (2001-11-18 16:22) [16]

Какое к черту серьезное пожирание стека - для стандатного Лайнс глубина максимум 80 вызовов

← →
vasco (2001-11-18 17:46) [17]

Согласен, просто если этот же подход использовать в стратегии, нулей будет больше...

← →
anod (2001-11-18 21:31) [18]

А чем это вам не метод Merlina.
Создаётся новая матрица, размером в поля (4x4 miniLines)
И просматривается поле. Если клетка своболна, тогда этому эл-ту матрицы присваевается 254 иначе 255 (т.е. что-то чтоит уже там)
Шарику, который мы взяли :=253, а куда его надо положить - 0.
Теперь идет метод Merlin"a, только не от начальной точки, о от нуля.
И когда просмотрели ищем самый короткий путь, пока <>0.
Вот тут-то и происходит зацикливание. Потомучто если нет пути, то мы 0 и недостигнем. Надо как-то это отловить. и Написать игроку, что ход невозможен.

← →
Merlin (2001-11-19 15:05) [19]

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

Кстати, еще один вариант. Для очень больших массивов.
Суть:
Движемся по направлению к конечной точке. Если нельзя двигаться напрямую к ней, то выбираем случайно любое доступное направление. Если зашли в тупик, то возвращаемся назад до первого свободного поворота.
Самое главное. Если мы своим движением образовали замкнутое пространство внутри которого нет конечной точки, то помечаем его целиком, как стену.
Как говорится, лучше один раз увидеть:
.B..... ######. ....... ####... .1..... .A..... Буквально с первого шага получили замкнутуе пространство слева, отрубаем его (совершенно верно то, что замкнутое пространство получилось и справа, но его отрубать нельзя, т.к. в нем конечная точка :) .B..... ######. ...5... ####4.. #123... #A..... На 5-ом шаге, также есть замкнутый контур с пустыми полями, помечаем его и левее уже не двигаемся .B..... ######8 ###567. ####4.. #123... #A..... На 8-ом тоже есть контур, заполняем и его .B..... ######8 ###567# ####4## #123### #A##### И т.д.
Надеюсь суть понятна :) Он не обеспечивает нахождения кратчайшего пути, но! дает фору первому методу на больших лабиринтах. Здесь только одна сложность, в поиске замкнутого контура и определения, есть ли конечная точка в нем или нет. Но на эту тему, есть в инете алгоритмы.

← →
Дремучий (2001-11-19 16:31) [20]

В принципе это и есть то, что предлагал Дремучий.
Просто с иллюстрациями и более подробно.
;))

← →
-=CrazyFish=- (2001-11-19 17:06) [21]

А вот еще один метод.
Рисуешь аналог поля (в виде соприкасающихся клеток) на битмэпке, там, где шарик есть - один цвет, там, где шарика нет (или есть тот, который двигаем)- другой. Выполняешь метод FloodFill в исходной клетке новым цветом. Если конечная клетка окрасилась в новый цвет, значит путь свободен.

← →
Merlin (2001-11-19 17:39) [22]

> Дремучий © (19.11.01 16:31)
> В принципе это и есть то, что предлагал Дремучий.
Возможно, но здесь есть важная деталь про отбрасывание областей, куда заходить бессмысленно. Иначе получаем простой перебор, что реализовать проще всего, но не интересно, ИМХО :)

> -=CrazyFish=- © (19.11.01 17:06)
Для задачи lines требуется еще и определить путь, по которому поскачет шарик туда... А это решение мне напомнило анекдот про гвоздь.

Программист и плотник. Есть две доски в первой вбит гвоздь на половину, во второй по самую шляпку. Задача: вытащить оба гвоздя.
1. Плотник. Свободно выдирает гвоздь забитый наполовину и начинает колупаться со вторым.
2. Программист. Колупается с забитым по шляпку, в конце концов вытаскивает его. Забивает второй гвоздь по шляпку и объявляет: "Вытаскивается аналогично!"
:)

← →
-=CrazyFish=- (2001-11-19 18:04) [23]

>Merlin
Разумеется, метод, который я предложил, бредовый.
Но я видел несколько клонов Lines, в которых путь не прорисовывается в принципе, шарик просто исчезает в одном месте и появляется в другом...
P.S. Анегдот мне понравился.

← →
anod (2001-11-19 21:57) [24]

2Merlin
И как мне кажется опять будет происходить зацикливание, если
ход невозможен. В цикле надо проверять условие " пока не равно В ".
??

← →
Merlin (2001-11-19 22:14) [25]

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

Если проверять эти условия, то зацикливания не будет.

← →
anod (2001-11-19 22:59) [26]

Ну я пишу (по 1 спосбу):
if (x<4)and(x>1)and(y<4)and(y>1)and (rp[x+1,y]>=min)and(rp[x-1,y]>=min)and (rp[x,y+1]>=min)and(rp[x,y-1]>=min)then begin Form1.Caption:="Нельзя!"; break; end;

где мин - это последнее минимальное число, вокруг текущей клетки.
Вроед, не работает.

← →
Boo (2001-11-28 19:48) [27]

Начало:
.B.....
######.
.......
####...
.......
.A.....

Шаг первый:
.B.....
######.
.......
####...
.1.....
1A1....

Шаг второй:
.B.....
######.
.......
####...
212....
1A12...

Шаг третий:
.B.....
######.
.......
####...
2123...
1A123..

Шаг четвертый:
.B.....
######.
.......
####...
21234..
1A1234.

и т. д.

Шаг четвертый:
.B43210
######9
0987678
####567
2123456
1A12345

где ноль - енто 10 и т. д.
получили: от а до б - за 15 шагов...
самый короткий путь -
.B-----
######|
09876|-
####5|7
21234|6
1A----5

а там уже только программная реализация (моно и без рекурсии, а лучше все-таки с ней)

← →
fliz (2001-11-29 15:41) [28]

2 Мерлин

то что вы предложили, есть наипростейший "метод волны".
мы это в институте проходили. Используется при трассировке
печатных плат, но с сильными оптимизациями."Тормознутость"
просчета - почти квадратичная зависимость от размерности
матрицы M x N. Т.е. для Lines 80x80 подойдет,
но я пробовал для 1500 x 1500 клеток.
На П-100 это занимало около 10 секунд расчета.

← →
Judith (2001-11-29 15:49) [29]

http://emanual.ru/download/716.html

← →
Desdechado (2001-11-29 19:35) [30]

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

Линии Найти похожие ветки