Алгоритм обхождения стоящих шариков

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

Заранее благодарен, Азат.  :

Вот здест глянь:
http://www.codemanual.net/main/algo/alg20.htm

Ооогромное спасибо за ссылку!  :D

Если нужны примеры (делал, когда сам интересовался), держи:

Движение по 4 направлениям:

Uses Crt;<br>Const<br>   Wall = #254;<br>   Move = #250;<br>   Nk = 250;<br><br>Var<br>   R: array [0..79, 0..49] of Byte;<br>   Ni: Byte;<br>   FX, FY: Byte;<br>   i, j: Word;<br><br>Procedure Init;<br>Begin<br>   For j := 0 to 49 do<br>      For i := 0 to 79 do<br>         If (i in [0, 79]) or (j in [0, 49]) then R[i, j] := 255<br>         else Case Mem[$B800:j*160+i*2] of<br>            32: R[i, j] := 254;<br>            Ord('X'): R[i, j] := 0;<br>            1: R[i, j] := 253;<br>            else R[i, j] := 255<br>         End;<br>   Ni := 0<br>End;<br><br>Procedure Clear;<br>Begin<br>   For j := 1 to 48 do<br>      For i := 1 to 78 do<br>         Case Mem[$B800:j*160+i*2] of<br>            Ord(Move):<br>            Begin<br>               GotoXY(i, j);<br>               Write(' '#8)<br>            End;<br>            2:<br>            Begin<br>               GotoXY(i, j);<br>               Write(#1#8)<br>            End<br>         End<br>End;<br><br>Procedure Start;<br>Var<br>   Ok: Boolean;<br>   X, Y, N, X1, Y1: Byte;<br><br> Procedure Check(X, Y: Byte);<br> Begin<br>    Case R[X, Y] of<br>       253: Ok := True;<br>       254: R[X, Y] := Ni+1<br>    End<br> End;<br><br> Procedure Find(X, Y: Byte);<br> Begin<br>    If R[X, Y] < N then<br>    Begin<br>       N := R[X, Y];<br>       X1 := X;<br>       Y1 := Y<br>    End<br> End;<br><br>Begin<br>   Init;<br>   Ok := False;<br>   Repeat<br>      For j := 1 to 48 do<br>         For i := 1 to 78 do<br>         Begin<br>            If Ok then Break;<br>            If R[i, j] = Ni then<br>            Begin<br>               Check(i, j-1);<br>               Check(i+1, j);<br>               Check(i, j+1);<br>               Check(i-1, j)<br>            End<br>         End;<br>      Inc(Ni)<br>   Until Ok or (Ni > Nk);<br>   If Ok then<br>   Begin<br>      X := FX;<br>      Y := FY;<br>      TextAttr := $93;<br>      Repeat<br>         N := 255;<br>         Find(X, Y-1);<br>         Find(X+1, Y);<br>         Find(X, Y+1);<br>         Find(X-1, Y);<br>         If R[X1, Y1] = 0 then Break;<br>         GotoXY(X1, Y1);<br>         Write(Move);<br>         X := X1;<br>         Y := Y1<br>      Until False<br>   End<br>   else<br>   Begin<br>      TextAttr := $9E;<br>      GotoXY(FX, FY);<br>      Write(#2)<br>   End;<br>   TextAttr := $4F;<br>   Window(1, 1, 80, 50);<br>   GotoXY(3, 1);<br>   Write('Итераций - ', Ni, '/250  '#8#8);<br>   If ReadKey = #0 then ReadKey;<br>   TextAttr := $1F;<br>   Window(2, 2, 80, 49);<br>   Clear;<br>   GotoXY(FX, FY)<br>End;<br><br>Begin<br>   TextMode(Co80+Font8x8);<br>   TextAttr := $4E;<br>   ClrScr;<br>   GotoXY(3, 50);<br>   Write(#27#26#24#25' - Move; Space,Del,PgDn,Home,End,Tab - Wall; Insert - Man; PgUp - Target');<br>   GotoXY(54, 1);<br>   Write('ENTER - Start; ESC - Exit');<br>   Window(2, 2, 79, 49);<br>   TextAttr := $1F;<br>   ClrScr;<br>   Window(2, 2, 80, 49);<br>   Repeat<br>      Case ReadKey of<br>         #00: Case ReadKey of<br>            #72: If WhereY > 1 then GotoXY(WhereX, WhereY-1);<br>            #75: If WhereX > 1 then GotoXY(WhereX-1, WhereY);<br>            #77: If WhereX < 78 then GotoXY(WhereX+1, WhereY);<br>            #80: If WhereY < 48 then GotoXY(WhereX, WhereY+1);<br>            #71: {Home}<br>            Begin<br>               If WhereY > 1 then GotoXY(WhereX, WhereY-1);<br>               If Mem[$B800:WhereY*160+WhereX*2] = 32 then<br>                  Write(Wall+#8) else Write(' '#8);<br>               If (FX = WhereX) and (FY = WhereY) then FX := 0<br>            End;<br>            #83: {Del}<br>            Begin<br>               If WhereX > 1 then GotoXY(WhereX-1, WhereY);<br>               If Mem[$B800:WhereY*160+WhereX*2] = 32 then<br>                  Write(Wall+#8) else Write(' '#8);<br>               If (FX = WhereX) and (FY = WhereY) then FX := 0<br>            End;<br>            #81: {PgDn}<br>            Begin<br>               If WhereX < 78 then GotoXY(WhereX+1, WhereY);<br>               If Mem[$B800:WhereY*160+WhereX*2] = 32 then<br>                  Write(Wall+#8) else Write(' '#8);<br>               If (FX = WhereX) and (FY = WhereY) then FX := 0<br>            End;<br>            #79: {End}<br>            Begin<br>               If WhereY < 48 then GotoXY(WhereX, WhereY+1);<br>               If Mem[$B800:WhereY*160+WhereX*2] = 32 then<br>                  Write(Wall+#8) else Write(' '#8);<br>               If (FX = WhereX) and (FY = WhereY) then FX := 0<br>            End;<br>            #59: {F1 - Clr}<br>            Begin<br>               For j := 1 to 48 do<br>                  For i := 1 to 78 do<br>                  Begin<br>                     GotoXY(i, j);<br>                     Write(' '#8)<br>                  End;<br>               FX := 0<br>            End;<br>            #60: {F2 - Fill}<br>            Begin<br>               For j := 1 to 48 do<br>                  For i := 1 to 78 do<br>                  Begin<br>                     GotoXY(i, j);<br>                     Write(Wall+#8)<br>                  End;<br>               FX := 0<br>            End;<br>            #73: {PgUp}<br>               Write('X'#8);<br>            #82: {Ins}<br>            Begin<br>               i:= WhereX;<br>               j := WhereY;<br>               GotoXY(FX, FY);<br>               Write(' ');<br>               GotoXY(i, j);<br>               Write(#1#8);<br>               FX := i;<br>               FY := j<br>            End<br>         End;<br>         #09: {Tab}<br>            For Ni := 1 to 100 do<br>            Begin<br>               i := Random(78)+1;<br>               j := Random(48)+1;<br>               If Mem[$B800:j*160+i*2] <> 1 then<br>               Begin<br>                  GotoXY(i, j);<br>                  Write(Wall+#8)<br>               End<br>            End;<br>         #32: {Space}<br>         Begin<br>            If Mem[$B800:WhereY*160+WhereX*2] = 32 then<br>               Write(Wall+#8) else Write(' '#8);<br>            If (FX = WhereX) and (FY = WhereY) then FX := 0<br>         End;<br>         #13: {Enter}<br>            If FX <> 0 then Start;<br>         #27: {Esc}<br>            Break<br>      End<br>   Until False;<br>   TextMode(Co80);<br>   TextAttr := 7;<br>   ClrScr<br>End.

