SFML и C++ Уроки \ Разработка игр › Форумы › Логика игр › Поиск пути(Алгоритм Ли)-тестовая версия
В этой теме 2 ответа, 2 участника, последнее обновление barbar 7 года/лет, 8 мес. назад.
-
АвторСообщения
-
C++123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322#include <SFML\Graphics.hpp>#include <list>#include <math.h>#include <sstream>#include <iostream>class Block {public:float x, y;sf::String File, name;sf::Image image;sf::Texture texture;sf::Sprite sprite;int Value;Block(sf::String F, float X, float Y, sf::String Name, int value) {name = Name;File = F;image.loadFromFile(File);texture.loadFromImage(image);sprite.setTexture(texture);x = X; y = Y;Value = value;sprite.setPosition(x, y);}};class TextOut {public:float x, y, timeStart, time;sf::Color color;sf::String TextString;sf::Font font;sf::Text text;TextOut(float X, float Y, sf::String TextStrinG, sf::Font Font, sf::Color Color, float TimeStart){sf::Text Text(TextStrinG, font, 20);x = X, y = Y, TextString = TextStrinG, font = Font, color = Color, timeStart = TimeStart;text = Text;text.setPosition(x, y);text.setColor(color);timeStart = TimeStart;}void update(sf::RenderWindow &window, float time){if (timeStart >= 0){//x += 0.04; смещение//y -= 0.04; смещениеtext.setPosition(x, y);//text.setOrigin(x / 2, y / 2);window.draw(text);//timeStart -= time; (удаление когда время = 0)//std::cout << time << std::endl;}}};bool checkFree(float x, float y, std::list<Block*> entities){bool free = true;std::list<Block*>::iterator it;if ((x < 0) || (x>400) || (y < 0) || (y>400)){return false;}for (it = entities.begin(); it != entities.end(); it++){if (((*it)->x == x) && ((*it)->y == y))free = false;}return free;}bool find_path(std::list<Block*> &entities){bool free = false;int W = 400;int H = 400;int StartX, StartY;int FinishX, FinishY;bool findPath = false;float counts=0;float countsPathList = 0;std::list<Block*>::iterator it;for (it = entities.begin(); it != entities.end(); it++){if ((*it)->name == "start"){StartX = (*it)->x;StartY = (*it)->y;}if ((*it)->name == "finish"){FinishX = (*it)->x;FinishY = (*it)->y;}}if ((FinishX != 0) && (StartX != 0)){float itDistance = 1000;float Distance = 1;while (!findPath){for (it = entities.begin(); it != entities.end(); it++){counts += 1;if (findPath) break;if ((*it)->Value == itDistance){float UpX = (*it)->x;float UpY = (*it)->y - 20;free = checkFree(UpX, UpY, entities);if (free){entities.push_back(new Block("path.png", UpX, UpY, "path", Distance));}//Rightfloat RigthX = (*it)->x+20;float RigthY = (*it)->y;free = checkFree(RigthX, RigthY, entities);if (free){entities.push_back(new Block("path.png", RigthX, RigthY, "path", Distance));}//Leftfloat LeftX = (*it)->x-20;float LeftY = (*it)->y;free = checkFree(LeftX, LeftY, entities);if (free){entities.push_back(new Block("path.png", LeftX, LeftY, "path", Distance));}//Downfloat DownX = (*it)->x;float DownY = (*it)->y + 20;free = checkFree(DownX, DownY, entities);if (free){entities.push_back(new Block("path.png", DownX, DownY, "path", Distance));}if ( ( (UpX == FinishX) && (UpY == FinishY) ) || ((RigthX == FinishX) && (RigthY == FinishY)) || ((LeftX == FinishX) && (LeftY == FinishY)) || ((DownX == FinishX) && (DownY == FinishY))){findPath = true;}}}itDistance = Distance;Distance++;std::cout << "main:" << counts << std::endl;std::cout << "PathList" << countsPathList << std::endl;}}return findPath;};int main(){sf::RenderWindow window(sf::VideoMode(400, 400), "Path finder1");sf::Image image;image.loadFromFile("map.png");sf::Texture texture;texture.loadFromImage(image);sf::Sprite map;map.setTexture(texture);bool free = false;bool start = false;bool finish = false;//timefloat time = 0;sf::Clock clock;//textOutsf::Font font;font.loadFromFile("CyrilicOld.ttf");sf::Text text("500", font, 20);text.setColor(sf::Color::Red);text.setPosition(100, 100);//std::list<Block*> entities;//создаю список, сюда буду кидать объекты.например врагов.std::list<Block*>::iterator it;//итератор чтобы проходить по эл-там спискаstd::list<TextOut*> ListTextOut;std::list<TextOut*>::iterator itTextOut;int x = 0;int y = 0;int count = 0;bool findPath = false;while (window.isOpen()){//timetime = clock.getElapsedTime().asMicroseconds();clock.restart();time = time / 1000;window.clear();sf::Event event;while (window.pollEvent(event)){if (event.type == sf::Event::Closed)window.close();}sf::Vector2i localPosition = sf::Mouse::getPosition(window);if (sf::Mouse::isButtonPressed(sf::Mouse::Left)) {x = 20 * (int(localPosition.x) / 20);y = 20 * (int(localPosition.y) / 20);free = checkFree(x, y, entities);if (free){entities.push_back(new Block("hero.png", x, y, "start", 1000));}start = true;}if (sf::Mouse::isButtonPressed(sf::Mouse::Right)) {x = 20 * (int(localPosition.x) / 20);y = 20 * (int(localPosition.y) / 20);free = checkFree(x, y, entities);if (free){entities.push_back(new Block("block.png", x, y, "block", 999));}}if (sf::Mouse::isButtonPressed(sf::Mouse::Middle)) {x = 20 * (int(localPosition.x) / 20);y = 20 * (int(localPosition.y) / 20);free = checkFree(x, y, entities);if (free){entities.push_back(new Block("finish.png", x, y, "finish", 1001));}finish = true;}if ((finish == true) && (start == true) && (findPath == false)){findPath = find_path(entities);}window.draw(map);for (it = entities.begin(); it != entities.end(); it++){window.draw((*it)->sprite);}count = 0;for (it = entities.begin(); it != entities.end(); it++){count += 1;}for (it = entities.begin(); it != entities.end(); it++){if ((*it)->Value < 999)ListTextOut.push_back(new TextOut((*it)->x, (*it)->y, std::to_string((*it)->Value), font, sf::Color::Blue, 1 * 1000));}for (itTextOut = ListTextOut.begin(); itTextOut != ListTextOut.end();){TextOut *b = *itTextOut;b->update(window, time);itTextOut++;}window.display();}return 0;}
Вкратце что делается. Левой кнопкой мыши добавляется Стартовая позиция. Правой кнопкой мыши добавляются блоки-препятствия. Средней кнопкой мыши добавляется Финиш и сразу запускается поиск пути.
Пока долго. Никто никуда не двигается по найденному пути. Но начало положено.
P.S. Это поиск ортогональный. То есть в каждом следующем цикле проверяются 4 рядом стоящие клетки. Справа, слева, снизу, сверху.
Во вложении “png” с блоками и картой.
Вложения:
You must be logged in to view attached files.C++123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366#include <SFML\Graphics.hpp>#include <list>#include <math.h>#include <sstream>#include <iostream>class Block {public:float x, y;sf::String File, name;sf::Image image;sf::Texture texture;sf::Sprite sprite;int Value;Block(sf::String F, float X, float Y, sf::String Name, int value) {name = Name;File = F;image.loadFromFile(File);texture.loadFromImage(image);sprite.setTexture(texture);x = X; y = Y;Value = value;sprite.setPosition(x, y);}};class TextOut {public:float x, y, timeStart, time;sf::Color color;sf::String TextString;sf::Font font;sf::Text text;TextOut(float X, float Y, sf::String TextStrinG, sf::Font Font, sf::Color Color, float TimeStart){sf::Text Text(TextStrinG, font, 12);x = X, y = Y, TextString = TextStrinG, font = Font, color = Color, timeStart = TimeStart;text = Text;text.setPosition(x, y);text.setColor(color);timeStart = TimeStart;}void update(sf::RenderWindow &window, float time){if (timeStart >= 0){//x += 0.04; смещение//y -= 0.04; смещениеtext.setPosition(x, y);//text.setOrigin(x / 2, y / 2);window.draw(text);//timeStart -= time; (удаление когда время = 0)//std::cout << time << std::endl;}}};bool checkFree(float x, float y, std::list<Block*> entities){bool free = true;std::list<Block*>::iterator it;if ((x < 0) || (x>400) || (y < 0) || (y>400)){return false;}for (it = entities.begin(); it != entities.end(); it++){if (((*it)->x == x) && ((*it)->y == y))free = false;}return free;}bool find_path(std::list<Block*> &entities){bool free = false;int W = 400;int H = 400;int StartX, StartY;int FinishX, FinishY;bool findPath = false;float counts=0;float countsPathList = 0;std::list<Block*>::iterator it;std::list<Block*>::iterator itPath;for (it = entities.begin(); it != entities.end(); it++){if ((*it)->name == "start"){StartX = (*it)->x;StartY = (*it)->y;}if ((*it)->name == "finish"){FinishX = (*it)->x;FinishY = (*it)->y;}}if ((FinishX != 0) && (StartX != 0)){float itDistance = 1000;float Distance = 1;while (!findPath){for (it = entities.begin(); it != entities.end(); it++){counts += 1;if (findPath) break;if ((*it)->Value == itDistance){float UpX = (*it)->x;float UpY = (*it)->y - 20;free = checkFree(UpX, UpY, entities);if (free){entities.push_back(new Block("path.png", UpX, UpY, "path", Distance));}//Rightfloat RigthX = (*it)->x+20;float RigthY = (*it)->y;free = checkFree(RigthX, RigthY, entities);if (free){entities.push_back(new Block("path.png", RigthX, RigthY, "path", Distance));}//Leftfloat LeftX = (*it)->x-20;float LeftY = (*it)->y;free = checkFree(LeftX, LeftY, entities);if (free){entities.push_back(new Block("path.png", LeftX, LeftY, "path", Distance));}//Downfloat DownX = (*it)->x;float DownY = (*it)->y + 20;free = checkFree(DownX, DownY, entities);if (free){entities.push_back(new Block("path.png", DownX, DownY, "path", Distance));}if ( ( (UpX == FinishX) && (UpY == FinishY) ) || ((RigthX == FinishX) && (RigthY == FinishY)) || ((LeftX == FinishX) && (LeftY == FinishY)) || ((DownX == FinishX) && (DownY == FinishY))){findPath = true;for (itPath = entities.begin(); itPath != entities.end(); itPath++){if ((*itPath)->name == "finish"){(*itPath)->Value = Distance;}}}}}itDistance = Distance;Distance++;std::cout << "main:" << counts << std::endl;std::cout << "PathList" << countsPathList << std::endl;}}float Distance = 0;float Dx = 0;float Dy = 0;for (itPath = entities.begin(); itPath != entities.end(); itPath++){if ((*itPath)->name == "finish"){Dx = (*itPath)->x;Dy = (*itPath)->y;Distance = (*itPath)->Value;}}while (Distance != 0){Distance--;for (itPath = entities.begin(); itPath != entities.end(); itPath++){if (((*itPath)->Value == Distance)){float itX = (*itPath)->x;float itY = (*itPath)->y;float range = sqrt((itX - Dx) * (itX - Dx) + (itY - Dy) * (itY - Dy));if (range == 20){Dx = itX;Dy = itY;(*itPath)->name = "GoodPath";break;}}}}return findPath;};int main(){sf::RenderWindow window(sf::VideoMode(400, 400), "Path finder1");sf::Image image;image.loadFromFile("map.png");sf::Texture texture;texture.loadFromImage(image);sf::Sprite map;map.setTexture(texture);bool free = false;bool start = false;bool finish = false;//timefloat time = 0;sf::Clock clock;//textOutsf::Font font;font.loadFromFile("CyrilicOld.ttf");sf::Text text("500", font, 8);text.setColor(sf::Color::Red);text.setPosition(100, 100);//std::list<Block*> entities;//создаю список, сюда буду кидать объекты.например врагов.std::list<Block*>::iterator it;//итератор чтобы проходить по эл-там спискаstd::list<TextOut*> ListTextOut;std::list<TextOut*>::iterator itTextOut;int x = 0;int y = 0;int count = 0;bool findPath = false;while (window.isOpen()){//timetime = clock.getElapsedTime().asMicroseconds();clock.restart();time = time / 1000;window.clear();sf::Event event;while (window.pollEvent(event)){if (event.type == sf::Event::Closed)window.close();}sf::Vector2i localPosition = sf::Mouse::getPosition(window);if (sf::Mouse::isButtonPressed(sf::Mouse::Left)) {x = 20 * (int(localPosition.x) / 20);y = 20 * (int(localPosition.y) / 20);free = checkFree(x, y, entities);if (free){entities.push_back(new Block("hero.png", x, y, "start", 1000));}start = true;}if (sf::Mouse::isButtonPressed(sf::Mouse::Right)) {x = 20 * (int(localPosition.x) / 20);y = 20 * (int(localPosition.y) / 20);free = checkFree(x, y, entities);if (free){entities.push_back(new Block("block.png", x, y, "block", 999));}}if (sf::Mouse::isButtonPressed(sf::Mouse::Middle)) {x = 20 * (int(localPosition.x) / 20);y = 20 * (int(localPosition.y) / 20);free = checkFree(x, y, entities);if (free){entities.push_back(new Block("finish.png", x, y, "finish", 1001));}finish = true;}if ((finish == true) && (start == true) && (findPath == false)){findPath = find_path(entities);}window.draw(map);for (it = entities.begin(); it != entities.end(); it++){window.draw((*it)->sprite);}count = 0;for (it = entities.begin(); it != entities.end(); it++){count += 1;}for (it = entities.begin(); it != entities.end(); it++){if (((*it)->Value < 999) && ((*it)->name != "GoodPath"))ListTextOut.push_back(new TextOut((*it)->x, (*it)->y, std::to_string((*it)->Value), font, sf::Color::Blue, 1 * 1000));elseif ((*it)->Value < 999)ListTextOut.push_back(new TextOut((*it)->x, (*it)->y, std::to_string((*it)->Value), font, sf::Color::Cyan, 1 * 1000));}for (itTextOut = ListTextOut.begin(); itTextOut != ListTextOut.end();){TextOut *b = *itTextOut;b->update(window, time);itTextOut++;}window.display();}return 0;}Обновлённая версия с выводом пути в цвете.
У меня не знает что такое to_string
-
АвторСообщения
Для ответа в этой теме необходимо авторизоваться.