4
\$\begingroup\$

IMPORTANT: giving too big combination of node count and edge/neighbor count can overflow your RAM and swap file very quickly, thus I recommend staying below 500 on node count and below 50 on neighbor count.

Background

I had an assignment on generating multi dimensional maze, which I didn't submit in time. The assignment required Python 2.7 only with standard library and I had no idea what algorithm to choose.

Feeling miserable, I went to a lecture which explained backtracking with some node/value selection strategies (which turns out have been covered before). And after a few hours of sinking in the lecture, I was able to apply it on the problem.

Problem

Generate a maze with \$N\$ nodes, \$K < N\$ of which are border nodes. Each border must have degree of \$m\$, and each non-border node must have degree of \$p>m\$. The generated maze must be a minimally connected graph.

After generation of the graph is done, assign wall, hole, monster and gold properties to each node. Wall or hole has no effect on the graph structure of the maze! Every property has value of either \$1\$ or \$0\$. If monster is present on the node, make smell present as well. If there is hole in the node, make wind present as well.


Solution (algorithm)

Generate the nodes, assigning indices in increasing order. Partition the generated nodes, making first \$K\$ nodes border nodes, and the rest non-border nodes. At each step:

  1. Sort nodes (prefer nodes which have highest neighbor count filled in, and if the same, prefer border nodes, as this will put more constraining nodes first)

  2. Create a copy of nodes with satisfied nodes removed (the ones which have required degree), name it remaining

  3. Pick the front node (it is the most constraining node to start from, thus it allows to exit from erroneous branch of decision tree quicker), name it current_node

  4. first = remaining.rbegin(), last = prev(remaining.rend())

  5. While first != last

    5.1. Set next neighbor of current_node to *first, and neighbor of *first to current_node.

    5.2. Go to 1, save result in result.

    5.3 If result is not empty, it is the solution. Return it propagating from every level of recursion.

    5.4 If result is empty, pop a neighbor from current_node and *first

    5.5 Advance first.

  6. Return empty result

Do note that since neighbor is chosen from the least connected nodes, it guarantees that graph is minimally connected (well, at least I believe so).


Code

graph_node.hpp:

#ifndef MAZE_GENERATOR_GRAPH_NODE_HPP
#define MAZE_GENERATOR_GRAPH_NODE_HPP

#include <cstddef>
#include <vector>
#include <ostream>
#include <algorithm>

namespace shino {

    struct graph_node {
        std::size_t index;
        std::vector<std::size_t> neighbor_indices;
        std::size_t border_count;
        int gold;
        bool wall;
        double wind;
        double smell;
        bool monster;
        bool hole;
    };

    bool is_border_node(const graph_node& node) {
        return node.index < node.border_count;
    }

    bool operator>(const graph_node& lhs, const graph_node& rhs) {
        if (lhs.neighbor_indices.size() == rhs.neighbor_indices.size()) {
            bool is_lhs_border = is_border_node(lhs);
            bool is_rhs_border =  is_border_node(rhs);

            return is_lhs_border > is_rhs_border; //prefer borders
        } else {
            return lhs.neighbor_indices.size() < rhs.neighbor_indices.size();
        }
    }

    bool operator<(const graph_node& lhs, const graph_node& rhs) {
        return rhs > lhs;
    }

    std::ostream& operator<<(std::ostream& os, const graph_node& node) {
        os << "index: " << node.index << ' ' << "is border: " << is_border_node(node) << ", neighbors:{";
        if (node.neighbor_indices.empty())
            return os << '}';
        os << node.neighbor_indices.front();
        for (std::size_t i = 1; i < node.neighbor_indices.size(); ++i) {
            os << ',' << node.neighbor_indices[i];
        }

        return os << '}';
    }

    bool is_satisfied(const graph_node& node, std::size_t border_neighbor_count, std::size_t node_neighbor_count) {
        if (is_border_node(node))
            return node.neighbor_indices.size() == border_neighbor_count;
        else
            return node.neighbor_indices.size() == node_neighbor_count;
    }

    bool has_this_neighbor(const graph_node& node, std::size_t neighbor_index) {
        return !node.neighbor_indices.empty() and std::find_if(node.neighbor_indices.begin(), node.neighbor_indices.end(), [neighbor_index](auto&& neighbor){
            return neighbor == neighbor_index;
        }) != node.neighbor_indices.end();
    }
}

