3
\$\begingroup\$

Overview

I am constructing a Graph with randomly generated nodes called Positions. The Graph has a width and a height and is represented using an adjacency list std::map<std::pair<int, int>, mrrobo::Position> m_maze;, that are open, closed, and may not have a route back to the root. I want to find a single path to the Position with an x value of width - 1 of and y value of height - 1, the end of the maze. If not possible I return an empty array. Also, the generation of the maze Positions is handled by a function managed by another developer namespace called bool otherns::generate_postion(int x, int y) so that's abstracted and given to my code in an assumed valid state.

The primary feedback I'm looking for is with my implementation of graph search in Graph::search(). As well as how I determine possible_edge = { {x, y-1}, {x-1, y}, {x+1, y}, {x, y+1} } in my Graph::get_position_edges() function. Using C++17 features I want to find ways to optimize this graph search if possible.

Main.cpp

#include <iostream>

#include "graph.cpp"

int main()
{
    mrrobo::Graph graph;
    std::cout << "width: " << graph.width() << '\n';
    std::cout << "height: " << graph.height() << '\n';

    graph.get_position_edges();
    graph.search();

    return 0;
}

Graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <stdio.h>
#include <string>
#include <sstream>
#include <map>

namespace mrrobo
{
    struct Position
    {
        int x;
        int y;
        bool is_open;
        bool is_visited;
        std::vector<Position> edges;
    };
    class Graph
    {
        private:
            int m_height;
            int m_width;
        public:
            Graph();
            std::map<std::pair<int, int>, mrrobo::Position> m_graph;
            int width();
            int height();
            void get_position_edges();
            void search();
    };
}

#endif /* GRAPH_H */

Graph.cpp

#include "graph.h"

mrrobo::Graph::Graph() {
    otherns::set_width_and_height();
}

int mrrobo::Graph::width() { return m_width; }
int mrrobo::Graph::height() { return m_height; }

void mrrobo::Graph::get_position_edges() {
    std::ostringstream oss;

    std::vector<std::pair<int, int>> open_postions;
    mrrobo::Position p;
    p.is_visited = false;
    for (int y = 0; y < m_height; ++y) {
        for (int x = 0; x < m_width; ++x) {
            bool result = otherns::generate_postion(x,y);
            if(result) {
                p.is_open = true;
                m_graph.insert( {{x,y}, p} );
                open_postions.push_back({x,y});
                oss << "○ ";
            } else {
                p.is_open = false;
                m_graph.insert( {{x,y}, p} );
                oss << "● ";
            }
        }
        oss << '\n';
    }
    std::cout << '\n' << oss.str() << '\n';

    for(int n=0; n < open_postions.size(); ++n) {
        int x = open_postions[n].first;
        int y = open_postions[n].second;
        std::vector<std::pair<int, int>> possible_edge = { {x, y-1}, {x-1, y}, {x+1, y}, {x, y+1} };
        for(int i=0; i < possible_edge.size(); ++i) {
            int x_edge = possible_edge[i].first;
            int y_edge = possible_edge[i].second;

            if((x_edge > -1 && x_edge < m_width + 1) &&
                (y_edge > -1 && y_edge < m_height + 1) &&
                m_graph[{x_edge, y_edge}].is_open) {

                    m_graph[{x,y}].edges.push_back( {x_edge, y_edge} );
            }
        }
    }
}

void mrrobo::Graph::search() {
    std::stack<std::pair<int,int>> reversed_path;
    int x = 0;
    int y = 0;
    bool dead_end = true;

    if(m_graph[{x,y}].is_open) {
        reversed_path.push({x,y});
        while((x < m_width || y < m_height) && !reversed_path.empty()) {
            if(x == m_width - 1 && y == m_height - 1) {
                m_graph[{x,y}].is_visited = true;
                reversed_path.push({x,y});
                break;
            }
            dead_end = true;
            for(auto edge : m_graph[{x,y}].edges) {
                if(m_graph[{edge.x,edge.y}].is_open && m_graph[{edge.x,edge.y}].is_visited == false) {
                    m_graph[{x,y}].is_visited = true;
                    reversed_path.push({x,y});
                    x = edge.x;
                    y = edge.y;
                    dead_end = false;
                    break;
                }
            }
            if(dead_end) {
                m_graph[{x,y}].is_visited = true;
                x = reversed_path.top().first;
                y = reversed_path.top().second;
                reversed_path.pop();
            }
        }
    }

    std::stringstream solution_stream;
    if(reversed_path.empty()) {
        solution_stream << "[]";
    }
    else {
        std::stack<std::pair<int,int>> path;
        while(reversed_path.empty() == false) {
            path.push(reversed_path.top());
            reversed_path.pop();
        }
        solution_stream << '[';
        path.pop();
        while(path.empty() ==  false) {
            x = path.top().first;
            y = path.top().second;
            if(x != m_width - 1 || y != m_width - 1) {
                solution_stream << "{\"x\": " << x << ", \"y\": " << y << "}, ";
            } else {
                solution_stream << "{\"x\": " << x << ", \"y\": " << y << "}";
            }
            path.pop();
        }
        solution_stream << ']';
    }

    std::cout << solution_stream.str() << '\n';
}

Sample output

width: 6
height: 6

○ ○ ● ○ ○ ○
○ ● ○ ● ● ○
○ ● ○ ● ● ●
○ ○ ○ ○ ○ ○
● ● ● ● ● ○
○ ○ ○ ○ ○ ○

[{"x": 0, "y": 0}, {"x": 0, "y": 1}, {"x": 0, "y": 2}, {"x": 0, "y": 3}, {"x": 1, "y": 3}, {"x": 2, "y": 3}, {"x": 3, "y": 3}, {"x": 4, "y": 3}, {"x": 5, "y": 3}, {"x": 5, "y": 4}, {"x": 5, "y": 5}]
\$\endgroup\$
  • 1
    \$\begingroup\$ mrrobo::Garph graph; Does this really work? \$\endgroup\$ – yuri Jun 3 at 19:33
  • \$\begingroup\$ Yes is there a syntax error here? \$\endgroup\$ – greg Jun 3 at 19:37
  • \$\begingroup\$ No, just a typo: Garph. \$\endgroup\$ – vnp Jun 3 at 19:38
  • \$\begingroup\$ Fixed it, must have been a copy paste error when formatting the code \$\endgroup\$ – greg Jun 3 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.