Урок 11 – Обучалка C++Builder
Настоящий программист, как впрочем, и настоящий математик непременно являются поклонниками массивов. Если вы осилили десять уроков, то можно уже с уверенностью говорить о том, что вы никогда не забросите программирование. А значит пришла пора заняться многомерными массивами.
Двумерный массив – это определенный набор однотипных данных, упорядоченных в нескольких строках и нескольких столбцах. Каждый элемент двумерного массива носит общее имя массива и для его однозначной идентификации имеет два индекса, определяющие его положение в массиве – номер строки и номер столбца. Например, a[n][m].
Как и любая переменная, а здесь мы имеем дело с целым набором переменных, массив перед использованием необходимо объявить. Сделать это можно, например, так: int a[99][9]. Это будет означать, что вы зарезервировали область памяти под массив a на 100 строк и 10 столбцов для тысячи целых чисел.
Говорят, что размерность такого массива будет составлять 100х10. Обратите внимание, нумерация индексов элементом массива начинается с нуля. Двумерный массив имеет и другое название – матрица. Матрица является квадратной, если в ней число строк и столбцов совпадает.
Примером квадратной матрицы является удивительный квадрат, который открыли три тысячи лет назад китайские ученые. Размер такого квадрата 3х3, в него входят девять цифр привычной нам десятичной системы счисления кроме нуля.
А замечателен он тем, что сумма в нем в любых строках, столбцах и обеих диагоналях равна одному и тому же числу, причем ни в одной ячейке цифры не повторяются! Подробнее остановимся на квадратных матрицах в конце урока.
Сформируем двумерный массив размерностью 10х20 из двухсот целых случайных чисел с помощью двойного цикла «Для». Внутренний цикл является вложенным во внешний.
Измените размеры стартовой формы так, чтобы ее высота была чуть меньше высоты экрана, а ширина составила примерно четвертую часть от ширины экрана. На этой форме нового приложения разместите два объекта: электронную кнопку Button1 и поле вывода текста Label1.
Свойству Caption компонента Label1 предварительно придайте значение пустого множества. В функции обработки Button1Click разместите программный код:
int a[10][20], i, j; //объявление переменных
randomize(); //рандомизация
for (i=0; iCaption + a[i][j] + ” “; //вывод матрицы на экран
}
Label1->Caption = Label1->Caption + ”
“; //переход в следующую строку
}
На электронной кнопке Button1 поместите надпись «Матрица». Запустите проект приложения, кликните мышью по этой кнопке. На поверхность формы выплеснется матрица, состоящая из десяти строк и двадцати столбцов. В каждую ячейку матрицы помещается случайное целое однозначное число. Кликните по кнопке еще раз – появится вторая матрица.
Для того чтобы отделить эти матрицы друг от друга добавьте последней строкой, после фигурной скобочки «}», еще одну строку «переход в следующую строку». Посмотрите, что из этого получилось. Если вам непонятно, что делает какая-либо строка, то закомментируйте ее и запустите приложение на выполнение.
Иногда полезно удалить часть строки, чтобы уяснить, как работает эта строка.
Для того чтобы очистить форму после выброса нескольких матриц разместите на ней еще одну электронную кнопку Button2. Снабдите ее надписью «Очистить». В функцию обработки Button2Click впишите строку, которая в поле вывода текста Label1 поместит пустое множество, тем самым приготовит форму для вывода новой матрицы:
Label1->Caption =””; //очистка поля вывода текста
Проверьте проект приложения в работе. Откомпилируйте программу.
А теперь сформируем целочисленный двумерный массив 10х10, элементы которого будут взяты из диапазона от -50 до 50 и будут располагаться в этом массиве случайным образом.
Пусть программа подсчитает число отрицательных элементов в этой квадратной матрице и вычислит сумму всех ее элементов. Приложение можно построить на базе предыдущего приложения.
Алгоритм решения поставленной задачи в среде C++ Builder может выглядеть, например, так:
int a[10][10], i, j, n, s; //объявление переменных
randomize(); //рандомизация
n = 0, s = 0; //обнуление переменных
for (i=0; iCaption + a[i][j] + ” “; //вывод матрицы на экран
If (a[i][j]
s = s + a[i][j]; //суммирование всех элементов
}
Label1->Caption = Label1->Caption + ”
“;
}
Label1->Caption = Label1->Caption + “Отрицательных ” + n + ”
“;
Label1->Caption = Label1->Caption + “Сумма = ” + s + ”
” + ”
“;
Для проверки правильности сформированной квадратной матрицы и ее последующей обработки целесообразно временно ее размерность уменьшить до 3х3. Теперь вы быстро сможете протестировать программу.
До сих пор размерность матрицы, а, следовательно, число ее элементов задавал программист. Сделаем так, что бы пользователь мог сам задавать размерность матрицы.
Воспользуемся компонентом поле ввода-редактирования строки символов Edit (Редактор), который можно извлечь из палитры компонентов во вкладке Standard. Самым значимым свойством компонента Edit является свойство Text (Текст), которое содержит вводимую строку символов.
Для решения поставленной задачи целесообразно начать новый проект. На стартовой форме разместите компоненты: Label1, Button1, Edit1 и Edit2. Причем первый компонент расположите в верхнем левом углу формы, а остальные три компонента в правой стороне формы.
Свойству Text компонентов Edit1 и Edit2 придайте произвольные начальные значения, например, «5» и «10». Свойству Caption компонента Label1 не забудьте придать значение пустого множества. Затем приступайте к написанию функции обработки Button1Click:
int n = StrToInt(Edit1->Text); //число строк
if (n > 30) return; //ограничение числа строк
int m = StrToInt(Edit2->Text); //число столбцов
if (m > 30) return; //ограничение числа столбцов
int i, j, a[30][30];
randomize();
Label1->Caption = “”; //очистка поля вывода матрицы
for (i=0; iCaption + ” ” + a[i][j];
}
Label1->Caption = Label1->Caption + ”
“;
}
Первая и третья строки программного кода берут размерность матрицы из полей ввода-редактирования текста. Здесь используется функция преобразования StrToInt, которая позволяет переменную строкового типа преобразовать в переменную целого типа.
Протестируйте программу, создайте исполняемый EXE-файл и проверьте его работоспособность.
А теперь постройте программу, которая сформирует матрицу размерностью 4х5 из случайных чисел в диапазоне от одного до тысячи и отыщет максимальный элемент в этой матрице. Алгоритм решения поставленной задачи может выглядеть так:
int i, j, max, a[4][5];
randomize();
max = 0;
for (i=0; iCaption + a[i][j] + ” “;
}
Label1->Caption = Label1->Caption + ”
“;
}
for (i=0; iCaption = Label1->Caption + “Максимальный элемент ” + max + ”
“;
На этом можно завершить первое знакомство с матрицами. Если же вы заинтересовались этим разделом программирования, то рассмотрите ниже приведенные закономерности в квадратной матрице.
Двумерный массив в котором число строк совпадает с числом столбцов называют квадратной матрицей. Рассмотрим закономерности определяющие характерное расположение элементов в квадратной матрице.
Очевидно, что для элемента расположенного на главной диагонали номер его строки равен номеру его столбца i = j. Для элемента расположенного на побочной диагонали справедливо i + j = n + 1, где n — размер квадратной матрицы.
Проверьте справедливость этого равенства.
Для элементов расположенных выше главной диагонали справедливо утверждение i j. Выше побочной диагонали — i + j n + 1.
Если рассматривать положение элемента в квадратной матрице относительно обеих диагоналей, то он может находиться в одной из четвертей при условии:
1 четверть — (i
2 четверть — (i n + 1)
3 четверть — (i > j) и (i + j > n + 1)
4 четверть — (i > j) и (i + j
Теперь пришло время самостоятельно выполнить следующие задания:
1. Постройте программу, которая сформирует матрицу размерностью n = 8 из случайных чисел в диапазоне от нуля до девяти и вычислит сумму элементов, расположенных на главной диагонали.
2. Постройте программу, которая сформирует матрицу размерностью n = 10 из случайных чисел в диапазоне от нуля до девяти и подсчитает число двоек и пятерок, упавших на побочную диагональ.
3. Постройте программу, которая сформирует матрицу размерностью n = 12 из случайных чисел в диапазоне от нуля до девяти и вычислит сумму элементов, расположенных ниже побочной диагонали.
4. Постройте программу, которая сформирует матрицу размерностью n = 15 из случайных чисел в диапазоне от нуля до девяти и вычислит сумму элементов, расположенных во второй четверти.
Источник: http://bigcamagan.ru/urok-11/
Урок “Программирование линейных алгоритмов на C++BUILDER”
double cabs(struct complex z)
struct complex {double x, y;};
math.h
cabsl
Модуль комплексного числа z
long double cabsl(struct _complexl z)
struct complex { long double x, y; };
math.h
Ceil
Округление вверх , наименьшее целое не меньше х
double ceil(double x);
math.h
Ceil
Округление вверх , наименьшее целое не меньше Х
int Ceil(Extended X);
Math.hpp
Ceil
Округление вверх , наименьшее целое не меньше х
long double ceill(long double x);
math.h
Div
Целочисленное деление numer/denom
typedef struct {
int quot; // ÷частное
int rem; // – остаток
} div_t;
div_t div(int numer, int denom)
math.h
Exp
Экспонента
double exp(double x);
math.h
expl
Экспонента
long double expl(long double x);
math.h
fabs
Абсолютное значение
double fabs(double x);
math.h
fabsl
Абсолютное значение
long double fabsl(long double x);
math.h
floor
Округление вверх, наименьшее целое не меньше х
double floor(double x);
math.h
Floor
Округление вверх , наименьшее целое не меньше Х
int Floor(Extended X);
Math.hpp
floorl
Округление вверх , наименьшее целое не меньше х
long double floorl(long double x);
math.h
fmod
Остаток от деления x/y
double fmod(double x, double y)
math.h
fmodl
Остаток от деления x/y
long double fmodl(long double x, long double y)
math.h
frexp
Разделяет х на мантиссу (возвращает) и степень exponent
double frexp(double x, int *exponent);
math.h
Frexp
Разделяет X на мантиссу Mantissa (возвращает) и степень Exponent
void Frexp(Extended X, Extended &Mantissa, int &Exponent);
Math.hpp
frexp
Разделяет х на мантиссу (возвращает) и степень exponent
long double frexpl(long double x, int *exponent)
math.h
IntPower
Возводит Base в целую степень Exponent
Extended IntPower(Extended Base, int Exponent);
Math.hpp
Labs
Абсолютное значение
long labs(long int x);
stdlib.h
ldiv_t
Целочисленное деление numer/denom; quot – результат
rem – остаток
typedef struct {
long int quot; // целое
long int rem; // остаток
} ldiv_t
ldiv_t ldiv(long int numer, long int denom);
math.h stdlib.h
Log
Натуральный логарифм
double log(double x);
math.h
LnXP1
Натуральный логарифм (Х+1)
Extended LnXP1(Extended X);
Math.hpp
Log2
Логарифм по основанию 2
Extended Log2(Extended X)
Math.hpp
log10
Десятичный логарифм
double log10(double x)
math.h
Log10
Десятичный логарифм
Extended Log10(Extended X)
Math.hpp
log10l
Десятичный логарифм
long double log10l(long double x)
math.h
Logl
Натуральный логарифм
long double logl(long double x)
math.h
LogN
Логарифм Х по основанию Base
Extended LogN(Extended Base, Extended X)
Math.hpp
_lrotl
Циклический сдвиг влево valнаcountбитов
unsigned long _lrotl(unsigned long val, int count)
stdlib.h
_rotr
Циклический сдвиг вправо valнаcountбитов
unsigned long _lrotr(unsigned long val, int count)
stdlib.h
Max
Макрос возвращает максимальное значение из a и b любых типов
max(a, b);
stdlib.h
Min
Макрос возвращает минимальное значение из a и b любых типов
min(a, b)
stdlib.h
modf
Разделяет х на целую часть ipart и возвращает дробную часть.
double modf(double x, double *ipart)
math.h
modfl
Разделяет х на целую часть ipart и возвращает дробную часть.
long double modfl(long double x, long double *ipart)
math.h
Poly
Полином от х степени degreeкоэффициентами coeffs
double poly(double x, int n, double c[ ]);
math.h
Poly
Полином от X степени Coefficients_Sizeкоэффициентами Coefficients
Extended Poly(Extended X, const double * Coefficients, const int Coefficients_Size);
Math.hpp
polyl
Полином от от х степени degreeкоэффициентами coeffs
long double polyl(long double x, int degree, long double coeffs[]);
math.h
Pow
xy
math.h
Power
Возводит Base в степень Exponent
Extended Power(Extended Base, Extended Exponent);
Math.hpp
powl
xy
long double powl(long double x, long double y);
math.h
_lrotl
Циклический сдвиг влево valueнаcountбитов
unsigned short _rotl(unsigned short value, int count);
stdlib.h
_rotr
Циклический сдвиг вправо valueнаcountбитов
unsigned short _rotr( unsigned short value, int count);
stdlib.h
Sqrt
Корень квадратный
double sqrt(double x);
math.h
Sqrtl
Корень квадратный
long double sqrtl(long double x);
math.h
acos
Функция арккосинуса. Значение аргумента должно находиться в диапазоне от -1 до +1.
double acos(double x);
math.h, cmath
Функция
Описание
Синтаксис
Файл
Asin
Функция арксинуса. Значение аргумента должно находиться в диапазоне от -1 до +1.
double asin(double x);
math.h, cmath
atan
Функция арктангенса.
double atan(double x);
math.h, cmath
atan2
Функция арктангенса от значения y/x.
double atan2(double y,
double x);
math.h, cmath
Cos
Функция косинуса. Аргумент задается в радианах.
double cos(double x);
math.h, cmath
frexp
Разбивает число с плавающей точкой value на нормализованную мантиссу и целую часть как степень числа 2. Целочисленная степень записывается в область памяти, на которую указывает exp, а мантисса используется как значение, которое возвращает функция.
double frexp(double value, int *exp);
math.h, cmath
hypot
Вычисляет гипотенузу z прямоугольного треугольника по значениям катетов x, y:
double hypot(double x, double y);
math.h, cmath
pow10
Возвращает значение 10p
double pow10(int p);
math.h, cmath
Sin
Функция синуса. Угол задается в радианах.
double sin(double x);
math.h
Sinh
Возвращает значение гиперболического синуса для x.
double sinh(double x);
math.h
Tan
Функция тангенса. Угол задается в радианах.
double tan(double x);
math.h
Tanh
Возвращает значение гиперболического тангенса для x.
double tanh(double x);
math.h
Свойства
Параметры и значения
Caption
Программирование линейных алгоритмов
Width
551
Height
317
Left
196
Top
108
BorderIcon.biMinimize
False
BorderIcon.biMaximize
False
Наименование
Тип
Действия
StrToFloat(St)
float
преобразует строку St в вещественное число
StrToInt(St)
int
преобразует строку St в целое число
FloatToStr(W)
преобразует вещественное число W в строку символов
FormatFloat(формат, W)
преобразует вещественное число W в строку
IntToStr(W)
преобразует целое число W в строку символов
FloatToStrF(W, формат, n1, n2)
вещественное число W в строку символов под управлением формата:
ffFixed
фиксированное положение разделителя целой и дробной частей, n1 – общее количество цифр числа, n2 – количество цифр в дробной части, причем число округляется с учетом первой отбрасываемой цифры
fFfExponent
n1 задает общее количество цифр мантиссы, n2 – количество цифр порядка XX (число округляется)
ffGeneral
– универсальный формат, использующий наиболее удобную для чтения форму представления вещественного числа; соответствует формату ffFixed, если количество цифр в целой части n1, а само число больше 0,00001, в противном случае соответствует формату ffExponent.
№
Источник: https://infourok.ru/urok-programmirovanie-lineynih-algoritmov-na-cbuilder-1914846-page8.html
Урок 1. Введение
В этом уроке я подробно расскажу о Dagger и его возможностях. Мы разберем, что такое Component и Module, подключим Dagger к проекту, и сделаем несколько простых примеров
Зачем нужен Dagger
Если вы хотите снизить зависимость объектов друг от друга и упростить написание тестов для вашего кода, то вам подойдет паттерн Dependency Injection. А Dagger – это библиотека, которая поможет в реализации этого паттерна. В этом мини-курсе я опишу использование библиотеки Dagger версии 2 (далее по тексту даггер).
Плюсы даггера в сравнении с другими библиотеками: – генерирует код несложный для понимания и отладки- проверяет зависимости на этапе компиляции
– не создает проблем при использовании proguard
Сразу скажу, что тема нетривиальная и у вас могут возникать вопросы типа “а что будет, если сделать так?”. Все случаи я рассмотреть не могу, поэтому очень рекомендую вам создавать примеры и на них проверять как все это работает в том или ином случае. Мне практика очень сильно помогла лучше понять теорию.
Чтобы понять, зачем нам может понадобиться Dependency Injection и даггер, давайте рассмотрим небольшой абстрактный пример, в котором смоделируем ситуацию, когда создание одного объекта может повлечь за собой создание еще нескольких.
Пусть в нашем приложении есть некая MainActivity и, в соответствии с паттерном MVP, для нее есть презентер. Презентеру для работы нужны будут некие ItemController и DataController. Т.е.
нам надо будет создать два этих объекта перед тем, как создать презентер. Но для создания двух этих объектов нам, в свою очередь, нужны объекты ApiService и SharedPreferences.
А для создания ApiService нужны RestAdapter, RestAdapter.Builder, OkHttpClient и Cache.
В обычной реализации это может выглядеть так:
public class MainActivity extends Activity { MainActivityPresenter activityPresenter; @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.activity_main); File cacheDirectory = new File(“some path”); Cache cache = new HttpResponseCache(cacheDirectory, 50 * 1024 * 1024); OkHttpClient httpClient = new OkHttpClient(); httpClient.setCache(cache); RestAdapter.Builder builder = new RestAdapter.Builder(); builder.setClient(new OkClient(httpClient)); RestAdapter restAdapter = builder.build(); ApiService apiService = restAdapter.create(ApiService.class); ItemController itemController = new ItemController(apiService); SharedPreferences preference = getSharedPreferences(“item_prefs”, MODE_PRIVATE); DataController dataController = new DataController(preference); activityPresenter = new MainActivityPresenter(this, itemController, dataController); } }
В MainActivity мы создаем кучу объектов, чтобы по итогу получить один презентер. Нам в этом примере не важно, какие именно объекты создаются. Главное – это сколько кода может потребоваться написать в MainActivity, чтобы получить результат.
Если мы применим паттерн Dependency Injection и используем даггер, то код в Activity будет выглядеть так:
public class MainActivity extends Activity { MainActivityPresenter activityPresenter; @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); activityPresenter = App.getComponent().getPresenter(); } }
Разумеется, код создания объектов никуда не исчез. Но он вынесен из Activity в отдельные классы, к которым даггер имеет доступ. В итоге мы просто вызываем метод getPresenter чтобы получить объект MainActivityPresenter. А даггер уже сам создаст этот объект и всю необходимую для него иерархию объектов.
То же самое мы могли бы сделать и без даггера, простым переносом кода создания объектов в метод типа MainActivityPresenter.createInstance(). Но если у нас есть другой presenter, которому частично нужны те же объекты, в его методе createInstance нам придется дублировать код создания некоторых объектов.
При использовании даггера, код создания необходимого нам объекта будет существовать только в одном месте и в одном экземпляре, и даггер использует этот код везде, где потребуется создать объект.
Теория
Теперь давайте смотреть, как работает даггер изнутри.
Возьмем все тот же пример с Activity и Presenter. Т.е. когда Activity для своих нужд создает объект Presenter. Обычая схема создания будет выглядеть так:
Activity > Presenter
Т.е. Activity создает Presenter самостоятельно
При использовании даггера схема будет выглядеть так:
Activity -> Component -> Module -> Presenter
Activity обращается к компоненту, компонент с помощью модулей создает Presenter и возвращает его в Activity.
Модули и компоненты – это два ключевых понятия даггера.
Модули – это просто классы, куда мы помещаем код создания объектов. И обычно каждый модуль включает в себя объекты близкие по смыслу. Например:
Модуль ItemModule будет содержать в себе код создания объектов, связанных с пользователями, т.е. что-нибудь типа Item и ItemController.
Модуль NetworkModule – объекты OkHttpClient и ApiService.
Модуль StorageModule – объекты DataController и SharedPreferences
Компонент – это посредник между Activity и модулем. Когда Activity нужен какой-либо объект, она сообщает об этом компоненту. Компонент знает, какой модуль умеет создавать такой объект, просит модуль создать объект и передает его в Activity. При этом компонент может использовать другие модули, чтобы создать всю иерархию объектов, необходимую для создания искомого объекта.
Процесс работы даггера можно сравнить с обедом в McDonalds. Т.е. по аналогии со схемой даггера:
Activity -> Component -> Module -> Presenter
схема McDonalds выглядит так:
Клиент -> Кассир -> Производственная линия -> Заказ (Бигмак/Картошка/Кола)
Рассмотрим подробнее шаги этих схем:
| McDonalds | Даггер |
| Клиент определился, что его заказ будет состоять из бигмака, картошки и колы, и он говорит об этом кассиру | Activity сообщает компоненту, что ему понадобится Presenter |
| Кассир ходит по производственной линии и собирает заказ: берет бигмак, наливает колу, насыпает картошку | Компонент использует модули, чтобы создать все необходимые объекты, которые понадобятся для создания Presenter |
| Кассир комплектует заказ в пакет или на поднос и выдает его клиенту | Компонент в итоге получает от модулей требуемый объект Presenter и отдает его Activity |
Практика
Теперь на простом примере посмотрим, как создавать модули и компоненты, и как с их помощью Activity будет получать требуемые объекты.
Подключение даггера к проекту
Создайте новый проект. Чтобы использовать даггер, добавьте в раздел dependencies файла build.gradle вашего модуля:
Источник: https://startandroid.ru/ru/16-course/dagger2/424-urok-1.html
Разработать часы реального времени в среде программирования Algorithm Builder
Содержание
Задание: разработать часы реального времени на базе микроконтроллера AT90S8515. Время отображается с помощью четырех восьмисегментных индикаторов, управление осуществляется с помощью клавиатуры (3х4 – 12 кнопок). Программирование и прошивка МК осуществляется с помощью приложения Algorithm Builder.
Задачи устройства: при подаче питания на индикаторе отображается 00 часов 00 минут и часы начинают “идти”. При этом должна мигать точка второго разряда индикатора с периодом 1 сек (0.5с горит, 0.5с не горит).
При нажатии кнопки “*” включается режим ввода времени, при котором последовательно задаются часы и минуты и после ввода последней цифры начинается ход часов.
При вводе времени должна осуществляться проверка на некорректный ввод (например, при вводе первой цифры можно ввести только “0”, “1” или “2” остальные кнопки должны игнорироваться).
Рисунок 1 – Принципиальная электрическая схема блока клавиатуры и индикации.
1. Описание принципиальной схемы
На рисунке представлена принципиальная электрическая схема часов. Микроконтроллер является основной и единственной микросхемой, используемой в данной разработке. Для задания тактовой частоты контроллера используется кварцевый резонатор на 8 МГц. В качестве устройства отображения использованы четыре индикатора красного цвета свечения с общим анодом, каждый индикатор содержит 8 сегментов.
Индикация текущего времени осуществляется динамически, в данный конкретный момент времени отображается лишь одна цифра, что позволяет значительно снизить аппаратные затраты. Аноды каждой из четырех цифр являются раздельными, что позволяет в данный момент времени подключить к источнику питания только один анод и отобразить одну цифру.
Для этого часы имеют четыре транзисторных ключа. Ключи управляются микроконтроллером, причем соответствующий ключ открыт, если на выводе контроллера присутствует логический ноль. Одноименные сегменты всех четырех цифр соединены вместе и через токоограничивающие резисторы подключены к выводам порта “А” (выводы PА.0 … PА.7).
Управляющая программа один за другим подключает разряды индикатора к источнику питания и одновременно на соответствующие выводы порта “А” выставляется код отображаемой цифры. Поскольку сканирование индикатора происходит очень быстро, мерцание цифр становится незаметным.
Как видно из схемы, линии сканирования клавиатуры и индикации общие, что позволяет уменьшить число используемых выводов. Питаются часы от стабилизированного источника питания напряжением 5В.
Сразу после включения часов программа разрешает прерывания, настраивает порты контроллера соответствующим образом и устанавливает указатель стека на старшие адреса внутренней памяти данных. Далее программа переводит устройство в режим часов и запускает цикл сканирования клавиатуры, индикатора и цикл счета времени. Основой программы является обработчик прерываний от таймера.
2. Описание алгоритма программы
Часы реального времени организованы с использованием прерываний по таймеру 0, который тактируется системной частотой поделенной на 256.
Таймер предварительно загружается числом 100, что задает период генерации прерываний по переполнению таймера каждые 5 мс, обеспечивая высокую точность хода часов, при условии использования качественного кварцевого резонатора.
При использовании кварцевого резонатора 8 МГц длительность цикла инструкции равна 0.125 мкс. С учетом этого, при записи числа n в регистр таймера 0 TCNT0 период его переполнения определяется по выражению:
(256-n)*256*0,125 мкс
Таким образом, запись числа 100 обеспечит период переполнения 5мс с высокой для счета реального времени точностью:
(256-100)*256*0,125*=4,992мс.
Всю программу можно разбить на несколько частей – это основная программа и подпрограммы прерывания по переполнению таймера/счетчика, счета времени, вывода на индикацию, сканирования клавиатуры и режимов ввода времени.
В основной программе настраивается МК и ожидается нажатие клавиши, если клавиша нажата, то определяется ее код и происходит переход к одной из подпрограмм ввода, где анализируется какая цифра вводится в данный момент и корректность введенной цифры.
Помимо этого, каждые 5мс происходит вызов подпрограммы таймера/счетчика, где наращивается счетчик срабатываний (когда его значение станет равным 200, то это значит, что прошла 1сек) и вызываются подпрограммы счета времени, вывода на индикацию и сканирования клавиатуры.
2.1. Использование ресурсов
Использование периферийных устройств:
Таймер/счетчик0 – счетчик импульсов с периодом 5мс;
7 линий порта D – подключение клавиатуры 3х4 и управление анодами цифровых индикаторов;
8 линий порта A – сегментные линии индикаторов;
Используемые регистры:
R0 – используется при работе с таблицей данных, в нем содержится считанное значение из таблицы данных по адресу Z;
R1 – число секунд;
R2 – число минут;
R3 – число часов;
R4 – выводится на первый индикатор;
R5 – выводится на второй индикатор;
R6 – выводится на 3-й индикатор;
R7 – выводится на 4-й индикатор;
R8 – номер индикатора на который в данный момент будет выводиться информация;
R9 – счетчик срабатывания таймера;
R10, R11, R12 – используются в подпрограмме для сканирования клавиатуры;
R13, R14 – дребезг при нажатии или отжатии кнопки;
R15 – счетчик блокировки;
R18 – вспомогательный регистр, для разделения десятков и единиц.
2.2. Основная программа
При подаче питания и выполнении условий сброса выполняется процедура сброса (Reset) для инициализации системных устройств. Линии портов настраиваются на нужные уровни. Порт А необходимо настроить на выход, старшую тетраду порта D на выход и младшую на вход. Старшая тетрада порта D используется и для реализации индикации. Т.
е. подавая на один из этих выходов логический “0” сканируется клавиатура и одновременно зажигается нужный индикатор. Далее обнуляются используемые в программе регистры или заносятся в них нужные значения. Настраивается таймер, и заносятся нужные значения в регистры управления МК.
Прерывание по переполнению таймера становится активным после разрешения глобальных прерываний. Далее программа ждет нажатия клавиши и если клавиша нажата, то переходит к обработке подпрограммы соответствующей данному нажатию. Реализовать распознавание нажатия клавиши удобно с помощью 16-разрядного регистра, т.к.
клавиш 12, то будет использоваться 12 его младших разрядов.
Инициализация стека – это запись старшего адреса ОЗУ ($25F) в указатель стека SP.
Настройка таймера: запись числа $04 в регистр управления таймером TCCR0, запись числа 100 ($64) в таймер TCNT0 чтобы он переполнился через 5мс, запись числа $02 в регистр TIMSK (разрешение прерывания по переполнению таймера 0).
Далее заносится 1 в бит I (разрешение глобального прерывания).
2.3. Режимы работы устройства
Работу устройства можно разделить на 5 режимов:
Режим 0 – обычный ход часов, все разряды горят без мигания.
Режим 1 – мигает первый разряд, ожидается ввод часов
Режим 2 – мигает второй разряд, ожидается ввод часов
Режим 3 – мигает третий разряд, ожидается ввод минут
Режим 1 – мигает четвертый разряд, ожидается ввод минут.
Таким образом реагировать на нажатия клавиш в разных режимах необходимо по-разному, поэтому для каждого режима существует своя подпрограмма обработки нажатия клавиши.
Регистр r12 определен как переменная режима, в которой хранится номер текущего режима.
При нажатии кнопки в режиме 2 необходимо записать введенное значение часов в регистр r3 (текущее значение часов), а при нажатии кнопки в режиме 4 нужно выполнить те же действия с минутами.
2.4. Подпрограмма обработки прерывания таймера
В Algorithm Builder это подпрограмма с именем Timer_0_Overflow. Вызов этой подпрограммы осуществляется при переполнении таймера/счетчика 0, в нашем случае каждые 5мс. При входе в эту подпрограмму необходимо реализовать сохранение важных переменных и регистра флагов SREG в стеке, а при выходе из нее восстановить эти значения.
Далее организован счетчик (регистр R9), который фиксирует число входов в данную п/п. Когда этот счетчик становится равным 200, это значит, что прошла 1с (200*5мс=1с) и при этом увеличивается текущее значение секунд на 1. Затем реализуется вызов подпрограмм счета времени, если мы находимся не в режиме ввода, сканирование клавиатуры и вывод на индикацию.
Алгоритм реализации подпрограммы таймера приведен на рисунке 2.
Рисунок 2 – Алгоритм подпрограммы таймера/счетчика
2.5. Подпрограмма счета времени
В этой п/п в регистре R1 содержится число секунд, в R2 – число минут и в R3 – число часов. R9 – это счетчик, который инкрементируется каждый раз при вызове подпрограммы обработки прерывания по переполнению таймера 0, т.е.
R9 увеличивается каждые 5 мс. Таким образом, когда R9 достигает 200 (проходит 1 сек.), обнуляется R9 и увеличивается текущее число секунд на 1.
Естественно еще выполняется проверка секунд на равенство 60 и, если необходимо, увеличиваются минуты и часы.
При организации индикации существует следующая проблема: в R3 хранится текущее число часов в двоичном виде. А необходимо отдельно выводить число десятков и число единиц на первый и второй разряды индикатора. Например, сейчас 15 часов (R3=15), тогда на первый разряд индикатора необходимо вывести 1, а на второй – 5.
Для разделения десятков и единиц используется вспомогательный регистр R18 .
2.6. Вывод времени на индикацию
Динамическая индикация осуществляется следующим образом: вначале в порт А выводится код, который зажигает сегменты индикатора, при которых светится требуемая цифра (0, 1, 2 …) и открывается первый транзисторный ключ, путем посылки 0 в PORTD.4.
При этом будет отображаться только первый разряд индикатора. Через 5 мс необходимо закрыть первый транзисторный ключ, вывести в порт А код, который соответствует цифре, выводимой на второй разряд и открыть второй транзисторный ключ.
При этом будет отображаться только второй разряд индикатора. Далее эта процедура повторяется для каждого разряда, и после отображения четвертого разряда снова выводится первый разряд.
Таким образом, время обновления каждого разряда составляет 5мс * 4 = 20 мс, при такой частоте обновления человеческий глаз не замечает мерцания и воспринимает индикацию как статическую.
Для выполнения этих действий целесообразно использовать уже настроенный ранее таймер на 5 мс. Поэтому в подпрограмме обработчика прерывания по переполнению таймера будем вызываться функция INDICATION, которая и будет выполнять все вышеперечисленные действия.
При выводе на индикацию последовательно должны выводиться на каждый из четырех разрядов индикатора соответствующие значения. Для перебора разрядов использован счетчик (на регистре R8). Т.к. всего разрядов индикатора 4, то значения регистра R8 могут меняться в пределах от 1 до 4.
При входе в п/п INDIKATION счетчик инкрементируется и в соответствии с его значением выдается сканирующий “0” на соответствующую линию порта D и обновляются показания соответствующего индикатора. Сканирующий “0” далее будет служить также и для опроса клавиатуры.
При достижении счетчиком максимального значения его следует обнулять. Для облегчения вывода можно задействовать 4 регистра, например R4, R5, R6 и R7. Подпрограмма INDIKATION будет отображать значение регистра R4 на первом разряде индикатора, R5 – на втором, R6 – на третьем, R7 – на четвертом.
Теперь в любом месте программы при изменении значений регистров R4..R7 будет осуществляться изменение информации, выводимой на индикатор.
Таким образом, подпрограмма INDIKATION выводит на 1 разряд индикатора число, которое хранится в R4. Пусть в R4 хранится число от 0 до 9, тогда необходимо выводить в порт А код, который соответствует текущему значению R4. Осуществляется это по предварительно составленной таблицей данных кодов.
Таблица состоит из 10 байт, если первый байт таблицы послать в порт А, то на индикаторе появится цифра 0, если послать второй байт таблицы, то будет отображаться цифра 1 и т.д. Эта таблица кодов располагается в памяти программ.
Теперь чтобы вывести на индикатор значение регистра R4, необходимо взять адрес первого элемента таблицы кодов, прибавить к этому адресу регистр R4, по полученному адресу считать байт из таблицы и вывести этот байт в порт А.
Algorithm Builder позволяет поместить в тело программы кроме собственно программы произвольные данные: таблицы кодов, строки сообщений и пр. Для их записи используется элемент алгоритма “codetable”. Для определения их расположения в адресном пространстве, перед ними следует поставить вершину или метку.
При составлении таблицы кодов учитывался тот факт, что сегменты индикатора загораются при подаче на них логического “0”.
Блок-схема подпрограммы INDIKATION представлена на рисунке 6.
Рисунок 3 – Блок-схема подпрограммы индикатор
В начале подпрограммы выполняется сохранение важных регистров в стеке, далее инкрементируется счетчик номера разряда индикатора и проверяется на выход за пределы допустимых значений. После этого, если в данный момент обрабатывается первый разряд индикатора, то R4 выводится на индикатор и затем открывается первый транзисторный ключ, который включает первый разряд индикатора.
2.7. Опрос клавиатуры
Клавиатура сканируется с помощью логического “0”, который подается на соответствующую линию при выводе на индикацию. Далее требуется опросить 3 младших разряда порта D, и если один из них равен “0”, то это является признаком нажатия соответствующей кнопки. В этой подпрограмме также требуется реализовать процедуру антидребезга.
На рисунке 10 показан дребезг контактов при нажатии на кнопку. Как видно из рисунка в результате дребезга контактов кнопки происходит имитация ее многократного нажатия. Для того чтобы избежать неправильного декодирования, считывание скан-кода производится через некоторое время после фиксации факта изменения состояния.
Рисунок 7 – Дребезг контактов
Используется задержка длительностью 20мс и после этого снова опрашивается разряд порта D, на котором перед этим присутствовал “0”. Если состояние не изменилось, то считается, что кнопка нажата.
Источник: http://stud24.ru/programming-computer/razrabotat-chasy-realnogo-vremeni-v/460679-1744442-page1.html
Algorithm Builder. Урок 1 – Введение
Думаю, в наше время нет радиолюбителя, который никогда не сталкивался с микроконтроллерами. Рано или поздно, но это происходит.
Когда я в первый раз увидел схему с микроконтроллером, тут же закрыл страницу браузера, с мыслью: “А, все равно не соберу”.
Но время шло, схем с применением микроконтроллеров становилось все больше, и я все-таки решил начать. На деле все оказалось совсем не таким сложным, как я думал.
Для начала давайте разберемся: что вообще такое микроконтроллер (МК)? По сути, это миниатюрный компьютер, предназначенный для выполнения простейших задач. Все необходимое для работы микроконтроллера заключено в одном корпусе.
В микроконтроллере имеется различная периферия – порты вводавывода, таймеры, интерфейсы связи и т.д.
Микроконтроллер имеет три вида памяти, это RAM (оперативная память), FlashROM (Память программы), EEPROM (энергонезависимая память).
Главное отличие микроконтроллера от обычной микросхемы – это то, что микроконтроллер работает не по жесткой логике, установленной на заводе, а программируется.
Программа, классически пишется в специальной среде на компьютере на одном из языков программирования, после чего переводится на машинный язык(компилируется) и записывается в память контроллера. В этом курсе все будет немного по-другому – программа будет не писаться, а буквально рисоваться в виде блок-схемы.
Благодаря такому подходу программа выглядит более наглядно, а время на разработку программы сокращается в 3-5 раз, по сравнению с классическими приемами программирования.
Algorithm Builder – среда программирования
Algorithm Builder производит полный цикл разработки, начиная от ввода алгоритма, включая процесс отладки и заканчивая записью программы в память.
Начнем с краткого обзора интерфейса программы
Главное меню
- Файл. Служит для открытия, сохранения, закрытия проектов и отдельных алгоритмов, а так же выхода из программы.
- Редактировать. Действия, связанные с редактированием алгоритма: вырезать, копировать, выделить и т.д
- Отображение. Переключение алгоритм/таблица с переменными(о ней ниже) + шаблоны операций и условий.
- Поиск. Тут пояснять не нужно.
- Элементы. Алгоритм рисуется из специальных элементов: Текст, Вершина, Поле, Метка, Условие, Вектор б/у (безусловного) перехода, Настройщик. Со всеми ними мы познакомимся в процессе обучения. В меню находится еще несколько важных пунктов: Деактивировать, Макро, Прерывания. Деактивировать – данный компонент не будет компилироваться. Макро – для создания макросов. Прерывания – содержит список названии всех прерываний микроконтроллера. Об этой функции вы узнаете в следующих уроках, сейчас лишь скажу, что это чрезвычайно важная и необходимая для работы вещь.
- Программа. Действия, связанные с программой – компиляция (перевод на машинный язык), симуляция работы программы, чтение памяти контроллера (Flash и EEPROM) и т.д.
- Опции. Настройки проекта и среды.
- ?. Информация о Algoritm Builder и справка.
Панель инструментов
В пояснениях не нуждается. При наведении курсора на элементы панели всплывают подсказки.
Открытый проект
Тут есть особенность. Нельзя открыть два проекта одновременно.Чтобы открыть/создать новый проект нужно закрыть старый. После открытия проекта вы можете открыть/создать лишь отдельный файл-алгоритм. Файл проекта имеет расширение .alp, а отдельный файл-алгоритм имеет расширение .alg
Работа с переменными и константами
Организуется в виде специальной таблицы (переключить можно клавишей F12, либо через меню, либо клавишей на панели инструментов). Таким образом, сам алгоритм освобождается от лишних записей.
Огромное число меток, благодаря которым возможны переходы от одной части программы к другой, сильно загромождают код, и наглядность программы теряется. В Algorithm Builder переходы осуществляются намного проще – стрелкой (вектором). Но переходы по именованным меткам так же возможны.
Симуляция работы программы
Симулятор показывает все изменения, происходящие внутри виртуального микроконтроллера. Что бы проверить работу программы не обязательно даже покупать микроконтроллер! Симуляция может выполняться пошагово (с заходом в функции или нет), до установленной точки останова или до выделенного участка.
Отладка
Algorithm Builder обладает системой мониторной отладки на кристалле (On Chip debug) которая позволяет наблюдать содержимое памяти реального микроконтроллера в заданных точках.
При этом для связи микроконтроллера с компьютером используется всего одна ножка микроконтроллера, причем по выбору пользователя. Мониторная отладка может быть применена практически к любому микроконтроллеру.
Это программный вариант протокола debugWIRE.
Так почему же Algorithm Builder малоизвестен среди радиолюбителей? Во-первых, до 2010 программа была платной. Сегодня ПО распространяется абсолютно свободно. Во-вторых, отсутствие официальной поддержки программы. Вы не найдете ни одного апнота производителя в котором бы использовался Билдер. Интернет ресурсы, посвященные данной программе, можно пересчитать по пальцам.
Стоит немного рассказать о необходимых материалах и инструментах
Первое что понадобится – это паяльник. Основной инструмент радиолюбителя. Мощность паяльника должна быть в приделах 30-60 Вт. Почему нельзя больше? Мощный паяльник нагревается сильней, и повреждает дорожки платы и применяемые детали. Да и паять им не так удобно – такой паяльник намного больше и тяжелее. Подробнее о паяльниках и пайке
Для того, чтобы загрузить программу в микроконтроллер нужен программатор – в простейшем варианте состоит всего из нескольких резисторов и диодов (на порт LPT и COM).
Если у Вас на компьютере нет порта COM либо LPT, USB программатор можно заказать на eBay, DealExtreame или Aliexpress (Поисковой запрос“avr programmer”; стоит примерно 4-6$).
О выборе и сборке программатора я напишу в следующем уроке.
Для связи микроконтроллера с компьютером (например, чтобы передать от микроконтроллера к компьютеру данные с датчика температуры) необходим специальный переходник.
Он не имеет прямого отношения к этому курсу, однако для некоторых устройств он может быть полезен. Называется он USB-UART (для USB) или COM-UART (для COM порта).
Подробней я расскажу об этом в следующих уроках.
Ну и самое главное – микроконтроллер. В этом учебном курсе мы будем использовать микроконтроллер ATmega 88. Почему именно он? Это один микроконтроллер из серии ATmega 48, ATmega 88, ATmega 168, ATmega 328.
Это значит, что если вы знаете один микроконтроллер из серии – вы знаете и всю серию! Отличаются они лишь объемом памяти.
Если вы разрабатываете программу и понимаете, что программа не влезает в память – вы всегда сможете перейти на более “взрослый” микроконтроллер из серии, не меняя при этом самой программы.
Урок 2 – О создании первой программы
Источник: http://cxem.gq/mc/mc290.php
Введение в алгоритм A*
При разработке игр нам часто нужно находить пути из одной точки в другую. Мы не просто стремимся найти кратчайшее расстояние, нам также нужно учесть и длительность движения. Передвигайте звёздочку (начальную точку) и крестик (конечную точку), чтобы увидеть кратчайший путь. [Прим. пер.
: в статьях этого автора всегда много интерактивных вставок, рекомендую сходить в оригинал статьи.]
Для поиска этого пути можно использовать алгоритм поиска по графу, который применим, если карта представляет собой граф. A* часто используется в качестве алгоритма поиска по графу.
Поиск в ширину — это простейший из алгоритмов поиска по графу, поэтому давайте начнём с него и постепенно перейдём к A*.
Представление карты
Первое, что нужно при изучении алгоритма — понять данные. Что подаётся на вход? Что мы получаем на выходе?
Вход: алгоритмы поиска по графу, в том числе и A*, получают в качестве входных данных граф. Граф — это набор точек («узлов») и соединений («рёбер») между ними. Вот граф, который я передал A*:
A* не видит ничего другого. Он видит только граф. Он не знает, находится ли что-то в помещении или за его пределами, дверь это или комната, насколько велика область. Он видит только граф! Он не понимает никакой разницы между картой сверху и вот этой:
Выход: определяемый A* путь состоит из узлов и рёбер. Рёбра — это абстрактное математическое понятие. A* сообщает нам, что нужно перемещаться из одной точки в другую, но не сообщает, как это нужно делать.
Помните, что он ничего не знает о комнатах или дверях, он видит только граф.
Вы сами должны решить, чем будет являться ребро графа, возвращённое A* — перемещением с тайла на тайл, движением по прямой линии, открытием двери, бегом по кривому пути.
Компромиссы: для каждой игровой карты есть множество разных способов передачи графа поиска пути алгоритму A*. Карта на рисунке выше превращает двери в узлы. А что, если мы превратим двери в рёбра?А если мы применим сетку для поиска пути?
Граф поиска пути не обязательно должен быть тем же, что используется в вашей игровой карте.
В карте на основе сеток можно использовать граф поиска пути без сеток, и наоборот. A* выполняется быстрее с наименьшим количеством узлов графа. С сетками часто проще работать, но в них получается множество узлов. В этой статье рассматривается сам алгоритм A*, а не дизайн графов. Подробнее о графах можно прочитать на моей другой странице.
Для объяснений я в дальнейшем буду использовать сетки, потому что так проще визуализировать концепции.
Алгоритмы
Существует множество алгоритмов, работающих с графами. Я рассмотрю следующие:
Поиск в ширину выполняет исследование равномерно во всех направлениях. Это невероятно полезный алгоритм, не только для обычного поиска пути, но и для процедурной генерации карт, поиска путей течения, карт расстояний и других типов анализа карт.
Алгоритм Дейкстры (также называемый поиском с равномерной стоимостью) позволяет нам задавать приоритеты исследования путей.
Вместо равномерного исследования всех возможных путей он отдаёт предпочтение путям с низкой стоимостью.
Мы можем задать уменьшенные затраты, чтобы алгоритм двигался по дорогам, повышенную стоимость, чтобы избегать лесов и врагов, и многое другое. Когда стоимость движения может быть разной, мы используем его вместо поиска в ширину.
A* — это модификация алгоритма Дейкстры, оптимизированная для единственной конечной точки. Алгоритм Дейкстры может находить пути ко всем точкам, A* находит путь к одной точке. Он отдаёт приоритет путям, которые ведут ближе к цели.
Я начну с самого простого — поиска в ширину, и буду добавлять функции, постепенно превращая его в A*.
Поиск в ширину
Ключевая идея всех этих алгоритмов заключается в том, что мы отслеживаем состояние расширяющегося кольца, которое называется границей. В сетке этот процесс иногда называется заливкой (flood fill), но та же техника применима и для карт без сеток.
Посмотрите анимацию расширения границы: Как это реализовать? Повторяем эти шаги, пока граница не окажется пустой:
- Выбираем и удаляем точку из границы.
- Помечаем точку как посещённую, чтобы знать, что не нужно обрабатывать её повторно.
- Расширяем границу, глядя на её соседей. Всех соседей, которых мы ещё не видели, добавляем к границе.
Давайте рассмотрим это подробнее. Тайлы нумеруются в порядке их посещения: Алгоритм описывается всего в десяти строках кода на Python:frontier = Queue()
frontier.put(start )
visited = {}
visited[start] = True while not frontier.empty(): current = frontier.get() for next in graph.neighbors(current): if next not in visited: frontier.
put(next) visited[next] = True
В этом цикле заключается вся сущность алгоритмов поиска по графу этой статьи, в том числе и A*. Но как нам найти кратчайший путь? Цикл на самом деле не создаёт путей, он просто говорит нам, как посетить все точки на карте. Так получилось потому, что поиск в ширину можно использовать для гораздо большего, чем просто поиск путей.
В этой статье я показываю, как он применяется в играх tower defense, но его также можно использовать в картах расстояний, в процедурной генерации карт и многом другом. Однако здесь мы хотим использовать его для поиска путей, поэтому давайте изменим цикл так, чтобы отслеживать, откуда мы пришли для каждой посещённой точки, и переименуем visited в came_from:frontier = Queue()
frontier.
put(start )
came_from = {}
came_from[start] = None while not frontier.empty(): current = frontier.get() for next in graph.neighbors(current): if next not in came_from: frontier.put(next) came_from[next] = currentТеперь came_from для каждой точки указывает на место, из которого мы пришли. Это похоже на «хлебные крошки» из сказки. Нам этого достаточно для воссоздания целого пути.
Посмотрите, как стрелки показывают обратный путь к начальной позиции.
Код воссоздания путей прост: следуем по стрелкам обратно от цели к началу. Путь — это последовательность рёбер, но иногда проще хранить только узлы:
current = goal path = [current]
while current != start: current = came_from[current] path.append(current)
path.append(start) # optional
path.reverse() # optional
Таков простейший алгоритм поиска путей. Он работает не только в сетках, как показано выше, но и в любой структуре графов. В подземелье точки графа могут быть комнатами, а рёбра — дверями между ними. В платформере узлы графа могут быть локациями, а рёбра — возможными действиями: переместиться влево, вправо, подпрыгнуть, спрыгнуть вниз. В целом можно воспринимать граф как состояния и действия, изменяющие состояние. Подробнее о представлении карт я написал здесь. В оставшейся части статьи я продолжу использовать примеры с сетками, и расскажу о том, для чего можно применять разновидности поиска в ширину.
Ранний выход
Мы нашли пути из одной точки во все другие точки. Часто нам не нужны все пути, нам просто нужен путь между двумя точками. Мы можем прекратить расширять границу, как только найдём нашу цель. Посмотрите, как граница перестаёт расширятся после нахождения цели.
Код достаточно прямолинеен:frontier = Queue()
frontier.put(start )
came_from = {}
came_from[start] = None while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): if next not in came_from: frontier.
put(next) came_from[next] = current
Стоимость перемещения
Пока мы делали шаги с одинаковой стоимостью. В некоторых случаях поиска путей у разных типов движения есть разная стоимость. Например, в Civilization движение через равнины или пустыню может стоить 1 очко движения, а движение через лес — 5 очков движения.
На карте в самом начале статьи прохождение через воду стоит в 10 раз дороже, чем движение по траве. Ещё одним примером является диагональное движение в сетке, которое стоит больше, чем движение по осям. Нам нужно, чтобы поиск пути учитывал эту стоимость.
Давайте сравним количество шагов от начала с расстоянием от начала:
Для этого нам нужен алгоритм Дейкстры (также называемый поиском с равномерной стоимостью).
Чем он отличается от поиска в ширину? Нам нужно отслеживать стоимость движения, поэтому добавим новую переменную cost_so_far, чтобы следить за общей стоимостью движения с начальной точки. При оценке точек нам нужно учитывать стоимость передвижения. Давайте превратим нашу очередь в очередь с приоритетами.
Менее очевидно то, что у нас может получиться так, что одна точка посещается несколько раз с разной стоимостью, поэтому нужно немного поменять логику. Вместо добавления точки к границе в случае, когда точку ни разу не посещали, мы добавляем её, если новый путь к точке лучше, чем наилучший предыдущий путь.
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): new_cost = cost_so_far[current] + graph.cost(current, next) if next not in cost_so_far or new_cost
Использование очереди с приоритетами вместо обычной очереди изменяет способ расширения границы. Контурные линии позволяют это увидеть. Посмотрите видео, чтобы понаблюдать, как граница расширяется медленнее через леса, и поиск кратчайшего пути выполняется вокруг центрального леса, а не сквозь него:
Стоимость движения, отличающаяся от 1, позволяет нам исследовать более интересные графы, а не только сетки. На карте в начале статьи стоимость движения основана на расстоянии между комнатами. Стоимость движения можно также использовать, чтобы избегать или предпочитать области на основании близости врагов или союзников. Интересная деталь реализации: обычная очередь с приоритетами поддерживает операции вставки и удаления, но в некоторых версиях алгоритма Дейкстры используется и третья операция, изменяющая приоритет элемента, уже находящегося в очереди с приоритетами. Я не использую эту операцию, и объясняю это на странице реализации алгоритма.
Эвристический поиск
В поиске в ширину и алгоритме Дейкстры граница расширяется во всех направлениях. Это логичный выбор, если вы ищете путь ко всем точкам или ко множеству точек. Однако обычно поиск выполняется только для одной точки. Давайте сделаем так, чтобы граница расширялась к цели больше, чем в других направлениях.
Во-первых, определим эвристическую функцию, сообщающую нам, насколько мы близки к цели:def heuristic(a, b): # Manhattan distance on a square grid return abs(a.x – b.x) + abs(a.y – b.y)
В алгоритме Дейкстры для порядка очереди с приоритетами мы использовали расстояние от начала.
В жадном поиске по первому наилучшему совпадению для порядка очереди с приоритетами мы вместо этого используем оцененное расстояние до цели. Точка, ближайшая к цели, будет исследована первой. В коде используется очередь с приоритетами из поиска в ширину, но не применяется cost_so_far из алгоритма Дейкстры:frontier = PriorityQueue()
frontier.
put(start, 0)
came_from = {}
came_from[start] = None while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): if next not in came_from: priority = heuristic(goal, next) frontier.
put(next, priority) came_from[next] = currentДавайте посмотрим, как это работает: Ого! Потрясающе, правда? Но что случится на более сложной карте? Эти пути не являются кратчайшими. Итак, этот алгоритм работает быстрее, когда препятствий не очень много, но пути не слишком оптимальны. Можно ли это исправить? Конечно.
Алгоритм A*
Алгоритм Дейкстры хорош в поиске кратчайшего пути, но он тратит время на исследование всех направлений, даже бесперспективных. Жадный поиск исследует перспективные направления, но может не найти кратчайший путь. Алгоритм A* использует и подлинное расстояние от начала, и оцененное расстояние до цели.
Код очень похож на алгоритм Дейкстры:frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() if current == goal: break for next in graph.neighbors(current): new_cost = cost_so_far[current] + graph.
cost(current, next) if next not in cost_so_far or new_cost Сравните алгоритмы: алгоритм Дейкстры вычисляет расстояние от начальной точки.
Жадный поиск по первому наилучшему совпадению оценивает расстояние до точки цели. A* использует сумму этих двух расстояний.
Попробуйте в оригинале статьи делать отверстия в разных местах стены. Вы обнаружите, что жадный поиск находит правильный ответ, A* тоже его находит, исследуя ту же область.
Когда жадный поиск по первому наилучшему находит неверный ответ (более длинный путь), A* находит правильный, как и алгоритм Дейкстры, но всё равно исследует меньше, чем алгоритм Дейкстры.
A* берёт лучшее от двух алгоритмов. Поскольку эвристика не оценивает расстояния повторно, A* не использует эвристику для поиска подходящего ответа. Он находит оптимальный путь, как и алгоритм Дейкстры. A* использует эвристику для изменения порядка узлов, чтобы повысить вероятность более раннего нахождения узла цели.
И… на этом всё! В этом и заключается алгоритм A*.
Дополнительное чтение
Вы готовы реализовать его? Попробуйте использовать готовую библиотеку. Если вы хотите реализовать его самостоятельно, то у меня есть инструкция по пошаговой реализации графов, очередей и алгоритмов поиска пути на Python, C++ и C#.
Какой алгоритм стоит использовать для поиска путей на игровой карте?
- Если вам нужно найти пути из или ко всем точкам, используйте поиск в ширину или алгоритм Дейкстры. Используйте поиск в ширину, если стоимость движения одинакова. Используйте алгоритм Дейкстры, если стоимость движения изменяется.
- Если нужно найти пути к одной точке, используйте жадный поиск по наилучшему первому или A*. В большинстве случаев стоит отдать предпочтение A*. Когда есть искушение использовать жадный поиск, то подумайте над применением A* с «недопустимой» эвристикой.
А что насчёт оптимальных путей? Поиск в ширину и алгоритм Дейкстры гарантированно найдут кратчайший путь по графу. Жадный поиск не обязательно его найдёт. A* гарантированно найдёт кратчайший путь, если эвристика никогда не больше истинного расстояния. Когда эвристика становится меньше, A* превращается в алгоритм Дейкстры.
Когда эвристика становится больше, A* превращается в жадный поиск по наилучшему первому совпадению.
А как насчёт производительности? Лучше всего устранить ненужные точки графа. Если вы используете сетку, то прочитайте это. Уменьшение размера графа помогает всем алгоритмам поиска по графам.
После этого используйте простейший из возможных алгоритмов. Простые очереди выполняются быстрее. Жадный поиск обычно выполняется быстрее, чем алгоритм Дейкстры, но не обеспечивает оптимальных путей. Для большинства задач по поиску путей оптимальным выбором является A*.
А что насчёт использования не на картах? Я использовал в статье карты, потому что думаю, что на них проще объяснить работу алгоритма.
Однако эти алгоритмы поиска по графам можно использовать на любых графах, не только на игровых картах, и я пытался представить код алгоритма в виде, не зависящем от двухмерных сеток. Стоимость движения на картах превращается в произвольные веса рёбер графа.
Эвристики перенести на произвольные карты не так просто, необходимо создавать эвристику для каждого типа графа. Для плоских карт хорошим выбором будут расстояния, поэтому здесь мы использовали их.
Я написал ещё много всего о поиске путей здесь.
Не забывайте, что поиск по графам — это только одна часть того, что вам нужно. Сам по себе A* не обрабатывает такие аспекты, как совместное движение, перемещение препятствий, изменение карты, оценку опасных областей, формации, радиусы поворота, размеры объектов, анимацию, сглаживание путей и многое другое.
Источник: https://habr.com/post/331192/
Загрузка...