#endif //MAZE_GENERATOR_GRAPH_NODE_HPP

main.cpp:

#include <iostream>
#include <vector>
#include <queue>
#include <optional>
#include <algorithm>
#include <iterator>
#include <random>

#include "graph_node.hpp"

template <typename Compare = std::less<>>
using ranking = std::priority_queue<shino::graph_node, std::vector<shino::graph_node>, Compare>;

using maze = std::vector<shino::graph_node>;

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    os << "-----\n";
    for (auto&& elem: v) {
        os << elem << '\n';
    }
    return os << "-----\n\n";
}

maze generate_nodes(std::size_t node_count, std::size_t border_count) {
    maze nodes(node_count);
    for (std::size_t index = 0; index < node_count; ++index) {
        nodes[index].index = index;
        nodes[index].border_count = border_count;
    }

    return nodes;
}

std::optional<maze> generate_maze(const maze& nodes,
                   std::size_t border_neighbor_count,
                   std::size_t node_neighbor_count) {
    if (border_neighbor_count == 0)
        return {};
    auto new_nodes = nodes;
    auto remaining = new_nodes;
    auto new_end = std::remove_if(remaining.begin(), remaining.end(), [border_neighbor_count, node_neighbor_count](auto&& node) {
        return shino::is_satisfied(node, border_neighbor_count, node_neighbor_count);
    });
    remaining.erase(new_end, remaining.end());
    std::sort(remaining.begin(), remaining.end());

    if (remaining.empty())
        return new_nodes;

    auto& current_node = new_nodes[remaining.front().index];
    auto first = remaining.rbegin();
    auto last = std::prev(remaining.rend());
    while (first != last) {
        if (shino::has_this_neighbor(current_node, first->index)) {
            ++first;
            continue;
        }
        auto& candidate_neighbor = new_nodes[first->index];
        current_node.neighbor_indices.push_back(candidate_neighbor.index);
        candidate_neighbor.neighbor_indices.push_back(current_node.index);
        auto result = generate_maze(new_nodes, border_neighbor_count, node_neighbor_count);
        if (result.has_value())
            return result;
        current_node.neighbor_indices.pop_back();
        candidate_neighbor.neighbor_indices.pop_back();
        ++first;
    }

    return {}; //no solution found
}

void assign_properties(maze& nodes, double wall_probability, double hole_probability,
                       double monster_probability, double gold_probability) {
    std::mt19937 twister(std::random_device{}());
    std::bernoulli_distribution wall_distribution(wall_probability);
    std::bernoulli_distribution hole_distribution(hole_probability);
    std::bernoulli_distribution monster_distribution(monster_probability);
    std::bernoulli_distribution gold_distribution(gold_probability);

    for (auto&& node: nodes) {
        node.wall = wall_distribution(twister);
        node.hole = hole_distribution(twister);
        node.wind = node.hole;
        node.monster = monster_distribution(twister);
        node.smell = node.monster;
        node.gold = gold_distribution(twister);
    }
}

int main(int argc, char* argv[])
{
    if (argc != 9) {
        std::cerr << "usage: program node_count border_count border_edge_count non_border_edge_count "
                     "wall_probability hole_probability monster_probability gold_probability" << '\n';
        return -1;
    }

    std::size_t node_count = std::stoul(argv[1]);
    std::size_t border_count = std::stoul(argv[2]);
    std::size_t border_edge_count = std::stoul(argv[3]);
    std::size_t non_border_edge_count = std::stoul(argv[4]); //sometimes also referred as just node edge count

    double wall_probability = std::stod(argv[5], nullptr);
    double hole_probability = std::stod(argv[6], nullptr);
    double monster_probability = std::stod(argv[7], nullptr);
    double gold_probability = std::stod(argv[8], nullptr);

    auto nodes = generate_nodes(node_count, border_count);
    std::cout << nodes << '\n';
    auto found_solution = generate_maze(nodes, border_edge_count, non_border_edge_count);
    if (found_solution.has_value()) {
        auto solution = std::move(found_solution.value());
        assign_properties(solution, wall_probability, hole_probability, monster_probability, gold_probability);
        std::cout << "solution is:\n" << solution << '\n';
    } else {
        std::cout << "solution not found\n";
    }
}

