Урок 1

Лабиринт

#Урок Лабиринт

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

Напомним, что переход в графический режим производится вызовом функции SetCoordinateSystem(), синоним – Gra_SetCoordinateSystem(). Все графические функции имеют синонимы, начинающиеся с «Gra», что облегчает поиск нужной функции на всплывающей панели подсказок. *Для рисования на полотне используются 2 инструмента: перо и кисть (pen и brush). Пером рисуют линии и фигуры, кисть используется для заливки одним цветом многоугольников, кругов или всего полотна. Для того, чтобы нарисовать чёрный квадрат, перо и кисть – оба должны быть черного цвета.*

Сначала научимся рисовать картинки, состоящие из квадратных клеток. Нарисуем вот такой прямоугольник, состоящий из 6 клеток. Выберем стандартную школьную систему координат (X,Y), размер клеток примем равной единице.

Лабиринт

Цвета клеток будем хранить в двумерном массиве map. Элементы массива будут принимать значения 1 для чёрных клеток и 0 для белых. Так чёрная клетка с координатами (x=1,y=1) соответствует элементу массива map[1,1], который принимает значение 1. Над ней находится белая клетка с координатами (x=1,y=2), которой соответствует элемент массива map[1,2], который принимает значение 0.

w=3       # ширина 
h=2       # высота 
array map[w,h]float

map[1,1]=1  # чёрная
map[1,2]=0  # белая

Вторая и третья колонки соответствуют элементам массива:

map[2,1]=0  # белая
map[2,2]=1  # чёрная

map[3,1]=1  # чёрная
map[3,2]=1  # чёрная

Более удобно исходные значения элементов массива можно присвоить так:

w=3       # ширина 
h=2       # высота 
array map[w,h]float=((1,0),(0,1),(1,1)) # карта цвета клеток

Теперь напишем скрипт, рисующий чёрные клетки.

Переходим в графический режим с координатной сеткой и размерами полотна для рисования достаточными для размещения нашего прямоугольника с запасом равным единице со всех 4-х сторон:

SetCoordinateSystem(0,0,w+2,h+2, 2,1) 

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

Рисуем цифры координат 1, 2, 3 по горизонтали и цифры 1, 2 по вертикали:

for y=1,h                # рисуем координаты клеток по вертикали
  Gra_Text(0.3,y+0.4,toString(y),12)
for x=1,w                # рисуем координаты клеток по горизонтали
  Gra_Text(x+0.4,0.5,toString(x),12)

Здесь использована встроенная графическая функция Gra_Text(), которая выводит на полотно текст. Входные параметры этой функции – левый нижний угол области выводимого текста, собственно текст и номер слоя. Функция toString() преобразует число в строковый вид.

Теперь создаём массив sq[] для хранения координат углов клеток, устанавливаем чёрный цвет кисти для заполнения чёрных клеток и создаём собственную функцию DrawSquare(), которая по координатам нижнего левого угла рисует квадрат со стороной, равной 1 и заполняет его установленным цветом кисти..

array sq[4,2]float 
SetBrushParameters(clBlack) # устанавливаем цвет кисти 

Function DrawSquare(_x, _y)
  sq[1,1]=_x
  sq[1,2]=_y
  sq[2,1]=_x+1
  sq[2,2]=_y
  sq[3,1]=_x+1
  sq[3,2]=_y+1
  sq[4,1]=_x
  sq[4,2]=_y+1
  Polygon(sq)
  Return

В нашей функции DrawSquare() используется встроенная графическая функция Polygon(). На вход этой функции подаётся массив с координатами точек. Функция последовательно соединяет отрезками все точки и замыкает контур, т.е. соединяет первую точку с последней. Всю площадь внутри контура заливает установленным цветом кисти. Цвет кисти устанавливается вызовом встроенной процедуры SetBrushParameters(), на вход которой подаётся какая-нибудь константа цвета. В нашем случае clBlack – это константа чёрного цвета и следовательно кисть будет чёрной.

Итак, всё готово, чтобы собрать вместе текст скрипта, рисующий требуемую картинку:

w=3       # ширина лабиринта
h=2       # высота лабиринта
# Массив с картой лабиринта, во внутренних скобках столбцы лабиринта, чёрные клетки - единица, белые - ноль
array map[w,h]float=((1,0),(0,1),(1,1))

SetCoordinateSystem(0,0,w+2,h+2, 2,1) # устанавливаем графический режим, рисуем координатную сетку

for y=1,h                # рисуем координаты клеток по вертикали
  Gra_Text(0.3,y+0.4,toString(y),12)
for x=1,w                # рисуем координаты клеток по горизонтали
  Gra_Text(x+0.4,0.5,toString(x),12)

array sq[4,2]float       # массив, в который будем заносить координаты углов одной клетки 
SetBrushParameters(clBlack) # устанавливаем цвет кисти для зарисовки чёрных клеток

