3D-Rush-Hour-Solver/src/utils/utils.hpp at ce972857079c284d46ca7a32d8ae6ef664cc4cb2 · himanusia/3D-Rush-Hour-Solver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#pragma once

#include <godot_cpp/variant/utility_functions.hpp>
#include <godot_cpp/variant/string.hpp>

#include <algorithm>
#include <chrono>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <functional>

using namespace std;
using namespace godot;

enum AlgoType {
    BFS,
    UCS,
    ASTAR,
};

struct Coordinates {
    int x;
    int y;

    bool operator<(const Coordinates& other) const {
        if (x != other.x) {
            return x < other.x;
        }
        return y < other.y;
    }

    bool operator==(const Coordinates& other) const {
        return x == other.x && y == other.y;
    }

    bool operator!=(const Coordinates& other) const {
        return !(*this == other);
    }
};

struct Piece {
    char id;
    Coordinates coordinates;
    int size;
    bool is_vertical;
    bool is_primary;
};

struct Board {
    int rows;
    int cols;
    int other_pieces_count;
    int pixel_size;
    int pixel_padding;
    Coordinates exit_coordinates;

    vector<vector<char>> grid;
    int piece_padding = 1;
};

struct PieceMove {
    Coordinates old_coordinates;
    Coordinates new_coordinates;
};

struct Solution {
    vector<PieceMove> moves;
    chrono::duration<double, milli> duration;
    int node;
    bool is_solved;
    Solution() : node(0), is_solved(false) {}
};

struct SearchNode {
    vector<Piece> pieces;
    Board board;
    vector<PieceMove> path;
    int val;

    char piece_moved;
    Coordinates original_position;

    SearchNode(const vector<Piece>& p, const Board& b, const vector<PieceMove>& path, int v, char pid = ' ', Coordinates opos = {-1,-1}) : pieces(p), board(b), path(path), val(v), piece_moved(pid), original_position(opos) {}

    bool operator>(const SearchNode& other) const {
        return val > other.val;
    }
};

class Utils {
public:
    static void print_board(Board& board,  vector<Piece>& pieces);
    static godot::String stringToGodotString(const string& stdString);
    static string godotStringToString(const godot::String& godotString);

    static int calculate(const Board& initial_board, const vector<Piece>& current_pieces);
    static bool is_exit(const Board& initial_board, const vector<Piece>& current_pieces);

    // helper function
    static const Piece* get_primary_piece(const vector<Piece>& pieces_list);
    static string state_to_string(const vector<Piece>& current_pieces);
    static bool is_cell_clear(const Board& initial_board, int r_check, int c_check, const vector<Piece>& pieces_in_state, char moving_piece_id);
    using ValueCalculator = function<int(const Board& board_state, const vector<Piece>& next_pieces_state, const SearchNode& parent_node)>;
    static vector<SearchNode> generate_next(const SearchNode& current_node, ValueCalculator calculate_node_value);

    struct SearchParams {
        string algorithm_name;
        function<int(const Board&, const vector<Piece>&)> calculate_initial_val;
        ValueCalculator successor_val;
        function<godot::String(const SearchNode&)> get_node_exploration;
        function<godot::String(const SearchNode&, const Solution&)> get_solution_details;
    };

    static Solution search(const Board& initial_board, const vector<Piece>& initial_pieces, const SearchParams& params);
};