Header file for the maze data structure and public functions. More...

#include <stdint.h>
#include <stdbool.h>

Include dependency graph for maze.h:

This graph shows which files directly or indirectly include this file:

Data Structures
union	maze_bitmask_compressed
	Used for sending the maze over serial or WiFi. More...

struct	maze_gap_bitmask
	This struct contains the maze gap bitmasks for serialisation. More...

struct	maze_grid
	This struct contains the maze grid information. More...

struct	maze_grid_cell
	This struct contains the node information. More...

struct	maze_navigator_state
	This struct contains the state of a navigator in the maze. More...

struct	maze_point
	This struct contains the coordinates of a point. More...

Macros
#define	MAZE_INVERT_BITMASK(x) ((0xFu - x) & 0xFu)
	This macro inverts an 4-bit bitmask. More...

Typedefs
typedef union maze_bitmask_compressed	maze_bitmask_compressed_t
	Used for sending the maze over serial or WiFi.

typedef struct maze_gap_bitmask	maze_gap_bitmask_t
	This struct contains the maze gap bitmasks for serialisation.

typedef struct maze_grid_cell	maze_grid_cell_t
	This struct contains the node information. More...

typedef struct maze_grid	maze_grid_t
	This struct contains the maze grid information. More...

typedef struct maze_navigator_state	maze_navigator_state_t
	This struct contains the state of a navigator in the maze.

typedef struct maze_point	maze_point_t
	This struct contains the coordinates of a point. More...

Enumerations
enum	maze_cardinal_direction_t { MAZE_NORTH = 0 , MAZE_EAST = 1 , MAZE_SOUTH = 2 , MAZE_WEST = 3 , MAZE_NONE = 255 }
	This enum contains the possible directions. More...

enum	maze_relative_direction_t { MAZE_FRONT , MAZE_RIGHT , MAZE_BACK , MAZE_LEFT }
	This enum contains the relative directions of instructions from the navigator's perspective. More...

enum	maze_wall_direction_t { MAZE_NO_WALLS = 0 , MAZE_FRONT_WALL = 1 , MAZE_RIGHT_WALL = 2 , MAZE_BACK_WALL = 4 , MAZE_LEFT_WALL = 8 }
	This enum contains bitmasks for the walls. Useful when updating more than one wall at a time. More...

Functions
void	maze_clear_heuristics (maze_grid_t *p_grid)
	Clears the maze heuristics. This sets the F, G, and H values of each node to UINT32_MAX for the A* and floodfill algorithm. More...

maze_grid_t	maze_create (uint16_t rows, uint16_t columns)
	Create a maze with the specified number of rows and columns. More...

int16_t	maze_deserialise (maze_grid_t p_grid, maze_gap_bitmask_t p_no_walls_array)
	Deserialises the maze from a bitmask array. maze_serialise. More...

void	maze_destroy (maze_grid_t *p_grid)
	Destroys the maze by freeing the memory allocated to the grid array. More...

maze_grid_cell_t *	maze_get_cell_at_coords (maze_grid_t p_grid, const maze_point_t p_coordinates)
	Get the cell at the specified coordinates. More...

maze_grid_cell_t *	maze_get_cell_in_dir (maze_grid_t p_grid, maze_grid_cell_t p_from, maze_cardinal_direction_t direction)
	Get the cell in the specified direction from a specific cell. More...

maze_cardinal_direction_t	maze_get_dir_from_to (const maze_point_t p_point_a, const maze_point_t p_point_b)
	Get the direction from p_point_a to p_point_b if they are adjacent. More...

int8_t	maze_get_nav_dir_offset (const maze_navigator_state_t *p_navigator)
	Get the offset from the navigator's current direction to any other possible direction. More...

maze_relative_direction_t	maze_get_relative_dir (const maze_cardinal_direction_t direction_from, const maze_cardinal_direction_t direction_to)
	Gets the relative direction from the current direction to the desired cardinal direction. More...

char *	maze_get_string (maze_grid_t *p_grid)
	Get the string representation of the maze for pretty printing. More...