Движение по 8 направлениям:

Uses Crt;<br>Const<br>   Wall = #254;<br>   Move = #250;<br>   Nk = 250;<br><br>Var<br>   R: array [0..79, 0..49] of Byte;<br>   Ni: Byte;<br>   FX, FY: Byte;<br>   i, j: Word;<br><br>Procedure Init;<br>Begin<br>   For j := 0 to 49 do<br>      For i := 0 to 79 do<br>         If (i in [0, 79]) or (j in [0, 49]) then R[i, j] := 255<br>         else Case Mem[$B800:j*160+i*2] of<br>            32: R[i, j] := 254;<br>            Ord('X'): R[i, j] := 0;<br>            1: R[i, j] := 253;<br>            else R[i, j] := 255<br>         End;<br>   Ni := 0<br>End;<br><br>Procedure Clear;<br>Begin<br>   For j := 1 to 48 do<br>      For i := 1 to 78 do<br>         Case Mem[$B800:j*160+i*2] of<br>            Ord(Move):<br>            Begin<br>               GotoXY(i, j);<br>               Write(' '#8)<br>            End;<br>            2:<br>            Begin<br>               GotoXY(i, j);<br>               Write(#1#8)<br>            End<br>         End<br>End;<br><br>Procedure Start;<br>Var<br>   Ok: Boolean;<br>   X, Y, N, X1, Y1: Byte;<br><br> Procedure Check(X, Y: Byte);<br> Begin<br>    Case R[X, Y] of<br>       253: Ok := True;<br>       254: R[X, Y] := Ni+1<br>    End<br> End;<br><br> Procedure Find(X, Y: Byte);<br> Begin<br>    If R[X, Y] < N then<br>    Begin<br>       N := R[X, Y];<br>       X1 := X;<br>       Y1 := Y<br>    End<br> End;<br><br>Begin<br>   Init;<br>   Ok := False;<br>   Repeat<br>      For j := 1 to 48 do<br>         For i := 1 to 78 do<br>         Begin<br>            If Ok then Break;<br>            If R[i, j] = Ni then<br>            Begin<br>               Check(i, j-1);<br>               Check(i+1, j);<br>               Check(i, j+1);<br>               Check(i-1, j);<br>               Check(i+1, j-1);<br>               Check(i+1, j+1);<br>               Check(i-1, j+1);<br>               Check(i-1, j-1)<br>            End<br>         End;<br>      Inc(Ni)<br>   Until Ok or (Ni > Nk);<br>   If Ok then<br>   Begin<br>      X := FX;<br>      Y := FY;<br>      TextAttr := $93;<br>      Repeat<br>         N := 255;<br>         Find(X, Y-1);<br>         Find(X+1, Y);<br>         Find(X, Y+1);<br>         Find(X-1, Y);<br>         Find(X+1, Y-1);<br>         Find(X+1, Y+1);<br>         Find(X-1, Y+1);<br>         Find(X-1, Y-1);<br>         If R[X1, Y1] = 0 then Break;<br>         GotoXY(X1, Y1);<br>         Write(Move);<br>         X := X1;<br>         Y := Y1<br>      Until False<br>   End<br>   else<br>   Begin<br>      TextAttr := $9E;<br>      GotoXY(FX, FY);<br>      Write(#2)<br>   End;<br>   TextAttr := $4F;<br>   Window(1, 1, 80, 50);<br>   GotoXY(3, 1);<br>   Write('Итераций - ', Ni, '/250  '#8#8);<br>   If ReadKey = #0 then ReadKey;<br>   TextAttr := $1F;<br>   Window(2, 2, 80, 49);<br>   Clear;<br>   GotoXY(FX, FY)<br>End;<br><br>Begin<br>   TextMode(Co80+Font8x8);<br>   TextAttr := $4E;<br>   ClrScr;<br>   GotoXY(3, 50);<br>   Write(#27#26#24#25' - Move; Space,Del,PgDn,Home,End,Tab - Wall; Insert - Man; PgUp - Target');<br>   GotoXY(54, 1);<br>   Write('ENTER - Start; ESC - Exit');<br>   Window(2, 2, 79, 49);<br>   TextAttr := $1F;<br>   ClrScr;<br>   Window(2, 2, 80, 49);<br>   Repeat<br>      Case ReadKey of<br>         #00: Case ReadKey of<br>            #72: If WhereY > 1 then GotoXY(WhereX, WhereY-1);<br>            #75: If WhereX > 1 then GotoXY(WhereX-1, WhereY);<br>            #77: If WhereX < 78 then GotoXY(WhereX+1, WhereY);<br>            #80: If WhereY < 48 then GotoXY(WhereX, WhereY+1);<br>            #71: {Home}<br>            Begin<br>               If WhereY > 1 then GotoXY(WhereX, WhereY-1);<br>               If Mem[$B800:WhereY*160+WhereX*2] = 32 then<br>                  Write(Wall+#8) else Write(' '#8);<br>               If (FX = WhereX) and (FY = WhereY) then FX := 0<br>            End;<br>            #83: {Del}<br>            Begin<br>               If WhereX > 1 then GotoXY(WhereX-1, WhereY);<br>               If Mem[$B800:WhereY*160+WhereX*2] = 32 then<br>                  Write(Wall+#8) else Write(' '#8);<br>               If (FX = WhereX) and (FY = WhereY) then FX := 0<br>            End;<br>            #81: {PgDn}<br>            Begin<br>               If WhereX < 78 then GotoXY(WhereX+1, WhereY);<br>               If Mem[$B800:WhereY*160+WhereX*2] = 32 then<br>                  Write(Wall+#8) else Write(' '#8);<br>               If (FX = WhereX) and (FY = WhereY) then FX := 0<br>            End;<br>            #79: {End}<br>            Begin<br>               If WhereY < 48 then GotoXY(WhereX, WhereY+1);<br>               If Mem[$B800:WhereY*160+WhereX*2] = 32 then<br>                  Write(Wall+#8) else Write(' '#8);<br>               If (FX = WhereX) and (FY = WhereY) then FX := 0<br>            End;<br>            #59: {F1 - Clr}<br>            Begin<br>               For j := 1 to 48 do<br>                  For i := 1 to 78 do<br>                  Begin<br>                     GotoXY(i, j);<br>                     Write(' '#8)<br>                  End;<br>               FX := 0<br>            End;<br>            #60: {F2 - Fill}<br>            Begin<br>               For j := 1 to 48 do<br>                  For i := 1 to 78 do<br>                  Begin<br>                     GotoXY(i, j);<br>                     Write(Wall+#8)<br>                  End;<br>               FX := 0<br>            End;<br>            #73: {PgUp}<br>               Write('X'#8);<br>            #82: {Ins}<br>            Begin<br>               i:= WhereX;<br>               j := WhereY;<br>               GotoXY(FX, FY);<br>               Write(' ');<br>               GotoXY(i, j);<br>               Write(#1#8);<br>               FX := i;<br>               FY := j<br>            End<br>         End;<br>         #09: {Tab}<br>            For Ni := 1 to 100 do<br>            Begin<br>               i := Random(78)+1;<br>               j := Random(48)+1;<br>               If Mem[$B800:j*160+i*2] <> 1 then<br>               Begin<br>                  GotoXY(i, j);<br>                  Write(Wall+#8)<br>               End<br>            End;<br>         #32: {Space}<br>         Begin<br>            If Mem[$B800:WhereY*160+WhereX*2] = 32 then<br>               Write(Wall+#8) else Write(' '#8);<br>            If (FX = WhereX) and (FY = WhereY) then FX := 0<br>         End;<br>         #13: {Enter}<br>            If FX <> 0 then Start;<br>         #27: {Esc}<br>            Break<br>      End<br>   Until False;<br>   TextMode(Co80);<br>   TextAttr := 7;<br>   ClrScr<br>End.

 Я сделал такую игрушку лет восемь назад еще на турбо бэйсике. Тоже немного помучался с этим вопросом, но нашел очень простое решение:
 - в проге забиваешь bit-массив 9х9 для всех клеток : зеруешь (обнуляешь) его; скидываешь в него положение шариков (значение 0FFh); а по команде 'двигать шарик' заполняешь весь массив, от шарика по четырем направлениям, цифрами с номером шага(сначала 1, от одного по 4-м направлениям - 2 и т.д., естественно, только в нулевые ячейки и по часовой стрелке) пока не дойдешь до позиции назначения; если дальше не заполняется значит проход закрыт; как только доходишь до места назначения, в обратном порядке 'место....3,2,1,шар', строишь массив координат прохода(динамический, поскольку
каждый раз разный, но можно и простой  
2х81, чтобы не думать  ???не мало ли ???), этот массив берешь как за исходный для изображения движения шарика. Но придется все это запрограмировать.

