bogdan's (micro)blog

01:42 pm on Oct 7, 2018 | #more | tags: howto

in this post i’ll use C to construct a maze, that will be later used for my swarm experiments.

i’ll be using a graph-model for the maze: each vertex is a room from the maze, which is connected by edges to other rooms. in a 2-D classic maze of size m×n, with m spanning from top to bottom and n spanning from left to right, each room has at most 4 neighbors. this means each vertex in my graph will have at most 4 edges: top, bottom, left and right. the total number of edges is m×(n-1) for vertical edges (top, bottom) and (m-1)×n for horizontal edges (left, right). in order to create a maze, in the previously described graph, i’ll choose using a version of Dijkstra algorithm a maximum spanning tree. to make the maze random, i’ll mark each edge with a random weight and then run the maximum spanning tree algorithm.

i’ll be using matrices as data structures. this means that each vertex will be labeled with a pair (i,j) with i from 0 to m-1 and j from 0 to n-1. as the graph is not oriented, i’ll have:

- if (i,j) is linked to (i,j+1), than i’ll store in my matrix, on position (i,j) the weight of the edge [(i,j),(i,j+1)];
- if (i,j) is linked to (i+1,j), than i’ll store in my matrix, on position (i,j+n) the weight of the edge [(i,j),(i+1,j)];
- no need to store the [(i,j),(i,j-1)] edge as it’s equivalent to [(i,(j-1)),(i,(j-1)+1)];
- also, no need to store connections at the lower and right edge of the maze;

the number of required edges’ weights can be held in a m×(2×n-1)-n vector, corresponding to an incomplete m×(2×n-1) matrix.

this step is quite easy. just loop over all m×(2×n-1)-n and assign them a random value between 1 and 255. i’ll be using 0 to represent edges that are missing.

/** * the function initializes the weights matrix as described above; * @param m (int) the dimension of the maze on top-bottom axis; * @param n (int) the dimension of the maze on left-right axis; * @returns: an uint8_t matrix, of size (m-1)*2*(n-1) filled with random data; */ uint8_t * maze_weight_init (int m, int n) { /** @var maze the weight matrix */ uint8_t * maze; /** @var c is a variable index */ int c; /** i reserve the space in the computer memory for the matrix */ maze = (uint8_t *) malloc ((m * (2 * n - 1) - n) * sizeof (uint8_t)); /** if memory reservation is successful, i'm filling the matrix */ if (maze != NULL) for (c = 0; c < m * (2 * n - 1) - n; c++) *(maze + c) = (uint8_t) ((1 + rand ()) % 256); return maze; }

**tip:**

the matrix is stored as a single vector, meaning a cell on the position (i,j) can be accessed by finding as the (i×cols+j)-th component of the vector. this map is bijective, meaning that the i-th component of the vector corresponds to position (i/cols, i%cols) in the matrix, where / is the integer division and % is the reminder operator.

the matrix is not useful like this. it needs to be sorted. i'm using a simple (inefficient) bubble sort algorithm. i'll take advantage of how i stored the matrix so i can simply arrange the associated vector. i'll create a vector into which i'll keep the association of indices.

bubble sort works like this: take the first weight from the vector, and if it's heavier that the one above, swap their places. this has to be repeated until the entire vector is sorted: this happens when there are no swaps on a swipe.