for y=1,h               # цикл по строкам 
  for x=1,w             # цикл по столбцам
    if map[x,y] > 0
      DrawSquare(x,y)   # собственно рисуем чёрную клетку с координатами (x,y)
stop

Function DrawSquare(_x, _y)
  sq[1,1]=_x
  sq[1,2]=_y
  sq[2,1]=_x+1
  sq[2,2]=_y
  sq[3,1]=_x+1
  sq[3,2]=_y+1
  sq[4,1]=_x
  sq[4,2]=_y+1
  Polygon(sq)
  return

stop

Выполните скрипт в шаговом режиме.

Лабиринт

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

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

w=18        # ширина лабиринта
h=14        # высота лабиринта
# Массив с картой лабиринта, во внутренних скобках столбцы лабиринта, чёрные клетки - единица, белые - ноль
array map[w,h]float=((1,1,1,1,1,1,1,1,1,1,1,1,1,1),(1,0,1,0,1,0,0,0,0,1,0,1,0,1),(1,0,0,0,1,0,1,0,0,1,0,0,0,1),(1,1,1,0,1,0,1,0,1,1,0,1,0,1),(1,0,0,0,0,0,1,0,0,0,0,1,1,1),(1,0,1,1,1,1,1,1,0,1,1,1,1,1),(1,0,0,0,0,0,0,0,0,1,0,0,0,1),(1,0,0,1,1,1,0,1,1,1,0,1,0,1),(1,1,0,1,0,0,0,0,0,1,0,1,0,1),(1,0,0,1,0,1,1,1,0,1,0,1,0,1),(1,0,0,1,0,1,0,1,0,1,0,1,1,1),(1,1,1,1,0,0,0,1,0,0,0,1,0,1),(1,0,0,0,0,1,0,1,0,1,1,1,0,1),(1,0,1,1,0,1,0,1,0,0,0,0,0,1),(1,0,0,1,0,1,0,1,0,1,0,1,0,1),(1,0,0,1,1,1,0,1,1,1,0,1,0,1),(1,0,0,0,0,1,0,1,0,0,0,1,0,1),(1,1,1,1,1,1,1,1,1,0,1,1,1,1))

Запустим получившийся скрипт в автоматическом режиме

Лабиринт

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

Небольшое отступление о свойствах полотна и графических функциях. В нашей системе полотно имеет 2 слоя: нижний (первый) и верхний (второй). Графические функции, как и многие другие, имеют необязательные входные параметры. Например, функция рисования круга Gra_Circle() имеет обязательные параметры (координаты центра круга и радиус круга) и необязательный параметр – номер слоя. Вызов функции может выглядеть так: Gra_Circle(x,y,r) или так: Gra_Circle(x,y,r,2). В первом случае отсутствует параметр «номер слоя». В таком случае будет использовано значение параметра по умолчанию. Во всех графических функциях номер слоя по умолчанию равен 1 – это номер, соответствующий нижнему слою. Если мы хотим рисовать на верхнем слое, то при вызове функции номер слоя «2» нужно указывать явно, как во втором случае. Теперь поясним, чем может быть полезно использование двух слоёв полотна. Мы нарисовали лабиринт на нижнем слое. Теперь мы хотим нарисовать в лабиринте зелёный кружок, который визуализирует положение путешественника по лабиринту. Если мы нарисуем кружок на нижнем слое, то при перемещении путешественника нам придется перерисовывать лабиринт или по крайней мере, одну клетку, на которой ранее был нарисован кружок. Более простой вариант – рисовать кружок на втором слое, предварительно очистив его функцией Gra_Clean(). Кроме того, каждый слой имеет собственное перо и кисть, что позволяет не менять их цвет в процессе перемещения путешественника по лабиринту.

Установим цвет кисти и пера для второго слоя. Зададим радиус круга, координаты путешественника. Очистим второй слой и нарисуем на втором слое кружок в клетке с заданными координатами.

Gra_SetBrushParameters(clLime,0,2)  # устанавливаем цвет кисти (зелёный) для второго (верхнего) слоя полотна
Gra_SetPenParameters(1,clLime,0,2)  # устанавливаем толщину и цвет пера для второго (верхного) слоя полотна
r=0.3                           # радиус круга который будем рисовать в текущей клетке лабиринта   
x1=7                            # x1 и y1 - исходные координаты клетки в лабиринте
y1=6
Gra_Clean(2)                      # очищаем второй слой   
Gra_Circle(x1+0.5,y1+0.5,r,2)     # рисуем на верхнем слое зелёный кружок 

Вставьте этот текст в скрипт после отрисовки лабиринта и стартуйте.

Лабиринт

Сейчас поучимся перемещать путешественника. Будем двигать его вверх да самого края лабиринта. Вместо строк:

Gra_Clean(2)                      # очищаем второй слой   
Gra_Circle(x1+0.5,y1+0.5,r,2)     # рисуем на верхнем слое зелёный кружок 