вот пример: 0-пустые места;S-занятые шариками;V-место назначения;H-шар который двигать.

                              S  0  0  0  0  0  V  0  S
                              0  0  0  S  0  S  S  0  0
                              0  0  0  0  S  0  0  S  0
                              0  0  0  S  0  0  0  0  0
                              0  0  0  S  0  0  0  S  0
                              0  S  0  S  0  0  0  0  S
                              0  0  H  0  0  0  0  0  0
                              0  0  0  S  0  S  0  0  0
                              0  0  0  0  0  0  0  0  0
bit-массив уже заполненный:

                              S  7  6. 7. 8. 9. V  13 S
                              7  6  5. S  9  S  S  12 11
                              6  5  4. 5  S  7  8  S  10
                              5  4  3. S  5  6  7  8  9
                              4  3  2. S  4  5  6  S  10
                              3  S  1. S  3  4  5  6  S
                              2  1  H  1  2  3  4  5  6
                              3  2  1  S  3  S  5  6  7
                              4  3  2  3  4  5  6  7  8

Точками показан искомый кратчайший путь. После 9 можно и не заполнять (это я так).
***Все это не так сложно программируется.

Сообщение отредактировано: kardinal - 02.03.03, 12:05

Так это и есть волновой алгоритм;) Даже в самом простом виде, без диагоналей (путь далеко не кратчайший)...

