RoadSearcher

Road Searcher

Структура программы:

• img.h - модуль для работы с картинками, пока поддержка только BMP формата.
• graphmap.h - модуль построения графа по картике и нахождение в нем маршрутов.

• roadSearcher.cpp - главный код

  ---

  ---

  Модуль img.h - работа с картинками

---

---

template class Img

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

Cвойства:

int width, height; - широта и высота
Row *data; - массив строк данных, которые хранятся в ячейке
Settings settings; - настройки для разных типов данных (если это будет работа с картинкой)

Методы:

Img(int width, int height) - конструктор с укозанием широты и высоты
Img() - конструктор по умолчанию
init() - инициализация картинки(данных) по широте и высоте
Row operator[](int n) - перегрузка оператора [] для возможности обращения к каждой строке данных

---

---

template class Row

Вспомогательный класс, для реализации структуры 2х мерного массива с данными

Cвойства:

int width; - ширина строки
T** pixel; - ячейка с хранимыми данными

Методы:

Row() - конструктор по умолчанию
Row(int width) - конструктор с шириной, инициализация по ширине
T* operator[](int n) - перегрузка оператора [] для возможности обращения к каждой ячейке данных

---

---

Работа с BMP

---

---

class Pixel

Хранит информацию о пикселе картинки( параметр для класса Img)

Cвойства:

int r; - красный цвет
int g; - зелены цвет
int b; - синий цвет
int a; - канал

Методы:

конструктор (r, g, b),
конструктор (),
конструктор (r, g, b, a)

---

Структура settings - для прописания настроек картинки

struct Settings
{
    //настройки для bmp файла
    unsigned int imgWidth = 500, imgHeight = 500;
    unsigned char signature[2] = { 'B', 'M' };
    unsigned int fileSize = 14 + 40 + imgWidth * imgHeight * 3;
    unsigned int reserved = 0;
    unsigned int offset = 14 + 40;

    unsigned int headerSize = 40;
    unsigned int dimensions[2] = { imgWidth, imgHeight };
    unsigned short colorPlanes = 1;
    unsigned short bpp = 32;
    unsigned int compression = 0;
    unsigned int imgSize = imgWidth * imgHeight * 3;
    unsigned int resolution[2] = { 2795, 2795 };
    unsigned int pltColors = 0;
    unsigned int impColors = 0;
    int lineImgSize
};

---

---

Класс BMP, наследник Img c параметром Pixel

Cвойства: что и у IMG

Методы:

void read() - считывание bmp картинки
void write() - запись bmp картинки
BMP() {} - конструктор по умолчанию;

---

Приминение:

BMP img;
cout << "Start read...";
img.read("test30.bmp");//считываем
img[4][5]->r = 180; //задаем пикселю с индексом 4-5 значение красного 180
img.write("output.bmp");//записываем
cout << "End." << endl;

---

---

Модуль graphmap.h - построение графа и нахождение маршрутов

---

---

class Node

Cвойства:

bool vizited; - посещен ли узел int w; - вес узла (или его возвышенность)
int distation; - расстояние до нужной точки (или выхода)
int dirCount; - количество возможных направлений
Pixel data; - данные внутри узла
Position pos; - позиция узла
Node *branches[8]; - соседние узлы

Методы:

void calcWeight - подсчет веса узла
calcDistation(Node previos) - рассчет расстояния относительно переданного предыдущего узла
operator < (const Node &v2) const - перегрузка операторов больше меньше, для очереди с приорететом

---

struct fo_sort - структура для сортировки указателей на узлы дерева

---

---

class Graph

Наследник Img (чтобы была возможность обратится к каждому узлу через индексы)

Cвойства:

BMP map; - картина на основе которой строится граф
Position start; - позиция откуда начнется поиск

Методы:

Graph(BMP map) - конструктор дерева по картинке (собирает из картинки граф)
calcdijkstra(Position start) - рассчет расстояний до каждого узла дерева от точки start
drowRoad(Position end) - рисует дорогу от начальной точки до точки end;

Приминение:

BMP img;
cout << "Start read...";
img.read("test29.bmp");//загружаем картинку
//img.write("output.bmp");
cout << "End." << endl;

cout << "Building tree...";
Graph map(img); //строим древо по этой картинке
cout << "End." << endl;

try 
{ 
 cout << "Drowing roud...";
 map.calcdijkstra(Position(220, 220)); //считаем все маршруты от точки 220 220
 BMP out = map.drowRoad(Position(860, 860)); //прокладываем маршрут к точке 860 860

 out.write("output30.bmp"); //записываем получившийся результат
 cout << "End." << endl;
}
catch (char* error) // если маршрут не найдет выводим ошибку
{
    cout << error <<endl;
}

Результат для кривой дракона:

Лабиринт:

Выход (зеленая линия):