Concerns

  1. It passes each node combination by value, and since recursion is quite deep, it overflows memory very quickly.

  2. Recursion depth is bound by edge count, which is much bigger than vertex count.

  3. In general performs more operations than necessary, but I didn't find any way to reduce those.

  4. It is extremely slow to detect absence of solution.

Feel free to comment on anything else!

\$\endgroup\$
2
\$\begingroup\$

Generally, this is a well-written program, so it was hard to find much fault with it. However, here are a few things that might help you improve your program.

Don't over-use const

I don't know if I've ever given this advice here. Much more frequently, I advise people to add more const but in this case, a significant improvement can be made by not using it. Here's how. The current code contains these lines:

std::optional<maze> generate_maze(const maze& nodes,
                   std::size_t border_neighbor_count,
                   std::size_t node_neighbor_count) {
    if (border_neighbor_count == 0)
        return {};
    auto new_nodes = nodes;

We're making a copy of nodes so we can manipulate the copy. Why not just pass it in as non-const and use it directly? Also, it probably makes little practical difference, but the other two passed parameters can be const:

std::optional<maze> generate_maze(maze& new_nodes,
                   const std::size_t border_neighbor_count,
                   const std::size_t node_neighbor_count) {
    if (border_neighbor_count == 0)
        return {};

Because of the recursion, this saves a great deal of memory and time. (On my machine, a 500-node graph took 3.58 seconds before and with this single change, takes 2.95 seconds.)

Avoid premature optimization

The has_this_neighbor checks to see if the neighbor_indices vector is empty before calling std::find_if. I think you'll find, if you look at the code for std::find_if that that first check is not needed and not helpful. Omit it for clarity -- there is no measurable performance difference on my machine.

Use static for variables common to all instances of a class

The border_count variable within the graph_node structure should be static because all class members share the same value.

Remove unused templates

The first template in main.cpp is not used and should be removed from the code.

Use member functions where appropriate

It seems to me that is_satisfied, is_border_node and has_this_neighbor would be more appropriate as member functions rather than standalone functions, given their nature.

Minimize memory usage

The first part of generate_maze includes these lines:

auto remaining = new_nodes;
auto new_end = std::remove_if(remaining.begin(), remaining.end(), [border_neighbor_count, node_neighbor_count](auto&& node) {
    return node.is_satisfied(border_neighbor_count, node_neighbor_count);
});
remaining.erase(new_end, remaining.end());

But why copy all of them, then erase some of them when you could use std::copy_if instead to only grab the ones you need?

maze remaining;
std::copy_if(new_nodes.begin(), new_nodes.end(), std::back_inserter(remaining), [border_neighbor_count, node_neighbor_count](auto &node) { 
    return !node.is_satisfied(border_neighbor_count, node_neighbor_count);

This also confers a performance improvement because graph_node is trivially copyable.

Use the appropriate data types

In the graph_node structure, it seems to me that wind and smell should be bool rather than double types. Also, gold should probably also be bool rather than int.

Use for rather than while where appropriate

The while loop within generate_maze would be better expressed as a for loop:

const auto last = std::prev(remaining.rend());
for (auto first = remaining.rbegin(); first != last; ++first) {
    // loop contents, omitting all ++first 
}

One could make it even simpler using a range-for and a reverse iterator adapter.

Define member functions to clarify algorithm

It is quite simple to write a function like this:

void connect(graph_node &other) {
    neighbor_indices.push_back(other.index);
    other.neighbor_indices.push_back(index);
}

We can also write a complementary disconnect function and an isConnected similar to your existing has_this_neighbor function but taking a reference. Now the contents of the for loop mentioned above can be written much more clearly:

if (!first->isConnected(current_node)) {
    auto& candidate_neighbor = new_nodes[first->index];
    candidate_neighbor.connect(current_node);
    auto result = generate_maze(new_nodes, border_neighbor_count, node_neighbor_count);
    if (result.has_value())
        return result;
    candidate_neighbor.disconnect(current_node);
}

Consider wrapping it all in an object

Although the problem description says to add all of the attributes at the end, the program carries them all around throughout the run, so one could assign them at the beginning with the same result. I'd suggest make a Maze object that does the equivalent of generate_nodes and assign_properties in the constructor, and making generate_maze a member function. It would make the interface cleaner and easier to understand and may provide a small performance increase since each node need only be touched once at the beginning of the run rather than both before and after.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.