вставим цикл:

repeat
  y1=y1+1
  Gra_Clean(2)                      # очищаем второй слой   
  Gra_Circle(x1+0.5,y1+0.5,r,2)     # рисуем на верхнем слое зелёный кружок 
  breakif y1>=h

В рабочем режиме ставим точку остановки на строке repeat (клик по цифре слева от repeat). Стартуем скрипт. После достижения точки остановки продолжаем выполнение скрипта в шаговом режиме. Шаговый режим позволяет увидеть, что происходит при выполнении каждой строки скрипта. Видим, что путешественник шагает вверх напролом.

Лабиринт

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

Цикл перемещений может выглядеть так:

repeat
  if map[x1+1,y1]=0
    x1=x1+1                # шаг вправо
  else
    if map[x1-1,y1]=0
      x1=x1-1              # шаг влево
    else
      if map[x1,y1+1]=0
        y1=y1+1            # шаг вверх
      else
        if map[x1,y1-1]=0
          y1=y1-1          # шаг вниз 
  
  Gra_Clean(2)                      # очищаем второй слой   
  Gra_Circle(x1+0.5,y1+0.5,r,2)     # рисуем на верхнем слое зелёный кружок 
  sleep(0.5)
  breakif (x1=1)OR(y1=1)OR(x1=w)OR(y1=h)

Стартуем скрипт с этими исправлениями и обнаруживаем, что путешественник шагает вправо – влево без остановки. Кстати, остановить выполнение скрипта можно клавишей «Pause». Что же делать? Давайте отмечать посещённые клетки на карте лабиринта в массиве map[] и зарисовывать их серым цветом. Для этого после строки breakif вставим:

  map[x1,y1]=1
  Gra_SetBrushParameters(clGray)
  DrawSquare(x1,y1)                 

Стартуем скрипт. Видим, путешественник уткнулся с тупик.

Лабиринт

Дальнейшее усовершенствование алгоритма видится в том, чтобы по ходу путешественника запоминать неиспользованные ответвления лабиринта , к которым можно будет вернуться в случае попадания в тупик. Для запоминания координат клеток-ответвлений создадим специальный массив stack[1000,2]float и переменную stackPos, в которой будем хранить количество помещённых в массив координат. Для упрощения работы с массивом создадим 2 функции: stackPush(), которая будет заносить в массив одну пару координат клеток и stackPop(), которая будет извлекать из массива последнюю внесённую пару координат. Заметим, что такой подход к хранению и извлечению данных широко используется в программировании и называется «Стек». Это название взято, вероятно, из-за схожести данного алгоритма с правилом работы с пачкой листов бумаги, при котором новые листы кладутся сверху на пачку, а когда необходимо извлечь лист из пачки – берётся самый верхний лист. Особенность стека в его простоте: последние положенные в стек данные извлекаются первым, никаких перетасовок данных на происходит. В названиях функций используем английскую мнемонику: Push – впихнуть и Pop – вытащить.

Вот эти функции:

Function stackPush(_x, _y) # функция заносит в стек координаты клеток
  if map[_x, _y] <> 0  # не заносим в стек координаты чёрных и посещённых клеток
    return
  stackPos = stackPos + 1
  stack[stackPos, 1] = _x
  stack[stackPos, 2] = _y
  return
Function stackPop() # функция извлекает из стека координаты клеток в виде двумерного массива
  array a[2]float
  a[1] = stack[stackPos, 1]
  a[2] = stack[stackPos, 2]
  stackPos = stackPos - 1
  return a

Функция stackPush() имеет два входных параметра – координаты клетки. В теле функции проверяется, а не чёрная ли это клетка или не посещалась ли она уже. Если нет, то координаты заносятся в стек а счетчик стека наращивается на единицу. Возвращаемого значения функция не предоставляет. Функция stackPop() не имеет входных параметров. Функция возвращает одномерный массив с координатами клетки, которые извлекаются из стека. Счетчик стека уменьшается на 1.

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

  stackPush(x1+1, y1)               
  stackPush(x1-1, y1)
  stackPush(x1, y1+1)
  stackPush(x1, y1-1)

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

  coordinates = stackPop()    # достаём из стека координаты клетки
  x1 = coordinates[1]
  y1 = coordinates[2]  

Итак, всё необходимое у нас есть. Собираем все кусочки скриптов. Вставляем проверку, не пуст ли стек (stackPos = 0) и если пуст, то выдаём на экран сообщение и прерываем путешествие. Проверяем также, а не вышли ли мы за границы лабиринта. Если вышли, то выдаём на экран соответствующее сообщение и так же прерываем путешествие. Итоговый скрипт можно подсмотреть в файле …\Vasilisa\УРОКИ\4 Лабиринт\“04 лабиринт.txt”.

Стартуйте скрипт. Вы должны увидеть такую картину.

Лабиринт

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