void	maze_initialise_empty_walled (maze_grid_t *p_grid)
	Initialises an empty maze. This sets the coordinates of each node, all heuristic values to 0, and all pointers to NULL. This is useful for the A* algorithm. More...

void	maze_insert_nav_str (const maze_grid_t p_grid, const maze_navigator_state_t p_navigator, char *maze_str)
	Inserts the navigator character into the maze string for pretty printing. More...

uint32_t	maze_manhattan_dist (const maze_point_t p_point_a, const maze_point_t p_point_b)
	Calculates the manhattan distance between two points. More...

void	maze_nav_modify_walls (maze_grid_t p_grid, maze_navigator_state_t p_navigator, uint8_t aligned_wall_bitmask, bool is_set, bool is_unset)
	Modifies the walls of the navigator's current node. More...

int16_t	maze_nav_to_buffer (const maze_navigator_state_t p_navigator, uint8_t p_buffer, uint16_t buffer_size)
	Serialises the navigator state into a uint8_t buffer. The buffer is set with the navigator's coordinates, orientation, start node, and end node coordinates in that order. More...

maze_gap_bitmask_t	maze_serialise (maze_grid_t *p_grid)
	Serialises the maze into a bitmask array. maze_deserialise. More...

int16_t	maze_serialised_to_buffer (const maze_gap_bitmask_t p_bitmask, uint8_t p_buffer, uint16_t buffer_size)
	Serialises the maze into a uint8_t buffer. More...

void	maze_uint16_to_uint8_buffer (uint16_t value, uint8_t *p_buffer)
	Helper function to convert a uint16_t to a uint8_t buffer. More...

Detailed Description

Header file for the maze data structure and public functions.

Author: Christopher Kok (chris.nosp@m.@for.nosp@m.celig.nosp@m.htni.nosp@m.ng.xy.nosp@m.z)

Version: 0.1

Date: 2023-11-07

Copyright: Copyright (c) 2023

Macro Definition Documentation

◆ MAZE_INVERT_BITMASK

#define MAZE_INVERT_BITMASK ( x ) ((0xFu - x) & 0xFu)

This macro inverts an 4-bit bitmask.

Parameters

[in] x Bitmask to invert.

Typedef Documentation

◆ maze_grid_cell_t

typedef struct maze_grid_cell maze_grid_cell_t

This struct contains the node information.

Note: Ensure that the initialisation of the struct sets all pointers to NULL. Otherwise, the program might have undefined behaviour.

◆ maze_grid_t

typedef struct maze_grid maze_grid_t

This struct contains the maze grid information.

Note: The grid array is indexed by row first, then column.

◆ maze_point_t

typedef struct maze_point maze_point_t

This struct contains the coordinates of a point.

Enumeration Type Documentation

◆ maze_cardinal_direction_t

enum maze_cardinal_direction_t

This enum contains the possible directions.

Enumerator
MAZE_NORTH	North is the top of the maze.
MAZE_EAST	East is the right of the maze.
MAZE_SOUTH	South is the bottom of the maze.
MAZE_WEST	West is the left of the maze.
MAZE_NONE	None is used for errors.

◆ maze_relative_direction_t

enum maze_relative_direction_t

This enum contains the relative directions of instructions from the navigator's perspective.

Enumerator
MAZE_FRONT	Front is the direction the navigator is facing.
MAZE_RIGHT	Right of the navigator.
MAZE_BACK	Back of the navigator.
MAZE_LEFT	Left of the navigator.

◆ maze_wall_direction_t

enum maze_wall_direction_t

This enum contains bitmasks for the walls. Useful when updating more than one wall at a time.

Note: The bitmasks are powers of 2, so they can be bitwise ORed together. They DIFFER from the cardinal_direction_t enum.

Enumerator
MAZE_NO_WALLS	No walls.
MAZE_FRONT_WALL	Front wall.
MAZE_RIGHT_WALL	Right wall.
MAZE_BACK_WALL	Back wall.
MAZE_LEFT_WALL	Left wall.

