a_star.c File Reference

Source file for the implementation of the a* algorithm. More...

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "pathfinding/binary_heap.h"
#include "pathfinding/a_star.h"
#include "pathfinding/maze.h"

Include dependency graph for a_star.c:

Functions
void	a_star (maze_grid_t *p_grid, maze_grid_cell_t *p_start_node, maze_grid_cell_t *p_end_node)
	Runs the A* algorithm on a grid maze to find the shortest path between two points, if one exists. The path can be retrieved by checking the p_came_from field of each node. More...
a_star_path_t *	a_star_get_path (maze_grid_cell_t *p_end_node)
	Get the path from the start node to the end node (inclusive). More...
char *	a_star_get_path_str (maze_grid_t *p_grid, a_star_path_t *p_path)
	Gets the string representation of the path from the start node to the end node. More...
int16_t	a_star_maze_path_nav_to_buffer (maze_grid_t *p_grid, const a_star_path_t *p_path, const maze_navigator_state_t *p_navigator, uint8_t *p_buffer, uint16_t buffer_size)
	Inserts the maze, path and navigator state into a buffer. More...
int16_t	a_star_path_to_buffer (const a_star_path_t *p_path, uint8_t *p_buffer, uint16_t buffer_size)
	Inserts the path in coordinates from the start node to the end node into a buffer. More...

Detailed Description

Source file for the implementation of the a* algorithm.

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

a_star()

void a_star	(	maze_grid_t *	p_grid,
		maze_grid_cell_t *	p_start_node,
		maze_grid_cell_t *	p_end_node
	)

Runs the A* algorithm on a grid maze to find the shortest path between two points, if one exists. The path can be retrieved by checking the p_came_from field of each node.

Parameters

[in]	p_grid	The grid maze.
[in]	p_start_node	Pointer to the start node.
[in]	p_end_node	Pointer to the end node.

References binary_heap_insert(), binary_heap::capacity, maze_grid::columns, maze_grid_cell::coordinates, maze_grid_cell::f, maze_grid_cell::g, maze_grid_cell::h, maze_manhattan_dist(), binary_heap::p_array, maze_grid::p_grid_array, maze_grid::rows, and binary_heap::size.

Here is the call graph for this function:

a_star_get_path()

a_star_path_t * a_star_get_path

(

maze_grid_cell_t *

p_end_node

)

Get the path from the start node to the end node (inclusive).

Parameters

[in]

p_end_node

Pointer to the end node.

Returns

a_star_path_t* Pointer to the path.

References maze_grid_cell::g, a_star_path::length, maze_grid_cell::p_came_from, and a_star_path::p_path.

a_star_get_path_str()

char * a_star_get_path_str	(	maze_grid_t *	p_grid,
		a_star_path_t *	p_path
	)

Gets the string representation of the path from the start node to the end node.

Parameters

[in]	p_grid	Pointer to the grid maze.
[in]	p_path	Pointer to the path.

Returns

char* The string representation of the path.

Warning

The string must be freed after use.

References maze_grid::columns, maze_grid_cell::coordinates, a_star_path::length, maze_get_dir_from_to(), maze_get_string(), MAZE_NONE, maze_grid_cell::p_came_from, and a_star_path::p_path.

Here is the call graph for this function:

a_star_maze_path_nav_to_buffer()

int16_t a_star_maze_path_nav_to_buffer	(	maze_grid_t *	p_grid,
		const a_star_path_t *	p_path,
		const maze_navigator_state_t *	p_navigator,
		uint8_t *	p_buffer,
		uint16_t	buffer_size
	)

Inserts the maze, path and navigator state into a buffer.

Parameters

[in]	p_grid	Pointer to the maze grid.
[in]	p_path	Pointer to the path generated by A*, NULL if no path exists.
[in]	p_navigator	Pointer to the navigator state.
[out]	p_buffer	Pointer to the buffer to store the maze, path and navigator state in.
[in]	buffer_size	Size of the buffer. Checks if the buffer is large enough.

Returns

int16_t -1 if the buffer is too small, the size of the buffer required otherwise.

References a_star_path_to_buffer(), maze_grid::columns, DEBUG_PRINT, a_star_path::length, maze_nav_to_buffer(), maze_serialise(), maze_serialised_to_buffer(), maze_uint16_to_uint8_buffer(), and maze_grid::rows.

Here is the call graph for this function:

a_star_path_to_buffer()

int16_t a_star_path_to_buffer	(	const a_star_path_t *	p_path,
		uint8_t *	p_buffer,
		uint16_t	buffer_size
	)

Inserts the path in coordinates from the start node to the end node into a buffer.

Parameters

[in]	p_path	Pointer to the path generated by the A* algorithm.
[out]	p_buffer	Pointer to the buffer to store the path in.
[in]	buffer_size	Size of the buffer. Checks if the buffer is large enough.

Returns

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

References maze_grid_cell::coordinates, DEBUG_PRINT, a_star_path::length, maze_uint16_to_uint8_buffer(), a_star_path::p_path, maze_point::x, and maze_point::y.

Here is the call graph for this function:

Here is the caller graph for this function: