Skip to content
/ fornax Public

Collection of tools to visualize Path Finding Algorithms

License

Notifications You must be signed in to change notification settings

andinus/fornax

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

76 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Fornax

Websitehttps://andinus.unfla.me/projects/fornax
Sourcehttps://git.unfla.me/fornax
GitHub (mirror)https://github.com/andinus/fornax

This collection includes:

  • fornax: Program that parses Fornax Format and outputs video solution.
  • Algorithms: Various algorithms solved in several programming languages.

Writings:

Demo

Solution for DFS-60, generated on 2021-11-16 (click to play):

https://andinus.unfla.me/resources/projects/fornax/2021-11-16-DFS-60-00000436.png

Fornax v0.1.0:

Usage

# Solve the maze.
raku algorithms/raku/DFS.raku resources/input/06 > /tmp/solution.fornax

# Visualize the solution.
raku -Ilib bin/fornax /tmp/solution.fornax

Installation

fornax is written in Raku, it can be installed with zef. You can also run it without zef, just run raku -Ilib bin/fornax from within the source directory.

  • Note: Cairo module & ffmpeg program is required.

Release

  1. Run zef install 'fornax:auth<zef:andinus>'

Fornax should be installed, try running fornax --version to confirm.

  • Solving programs / solutions are not included in the distribution, get them from this repository.

From Source

You can either download the release archive generated by cgit/GitHub or clone the project if you have git installed.

Without git

  1. Download the release:
  2. Extract the file.
  3. Run zef install . in source directory.

With git

All commits by Andinus will be signed by this PGP Key.

# Clone the project.
git clone https://git.tilde.institute/andinus/fornax
cd fornax

# Install fornax.
zef install .

Documentation

Fornax parses Fornax format, generates a PNG for each iteration which is later converted to a slideshow with ffmpeg.

  • Solved paths are highlighted if the iteration is preceded by |.
  • Illegal paths are highlighted if the iteration is preceded by !.

Options

  • input: This takes solved input file in the Fornax format.
  • fps: Frame rate for the video solution.
  • skip-video: Skip generating the video solution.
  • batch: Number of iterations to process at once.

Fornax Format

Fornax format defines 2 formats:

  • Maze (input)
  • Solution (output)

Grids

A grid is printed for every iteration. Grids are composed of cells.

CellSymbol
Path.
Blocked#
Start^
Destination$
Visited-
Current Path~~~
Current Position@

Maze (input)

Maze input must be in this format:

...rows

It is upto the program to infer the number of rows & columns from the input file or it ask the user.

Solution (output)

Fornax solution format is an intermediate output file generated after solving the maze. Algorithms must output the solution in this format:

rows:<number of rows> cols:<number of columns>

...iterations

...iterations is to be replaced by the resulting grid in each iteration that is to be included in the final video. Since the number of rows and columns is known, the whole grid should be printed in a single line.

  • Every iteration should be separated by a newline.
  • If the iteration cells is not equal to rows * columns or (rows * columns) + 1 then it may be ignored by the program that parses the file.
  • Solved iteration can be preceded by | character.
  • Iteration that tries to walk on a blocked path can be preceded by ! character.
  • First iteration is assumed to be the maze.

Project Structure

  • Algorithms are located in algorithms/ directory, sub-directory needs to be created for programming languages which will hold the actual source.
  • Sample solutions can be found in resources/solutions/ directory.
    • Note: Some solutions might output illegal moves (like walking over blocked path), this error is only in visualization, the solution is correct.

      This has been fixed in commit 8cef86f0eb8b46b0ed2d7c37fa216890300249f6.

Bugs

  • If the number of iterations are greater than an 8 digit number then the slideshow might be incorrect.
  • /tmp is assumed to exist.
  • Might panic with: MoarVM oops: MVM_str_hash_entry_size called with a stale hashtable pointer. This has been fixed: rakudo/rakudo#4634.

News

v0.2.0 - 2021-11-25

  • Add demo videos.
  • Add more solutions.
  • Implement BFS in Java.
  • Implement DFS in Raku.
  • Add basic tests.

v0.1.1 - 2021-11-16

  • Add option to skip generating slideshow.
  • Use random directory to store solutions.
  • Process iterations in parallel.
  • Wait 4s on solution frame.
  • Add incomplete BFS program.
  • Add demo videos.
  • Upgrade to latest Fornax Format.
  • Add more solutions.

v0.1.0 - 2021-11-03

  • Initial implementation:
    • Includes DFS solver in Java and a tool to visualize the solution.