Function Documentation

◆ maze_clear_heuristics()

void maze_clear_heuristics ( maze_grid_t * p_grid )

Clears the maze heuristics. This sets the F, G, and H values of each node to UINT32_MAX for the A* and floodfill algorithm.

Parameters

[in,out] p_grid Pointer to the maze grid.

References maze_grid::columns, maze_grid_cell::f, maze_grid_cell::g, maze_grid_cell::h, maze_grid_cell::is_visited, maze_grid::p_grid_array, and maze_grid::rows.

Here is the caller graph for this function:

◆ maze_create()

maze_grid_t maze_create	(	uint16_t	rows,
		uint16_t	columns
	)

Create a maze with the specified number of rows and columns.

Parameters

[in]	rows	Number of rows in the maze.
[in]	columns	Number of columns in the maze.

Returns: maze_grid_t Empty maze. Indexed first by row, then column.

Warning: The maze must be destroyed by destroy_maze.

References maze_initialise_empty_walled().

Here is the call graph for this function:

◆ maze_deserialise()

int16_t maze_deserialise	(	maze_grid_t *	p_grid,
		maze_gap_bitmask_t *	p_no_walls_array
	)

Deserialises the maze from a bitmask array. maze_serialise.

Parameters

[in,out]	p_grid	Pointer to the maze grid.
[in]	p_no_walls_array	Pointer to the bitmask array of maze gaps.

Returns: int16_t 0 if successful, -1 otherwise.

References maze_grid::columns, maze_gap_bitmask::columns, maze_gap_bitmask::p_bitmask, maze_grid::p_grid_array, maze_grid::rows, and maze_gap_bitmask::rows.

◆ maze_destroy()

void maze_destroy ( maze_grid_t * p_grid )

Destroys the maze by freeing the memory allocated to the grid array.

Parameters

[in,out] p_grid Pointer to the maze grid.

References maze_grid::columns, maze_grid::p_grid_array, and maze_grid::rows.

◆ maze_get_cell_at_coords()

maze_grid_cell_t * maze_get_cell_at_coords	(	maze_grid_t *	p_grid,
		const maze_point_t *	p_coordinates
	)

Get the cell at the specified coordinates.

Parameters

[in]	p_grid	Pointer to the maze grid.
[in]	p_coordinates	Pointer to the coordinates.

Returns: maze_grid_cell_t* Pointer to the cell. NULL if the cell is out of bounds.

References maze_grid::columns, maze_grid::p_grid_array, maze_grid::rows, maze_point::x, and maze_point::y.

Here is the caller graph for this function:

◆ maze_get_cell_in_dir()

maze_grid_cell_t * maze_get_cell_in_dir	(	maze_grid_t *	p_grid,
		maze_grid_cell_t *	p_from,
		maze_cardinal_direction_t	direction
	)

Get the cell in the specified direction from a specific cell.

Parameters

[in]	p_grid	Pointer to the maze grid.
[in]	p_from	Pointer to the cell to get the next cell from.
[in]	direction	Cardinal direction to get the next cell from.

Returns: maze_grid_cell_t* Pointer to the cell. NULL if the cell is out of bounds.

References maze_grid_cell::coordinates, MAZE_EAST, maze_get_cell_at_coords(), MAZE_NORTH, MAZE_SOUTH, MAZE_WEST, maze_point::x, and maze_point::y.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ maze_get_dir_from_to()

maze_cardinal_direction_t maze_get_dir_from_to	(	const maze_point_t *	p_point_a,
		const maze_point_t *	p_point_b
	)

Get the direction from p_point_a to p_point_b if they are adjacent.

Parameters

[in]	p_point_a	Pointer to point a.
[in]	p_point_b	Pointer to point b.

Returns: maze_cardinal_direction_t Direction from point a to point b. NONE if they are not adjacent.

References MAZE_EAST, MAZE_NONE, MAZE_NORTH, MAZE_SOUTH, MAZE_WEST, maze_point::x, and maze_point::y.

Here is the caller graph for this function:

