Блог

Итак, я делаю симуляцию на C и использую SFML для графики. Я собираюсь использовать это изображение здесь, чтобы объяснить, что я пытаюсь сделать. Итак, вот проблема, с которой я столкнулся. Я создаю объект (при входе) и хочу, чтобы этот объект переместился на ‘1’. Затем я хотел бы переместить его на ‘4’. После этого я хотел бы переместить его на счетчик ‘1’. Теперь, как вы можете видеть, коричневые полки, помеченные как 1,2,3,4,5,6, должны иметь границы. То же самое для счетчика и стен. Мне нужна помощь в определении этих границ или определении путей перемещения, чтобы объект перемещался с «1» на «4», чтобы противостоять «1», не сталкиваясь ни с чем. Я мог бы жестко запрограммировать все пути, но у меня мало времени, и код станет действительно длинным. Итак, если есть более простой способ сделать это, пожалуйста, сообщите. Я ценю всю помощь, спасибо!

Расширение из комментария ранее сегодня.

Давайте воспользуемся алгоритмом Дейкстры, чтобы найти путь между узлами.

Сначала нам нужно определить узел, для нас нам, по крайней мере, нужна позиция и контейнер соседей, но для алгоритма было бы полезно иметь флаг, представляющий, посещали ли мы узел или нет, и число для представления кратчайшего расстояния, вычисленного с начала до сих пор. Это может выглядеть так:

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

Это также помогло бы иметь возможность рисовать узел и его соединение с его соседями, поэтому давайте унаследуем sf::Drawable и напишем функцию для визуализации узла. Я также добавляю флаг выделения для выделения конечного пути.

 struct Node : public sf::Drawable {
Node(const sf::Vector2famp; 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::RenderTargetamp; 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 autoamp; neighbour : neighbours) {
            color =
                highlight amp;amp; 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(Nodeamp; rhs) const {
    const auto delta = rhs.position - position;
    return sqrt(pow(delta.x, 2)   pow(delta.y, 2));
}
...
 

Потрясающе, теперь мы можем сохранять узлы и рисовать их.
Давайте определим класс узлов, который будет содержать наши узлы и иметь функцию Дейкстры. Еще раз, я хочу, чтобы он был доступен для рисования, поэтому он также будет наследоваться от sf::Drawable .

 class Nodes : public sf::Drawable {
public:
    void dijkstra() {
        // todo: algorithm
    }
private:
    void draw(sf::RenderTargetamp; target, sf::RenderStates states) const {
        for (const autoamp; 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(amp;nodes[j]);
                nodes[j].neighbours.push_back(amp;nodes[i]);
            }
        }
    }
}
 

Хорошо, теперь давайте посмотрим на наши узлы.

Фантастика. Теперь приступим к написанию алгоритма.

Я не собираюсь объяснять алгоритм, но я его реализую.

Для будущей задачи я предлагаю использовать улучшенный алгоритм, такой как A *, который основан на алгоритме Дейкстры.

1. Отметьте все узлы, которые не посещались. Создайте набор всех непросмотренных узлов, называемый непросмотренным набором.

 unordered_set<Node*> unvisited;
for (autoamp; node : nodes) {
    node.visited = false;
    node.highlight = false;
    unvisited.insert(amp;node);
}
 

2. Назначьте каждому узлу предварительное значение расстояния: установите его равным нулю для нашего начального узла и бесконечности для всех остальных узлов. Установите начальный узел как текущий.

Начальный узел и конечный узел здесь жестко запрограммированы!Передайте индексы или что-то еще в функцию, чтобы разрешить вызов любого пути между двумя узлами.

 Nodeamp; initial = nodes.front();
Nodeamp; 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 = amp;initial;
 

3. Для текущего узла рассмотрите всех его не посещенных соседей и вычислите их ориентировочные расстояния до текущего узла. Сравните недавно рассчитанное ориентировочное расстояние с текущим присвоенным значением и назначьте меньшее. Например, если текущий узел A отмечен расстоянием 6, а ребро, соединяющее его с соседним B, имеет длину 2, то расстояние до B через A будет 6 2 = 8. Если B ранее был отмечен расстоянием, превышающим 8, измените его на 8. В противном случае текущее значение будет сохранено.

 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. Когда мы закончим рассмотрение всех непросмотренных соседей текущего узла, пометьте текущий узел как посещенный и удалите его из набора непросмотренных. Посещенный узел больше никогда не будет проверен.

 current->visited = true;
unvisited.erase(current);
 

5. Если конечный узел отмечен как посещенный (при планировании маршрута между двумя конкретными узлами) или если наименьшее ориентировочное расстояние между узлами в наборе непросмотренных равно бесконечности (при планировании полного обхода; происходит, когда нет связи между начальным узлом и оставшимися непросмотренными узлами), затем остановитесь. Алгоритм завершен.

 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 != amp;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. В противном случае выберите непросмотренный узел, который отмечен наименьшим предварительным расстоянием, установите его в качестве нового «текущего узла» и вернитесь к шагу 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::Vector2famp; 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(Nodeamp; rhs) const {
        const auto delta = rhs.position - position;
        return sqrt(pow(delta.x, 2)   pow(delta.y, 2));
    }
private:
    void draw(sf::RenderTargetamp; 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 autoamp; neighbour : neighbours) {
            color =
                highlight amp;amp; 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(amp;nodes[j]);
                    nodes[j].neighbours.push_back(amp;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 (autoamp; node : nodes) {
            node.visited = false;
            node.highlight = false;
            unvisited.insert(amp;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.
        Nodeamp; initial = nodes.front();
        Nodeamp; 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 = amp;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 != amp;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::RenderTargetamp; target, sf::RenderStates states) const {
        for (const autoamp; 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;
}