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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
|
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FORNAX
Collection of tools to visualize Path Finding
Algorithms
Andinus
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Table of Contents
─────────────────
1. Demo
2. Installation
.. 1. Release
.. 2. From Source
3. Project Structure
4. Documentation
.. 1. Options
5. Fornax Format
.. 1. Grids
.. 2. Maze (input)
.. 3. Solution (output)
6. News
.. 1. v0.1.1 - 2021-11-16
.. 2. v0.1.0 - 2021-11-03
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
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.
Writings:
• Fornax: Generating 4.8 million frames:
<https://andinus.unfla.me/writings/2021/fornax-generating-4.8-million-frames.html>
1 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]
• Mirror: <https://diode.zone/w/u6tuoktG1ZZWCQFZodKqyu>
Fornax v0.1.0:
• Solution for /DFS-33/, generated on /2021-11-03/:
<https://andinus.unfla.me/resources/projects/fornax/2021-11-03-DFS-33.mp4>
• DFS-51-incomplete (upto 187,628 frames; 120 fps):
<https://diode.zone/w/4RSFatXPL3GrkUucnFdxVS>
• DFS-51-incomplete (upto 4,000 frames; 120 fps):
<https://diode.zone/w/hWWaw8uKHCP5weUP5WWArD>
[https://andinus.unfla.me/resources/projects/fornax/2021-11-16-DFS-60-00000436.png]
<https://andinus.unfla.me/resources/projects/fornax/2021-11-16-DFS-60.mp4>
2 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.
2.1 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.
2.2 From Source
───────────────
You can either download the release archive generated by cgit/GitHub
or clone the project if you have `git' installed.
2.2.1 Without `git'
╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌
1. Download the release:
• <https://git.unfla.me/fornax>
• <https://github.com/andinus/fornax/releases>
2. Extract the file.
3. Run `zef install .' in source directory.
2.2.2 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 .
└────
[PGP Key]
<https://andinus.nand.sh/static/D9AE4AEEE1F1B3598E81D9DFB67D55D482A799FD.asc>
3 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'.
4 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.
• *Note*: `/tmp' must exist.
4.1 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.
5 Fornax Format
═══════════════
Fornax format defines 2 formats:
• Maze (input)
• Solution (output)
5.1 Grids
─────────
A grid is printed for every iteration. Grids are composed of cells.
━━━━━━━━━━━━━━━━━━━━━━━━━━
Cell Symbol
──────────────────────────
Path `.'
Blocked `#'
Start `^'
Destination `$'
──────────────────────────
Visited `-'
Current Path `~'
Current Position `@'
━━━━━━━━━━━━━━━━━━━━━━━━━━
5.2 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.
5.3 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.
6 News
══════
6.1 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.
6.2 v0.1.0 - 2021-11-03
───────────────────────
⁃ Initial implementation:
• Includes DFS solver in Java and a tool to visualize the solution.
|