◆ maze_get_nav_dir_offset()

int8_t maze_get_nav_dir_offset ( const maze_navigator_state_t * p_navigator )

Get the offset from the navigator's current direction to any other possible direction.

This is positive for clockwise turns and negative for: anticlockwise turns. It is the minimum number of turns required to get from the current direction to the desired direction.

Parameters

[in] p_navigator Pointer to the navigator.

Returns: int8_t Offset of the current direction from cardinal directions.

References maze_navigator_state::orientation.

◆ maze_get_relative_dir()

maze_relative_direction_t maze_get_relative_dir	(	const maze_cardinal_direction_t	direction_from,
		const maze_cardinal_direction_t	direction_to
	)

Gets the relative direction from the current direction to the desired cardinal direction.

Parameters

direction_from	Cardinal direction to get the relative direction from.
direction_to	Cardinal direction to get the relative direction to.

Returns: Relative direction from the navigator to the desired direction.

◆ maze_get_string()

char * maze_get_string ( maze_grid_t * p_grid )

Get the string representation of the maze for pretty printing.

Parameters

[in] p_grid Pointer to the maze grid.

Returns: char* Pointer to the string representation of the maze.

Warning: The string returned by this function must be freed.

References maze_grid::columns, maze_grid::p_grid_array, and maze_grid::rows.

Here is the caller graph for this function:

◆ maze_initialise_empty_walled()

void maze_initialise_empty_walled ( maze_grid_t * p_grid )

Initialises an empty maze. This sets the coordinates of each node, all heuristic values to 0, and all pointers to NULL. This is useful for the A* algorithm.

Parameters

[in,out] p_grid Pointer to an empty maze created by maze_create.

References maze_grid::columns, maze_grid_cell::coordinates, maze_grid_cell::f, maze_grid_cell::g, maze_grid_cell::h, maze_grid_cell::is_visited, maze_grid_cell::p_came_from, maze_grid::p_grid_array, maze_grid_cell::p_next, and maze_grid::rows.

Here is the caller graph for this function:

◆ maze_insert_nav_str()

void maze_insert_nav_str	(	const maze_grid_t *	p_grid,
		const maze_navigator_state_t *	p_navigator,
		char *	p_maze_str
	)

Inserts the navigator character into the maze string for pretty printing.

Parameters

[in]	p_grid	Pointer to the maze grid.
[in]	p_navigator	Pointer to the navigator.
[in,out]	p_maze_str	Pointer to the maze string returned by maze_get_string.

References maze_grid::columns, maze_grid_cell::coordinates, MAZE_EAST, MAZE_NORTH, MAZE_SOUTH, MAZE_WEST, maze_navigator_state::orientation, maze_navigator_state::p_current_node, maze_point::x, and maze_point::y.

◆ maze_manhattan_dist()

uint32_t maze_manhattan_dist	(	const maze_point_t *	p_point_a,
		const maze_point_t *	p_point_b
	)

Calculates the manhattan distance between two points.

Parameters

[in]	p_point_a	Pointer to first point.
[in]	p_point_b	Pointer to second point.

Returns: uint32_t Manhattan distance.

The distance between two points is the sum of the absolute differences: of their Cartesian coordinates: \(d = |x_1 - x_2| + |y_1 - y_2|\).

See also: https://en.wikipedia.org/wiki/Taxicab_geometry

References maze_point::x, and maze_point::y.

Here is the caller graph for this function:

◆ maze_nav_modify_walls()

void maze_nav_modify_walls	(	maze_grid_t *	p_grid,
		maze_navigator_state_t *	p_navigator,
		uint8_t	aligned_wall_bitmask,
		bool	is_set,
		bool	is_unset
	)

Modifies the walls of the navigator's current node.

Parameters

[in,out]	p_grid	Pointer to the maze grid.
[in]	p_navigator	Pointer to the navigator.
[in]	aligned_wall_bitmask	Bitmask of the walls to set or unset. This is aligned to MAZE_NORTH.
[in]	is_set	True if the walls are to be set.
[in]	is_unset	True if the walls are to be unset.

