How to make flood-fill Function recursively fill the ASCII image

Question

I need to use floodFill Function to turn all dots inside asterisk contour of an ASCII Image turn into asterisks. Could someone help?

"use strict";

let bitmap = [
  "................**********........................",
  "...............*..........*.......................",
  "..........*****............*........*.............",
  ".........*.................*.......*.*....*****...",
  "........*................***......*...*.**.....**.",
  "....****.................*.......*.....*.........*",
  "..**......................*******................*",
  ".*...............................................*",
  ".*...............................................*",
  "*...........****.............................****.",
  "*..........*....*.........................***.....",
  ".*.........*....*.......................**........",
  "..***.......****.......................*..........",
  ".....****......................******..*..........",
  ".........**********************.....****.........."
];



const bitmap2string = bitmap => bitmap.join("\n");

console.log(bitmap2string(bitmap));

const showOnPosition = (x, y) => 
  bitmap[y].charAt(x);

const changeSymbol = (x, y, symbol) => 
  bitmap[y].substr(0, x) + symbol + bitmap[y].substr(x + 1);

const floodFill = (x, y) => 
  showOnPosition(x, y) !== "*" 
    ? bitmap.map((line, i) => (i === y ? changeSymbol(x, y, "*") : line)) 
    : bitmap;

I've written the code for:

• showOnPosition - to check what's currently on x, y coordinates of an Array
• changeSymbol - to change the symbol on any given position
• floodFill - that checks what's on a current position and if it's not an asterisk changes it to asterisk and gives an updated array in console.

Now I'm stuck with how do I make all this recursively go through image (to the right) and fills the given contour with asterisks.

The result should be: with the call of floodFill Function with any coordinates, e.g. console.log(floodFill(8, 7)) it shows the following in the console

Answer 1

Here's a lazy but easy implementation:

let bitmap = [
    "................**********........................",
    "...............*..........*.......................",
    "..........*****............*........*.............",
    ".........*.................*.......*.*....*****...",
    "........*................***......*...*.**.....**.",
    "....****.................*.......*.....*.........*",
    "..**......................*******................*",
    ".*...............................................*",
    ".*...............................................*",
    "*...........****.............................****.",
    "*..........*....*.........................***.....",
    ".*.........*....*.......................**........",
    "..***.......****.......................*..........",
    ".....****......................******..*..........",
    ".........**********************.....****.........."
];

// convert to an array of arrays
bitmap = bitmap.map(row => [...row]);
xsize = bitmap[0].length;
ysize = bitmap.length;

floodFill = (x, y) => {

    // check bounds
    if (y < 0 || y >= ysize) return;
    if (x < 0 || x >= xsize) return;

    // already painted?
    if (bitmap[y][x] === '*') return;

    // paint!
    bitmap[y][x] = '*';

    // fill neighbours
    floodFill(x - 1, y);
    floodFill(x + 1, y);
    floodFill(x, y - 1);
    floodFill(x, y + 1);
};

floodFill(7, 8);

// convert to string
bitmap = bitmap.map(row => row.join('')).join('\n');

document.write('<pre>' + bitmap);

The problem with this solution is that the starting point is arbitrary and might well lie outside the bounds. A better approach would be to scan the matrix line by line and do a kind of "ray tracing" to determine if a point is inside or outside. This will run without recursion, in linear time.