Minimal A* implementation in C. No dynamic memory allocation.

Overview

Micro A Star Path Finder

This is a minimal A* path finder implementation in C, without any dynamic memory allocation.

Usage

The maximum size of the map is defined by the macro PATH_FINDER_MAX_CELLS, which can be modified to support larger maps.

The size of the map is defined by the variables cols and rows in the path_finder structure, and the total of cells must be smaller or equal to PATH_FINDER_MAX_CELLS.

struct path_finder path_finder = {0};
path_finder.cols = 24;
path_finder.rows = 24;
init_path_finder(&path_finder);
path_finder.data = game;
/* Callback to fill the initial state of the cells */
path_finder.fill_func = fill_cb;
/* Callback to set the custom score to the cells while finding a path */
path_finder.score_func = score_cb;
/* Fill with the initial state of the cells and the custom score */
path_finder_fill(&path_finder, game_object);
path_finder_set_start(&path_finder, from_col, from_row);
path_finder_set_end(&path_finder, to_col, to_row);
/* Find the path */
path_finder_find(&path_finder, game_object);

The callback fill_func is necessary to define which cells are passable and which are non-passable:

/* The parameters `col` and `row` indicate the cell of the map we are setting as passable or non-passable */
static bool fill_cb(struct path_finder *path_finder, int32_t col, int32_t row)
{
	struct game *game;
	uint8_t is_passable;
	game = path_finder->data;
	is_passable = 0;
	if (is_wall(game, col, row) == 1) {
		is_passable = 0;
	}
	return is_passable;
}

The callback score_func is optional and is called during the path_finder_find execution. The callback also takes a custom pointer, useful to point to a specific object. Use it to add custom score to the cells:

/* The parameters `col` and `row` indicate the cell of the map we are setting a score */
static int32_t score_cb(struct path_finder *path_finder, int32_t col, int32_t row, void *data)
{
	struct game *game;
	struct game_object *game_object;
	int32_t value;
	game = path_finder->data;
	game_object = data;
	value = 0;
	if (is_danger_zone(game, col, row) == 1) {
		/* The higher the value, the more avoided the cell is */
		value = 5;
		if (is_fearless(game_object) == 1) {
			/* Unless the character is fearless */
			value = 0;
		}
	}
	/* The value returned is incremented in the cell score */
	return value;
}