Note: both is_set and is_unset can be True. In this case, the entire cell's walls and gaps will be set.

References maze_navigator_state::p_current_node.

Here is the caller graph for this function:

◆ maze_nav_to_buffer()

int16_t maze_nav_to_buffer	(	const maze_navigator_state_t *	p_navigator,
		uint8_t *	p_buffer,
		uint16_t	buffer_size
	)

Serialises the navigator state into a uint8_t buffer. The buffer is set with the navigator's coordinates, orientation, start node, and end node coordinates in that order.

Parameters

p_navigator	Pointer to the navigator state.
p_buffer	Pointer to the buffer.
buffer_size	Length of the buffer for checks.

Returns: int16_t -1 if the buffer is too small, 0 otherwise.

Note: The buffer is expected to be cleared before calling this function.

Warning: The buffer must be large enough to fit the navigator state.

References maze_grid_cell::coordinates, maze_uint16_to_uint8_buffer(), maze_navigator_state::orientation, maze_navigator_state::p_current_node, maze_navigator_state::p_end_node, maze_navigator_state::p_start_node, maze_point::x, and maze_point::y.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ maze_serialise()

maze_gap_bitmask_t maze_serialise ( maze_grid_t * p_grid )

Serialises the maze into a bitmask array. maze_deserialise.

Parameters

[in] p_grid Pointer to the maze grid.

Returns: maze_gap_bitmask_t Bitmask array of maze gaps. Take OxF - bitmask to get the walls.

References maze_grid::columns, maze_gap_bitmask::p_bitmask, maze_grid::p_grid_array, maze_grid_cell::p_next, and maze_grid::rows.

Here is the caller graph for this function:

◆ maze_serialised_to_buffer()

int16_t maze_serialised_to_buffer	(	const maze_gap_bitmask_t *	p_bitmask,
		uint8_t *	p_buffer,
		uint16_t	buffer_size
	)

Serialises the maze into a uint8_t buffer.

Parameters

p_bitmask	Pointer to the maze gap bitmask.
p_buffer	Pointer to the buffer.
buffer_size	Size of the buffer.

Returns: int16_t -1 if the buffer is too small, 0 otherwise.

Note: The buffer must be large enough to fit the maze, and the buffer must be cleared before calling this function.

References maze_bitmask_compressed::bits, maze_gap_bitmask::columns, maze_uint16_to_uint8_buffer(), and maze_gap_bitmask::rows.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ maze_uint16_to_uint8_buffer()

void maze_uint16_to_uint8_buffer	(	uint16_t	value,
		uint8_t *	p_buffer
	)

Helper function to convert a uint16_t to a uint8_t buffer.

Parameters

value	Value to convert.
p_buffer	uint8_t buffer of size 2.

This shifts the 8 MSBs of the value to the 8 LSBs of the buffer.

Here is the caller graph for this function:

Data Structures

Macros

Typedefs

Enumerations

Functions

Detailed Description

Macro Definition Documentation

◆ MAZE_INVERT_BITMASK

Typedef Documentation

◆ maze_grid_cell_t

◆ maze_grid_t

◆ maze_point_t

Enumeration Type Documentation

◆ maze_cardinal_direction_t

◆ maze_relative_direction_t

◆ maze_wall_direction_t

Function Documentation

◆ maze_clear_heuristics()

◆ maze_create()

◆ maze_deserialise()

◆ maze_destroy()

◆ maze_get_cell_at_coords()

◆ maze_get_cell_in_dir()

◆ maze_get_dir_from_to()

◆ maze_get_nav_dir_offset()

◆ maze_get_relative_dir()

◆ maze_get_string()

◆ maze_initialise_empty_walled()

◆ maze_insert_nav_str()

◆ maze_manhattan_dist()

◆ maze_nav_modify_walls()

◆ maze_nav_to_buffer()

◆ maze_serialise()

◆ maze_serialised_to_buffer()

◆ maze_uint16_to_uint8_buffer()