/** the function is sorting the associated vector V, returning a mapping of the * sorted indices, M, with V(i) being the original vector, while V(M(i)) is the sorted one * @param weights (uint8_t *) is the original vector * @param m (int) is the top-bottom size of the maze * @param n (int) is the left-right size of the maze * @returns: an int mapping vector between the sorted version and the original one */ int * maze_edges_sort (uint8_t * weights, int m, int n) { /** @var indices the vector containing the sorted mapping */ int * indices; /** * @var c a variable index * @var t a temporary variable used in swapping two indices * @var o a temporary variable storing last index swapped * @var l, initially the length of the weights vector, * after, the length of the unsorted vector */ int c, t, o, l = m * (2 * n - 1) - n; /** initialize indices with an identity mapping i->i */ indices = (int *) malloc (l * sizeof (int *)); for (c = 0; c < l; c++) *(indices + c) = c; if (indices != NULL) /** while there's still some unsorted part of the vector */ while (l > 0) { /** o holds the last swapped value */ o = 0; /** i'm looping until the end of the unsorted vector */ for (c = 1; c < l; c++) { /** if the weights don't respect the sort order, swap them */ if (*(weights + *(indices + c - 1)) > *(weights + *(indices + c))) { /** * of course, i'm swapping indices in the mapping, * not real values, as the initial vector remains * unchanged, only the mapping function deviates from * identity map */ t = *(indices + c - 1); *(indices + c - 1) = *(indices + c); *(indices + c) = t; /** store the last swapped index */ o = c; } } /** the length of the unsorted vector equals the last swapped index */ l = o; } return indices; }

this algorithm is more complex that the previous ones. for easier understanding, i need to explain some notions:

- a graph is a collection of vertices and edges, each edge connecting two vertices; it can and usually has loops - meaning starting from one vertex, it can be reached again going edge-by-edge; like a city with ring-roads;
- a tree is a graph with no loops; it means that starting with a vertex, and going edge-by-edge you'll never get to the same vertex again; like a computer network;
- in a graph (including a tree), a sub-tree is a collection of vertices and edges from the initial graph that behave like a tree - there are no loops;

i'll start with an empty set of sub-trees from the original graph. this will be called a forest set. forests have at least one tree. at the end of the algorithm i'll have in this set a tree that will link all vertices from the original graph. this is called a maximum spanning tree.

with each sorted edge, lighter to heavier, i'll do the following:

- if the edge is not connected to any sub-tree from my sub-tree set, i'll add the edge to the sub-tree set, coloring it with a new color;
- if the edge has one vertex connected to a sub-tree in my sub-tree set, i'll add the edge to the sub-tree set, coloring it with the same color as the rest of the sub-tree;
- if the edge has vertices on different sub-trees, than i'll add the edge and color both sub-trees, as well as the edge, with a common color. i'll use indexed colors, so i'll choose the minimum color;
- if the edge has vertices on the same sub-tree, i'll skip this edge; in this situation, the edge is creating a loop in the tree, making it a graph;

