blob: df63385f63e2245bf21f938a34512ab015b56394 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
#+title: Fornax
#+subtitle: Collection of tools to visualize Path Finding Algorithms
#+export_file_name: index
#+setupfile: ~/.emacs.d/org-templates/projects.org
| Website | https://andinus.unfla.me/projects/fornax |
| Source | https://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.
* Demo
Solution for /DFS-33/, generated on /2021-11-03/ (click to play).
[[https://andinus.unfla.me/resources/projects/fornax/2021-11-03-DFS-33.mp4][https://andinus.unfla.me/resources/projects/fornax/2021-11-03-DFS-33.png]]
* 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~.
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:
- https://git.unfla.me/andinus/fornax
- https://github.com/andinus/fornax/releases
2. Extract the file.
3. Run ~zef install .~ in source directory.
*** With ~git~
All commits by /Andinus/ will be signed by this [[https://andinus.nand.sh/static/D9AE4AEEE1F1B3598E81D9DFB67D55D482A799FD.asc][PGP Key]].
#+begin_src sh
# Clone the project.
git clone https://git.tilde.institute/andinus/fornax
cd fornax
# Install fornax.
zef install .
#+end_src
* 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 ~!~.
- *Note*: If the number of iterations are greater than an 8 digit number
then the slideshow might be incorrect.
* 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~.
* Fornax Format
Fornax format is an intermediate output file generated after solving the
maze. Algorithms must output the solution in this format.
#+begin_src
rows:<number of rows> cols:<number of columns>
...iterations
#+end_src
~...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.
** Grids
A grid is printed for every iteration. Grids are composed of cells.
| Cell | Symbol |
|------------------+--------|
| Path | ~.~ |
| Blocked | ~#~ |
| Destination | ~$~ |
|------------------+--------|
| Visited | ~-~ |
| Current Position | ~@~ |
- /Current Position/ is prioritized over /Blocked/ & /Destination/ symbol if
it makes sense.
* News
** v0.1.0 - 2021-11-03
+ Initial implementation. Includes DFS solver in Java, tool to visualize
the solution.
|