RoadSearcher/graphmap.h

#pragma once
#pragma once
#include "stdafx.h"
#include <iostream>
#include <locale.h>
#include <stdio.h>
#include <string>
#include "img.h"
#include <math.h>
#include <set>
#include <queue> 

using namespace std;
#pragma comment(linker, "/STACK:100000000")

int direction[8][2] = { { -1,1 } ,{ 0,1 },{ 1,0 },{ 1,1 },{ 0,-1 },{ -1,0 },{ -1,-1 },{ 1,-1 }};

class Position
{
public:
	int x, y;
	Position() 
	{
		this->x = 0;
		this->y = 0;
	};
	Position(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
	float calcDist(Position other) // ðàñ÷åò ðàññòîÿíèé ìåæäó ïîçèöèÿìè
	{
		x = this->x - other.x;
		y = this->y - other.y;

		return sqrt(x*x + y*y);
	}
};

class Node
{

public:
	bool vizited;

	int w; //âåñ óçëà (èëè åãî âîçâûøåííîñòü)
	int distation; // ðàññòîÿíèå äî íóæíîé òî÷êè (èëè âûõîäà)
	int dirCount; //êîëè÷åñòâî âîçìîæíûõ íàïðàâëåíèé
	Pixel data;
	Position pos;
	Node *branches[8];

	Node() { 
		this->distation = 100000000000.0;
		this->dirCount = 0; 
		this->w = 0; 
		this->vizited = 0; 
		pos = Position(0, 0);
		for (int i = 0; i < 8; i++)
		{
			branches[i] = (Node*)malloc(sizeof(Node));
		}
	};
	Node(Pixel data, int x, int y)
	{
		this->data = data;
		this->calcWeight();
		pos = Position(x, y);
		this->dirCount = 0;
		this->distation = 100000000000.0;
		this->vizited = 0;

		for (int i = 0; i < 8; i++)
		{
			branches[i] = (Node*)malloc(sizeof(Node));
		}
	}
	void calcWeight()
	{
		// c÷èòàåì âåñ óçëà ñ ïîìîùüþ êàêîé-ëèáî ôóíêöèè
		this->w = 255 - ((this->data.r + this->data.b + this->data.g) / 3) + 30;
		if (this->w > 200)
			this->w = 1000;
	}
	bool calcDistation(Node previos)
	{
		//ñ÷èòàåì ðàññòîÿíèå ïðîéäåííîãî ïóòè â äàííîé âåðøèíå
		float t = previos.pos.calcDist(this->pos);
	//	cout << t <<endl;
	
		float dist = previos.distation + this->w + t;
		//cout << dist << endl;
		// åñëè ìåíüøå , ìåíÿåì òåêóùåå çíà÷åíèå ðàññòîÿíèÿ
		if (dist < this->distation)
		{
			this->distation = dist;
			return true;
		}
		return false;
	}
	void printPos()
	{
		cout << this->pos.x << " - ";
		cout << this->pos.y << endl;
	}
	bool operator < (const Node &v2) const
	{
		return this->distation < v2.distation;
	}

	bool operator > (const Node &v2) const
	{
		return this->distation > v2.distation;
	}
};

struct fo_sort
{
	bool operator()(const Node *x, const Node *y) const
	{
		return *x > *y;
	}
};


class Graph : public Img <Node>
{
	BMP map;
	Position start;
public:


	/////////
	Graph(BMP map)
	{
		this->width = map.width;
		this->height = map.height;
		this->map = map;
		init();
		for (int x = 0; x < map.height; x++)
		{
			for (int y = 0; y < map.width; y++)
			{

				(*this)[x][y]->pos = Position(x, y);
				(*this)[x][y]->data = *map[x][y];
				(*this)[x][y]->calcWeight();
			}
		}

		for (int x = 0; x < map.height; x++)
		{
			for (int y = 0; y < map.width; y++)
			{
				int e = 0;
				for (int i = 0; i < 8; i++)
				{
					int xn = x + direction[i][0];
					int yn = y + direction[i][1];

					if (xn > 0 && xn < map.height)
					{
						if (yn > 0 && yn < map.width)
						{
							
							(*this)[x][y]->branches[e] = (*this)[xn][yn];
							e += 1;							 
							(*this)[x][y]->dirCount += 1;
						}

					}				
					
				}

			}
		}
	}
	///////////

	void calcdijkstra(Position start)
	{
		priority_queue <Node*, vector<Node*>, fo_sort> nodesToVisit;
		Node *current = (*this)[start.x][start.y];
		this->start = start;
		current->distation = 0;
		nodesToVisit.push(current);
		while (!nodesToVisit.empty())
		{
			current = nodesToVisit.top();
			nodesToVisit.pop();
			current->vizited = 1;
			int n = current->dirCount;
			for (int i = 0; i < n; i++)
			{
				if (current->branches[i]->vizited != 1)
				{
					if (current->branches[i]->calcDistation(*current))
						nodesToVisit.push(current->branches[i]);
				}
				else
				{
					//cout << "All good!";
				}
			}

		}

	}

	Node min(Node current)
	{
		float d = 1000000000.0;
		Node next;
		for (int i = 0; i < 8; i++)
		{
			if (current.branches[i]->distation <= d)
			{
				next = *current.branches[i];
				d = current.branches[i]->distation;
			}
		}
		return next;
	}
	BMP drowRoad(Position end)
	{
		int x = end.x;
		int y = end.y;
		Node current = *(*this)[x][y];
		
		while (current.distation != 0)
		{
			current = min(current);
			if (map[current.pos.x][current.pos.y]->b < 20 &&
				map[current.pos.x][current.pos.y]->g < 20 &&
				map[current.pos.x][current.pos.y]->r < 20)
				throw "The rok is very cool! I can't go there! Sorry o-o I'm not a sportsman!";

			map[current.pos.x][current.pos.y]->b = 0;
			map[current.pos.x][current.pos.y]->g = 255;
			map[current.pos.x][current.pos.y]->r = 0;
		}

		map[start.x][start.y]->b = 0;
		map[start.x][start.y]->g = 0;
		map[start.x][start.y]->r = 255;

		map[end.x][end.y]->b = 0;
		map[end.x][end.y]->g = 0;
		map[end.x][end.y]->r = 255;

		return map;
	}





};