C Maze Generation

About

This repository contains the source code for our Maze generation extension for the Imperial Y1 C Project. Using C and the Raylib game engine, we have implemented 3 maze generation algorithm visualisations, Randomised Prim's, Randomised Kruskal's and Recursive Backtracking, as well as Dijkstra's pathfinding algorithm.

Examples

Prim's Algorithm:

Kruskal's Algorithm:

Dijkstra's Algorithm:

Getting Started

These instructions will get you a copy of the project up and running on your local machine for development and testing purposes.

Prerequisites

Ensure that you have the following prerequisites installed:

• gcc - Download and install version 9.3.0 +
• make - Download and install version 4.2.1 +

A compatible Raylib version is included as a submodule in the repository. Please note that the Makefile only provides compilation instructions for Linux, WSL and MacOS. Manual generation of the Raylib librarylib.a file may be required.

Installation

Firstly clone the repository:

git clone --recurse-submodules https://github.com/ethanrange/c-maze-generation.git

If the project has already been cloned without the --recurse-submodules flag, initialise and fetch the raylib submodule with:

git submodule update --init

The main program then may be compiled with make in src:

cd src
make
../bin/main

Units tests may be compiled and run with:

cd testsuite
make test

Usage

The maze starts in a blank uninitialised state. Left click any tile to convert it to a goal tile. Dijkstra's algorithm will find the path to the cloest goal tile from the player.

Player Controls

Control	Action
W A S D	Player Movement
Left Mouse	Create Goal

Algorithm Controls

Control	Action
P	Run Prims
K	Run Kruskals
B	Run Recursive Backtrack
D	Run Dijkstras
Shift + P	Step Prims
Shift + K	Step Kruskals
Shift + D	Step Dijkstras

Miscellaneous Controls

Control	Action
T	Print Test Summary

License

This project is licensed under the MIT License - see the LICENSE.md file for details