maze.c File Reference

Contains the implementation of utility maze functions. More...

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include "pathfinding/maze.h"

Include dependency graph for maze.c:

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 *p_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

Contains the implementation of utility maze 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

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: