So I am making a simulation in C++ and I am using SFML for graphics. I am going to use this image here to explain what I am trying to do. So here's the issue I am facing. I spawn an object (at entry) and I want that object to move to '1'. Then I would like to move it to '4'. After that I would like to move it to the counter '1'. Now as you can see, the brown shelves labelled 1,2,3,4,5,6 are supposed to have boundaries. Same for the counter and walls as well. What I need help is in defining these boundaries OR defining movement paths so that the object moves from '1' to '4' to counter '1' without colliding with anything. I could hard-code all the paths but I am short on time and the code will get really really long. So if there is a simpler way to do this then please do tell. I appreciate all the help, thank you!
0
votes
Please post a Minimum Reproducible Example of what you have so far.
– GaryNLOL
For the movement path could you use Dijkstra's algorithm? Have a node at all the places you want to go, connect the nodes together, then when you want to move from one place to another call the algorithm and it will give you the path, then just follow the path. The nodes might look like: i.stack.imgur.com/1I5cn.jpg
– Lily
@GaryNLOL I literally have nothing so far when it comes to the movement of the object. I have been trying to visualize and think logics for this.
– Zereff
@Lily Thanks for the visualization. I will try the algorithm
– Zereff
1 Answers
0
votes
Expanding from comment earlier today.
Let us use Dijkstra's algorithm to find a path between nodes.
First we need to define a Node, for us we at least need a position and container of neighbours, but for the algorithm it would help to have a flag representing whether we have visited the Node or not, and a number to represent the shortest distance calculated from the start so far. This might look like:
struct Node {
Node(const sf::Vector2f& position) :
position{ position },
visited{}, tentative_distance{}
{}
sf::Vector2f position;
bool visited;
float tentative_distance;
};
It would also help be able to draw a node and it's connection to it's neighbours, so let's inherit from sf::Drawable and write a function to render the node. I also add a highlight flag for rendering the final path highlighted.
struct Node : public sf::Drawable {
Node(const sf::Vector2f& position) :
position{ position },
visited{}, tentative_distance{}, highlight{}
{}
sf::Vector2f position;
bool visited;
float tentative_distance;
bool highlight;
std::vector<Node*> neighbours;
private:
void draw(sf::RenderTarget& target, sf::RenderStates states) const {
// draw node circle
constexpr auto radius = 8.f;
auto color =
highlight ? sf::Color::White : sf::Color(127, 127, 127);
sf::CircleShape shape(radius);
shape.setOrigin({ radius, radius });
shape.setPosition(position);
shape.setFillColor(color);
target.draw(shape, states);
// draw lines to neighbours
for (const auto& neighbour : neighbours) {
color =
highlight && neighbour->highlight ?
sf::Color::White :
sf::Color(127, 127, 127);
sf::Vector2f delta = neighbour->position - position;
sf::Vertex line[] = {
{ position, color },
{ position + delta / 2.f, color }
};
target.draw(
line,
2,
sf::Lines
);
}
}
};
Finally, we are going to need to compare the distance of Nodes, so we'll write a member function that does this.
...
float distance(Node& rhs) const {
const auto delta = rhs.position - position;
return sqrt(pow(delta.x, 2) + pow(delta.y, 2));
}
...
Awesome, we can now stores Nodes and draw them. Let's define a Nodes class that will contain our Nodes, and have the Dijkstra function. Once again, I want it to be drawable, so it will also inherit from sf::Drawable.
class Nodes : public sf::Drawable {
public:
void dijkstra() {
// todo: algorithm
}
private:
void draw(sf::RenderTarget& target, sf::RenderStates states) const {
for (const auto& node : nodes) {
target.draw(node, states);
}
}
std::vector<Node> nodes;
};
Now we will create a constructor that will create the nodes. There are soooo many ways we could create the nodes. In the past, I have written tools to edit nodes and save to a JSON file, but for the purposes of this example we will use a simple constructor that reads a string and creates a node at every # in the string. Note that if you want to connect Node A and Node B then Node A has to have Node B in it's neighbours and vice versa, you might want to write a function to ensure this two way connection.
Nodes() {
// create maze (for testing purposes)
const std::string maze{ R"(#####
# #
#####
# #
# ###
# #
####
#
#### )" };
// create nodes
sf::Vector2f position;
constexpr auto increment = 32.f;
for (const auto character : maze) {
switch (character) {
case '\n':
position.x = 0.f;
position.y += increment;
break;
case '#':
nodes.emplace_back(position);
case ' ':
position.x += increment;
break;
}
}
// connect to neighbours
for (size_t i = 0; i < nodes.size(); ++i) {
for (size_t j = i + 1; j < nodes.size(); ++j) {
if (nodes[i].distance(nodes[j]) <= increment + 1.f) {
nodes[i].neighbours.push_back(&nodes[j]);
nodes[j].neighbours.push_back(&nodes[i]);
}
}
}
}
Ok, now lets view our nodes.
Fantastic. Now to start writing the algorithm.
I am not going to explain the algorithm, but I will implement it.
For a future task I suggest used an improved algorithm like A* which builds on Dijkstra's algorithm.
- Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
unordered_set<Node*> unvisited;
for (auto& node : nodes) {
node.visited = false;
node.highlight = false;
unvisited.insert(&node);
}
- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. Set the initial node as current.
Initial node and destination node are hardcoded here! Pass in the indexes or whatever into the function to allow any path between two nodes to be called.
Node& initial = nodes.front();
Node& destination = nodes.back();
initial.tentative_distance = 0.f;
constexpr auto infinity = std::numeric_limits<float>::infinity();
for (size_t i = 1; i < nodes.size(); ++i) {
nodes[i].tentative_distance = infinity;
}
Node* current = &initial;
- For the current node, consider all of its unvisited neighbours and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbour B has length 2, then the distance to B through A will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, the current value will be kept.
for (auto* neighbour : current->neighbours) {
if (neighbour->visited) {
continue;
}
// Compare the newly calculated tentative distance to the
// current assigned value and assign the smaller one.
const auto neighbour_distance = current->distance(*neighbour);
neighbour->tentative_distance = std::min(
neighbour->tentative_distance,
current->tentative_distance + neighbour_distance
);
}
- When we are done considering all of the unvisited neighbours of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
current->visited = true;
unvisited.erase(current);
- If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
Node* smallest_tentative_distance{};
for (auto* node : unvisited) {
if (
!smallest_tentative_distance ||
node->tentative_distance <
smallest_tentative_distance->tentative_distance
) {
smallest_tentative_distance = node;
}
}
if (destination.visited) {
// trace path back and highlight it
while (current != &initial) {
current->highlight = true;
Node* smallest_distance{};
for (auto* node : current->neighbours) {
if (
!smallest_distance ||
node->tentative_distance <
smallest_distance->tentative_distance
) {
smallest_distance = node;
}
}
current = smallest_distance;
}
current->highlight = true;
break;
}
if (smallest_tentative_distance->tentative_distance == infinity) {
break;
}
- Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.
Note we now need to wrap step 3, 4, 5 and 6 in a loop.
while (true) {
...
current = smallest_tentative_distance;
}
That's the algorithm implemented! Now to call it!
Hooray. That's the hard part done. I have not tested my code too much, nor optimised it or anything, it is all just an example, I suggest you make your own attempt. Currently we are just visualising the results, but you should be able to figure out how to make something follow the path.
In the past I've stored the calculated path in a container of positions (the position of each node in the path), and then had the object move towards the position at the back of the container, then once the object had passed the position (x or y sign changed) pop the back of the container and repeat until the container is empty.
Full example code:
#include <SFML/Graphics.hpp>
#include <vector>
#include <unordered_set>
struct Node : public sf::Drawable {
Node(const sf::Vector2f& position) :
position{ position },
visited{}, tentative_distance{}, highlight{}
{}
sf::Vector2f position;
bool visited;
float tentative_distance;
bool highlight;
std::vector<Node*> neighbours;
/// returns distance between this node and passed in node
float distance(Node& rhs) const {
const auto delta = rhs.position - position;
return sqrt(pow(delta.x, 2) + pow(delta.y, 2));
}
private:
void draw(sf::RenderTarget& target, sf::RenderStates states) const {
// draw node circle
constexpr auto radius = 8.f;
auto color =
highlight ? sf::Color::White : sf::Color(127, 127, 127);
sf::CircleShape shape(radius);
shape.setOrigin({ radius, radius });
shape.setPosition(position);
shape.setFillColor(color);
target.draw(shape, states);
// draw lines to neighbours
for (const auto& neighbour : neighbours) {
color =
highlight && neighbour->highlight ?
sf::Color::White :
sf::Color(127, 127, 127);
sf::Vector2f delta = neighbour->position - position;
sf::Vertex line[] = {
{ position, color },
{ position + delta / 2.f, color }
};
target.draw(
line,
2,
sf::Lines
);
}
}
};
class Nodes : public sf::Drawable {
public:
Nodes() {
// create maze (for testing purposes)
const std::string maze{ R"(#####
# #
#####
# #
# ###
# #
####
#
#### )" };
// create nodes
sf::Vector2f position;
constexpr auto increment = 32.f;
for (const auto character : maze) {
switch (character) {
case '\n':
position.x = 0.f;
position.y += increment;
break;
case '#':
nodes.emplace_back(position);
case ' ':
position.x += increment;
break;
}
}
// connect to neighbours
for (size_t i = 0; i < nodes.size(); ++i) {
for (size_t j = i + 1; j < nodes.size(); ++j) {
if (nodes[i].distance(nodes[j]) <= increment + 1.f) {
nodes[i].neighbours.push_back(&nodes[j]);
nodes[j].neighbours.push_back(&nodes[i]);
}
}
}
}
void dijkstra() {
using namespace std;
// 1. Mark all nodes unvisited.
// Create a set of all the unvisited nodes called the unvisited set.
unordered_set<Node*> unvisited;
for (auto& node : nodes) {
node.visited = false;
node.highlight = false;
unvisited.insert(&node);
}
// 2. Assign to every node a tentative distance value:
// set it to zero for our initial node
// and to infinity for all other nodes.
Node& initial = nodes.front();
Node& destination = nodes.back();
initial.tentative_distance = 0.f;
constexpr auto infinity = std::numeric_limits<float>::infinity();
for (size_t i = 1; i < nodes.size(); ++i) {
nodes[i].tentative_distance = infinity;
}
// Set the initial node as current.
Node* current = &initial;
while (true) {
// 3. For the current node, consider all of its unvisited neighbours
// and calculate their tentative distances through the current node.
for (auto* neighbour : current->neighbours) {
if (neighbour->visited) {
continue;
}
// Compare the newly calculated tentative distance to the
// current assigned value and assign the smaller one.
const auto neighbour_distance = current->distance(*neighbour);
neighbour->tentative_distance = std::min(
neighbour->tentative_distance,
current->tentative_distance + neighbour_distance
);
}
// 4. When we are done considering all of the unvisited neighbours
// of the current node, mark the current node as visited and remove
// it from the unvisited set.
current->visited = true;
unvisited.erase(current);
// 5. If the destination node has been marked visited
// (when planning a route between two specific nodes) or
// if the smallest tentative distance among the nodes in the
// unvisited set is infinity (when planning a complete traversal;
// occurs when there is no connection between the initial node and
// remaining unvisited nodes), then stop.
// The algorithm has finished.
Node* smallest_tentative_distance{};
for (auto* node : unvisited) {
if (
!smallest_tentative_distance ||
node->tentative_distance <
smallest_tentative_distance->tentative_distance
) {
smallest_tentative_distance = node;
}
}
if (destination.visited) {
// trace path back and highlight it
while (current != &initial) {
current->highlight = true;
Node* smallest_distance{};
for (auto* node : current->neighbours) {
if (
!smallest_distance ||
node->tentative_distance <
smallest_distance->tentative_distance
) {
smallest_distance = node;
}
}
current = smallest_distance;
}
current->highlight = true;
break;
}
if (smallest_tentative_distance->tentative_distance == infinity) {
break;
}
// 6. Otherwise, select the unvisited node that is marked with the
// smallest tentative distance, set it as the new "current node",
// and go back to step 3.
current = smallest_tentative_distance;
}
}
private:
void draw(sf::RenderTarget& target, sf::RenderStates states) const {
for (const auto& node : nodes) {
target.draw(node, states);
}
}
std::vector<Node> nodes;
};
int main() {
using namespace std;
Nodes nodes;
nodes.dijkstra();
sf::RenderWindow window(
sf::VideoMode(240, 360),
"Dijkstra!",
sf::Style::Default,
sf::ContextSettings(0, 0, 8)
);
window.setView({ { 64.f, 128.f }, { 240.f, 360.f } });
while (window.isOpen()) {
sf::Event event;
while (window.pollEvent(event)) {
if (event.type == sf::Event::Closed)
window.close();
}
window.clear();
window.draw(nodes);
window.display();
}
return 0;
}
