Witaj!
tBane dodał nowy post w wątku: Algorytm znajdowania ścieżki
Cześć! :D
Udało mi się zrozumieć i napisać samemu od podstaw algorytm znajdujący ścieżkę pomiędzy dwoma punktami.
Algorytm żeby nie był zbyt monotonny czasem znajduje ścieżkę kierując się w górę, a czasem w dół :-) Dzięki czemu ścieżki są różnorodne :-) Oto mój algorytm - Pathfinding by tBane :-)
Kopiuj
void Path::generatePath() { enum Direction { Top, Bottom }; Direction direction = Direction(rand() % 2); std::vector<std::vector<sf::Vector2i>> paths; std::vector<std::vector<bool>> visited(mapa->_size.y, std::vector<bool>(mapa->_size.x, false)); paths.push_back({ _startPoint }); while (!paths.empty()) { std::vector<sf::Vector2i> path = paths.front(); paths.erase(paths.begin()); sf::Vector2i point = path.back(); if (point.x < 0 || point.y < 0 || point.x >= mapa->_size.x || point.y >= mapa->_size.y) continue; if (visited[point.y][point.x]) continue; visited[point.y][point.x] = true; if (point == _endPoint) { _pathPoints = path; return; } if (direction == Direction::Top) { std::vector<sf::Vector2i> top = path; top.push_back({ point.x, point.y - 1 }); paths.push_back(top); std::vector<sf::Vector2i> bottom = path; bottom.push_back({ point.x, point.y + 1 }); paths.push_back(bottom); } else { std::vector<sf::Vector2i> bottom = path; bottom.push_back({ point.x, point.y + 1 }); paths.push_back(bottom); std::vector<sf::Vector2i> top = path; top.push_back({ point.x, point.y - 1 }); paths.push_back(top); } std::vector<sf::Vector2i> right = path; right.push_back({ point.x + 1, point.y }); paths.push_back(right); std::vector<sf::Vector2i> left = path; left.push_back({ point.x - 1, point.y }); paths.push_back(left); } _pathPoints.clear(); }
Z poważaniem,
4programmers.net
|