To check if a cell is a path, access the path finder array directly or use path_finder_is_path (be careful, this function doesn't check the passed values of column and row are inside the range of the map dimensions, as they should be):

cell_is_path = path_finder_is_path(&path_finder, col, row);

If a path is found by the path finder, the value of has_path inside the structure path_finder is set to 1.

It is also possible to process only one step of the path finder at a time, useful to divide the processing in multiple frames:

uint8_t still_working;
path_finder_begin(&path_finder);
still_working = path_finder_find_step(&path_finder, NULL);

Or, to run the entire process, but drawing the intermediate steps:

path_finder_begin(&path_finder);
while (path_finder_find_step(&path_finder, NULL) == 1) {
	draw();
}

Test

The test generates an output with the map:

./test 0 80 12345 0 0 23 11 24 13
  Passable chance: 80
            Start: 'S' (or 's' if fall in a wall)
              End: 'E' (or 'e' if fall in a wall)
        Open path: 'O'
      Closed path: 'X'
             Path: '*'
       Unpassable: '#'
Map:
##########################
#S#    #      #       #  #
#****###  #      # ##    #
### **#******##    #     #
###  ***#  #**  #   # ## #
#  #  ## #   * # #  #  # #
#   ##  #    *# ##       #
## #   # #  #****#       #
#    #     #    *******  #
#   #  #      #  #    *# #
# #  #  ##         # #**##
# # #       ##         **#
#                       E#
#  #    ## # ### #    #  #
##########################
A path was found!

LICENSE

The source code of this project is licensed under the terms of the ZLIB license:

Copyright (c) 2017 Felipe Ferreira da Silva

This software is provided 'as-is', without any express or implied warranty. In no event will the authors be held liable for any damages arising from the use of this software.

Permission is granted to anyone to use this software for any purpose, including commercial applications, and to alter it and redistribute it freely, subject to the following restrictions:

  1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
  2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
  3. This notice may not be removed or altered from any source distribution.
Owner
Felipe da Silva
C programmer (16 years) and Biologist at Federal University of Minas Gerais (UFMG). Migrating account…
Felipe da Silva
Sketch-Based Streaming Anomaly Detection in Dynamic Graphs

AnoGraph Implementation of Sketch-Based Streaming Anomaly Detection in Dynamic Graphs. Siddharth Bhatia, Mohit Wadhwa, Philip S. Yu, Bryan Hooi Existi

Stream-AD 51 May 10, 2022
2D GPU renderer for dynamic UIs

vger vger is a vector graphics renderer which renders a limited set of primitives, but does so almost entirely on the GPU. Works on iOS and macOS. API

Audulus LLC 115 Jun 21, 2022
Plot dynamic 3d functions z = f(x, y, t)

A tool for plotting 3D functions Controls Button Description Arrows Rotate view F Enable/Disable filling surface faces G Enable/Disable showing coordi

Boris Starkov 2 Oct 15, 2021
Minimal pathtracer using Vulkan RayTracing

Single File Vulkan Pathtracing Minimal pathtracer using Vulkan RayTracing Environment Vulkan SDK 1.2.162.0 GPU / Driver that support Vulkan Ray Tracin

Yuki Nishidate 25 May 8, 2022
Vulkan Minimal Hybrid Rendering

Vulkan Minimal Hybrid Rendering A minimal hybrid rendering sample using ray query Features Rasterization Raytraced shadow Environment Vulkan SDK 1.2.1

Yuki Nishidate 7 Aug 16, 2021
Legion Low Level Rendering Interface provides a graphics API agnostic rendering interface with minimal CPU overhead and low level access to verbose GPU operations.

Legion-LLRI Legion-LLRI, or “Legion Low Level Rendering Interface” is a rendering API that aims to provide a graphics API agnostic approach to graphic

Rythe Interactive 25 Mar 8, 2022
Minimal raytracing example with a combination of embree and tinyobjloader

embree-tinyobj-example minimal raytracing example with a combination of embree and tinyobjloader Requirements CMake (>=3.20) Embree (>=3) OpenMP (Opti

yumcyawiz 2 Apr 7, 2022
A minimal Direct3D 12 example that draws an animated triangle, written entirely in C-style C++, and all taking place inside a single function.

A minimal Direct3D 12 example that draws an animated triangle, written entirely in C-style C++, and all taking place inside a single function.

Taoufik Rida Bouftass 7 May 3, 2022
Fast C++ implementation with JSI binding of MD5 for React Native

react-native-quick-md5 Brazingly fast C++ implementation with JSI binding of MD5 for React Native. Confirmed that it's 10x faster than using spark-md5

Takuya Matsuyama 73 Jun 13, 2022
An open-source implementation of Autodesk's FBX

SmallFBX An open-source implementation of Autodesk's FBX that is capable of import & export mesh, blend shape, skin, and animations. Mainly intended t

Seiya Ishibashi 40 Jun 16, 2022
A C++/DirectX 11 implementation of "A Scalable and Production Ready Sky and Atmosphere Rendering Technique"

Atmosphere Renderer A C++/DirectX 11 implementation of "A Scalable and Production Ready Sky and Atmosphere Rendering Technique" Features interactive e

Z Guan 29 Jun 23, 2022
Sandbox for graphics paper implementation

Graphics Experiments 適当にグラフィックス関連の論文などを読んで実装・検証したものを置きます。 I'll randomly put something for implementing/validating graphics papers here. 実装 / Implement

shocker-0x15 73 Jun 23, 2022
A heterogeneous OpenCL implementation of AutoDock Vina

Vina-GPU A heterogeneous OpenCL implementation of AutoDock Vina Compiling and Running Note: at least one GPU card is required and make sure the versio

Nanjing University of Posts and Telecommunications 31 Jun 22, 2022
Implementation of light baking system for ray tracing based on Activision's UberBake

Vulkan Light Bakery MSU Graphics Group Student's Diploma Project Treefonov Andrey [GitHub] [LinkedIn] EARLY STAGES OF DEVELOPMENT Project Goal The goa

Andrei Treefonov 5 May 24, 2022
An implementation of OpenGL 3.x-ish in clean C

PortableGL "Because of the nature of Moore's law, anything that an extremely clever graphics programmer can do at one point can be replicated by a mer

Robert Winkler 479 Jun 16, 2022
Deno gl - WIP Low-level OpenGL (GLFW) bindings and WebGL API implementation for Deno.

deno_gl WIP Low-level OpenGL (GLFW) bindings and WebGL API implementation for Deno. Building Make dist directory if it doesn't exist. Build gl helper

DjDeveloper 14 Jun 11, 2022
A C++ implementation of Fast Simulation of Mass-Spring Systems

Fast Mass-Spring System Simulator A C++ implementation of Fast Simulation of Mass-Spring Systems [1], rendered with OpenGL. The dynamic inverse proced

Samer Itani 146 Jun 22, 2022
Implementation of Peter Shirley's Ray Tracing In One Weekend book using Vulkan and NVIDIA's RTX extension.

Ray Tracing In Vulkan My implementation of Peter Shirley's Ray Tracing in One Weekend books using Vulkan and NVIDIA's RTX extension (formerly VK_NV_ra

Tanguy Fautre 764 Jun 25, 2022
Source code for pbrt, the renderer described in the third edition of "Physically Based Rendering: From Theory To Implementation", by Matt Pharr, Wenzel Jakob, and Greg Humphreys.

pbrt, Version 3 This repository holds the source code to the version of pbrt that is described in the third edition of Physically Based Rendering: Fro

Matt Pharr 4.2k Jun 22, 2022