dfs.h File Reference

Header file for the depth first search algorithm for mapping the maze. More...

#include <stdint.h>
#include "pathfinding/maze.h"
#include "pathfinding/floodfill.h"

Include dependency graph for dfs.h:

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

Go to the source code of this file.

Functions
void	dfs_depth_first_search (maze_grid_t *p_grid, maze_grid_cell_t *p_start_node, maze_navigator_state_t *p_navigator, floodfill_explore_func_t p_explore_func, floodfill_move_navigator_t p_move_navigator)
	Conducts a depth first search on a maze. More...
bool	dfs_is_all_reachable_visited (maze_grid_t *p_grid, maze_navigator_state_t *p_navigator)
	Checks if all reachable nodes from the navigator's current position has been visisted. More...

Detailed Description

Header file for the depth first search algorithm for mapping the maze.

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-18

Copyright

Copyright (c) 2023

Function Documentation

dfs_depth_first_search()

void dfs_depth_first_search	(	maze_grid_t *	p_grid,
		maze_grid_cell_t *	p_start_node,
		maze_navigator_state_t *	p_navigator,
		floodfill_explore_func_t	p_explore_func,
		floodfill_move_navigator_t	p_move_navigator
	)

Conducts a depth first search on a maze.

Parameters

[in]	p_grid	Pointer to the grid.
[in]	p_start_node	Pointer to the start node.
[in,out]	p_navigator	Pointer to the navigator state.
[in]	p_explore_func	Function pointer to explore the current node.
[in]	p_move_navigator	Function pointer to move the navigator.

References maze_grid::columns, maze_grid_cell::coordinates, dfs_is_all_reachable_visited(), maze_grid_cell::is_visited, maze_get_dir_from_to(), maze_nav_modify_walls(), MAZE_NONE, maze_navigator_state::orientation, maze_grid_cell::p_came_from, maze_navigator_state::p_current_node, maze_grid::p_grid_array, maze_grid_cell::p_next, and maze_grid::rows.

Here is the call graph for this function:

dfs_is_all_reachable_visited()

bool dfs_is_all_reachable_visited	(	maze_grid_t *	p_grid,
		maze_navigator_state_t *	p_navigator
	)

Checks if all reachable nodes from the navigator's current position has been visisted.

Parameters

[in]	p_grid	Pointer to the grid.
[in]	p_navigator	Pointer to the navigator state.

Returns

true All reachable nodes have been visited.

false Not all reachable nodes have been visited.

References binary_heap_delete_min(), binary_heap_peek(), binary_heap::capacity, maze_grid::columns, maze_grid_cell::f, maze_grid_cell::g, maze_grid_cell::h, maze_grid_cell::is_visited, binary_heap::p_array, maze_navigator_state::p_current_node, maze_grid::p_grid_array, binary_heap_node::p_maze_node, maze_grid::rows, and binary_heap::size.

Here is the call graph for this function:

Here is the caller graph for this function: