From d0b8aafd73c07535a563364dccf05d228cb9a9ac Mon Sep 17 00:00:00 2001 From: Andinus Date: Wed, 17 Nov 2021 18:48:44 +0530 Subject: Remove output option, Define maze input format in README --- README | 112 +++++++++++++++++++++++++++++++++++++------------------------ README.org | 83 ++++++++++++++++++++++++++------------------- 2 files changed, 118 insertions(+), 77 deletions(-) diff --git a/README b/README index 76c9420..3a9352a 100644 --- a/README +++ b/README @@ -12,10 +12,18 @@ Table of Contents 1. Demo 2. Installation -3. Documentation -4. Project Structure +.. 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 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ @@ -113,7 +121,24 @@ Writings: -3 Documentation +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 @@ -124,39 +149,62 @@ Writings: • *Note*: If the number of iterations are greater than an 8 digit number then the slideshow might be incorrect. + • *Note*: `/tmp' must exist. -3.1 Options +4.1 Options ─────────── • `input': This takes solved input file in the /Fornax/ format. - • `frame-rate': Frame rate for the video. - • `output': Output directory (for solution video/images). + • `fps': Frame rate for the video solution. + • `skip-video': Skip generating the video solution. + • `batch': Number of iterations to process at once. -4 Project Structure -═══════════════════ +5 Fornax Format +═══════════════ - • Algorithms are located in `algorithms/' directory, sub-directory - needs to be created for programming languages which will hold the - actual source. + Fornax format defines 2 formats: + • Maze (input) + • Solution (output) - • 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. +5.1 Grids +───────── - This has been fixed in commit - `8cef86f0eb8b46b0ed2d7c37fa216890300249f6'. + A grid is printed for every iteration. Grids are composed of cells. + ━━━━━━━━━━━━━━━━━━━━━━━━━━ + Cell Symbol + ────────────────────────── + Path `.' + Blocked `#' + Start `^' + Destination `$' + ────────────────────────── + Visited `-' + Current Path `~' + Current Position `@' + ━━━━━━━━━━━━━━━━━━━━━━━━━━ -5 Fornax Format -═══════════════ - Fornax format is an intermediate output file generated after solving - the maze. Algorithms must output the solution in this format. +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: cols: │ @@ -182,28 +230,6 @@ Writings: • First iteration is assumed to be the maze. -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 `@' - ━━━━━━━━━━━━━━━━━━━━━━━━━━ - - • /Current Position/ is prioritized over /Blocked/ & /Destination/ - symbol if it makes sense. - - 6 News ══════ diff --git a/README.org b/README.org index 20a8b0b..5f580e8 100644 --- a/README.org +++ b/README.org @@ -1,7 +1,8 @@ #+title: Fornax #+subtitle: Collection of tools to visualize Path Finding Algorithms #+export_file_name: index -#+options: toc:1 +#+options: toc:2 +#+startup: overview #+setupfile: ~/.emacs.d/org-templates/projects.org | Website | https://andinus.unfla.me/projects/fornax | @@ -75,6 +76,21 @@ cd fornax zef install . #+end_src +* 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~. + * Documentation Fornax parses /Fornax format/, generates a ~PNG~ for each iteration which is @@ -85,33 +101,50 @@ later converted to a slideshow with ~ffmpeg~. - *Note*: If the number of iterations are greater than an 8 digit number then the slideshow might be incorrect. +- *Note*: ~/tmp~ must exist. ** Options - ~input~: This takes solved input file in the /Fornax/ format. -- ~frame-rate~: Frame rate for the video. -- ~output~: Output directory (for solution video/images). +- ~fps~: Frame rate for the video solution. +- ~skip-video~: Skip generating the video solution. +- ~batch~: Number of iterations to process at once. -* Project Structure +* Fornax Format -- Algorithms are located in ~algorithms/~ directory, sub-directory needs - to be created for programming languages which will hold the actual - source. +Fornax format defines 2 formats: +- Maze (input) +- Solution (output) -- Sample solutions can be found in ~resources/solutions/~ directory. +** Grids - - *Note*: Some solutions might output illegal moves (like walking over - blocked path), this error is only in visualization, the solution is - correct. +A grid is printed for every iteration. Grids are composed of cells. - This has been fixed in commit - ~8cef86f0eb8b46b0ed2d7c37fa216890300249f6~. +| Cell | Symbol | +|------------------+--------| +| Path | ~.~ | +| Blocked | ~#~ | +| Start | ~^~ | +| Destination | ~$~ | +|------------------+--------| +| Visited | ~-~ | +| Current Path | ~~~ | +| Current Position | ~@~ | -* Fornax Format +** Maze (input) + +Maze input must be in this format: +#+begin_src +...rows +#+end_src -Fornax format is an intermediate output file generated after solving the -maze. Algorithms must output the solution in this format. +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: #+begin_src rows: cols: @@ -135,24 +168,6 @@ columns is known, the whole grid should be printed in a single line. - 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 | ~#~ | -| Start | ~^~ | -| Destination | ~$~ | -|------------------+--------| -| Visited | ~-~ | -| Current Path | ~~~ | -| Current Position | ~@~ | - -- /Current Position/ is prioritized over /Blocked/ & /Destination/ symbol if - it makes sense. - * News ** v0.1.1 - 2021-11-16 -- cgit 1.4.1-2-gfad0 From 21d3b67237a8e1824bdcf130c84afca6f323c644 Mon Sep 17 00:00:00 2001 From: Andinus Date: Wed, 17 Nov 2021 18:49:36 +0530 Subject: Remove output option, rename frame-rate option to fps --- lib/Fornax/CLI.rakumod | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/lib/Fornax/CLI.rakumod b/lib/Fornax/CLI.rakumod index 35109b7..32303fc 100644 --- a/lib/Fornax/CLI.rakumod +++ b/lib/Fornax/CLI.rakumod @@ -15,14 +15,14 @@ proto MAIN(|) is export { unless so @*ARGS { put $*USAGE; exit }; {*} } #| Collection of tools to visualize Path Finding Algorithms multi sub MAIN( File $input, #= fornax format file (solved) - IO() :$out = '/tmp', #= output directory (default: /tmp) - Int() :$batch = 4, #= batch size (generate frames in parallel) - Rat() :$frame-rate = 1, #= frame rate (default: 1) + + Int() :$batch = 4, #= number of iterations to process at once (default: 4) + Int() :$fps = 1, #= frame rate for video solution (default: 1) Bool :$skip-video, #= skip video solution - Bool :$verbose = True, #= verbosity + Bool :$verbose = True, #= verbosity (default: True) ) is export { my IO() $output = "%s/fornax-%s".sprintf( - $out.absolute, ('a'...'z', 'A'...'Z', 0...9).roll(8).join + '/tmp', ('a'...'z', 'A'...'Z', 0...9).roll(8).join ); mkdir $output; die "Output directory doesn't exist" unless $output.d; @@ -166,7 +166,7 @@ multi sub MAIN( put "[fornax] Creating a slideshow." if $verbose; my Str $log-level = $verbose ?? "info" !! "error"; - run «ffmpeg -loglevel "$log-level" -r "$frame-rate" -i "$output/\%08d.png" + run «ffmpeg -loglevel "$log-level" -r "$fps" -i "$output/\%08d.png" -vf 'tpad=stop_mode=clone:stop_duration=4' -vcodec libx264 -crf 28 -pix_fmt yuv420p "$output/solution.mp4"»; } -- cgit 1.4.1-2-gfad0 From 22aa1c9b322c424724516d70b77d1d5b93155697 Mon Sep 17 00:00:00 2001 From: Andinus Date: Wed, 17 Nov 2021 18:50:25 +0530 Subject: Alias frame-rate to fps Preserves backwards compatibility. --- lib/Fornax/CLI.rakumod | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/lib/Fornax/CLI.rakumod b/lib/Fornax/CLI.rakumod index 32303fc..8b18215 100644 --- a/lib/Fornax/CLI.rakumod +++ b/lib/Fornax/CLI.rakumod @@ -17,7 +17,7 @@ multi sub MAIN( File $input, #= fornax format file (solved) Int() :$batch = 4, #= number of iterations to process at once (default: 4) - Int() :$fps = 1, #= frame rate for video solution (default: 1) + Int() :fps($frame-rate) = 1, #= frame rate for video solution (default: 1) Bool :$skip-video, #= skip video solution Bool :$verbose = True, #= verbosity (default: True) ) is export { @@ -166,7 +166,7 @@ multi sub MAIN( put "[fornax] Creating a slideshow." if $verbose; my Str $log-level = $verbose ?? "info" !! "error"; - run «ffmpeg -loglevel "$log-level" -r "$fps" -i "$output/\%08d.png" + run «ffmpeg -loglevel "$log-level" -r "$frame-rate" -i "$output/\%08d.png" -vf 'tpad=stop_mode=clone:stop_duration=4' -vcodec libx264 -crf 28 -pix_fmt yuv420p "$output/solution.mp4"»; } -- cgit 1.4.1-2-gfad0 From 428fa000256bd47c121f8b03b94f37e9f29095e0 Mon Sep 17 00:00:00 2001 From: Andinus Date: Wed, 17 Nov 2021 23:12:15 +0530 Subject: raku/DFS: Add DFS implementation in raku, Add input 06 --- algorithms/raku/DFS.raku | 69 ++++++++++++++++++++++++++++++++++++++++++++++++ resources/input/06 | 18 +++++++++++++ 2 files changed, 87 insertions(+) create mode 100644 algorithms/raku/DFS.raku create mode 100644 resources/input/06 diff --git a/algorithms/raku/DFS.raku b/algorithms/raku/DFS.raku new file mode 100644 index 0000000..4789ce9 --- /dev/null +++ b/algorithms/raku/DFS.raku @@ -0,0 +1,69 @@ +use Octans::Neighbors; + +subset File of Str where *.IO.f; + +# Cells as defined by fornax format. +constant $PATH = '.'; +constant $BLOK = '#'; +constant $DEST = '$'; +constant $STRT = '^'; +constant $VIS = '-'; +constant $CUR = '@'; +constant $CURPATH = '~'; + +sub MAIN(File $input) { + my @maze = $input.IO.lines.map(*.comb); + die "Inconsistent maze" unless [==] @maze.map(*.elems); + + put "rows:{@maze.elems} cols:{@maze[0].elems}"; + dfs(@maze, 0, 0); +} + +sub dfs( + @maze, Int $y, Int $x, @visited?, @cur-path? --> Bool +) { + # If @visited was not passed then mark the given cell as visited + # because it's the cell we're starting at. + @visited[$y][$x] = True unless @visited; + @cur-path[$y][$x] = True unless @cur-path; + + # neighbor block loops over the neighbors of $y, $x. + neighbor: for neighbors(@maze, $y, $x).List.pick(*) -> $pos { + # Move on to next neighbor if we've already visited this one. + next neighbor if @visited[$pos[0]][$pos[1]]; + + # Printing Marker cells. + given @maze[$pos[0]][$pos[1]] { + when $DEST { print "|" } + when $BLOK { print "!" } + } + + # Print the maze on every iteration. + for 0..@maze.end -> $j { + for 0..@maze[0].end -> $k { + if @maze[$j][$k] eq $STRT | $DEST { + print @maze[$j][$k]; + } else { + if $j == $pos[0] and $k == $pos[1] { + print "@"; + } else { + print( + @cur-path[$j][$k] + ?? "~" !! @visited[$j][$k] ?? "-" !! @maze[$j][$k] + ); + } + } + } + } + print "\n"; + + given @maze[$pos[0]][$pos[1]] { + when $DEST { exit; } + when $PATH|$STRT { + @visited[$pos[0]][$pos[1]] = @cur-path[$pos[0]][$pos[1]] = True; + dfs(@maze, $pos[0], $pos[1], @visited, @cur-path); + @cur-path[$pos[0]][$pos[1]] = False; + } + } + } +} diff --git a/resources/input/06 b/resources/input/06 new file mode 100644 index 0000000..8e58064 --- /dev/null +++ b/resources/input/06 @@ -0,0 +1,18 @@ +^...........#................... +........#...#................... +.......#..########.............. +.......#........................ +.......#........................ +......#......................... +...#.........#....############## +...#.........#.................. +.......#.....#.....#............ +...................#............ +........#..........#............ +....#...#...##.....#............ +........#..........#...######### +...................#............ +...................#......$..... +................................ +.............#.................. +.............#.................. -- cgit 1.4.1-2-gfad0 From 71ff6400dc3aef9ceb6c71f0d102f5b9ff40bab8 Mon Sep 17 00:00:00 2001 From: Andinus Date: Wed, 17 Nov 2021 23:14:44 +0530 Subject: Add usage instructions --- README | 53 +++++++++++++++++++++++++++++++++-------------------- README.org | 10 ++++++++++ 2 files changed, 43 insertions(+), 20 deletions(-) diff --git a/README b/README index 3a9352a..e1d4189 100644 --- a/README +++ b/README @@ -11,17 +11,18 @@ Table of Contents ───────────────── 1. Demo -2. Installation +2. Usage +3. Installation .. 1. Release .. 2. From Source -3. Project Structure -4. Documentation +4. Project Structure +5. Documentation .. 1. Options -5. Fornax Format +6. Fornax Format .. 1. Grids .. 2. Maze (input) .. 3. Solution (output) -6. News +7. News .. 1. v0.1.1 - 2021-11-16 .. 2. v0.1.0 - 2021-11-03 @@ -64,7 +65,19 @@ Writings: -2 Installation +2 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 + └──── + + +3 Installation ══════════════ `fornax' is written in Raku, it can be installed with `zef'. You can @@ -74,7 +87,7 @@ Writings: • *Note*: `Cairo' module & `ffmpeg' program is required. -2.1 Release +3.1 Release ─────────── 1. Run `zef install 'fornax:auth'' @@ -85,14 +98,14 @@ Writings: get them from this repository. -2.2 From Source +3.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' +3.2.1 Without `git' ╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌ 1. Download the release: @@ -102,7 +115,7 @@ Writings: 3. Run `zef install .' in source directory. -2.2.2 With `git' +3.2.2 With `git' ╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌ All commits by /Andinus/ will be signed by this [PGP Key]. @@ -121,7 +134,7 @@ Writings: -3 Project Structure +4 Project Structure ═══════════════════ • Algorithms are located in `algorithms/' directory, sub-directory @@ -138,7 +151,7 @@ Writings: `8cef86f0eb8b46b0ed2d7c37fa216890300249f6'. -4 Documentation +5 Documentation ═══════════════ Fornax parses /Fornax format/, generates a `PNG' for each iteration @@ -152,7 +165,7 @@ Writings: • *Note*: `/tmp' must exist. -4.1 Options +5.1 Options ─────────── • `input': This takes solved input file in the /Fornax/ format. @@ -161,7 +174,7 @@ Writings: • `batch': Number of iterations to process at once. -5 Fornax Format +6 Fornax Format ═══════════════ Fornax format defines 2 formats: @@ -169,7 +182,7 @@ Writings: • Solution (output) -5.1 Grids +6.1 Grids ───────── A grid is printed for every iteration. Grids are composed of cells. @@ -188,7 +201,7 @@ Writings: ━━━━━━━━━━━━━━━━━━━━━━━━━━ -5.2 Maze (input) +6.2 Maze (input) ──────────────── Maze input must be in this format: @@ -200,7 +213,7 @@ Writings: input file or it ask the user. -5.3 Solution (output) +6.3 Solution (output) ───────────────────── Fornax solution format is an intermediate output file generated after @@ -230,10 +243,10 @@ Writings: • First iteration is assumed to be the maze. -6 News +7 News ══════ -6.1 v0.1.1 - 2021-11-16 +7.1 v0.1.1 - 2021-11-16 ─────────────────────── ⁃ Add option to skip generating slideshow. @@ -246,7 +259,7 @@ Writings: ⁃ Add more solutions. -6.2 v0.1.0 - 2021-11-03 +7.2 v0.1.0 - 2021-11-03 ─────────────────────── ⁃ Initial implementation: diff --git a/README.org b/README.org index 5f580e8..f182f03 100644 --- a/README.org +++ b/README.org @@ -33,6 +33,16 @@ Fornax v0.1.0: - DFS-51-incomplete (upto 4,000 frames; 120 fps): https://diode.zone/w/hWWaw8uKHCP5weUP5WWArD +* Usage + +#+begin_src sh +# Solve the maze. +raku algorithms/raku/DFS.raku resources/input/06 > /tmp/solution.fornax + +# Visualize the solution. +raku -Ilib bin/fornax /tmp/solution.fornax +#+end_src + * Installation ~fornax~ is written in Raku, it can be installed with ~zef~. You can also -- cgit 1.4.1-2-gfad0 From 03745f7ce6b53054560f1c35d256de00c1113fd8 Mon Sep 17 00:00:00 2001 From: Andinus Date: Thu, 18 Nov 2021 16:43:05 +0530 Subject: Copy neighbors subroutine --- algorithms/raku/DFS.raku | 59 ++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 57 insertions(+), 2 deletions(-) diff --git a/algorithms/raku/DFS.raku b/algorithms/raku/DFS.raku index 4789ce9..0cc7207 100644 --- a/algorithms/raku/DFS.raku +++ b/algorithms/raku/DFS.raku @@ -1,5 +1,3 @@ -use Octans::Neighbors; - subset File of Str where *.IO.f; # Cells as defined by fornax format. @@ -67,3 +65,60 @@ sub dfs( } } } + +# neighbors returns the neighbors of given index. Neighbors are cached +# in @neighbors array. This way we don't have to compute them +# everytime neighbors subroutine is called for the same position. We +# don't need this caching here since every cell will be visited only +# once. This subroutine was taken from Octans::Neighbors. +sub neighbors( + @puzzle, Int $y, Int $x --> List +) is export { + # @directions is holding a list of directions we can move in. It's + # used later for neighbors subroutine. + state List @directions = ( + # $y, $x + ( +1, +0 ), # bottom + ( -1, +0 ), # top + ( +0, +1 ), # left + ( +0, -1 ), # right + ); + + # @neighbors holds the neighbors of given position. + state Array @neighbors; + + if @puzzle[$y][$x] { + # Don't re-compute neighbors. + unless @neighbors[$y][$x] { + # Set it to an empty array because otherwise if it has no + # neighbors then it would've be recomputed everytime + # neighbors() was called. + @neighbors[$y][$x] = []; + + my Int $pos-x; + my Int $pos-y; + + # Starting from the intital position of $y, $x we move to + # each direction according to the values specified in + # @directions array. In this case we're just trying to + # move in 4 directions (top, bottom, left & right). + direction: for @directions -> $direction { + $pos-y = $y + $direction[0]; + $pos-x = $x + $direction[1]; + + # If movement in this direction is out of puzzle grid + # boundary then move on to next direction. + next direction unless @puzzle[$pos-y][$pos-x]; + + # If neighbors exist in this direction then add them + # to @neighbors[$y][$x] array. + push @neighbors[$y][$x], [$pos-y, $pos-x]; + } + } + } else { + # If it's out of boundary then return no neighbor. + @neighbors[$y][$x] = []; + } + + return @neighbors[$y][$x]; +} -- cgit 1.4.1-2-gfad0 From 90f8478915a650be018667486449cbf00e9cd70c Mon Sep 17 00:00:00 2001 From: Andinus Date: Thu, 18 Nov 2021 16:56:34 +0530 Subject: Update README structure, Add bugs --- README | 89 +++++++++++++++++++++++++++++++++----------------------------- README.org | 53 +++++++++++++++++++++---------------- 2 files changed, 78 insertions(+), 64 deletions(-) diff --git a/README b/README index e1d4189..af6327f 100644 --- a/README +++ b/README @@ -15,14 +15,12 @@ Table of Contents 3. Installation .. 1. Release .. 2. From Source -4. Project Structure -5. Documentation +4. Documentation .. 1. Options -6. Fornax Format -.. 1. Grids -.. 2. Maze (input) -.. 3. Solution (output) -7. News +.. 2. Fornax Format +.. 3. Project Structure +5. Bugs +6. News .. 1. v0.1.1 - 2021-11-16 .. 2. v0.1.0 - 2021-11-03 @@ -134,24 +132,7 @@ Writings: -4 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'. - - -5 Documentation +4 Documentation ═══════════════ Fornax parses /Fornax format/, generates a `PNG' for each iteration @@ -160,12 +141,8 @@ Writings: • 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. - -5.1 Options +4.1 Options ─────────── • `input': This takes solved input file in the /Fornax/ format. @@ -174,16 +151,16 @@ Writings: • `batch': Number of iterations to process at once. -6 Fornax Format -═══════════════ +4.2 Fornax Format +───────────────── Fornax format defines 2 formats: • Maze (input) • Solution (output) -6.1 Grids -───────── +4.2.1 Grids +╌╌╌╌╌╌╌╌╌╌╌ A grid is printed for every iteration. Grids are composed of cells. @@ -201,8 +178,8 @@ Writings: ━━━━━━━━━━━━━━━━━━━━━━━━━━ -6.2 Maze (input) -──────────────── +4.2.2 Maze (input) +╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌ Maze input must be in this format: ┌──── @@ -213,8 +190,8 @@ Writings: input file or it ask the user. -6.3 Solution (output) -───────────────────── +4.2.3 Solution (output) +╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌ Fornax solution format is an intermediate output file generated after solving the maze. Algorithms must output the solution in this format: @@ -243,10 +220,40 @@ Writings: • First iteration is assumed to be the maze. -7 News +4.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'. + + +5 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: + . + + +6 News ══════ -7.1 v0.1.1 - 2021-11-16 +6.1 v0.1.1 - 2021-11-16 ─────────────────────── ⁃ Add option to skip generating slideshow. @@ -259,7 +266,7 @@ Writings: ⁃ Add more solutions. -7.2 v0.1.0 - 2021-11-03 +6.2 v0.1.0 - 2021-11-03 ─────────────────────── ⁃ Initial implementation: diff --git a/README.org b/README.org index f182f03..ec8d3f0 100644 --- a/README.org +++ b/README.org @@ -86,21 +86,6 @@ cd fornax zef install . #+end_src -* 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~. - * Documentation Fornax parses /Fornax format/, generates a ~PNG~ for each iteration which is @@ -109,10 +94,6 @@ 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. - ** Options - ~input~: This takes solved input file in the /Fornax/ format. @@ -120,13 +101,13 @@ later converted to a slideshow with ~ffmpeg~. - ~skip-video~: Skip generating the video solution. - ~batch~: Number of iterations to process at once. -* Fornax Format +** Fornax Format Fornax format defines 2 formats: - Maze (input) - Solution (output) -** Grids +*** Grids A grid is printed for every iteration. Grids are composed of cells. @@ -141,7 +122,7 @@ A grid is printed for every iteration. Grids are composed of cells. | Current Path | ~~~ | | Current Position | ~@~ | -** Maze (input) +*** Maze (input) Maze input must be in this format: #+begin_src @@ -151,7 +132,7 @@ Maze input must be in this format: It is upto the program to infer the number of rows & columns from the input file or it ask the user. -** Solution (output) +*** Solution (output) Fornax solution format is an intermediate output file generated after solving the maze. Algorithms must output the solution in this format: @@ -178,6 +159,32 @@ columns is known, the whole grid should be printed in a single line. - 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: + https://github.com/rakudo/rakudo/pull/4634. + * News ** v0.1.1 - 2021-11-16 -- cgit 1.4.1-2-gfad0 From eb96ab962545cf9b403f18422f1de698d9619499 Mon Sep 17 00:00:00 2001 From: Andinus Date: Thu, 18 Nov 2021 16:56:58 +0530 Subject: Move frame generation to a module, update progress reporting --- lib/Fornax/CLI.rakumod | 123 ++++++++------------------------------- lib/Fornax/GenerateFrame.rakumod | 100 +++++++++++++++++++++++++++++++ 2 files changed, 123 insertions(+), 100 deletions(-) create mode 100644 lib/Fornax/GenerateFrame.rakumod diff --git a/lib/Fornax/CLI.rakumod b/lib/Fornax/CLI.rakumod index 8b18215..d066ebf 100644 --- a/lib/Fornax/CLI.rakumod +++ b/lib/Fornax/CLI.rakumod @@ -1,5 +1,4 @@ -use Cairo; -use Fornax::Hex2RGB; +use Fornax::GenerateFrame; subset File of Str where *.IO.f; @@ -19,7 +18,7 @@ multi sub MAIN( Int() :$batch = 4, #= number of iterations to process at once (default: 4) Int() :fps($frame-rate) = 1, #= frame rate for video solution (default: 1) Bool :$skip-video, #= skip video solution - Bool :$verbose = True, #= verbosity (default: True) + Bool :$debug, #= debug logs ) is export { my IO() $output = "%s/fornax-%s".sprintf( '/tmp', ('a'...'z', 'A'...'Z', 0...9).roll(8).join @@ -27,40 +26,14 @@ multi sub MAIN( mkdir $output; die "Output directory doesn't exist" unless $output.d; - put "[fornax] Output: '$output'" if $verbose; + put "[fornax] Output: '$output'"; my Str @lines = $input.IO.lines; my Int() %meta{Str} = Metadata.parse(@lines.first).Hash - or die "Cannot parse metadata"; - - # Cells as defined by fornax format. - constant $PATH = '.'; - constant $BLOK = '#'; - constant $DEST = '$'; - constant $STRT = '^'; - constant $VIS = '-'; - constant $CUR = '@'; - constant $CURPATH = '~'; + or die "Cannot parse metadata"; constant %CANVAS = :1920width, :1080height; - # Colors. - constant %C = ( - bg-main => "#ffffff", - - red-subtle-bg => "#f2b0a2", - blue-subtle-bg => "#b5d0ff", - cyan-subtle-bg => "#c0efff", - green-subtle-bg => "#aecf90", - - fg-main => "#000000", - - fg-special-cold => "#093060", - fg-special-warm => "#5d3026", - fg-special-mild => "#184034", - fg-special-calm => "#61284f", - ).map: {.key => hex2rgb(.value)}; - # Every cell must be square. Get the maximum width, height and use # that to decide which is to be used. my Int %cell = width => %CANVAS div %meta, @@ -79,7 +52,8 @@ multi sub MAIN( $side = %cell; } - enum IterStatus ; + my $render-start = now; + my Int $total-frames = @lines.elems - 1; my Promise @p; for @lines.skip.kv -> $idx, $iter is rw { @@ -88,89 +62,38 @@ multi sub MAIN( if @p.elems == $batch { await @p; @p = []; + + print "\r"; + print "%s Remaining: %.2fs Elapsed: %.2fs %s".sprintf( + "[fornax $idx/$total-frames]", + ((now - $render-start) / $idx) * ($total-frames - $idx), + now - $render-start, " ", + ); } push @p, start { - my IterStatus $status; - given $iter.substr(0, 1) { - when '|' { $status = Completed } - when '!' { $status = Blocked } - default { $status = Walking } - }; - - # Remove marker. - $iter .= substr(1) if $status == Completed|Blocked; - - put "[fornax] $idx $iter $status" if $verbose; - - my @grid = $iter.comb.rotor: %meta; - warn "Invalid grid: $idx $iter $status" unless @grid.elems == %meta; - - given Cairo::Image.create( - Cairo::FORMAT_ARGB32, %CANVAS, %CANVAS - ) { - given Cairo::Context.new($_) { - # Paint the entire canvas white. - .rgb: |%C; - .rectangle(0, 0, %CANVAS, %CANVAS); - .fill; - - for ^%meta -> $r { - for ^%meta -> $c { - my Int @target = %excess div 2 + $c * $side, - %excess div 2 + $r * $side, - $side, $side; - - .rectangle: |@target; - - given @grid[$r][$c] -> $cell { - # According to the format, current - # position may be prioritized over - # Destination symbol so we colorize it - # according to $status. - when $cell eq $CUR { - .rgba: |%C, 0.56; - .rgba: |%C, 0.72 if $status == Completed; - .rgba: |%C, 0.72 if $status == Blocked; - } - when $cell eq $CURPATH { - .rgba: |%C, 0.84; - .rgba: |%C, 0.96 if $status == Completed; - .rgba: |%C, 0.96 if $status == Blocked; - } - when $cell eq $VIS { - .rgba: |%C, 0.72; - } - when $cell eq $BLOK { .rgba: |%C, 0.56 } - when $cell eq $STRT|$DEST { .rgba: |%C, 0.72 } - default { .rgba: |%C, 0.08 } - } - .fill :preserve; - - .rgb: |%C; - .stroke; - } - } - } - .write_png("%s/%08d.png".sprintf: $output, $idx); - .finish; - } + generate-frame( + :%CANVAS, :%excess, :$side, :%meta, :$iter, :$idx, :$debug, + :out("%s/%08d.png".sprintf: $output, $idx), + ); } } # Wait for remaining jobs to finish. await @p; - put "[fornax] Generated images." if $verbose; + print "\r"; + put "[fornax] Generated $total-frames frames in %.2fs. %s".sprintf( + now - $render-start, " " x 16, + ); unless $skip-video { - put "[fornax] Creating a slideshow." if $verbose; + put "[fornax] Creating a slideshow."; - my Str $log-level = $verbose ?? "info" !! "error"; + my Str $log-level = $debug ?? "info" !! "error"; run «ffmpeg -loglevel "$log-level" -r "$frame-rate" -i "$output/\%08d.png" -vf 'tpad=stop_mode=clone:stop_duration=4' -vcodec libx264 -crf 28 -pix_fmt yuv420p "$output/solution.mp4"»; } - put "[fornax] Output: '$output'"; } multi sub MAIN( diff --git a/lib/Fornax/GenerateFrame.rakumod b/lib/Fornax/GenerateFrame.rakumod new file mode 100644 index 0000000..e19d342 --- /dev/null +++ b/lib/Fornax/GenerateFrame.rakumod @@ -0,0 +1,100 @@ +use Cairo; +use Fornax::Hex2RGB; + +# Cells as defined by fornax format. +constant $PATH = '.'; +constant $BLOK = '#'; +constant $DEST = '$'; +constant $STRT = '^'; +constant $VIS = '-'; +constant $CUR = '@'; +constant $CURPATH = '~'; + +# Colors. +constant %C = ( + bg-main => "#ffffff", + + red-subtle-bg => "#f2b0a2", + blue-subtle-bg => "#b5d0ff", + cyan-subtle-bg => "#c0efff", + green-subtle-bg => "#aecf90", + + fg-main => "#000000", + + fg-special-cold => "#093060", + fg-special-warm => "#5d3026", + fg-special-mild => "#184034", + fg-special-calm => "#61284f", +).map: {.key => hex2rgb(.value)}; + +enum IterStatus ; + +sub generate-frame( + :%CANVAS, :$out, :%excess, :$side, :%meta, :$iter is copy + , :$idx, :$debug, +) is export { + my IterStatus $status; + given $iter.substr(0, 1) { + when '|' { $status = Completed } + when '!' { $status = Blocked } + default { $status = Walking } + }; + + # Remove marker. + $iter .= substr(1) if $status == Completed|Blocked; + + put "\n[fornax] $idx $iter $status" if $debug; + + my @grid = $iter.comb.rotor: %meta; + warn "Invalid grid: $idx $iter $status" unless @grid.elems == %meta; + + given Cairo::Image.create( + Cairo::FORMAT_ARGB32, %CANVAS, %CANVAS + ) { + given Cairo::Context.new($_) { + # Paint the entire canvas white. + .rgb: |%C; + .rectangle(0, 0, %CANVAS, %CANVAS); + .fill; + + # This seems to be slower than creating an intermediate + # variable and assigning from that. Difference is not much + # so we'll ignore it. + for ^%meta X ^%meta -> ($r, $c) { + my Int @target = %excess div 2 + $c * $side, + %excess div 2 + $r * $side, + $side, $side; + + .rectangle: |@target; + + given @grid[$r][$c] -> $cell { + # According to the format, current position may be + # prioritized over Destination symbol so we + # colorize it according to $status. + when $cell eq $CUR { + .rgba: |%C, 0.56; + .rgba: |%C, 0.72 if $status == Completed; + .rgba: |%C, 0.72 if $status == Blocked; + } + when $cell eq $CURPATH { + .rgba: |%C, 0.84; + .rgba: |%C, 0.96 if $status == Completed; + .rgba: |%C, 0.96 if $status == Blocked; + } + when $cell eq $VIS { + .rgba: |%C, 0.72; + } + when $cell eq $BLOK { .rgba: |%C, 0.56 } + when $cell eq $STRT|$DEST { .rgba: |%C, 0.72 } + default { .rgba: |%C, 0.08 } + } + .fill :preserve; + + .rgb: |%C; + .stroke; + } + } + .write_png($out); + .finish; + } +} -- cgit 1.4.1-2-gfad0 From 3149b8c7148797e340fc6c226b031b2eeb532560 Mon Sep 17 00:00:00 2001 From: Andinus Date: Thu, 18 Nov 2021 16:58:29 +0530 Subject: Add GenerateFrame to META6.json, update version --- META6.json | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/META6.json b/META6.json index 1cf95de..3fc67d1 100644 --- a/META6.json +++ b/META6.json @@ -1,14 +1,15 @@ { "name" : "fornax", "auth" : "zef:andinus", - "version" : "0.1.0", + "version" : "0.2.0", "description" : "Collection of tools to visualize Path Finding Algorithms", "authors" : [ "Andinus " ], "license" : "ISC", "perl" : "6.d", "provides" : { "Fornax::CLI" : "lib/Fornax/CLI.rakumod", - "Fornax::Hex2RGB" : "lib/Fornax/Hex2RGB.rakumod" + "Fornax::Hex2RGB" : "lib/Fornax/Hex2RGB.rakumod", + "Fornax::GenerateFrame" : "lib/Fornax/GenerateFrame.rakumod" }, "depends" : [ "Cairo:ver<0.2.7+>" -- cgit 1.4.1-2-gfad0 From 5df46f19a7ed9772cd639a81e4ab57efb8023bbb Mon Sep 17 00:00:00 2001 From: Andinus Date: Thu, 18 Nov 2021 16:59:32 +0530 Subject: Add basic test for Fornax::GenerateFrame --- t/00-basic.rakutest | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/t/00-basic.rakutest b/t/00-basic.rakutest index a119847..9731395 100644 --- a/t/00-basic.rakutest +++ b/t/00-basic.rakutest @@ -1,6 +1,7 @@ use Test; -plan 2; +plan 3; use-ok 'Fornax::CLI'; use-ok 'Fornax::Hex2RGB'; +use-ok 'Fornax::GenerateFrame'; -- cgit 1.4.1-2-gfad0 From 8af7ea1e0572870eb49e6a6784736a2ca803600e Mon Sep 17 00:00:00 2001 From: Andinus Date: Thu, 18 Nov 2021 17:00:08 +0530 Subject: Set stop duration to 2 seconds --- lib/Fornax/CLI.rakumod | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/Fornax/CLI.rakumod b/lib/Fornax/CLI.rakumod index d066ebf..bac08ff 100644 --- a/lib/Fornax/CLI.rakumod +++ b/lib/Fornax/CLI.rakumod @@ -91,7 +91,7 @@ multi sub MAIN( my Str $log-level = $debug ?? "info" !! "error"; run «ffmpeg -loglevel "$log-level" -r "$frame-rate" -i "$output/\%08d.png" - -vf 'tpad=stop_mode=clone:stop_duration=4' + -vf 'tpad=stop_mode=clone:stop_duration=2' -vcodec libx264 -crf 28 -pix_fmt yuv420p "$output/solution.mp4"»; } } -- cgit 1.4.1-2-gfad0 From b1259dc7b9aba4831cd61bf3521708ec3089ed3c Mon Sep 17 00:00:00 2001 From: Andinus Date: Thu, 18 Nov 2021 17:09:51 +0530 Subject: Set default crf to 24 From https://trac.ffmpeg.org/wiki/Encode/H.265: The default is 28, and it should visually correspond to libx264 video at CRF 23, but result in about half the file size. This will result in larger videos. Maybe the default should be libx265. I did try it, results in smaller videos but I wasn't able to play the video on Firefox. --- lib/Fornax/CLI.rakumod | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/Fornax/CLI.rakumod b/lib/Fornax/CLI.rakumod index bac08ff..98f20a7 100644 --- a/lib/Fornax/CLI.rakumod +++ b/lib/Fornax/CLI.rakumod @@ -92,7 +92,7 @@ multi sub MAIN( my Str $log-level = $debug ?? "info" !! "error"; run «ffmpeg -loglevel "$log-level" -r "$frame-rate" -i "$output/\%08d.png" -vf 'tpad=stop_mode=clone:stop_duration=2' - -vcodec libx264 -crf 28 -pix_fmt yuv420p "$output/solution.mp4"»; + -vcodec libx264 -crf 24 -pix_fmt yuv420p "$output/solution.mp4"»; } } -- cgit 1.4.1-2-gfad0