/** * the procedure takes as parameters a weight matrix together with its size * and modifies in place the weights matrix, removing the unnecessary edges * an edge is kept, if the weight is strict positive, while an edge is * deleted, if its weight is zero. * @param weights (uint8_t *) is the weight vector * @param m (int) is the maze top-bottom size * @param n (int) is the maze left-right size */ void maze_init (uint8_t * weights, int m, int n) { /** * @var indices is the sorted mapping for the weights vector; * @var matrix is a vector-stored matrix that has 0 on (i,j) * 0 on (i,j) position, if the (i,j) vertex was not visited * color>0 on (i,j) position, if the (i,j) vertex was visited * and (i,j) is part of the "color" sub-tree */ int * indices, * matrix; /** * @var c,d are variable indices; * @var row,col are the row and column indices in the @see matrix * @var n_row,n_col are the indices for the vertex connected to * (row,col); * @var min_color is the minimum "color" when merging an existing * sub-tree with a new edge. the edge can link two existing * sub-trees, meaning i'll have to choose a single color for both * @var max_color is analog with @see min_color; * @var color is the current available color for new sub-trees; */ int c, d, row, col, n_row, n_col, min_color, max_color, color = 1; /** reserve memory for the is-visited? matrix */ matrix = (int *) malloc (m * n * sizeof (int)); for (c = 0; c < m * n; c++) *(matrix + c) = 0; /** sort the graph weights */ indices = maze_edges_sort (weights, m, n); /** loop through sorted edges */ for (c = 0; c < m * (2 * n - 1) - n; c++) { /** get the edge first vertex label as (row, col) */ row = *(indices + c) / (2 * n - 1); col = *(indices + c) % (2 * n - 1); /** * based on how is stored, get the label for the * second vertex associated with the edge */ if (col < n - 1) { n_row = row; n_col = col + 1; } else { col = col - n + 1; n_row = row + 1; n_col = col; } /** * check if the current edge can be added to the forest: * the edge needs to fulfill all requirements: * - the edge is not already part of a tree, meaning that both * vertices are the same non-zero color */ if ( (*(matrix + row * n + col) == *(matrix + n_row * n + n_col)) && *(matrix + row * n + col) > 0 ) { *(weights + *(indices + c)) = 0; continue; } /** * find the color of the new vertices, by getting minimum and * maximum color. both can be zero, if we start a new sub-tree */ if (*(matrix + row * n + col) < *(matrix + n_row * n + n_col)) { min_color = *(matrix + row * n + col); max_color = *(matrix + n_row * n + n_col); } else { min_color = *(matrix + n_row * n + n_col); max_color = *(matrix + row * n + col); } if (min_color == 0) { /** * here, min = max = 0, this means we have a new sub-tree * so i color it with the next available color */ if (max_color == 0) { *(matrix + row * n + col) = *(matrix + n_row * n + n_col) = color ++; } /** here, the edge has an open end, the other is connected */ else { *(matrix + row * n + col) = *(matrix + n_row * n + n_col) = max_color; } } else { /** * here min, max > 0, both different, this means that the * edge is connecting two different color sub-trees, so i * make both the same color (min color) */ *(matrix + row * n + col) = *(matrix + n_row * n + n_col) = min_color; for (d = 0; d < m * n; d++) if (*(matrix + d) == max_color) *(matrix + d) = min_color; } } /** remember to free the reserved memory */ free (indices); free (matrix); }

piece of cake. first, i'll have to initialize my weights. than, to build the maximum spanning tree. a good exercise is to display the maze on the screen using ASCII art.

#include/** required for malloc, srand and rand functions */ #include /** useful for printing stuff, with printf */ #include /** i need the uint8_t definition */ #include /** i need the time function */ /** * this is the normal, unix-style format for the program entrypoint * @param argc (int) is the number of arguments from the command line; * @param argv (char **) is an array of strings, containing the command line arguments; * @returns: an integer, zero if no error has occurred. */ int main (int argc, char ** argv) { /** @var weights (uint8_t *) my weights matrix */ uint8_t * weights; /** @var m, n (int) the maze size */ int m = 4, n = 4; /** make the random numbers random 🙂 */ srand (time (NULL)); /** initialize the weights matrix */ weights = maze_weight_init (m, n); /** build a maximum spanning tree from the matrix */ maze_init (weights, m, n); /** tell the operating system that there's no error */ return 0; }

- #artist 2
- #arts 4
- #away 3
- #bucharest 1
- #buggy 2
- #business 1
- #clothes 1
- #contest 3
- #dragosvoicu 1
- #education 1
- #food 2
- #friends 14
- #hobby 17
- #howto 9
- #ideas 25
- #life lessons 3
- #me 59
- #mobile fun 4
- #music 51
- #muvis 14
- #muviz 11
- #myth buxter 1
- #nice2know 15
- #night out 1
- #openmind 2
- #outside 3
- #poems 4
- #quotes 1
- #raspberry 4
- #remote 56
- #replied 51
- #sci-tech 7
- #sciencenews 1
- #sexaid 6
- #subway 39
- #th!nk 3
- #theater 1
- #zen! 4

aceast sait folosește cookie-uri pentru a îmbunătăți experiența ta, ca vizitator. în același scop, acest sait utilizează modulul Facebook pentru integrarea cu rețeaua lor socială. poți accesa aici politica mea de confidențialitate.