Where Can I Reach

Introduction

In a big level it is not always obvious where the worker can get to. Crates block corridors; a push can shut a door behind you. This section adds a key, W, that marks every square he can reach from where he stands - and the way it does it is one of the neatest ideas in programming: a procedure that calls itself.

Spreading Out

Think of spilling water on the square the worker stands on. It spreads to each neighbouring square that is open - floor or a goal - and from each of those to their neighbours, and so on, until it has run everywhere it can. Walls and crates stop it. Where the water got to is where he can walk.

Fill is that spreading, for one square:

if not Seen[Row, Col] and
   (L.Grid[Row, Col] in
     [Floor, Goal]) then
begin
  Seen[Row, Col] := True;
  At(Row, Col);
  Write('::');
  Fill(Row - 1, Col);
  Fill(Row + 1, Col);
  Fill(Row, Col - 1);
  Fill(Row, Col + 1);
end;

If the square is open and not yet reached, mark it, show it, and then fill from each of its four neighbours. That is all. Each of those calls does the same for its own neighbours, and the calls stop by themselves: a square already Seen is not filled twice, and a wall or a crate is not filled at all. The Seen array - a Boolean for every square - is the water.

Fill also checks that the square is on the board at all, so that a level with a gap in its walls cannot send it off the edge.

Where clears Seen, calls Fill once for the worker's own square, waits for a key, and then redraws every square that was marked - the :: marks go and the level is as it was.

Calling Itself

S16 showed that a routine can call itself, and what that needs on this Turbo Pascal: {$A-} at the top of the program. Without it, every call of Fill shares one Row and one Col, and the fill goes wrong - with no error at all. With it, each call has its own.

S16 also found the other rule for recursion here: pass only values, never a variable of the procedure's own as a var parameter. Fill takes Row and Col by value, and Seen belongs to the whole program.

How deep does it go? One call per square reached, at most - 160 on this board, and S16 ran 3,000 deep without trouble.

The Code

Start WARE8 from WARE7.

The program's second line, straight after program Warehouse;:

{$A-}

Add Seen to the variables, after Undo: MoveP;:

  Seen: array[1..Rows, 1..Cols]
    of Boolean;

In DrawAll, the bottom line gains W:

  Write('U undo  W where  R restart');
  Write('  Q quit');

After Back, add:

procedure Fill(Row, Col: Integer);
begin
  if (Row >= 1) and (Row <= Rows) and
     (Col >= 1) and (Col <= Cols) then
    if not Seen[Row, Col] and
       (L.Grid[Row, Col] in
         [Floor, Goal]) then
    begin
      Seen[Row, Col] := True;
      At(Row, Col);
      Write('::');
      Fill(Row - 1, Col);
      Fill(Row + 1, Col);
      Fill(Row, Col - 1);
      Fill(Row, Col + 1);
    end;
end;

procedure Where;
var
  I, J: Integer;
  K: Char;
begin
  for I := 1 to Rows do
    for J := 1 to Cols do
      Seen[I, J] := False;
  Fill(R, C);
  Read(Kbd, K);
  for I := 1 to Rows do
    for J := 1 to Cols do
      if Seen[I, J] then
        Show(I, J);
end;

And a line in the main program's case:

      'W': Where;

Starting from

WARE7 from S33, read into a new work file WARE8. Make the changes, CTRL-K CTRL-D, S, R.

What you should see

Press W on the first level, and every open square is marked :: - all but the crate's:

Press any key and the marks go. On a crowded level, W shows at a glance which parts of the warehouse are shut off.

Change One Thing

• Take out {$A-}. Press W. Are all the squares marked?
• Take out the two lines Fill(Row, Col - 1); and Fill(Row, Col + 1);. Press W. Which squares are marked now, and why?
• Add Crate to the set in Fill, making it [Floor, Goal, Crate]. Press W. What does the fill do now?

Exercises

34.1 Count the squares the worker can reach, and show Reach and the number on the second line while the marks are showing.

34.2 Mark every crate that the worker can walk up to - any crate with a reached square beside it - with !!, and put it back afterwards.

34.3 Show how many empty goals the worker can reach.

Worked solutions are in Appendix II.

When It Goes Wrong

Summary

A flood fill marks a square, then fills from each of its four neighbours; squares already marked, and walls and crates, stop it. The procedure calls itself, so the program needs {$A-}, and it takes its square by value with the Seen array global. W shows the marks until a key is pressed, then redraws the squares they covered.

Next

S35, The Level Editor - designing your own levels inside the game, and saving them to the file.