SFML 在随机固定路径中移动精灵

Question

所以我正在用 C++ 进行模拟，我正在使用 SFML 进行图形处理。我将在这里使用 this 图片来解释我想要做什么。所以这就是我面临的问题。我生成了一个对象（在入口处），我希望该对象移动到“1”。然后我想把它移到“4”。之后我想把它移到柜台“1”。现在您可以看到，标记为 1、2、3、4、5、6 的棕色货架应该有边界。柜台和墙壁也一样。我需要帮助的是定义这些边界或定义移动路径，以便对象从“1”移动到“4”以反“1”而不与任何东西发生碰撞。我可以对所有路径进行硬编码，但我的时间很短，而且代码会变得非常非常长。因此，如果有更简单的方法来执行此操作，请告诉。感谢大家的帮助，谢谢！

Answer 1

根据今天早些时候的评论展开。

让我们使用 Dijkstra 算法找到节点之间的路径。

首先我们需要定义一个节点，对于我们来说我们至少需要一个位置和邻居的容器，但是对于算法来说，有一个标志代表我们是否已经访问过节点，以及一个数字会有所帮助代表从开始算起的最短距离。这可能看起来像：

struct Node {
    Node(const sf::Vector2f& position) :
        position{ position },
        visited{}, tentative_distance{}
    {}
    sf::Vector2f position;
    bool visited;
    float tentative_distance;
};

它也有助于绘制节点及其与其邻居的连接，所以让我们继承 sf::Drawable 并编写一个函数来渲染节点。我还添加了一个高亮标志，用于突出显示最终路径。

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
            );
        }
    }
};

最后，我们将需要比较节点的距离，因此我们将编写一个成员函数来执行此操作。

...
float distance(Node& rhs) const {
    const auto delta = rhs.position - position;
    return sqrt(pow(delta.x, 2) + pow(delta.y, 2));
}
...

太棒了，我们现在可以存储节点并绘制它们了。让我们定义一个节点 class，它将包含我们的节点，并具有 Dijkstra 函数。再一次，我希望它是可绘制的，所以它也将继承自 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;
};

现在我们将创建一个构造函数来创建节点。我们可以通过多种方式创建节点。过去，我编写了工具来编辑节点并保存到 JSON 文件，但出于本示例的目的，我们将使用一个简单的构造函数来读取字符串并在每个 # 处创建一个节点在字符串中。请注意，如果您想连接节点 A 和节点 B，那么节点 A 必须在其邻居中有节点 B，反之亦然，您可能需要编写一个函数来确保这种双向连接。

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]);
            }
        }
    }
}

好的，现在让我们查看我们的节点。

太棒了。现在开始写算法。

我不打算解释算法，但我会实现它。

对于未来的任务，我建议使用改进的算法，例如基于 Dijkstra 算法的 A*。

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.

初始节点和目标节点在这里被硬编码！将索引或其他任何内容传递到函数中以允许调用两个节点之间的任何路径。

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.

请注意，我们现在需要将步骤 3、4、5 和 6 包装在一个循环中。

while (true) {
...
    current = smallest_tentative_distance;
}

这就是实现的算法！现在调用它！

万岁。这是最难的部分。我没有过多地测试我的代码，也没有优化它或任何东西，这只是一个例子，我建议你自己尝试。目前我们只是将结果可视化，但您应该能够弄清楚如何使某些东西遵循路径。

以前我把计算出的路径存储在一个位置容器中（路径中每个节点的位置），然后让物体向容器后面的位置移动，然后一旦对象已通过位置（x 或 y 符号已更改）弹出容器的背面并重复直到容器为空。

完整示例代码：

#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;
}

SFML 在随机固定路径中移动精灵

SFML moving sprite in random fixed paths

c++

algorithm

simulation

graphics

sfml