Цитата Shiru_Otaku, 02.03.03, 07:15:07

Так это и есть волновой алгоритм;) Даже в самом простом виде, без диагоналей (путь далеко не кратчайший)...

 Шут с ним - как это называется, я допер до этого сам и не согласен с Shiru_Otaku!!! В данной задаче это кратчайший путь!!!!!!!! Приведи пример, в котором это будет не так, тогда и поговорим!!!

Сообщение отредактировано: kardinal - 02.03.03, 12:17

Я незнаю правил Lines Если можно делать диагональные ходы - то элементарным добавлением ещё 4-х проверок на диагонали можно получать действительно кратчайший путь...

Цитата Shiru_Otaku, 03.03.03, 04:13:30

Я незнаю правил Lines

Увы, там нет ходов по диагонали.

Я делала нечто подобное для пути в лабиринте.
Идея такова:
от нужного шарика смотришь во все стороны. Где нету стенки (у меня было -1, т.е. 0 - пустой проход), там ставишь 1. Дале уже от клеток с "1" смотришь и ставишь "2" ...
(ставишь только тогда, когда в нужной клетке "0"). и т.д. - пока не достигнешь нужной клетки. А путь просчитываешь в обратном порядке.
На этом принципе по лабиринту за мной бегали монстрики :-)

Мо чего-то упустила, но основа такая.

 Ну дык у меня также.

Сообщение отредактировано: kardinal - 06.03.03, 10:10

У всех так-же:))

Народ, может хватит доказывать, что свой СТАНДАРТНЫЙ волновой вариант лучше другого.