Slacky Maze Challenge

{$I SRL-T/osr.simba}

type
  TPArray = record
    X, Y: Integer;
  end;

  TVisitedCell = record
    Distance: Integer;
    PreviousCell: TPArray;
  end;

var
  bmp: TMufasaBitmap;  // Bitmap (to load image into)
  start: TPArray;  // Start point
  stop: TPArray;   // End point
  visited: array of array of TVisitedCell;

function IsInBounds(const point: TPArray): Boolean; // Make sure not to go outside of the maze image
begin
  Result := (point.X >= 0) and (point.X < bmp.GetWidth()) and (point.Y >= 0) and (point.Y < bmp.GetHeight());
end;

function LoadMazeFromBitmap: array of array of Integer;
var
  x, y: Integer;
begin
  SetLength(Result, bmp.GetWidth(), bmp.GetHeight());
  for y := 0 to bmp.GetHeight() - 1 do
  begin
    for x := 0 to bmp.GetWidth() - 1 do
    begin
      if bmp.GetPixel(x, y) = clBlack then
        Result[x, y] := 1 // Wall of the maze
      else
        Result[x, y] := 0; // Open area that's moveable in
    end;
  end;
end;

function FindShortestPath(const maze: array of array of Integer): array of TPArray;
var
  directions: array[0..3] of TPArray; // N/E/S/W movement
  queue: array[0..629*479] of TPArray; // Hard-coded maximum size of the maze xD
  queueHead: Integer;   // Leading
  queueTail: Integer;   // Trailing
  current, next: TPArray;
  x, y, i: Integer;
begin
  SetLength(visited, bmp.GetWidth(), bmp.GetHeight());
  for y := 0 to bmp.GetHeight() - 1 do
  begin
    for x := 0 to bmp.GetWidth() - 1 do
    begin
      visited[x, y].Distance := -1;
      visited[x, y].PreviousCell.X := -1;
      visited[x, y].PreviousCell.Y := -1;
    end;
  end;

  directions[0].X := 1;
  directions[0].Y := 0;
  directions[1].X := -1;
  directions[1].Y := 0;
  directions[2].X := 0;
  directions[2].Y := 1;
  directions[3].X := 0;
  directions[3].Y := -1;

  queueHead := 0;
  queueTail := 0;
  queue[queueTail].X := start.X;
  queue[queueTail].Y := start.Y;
  Inc(queueTail);
  visited[start.X, start.Y].Distance := 0;

  while queueHead < queueTail do
  begin
    current := queue[queueHead];
    Inc(queueHead);

    if (current.X = stop.X) and (current.Y = stop.Y) then
      Break;

    for i := 0 to 3 do
    begin
      next.X := current.X + directions[i].X;
      next.Y := current.Y + directions[i].Y;

      if IsInBounds(next) and (maze[next.X, next.Y] = 0) and (visited[next.X, next.Y].Distance = -1) then
      begin
        visited[next.X, next.Y].Distance := visited[current.X, current.Y].Distance + 1;
        visited[next.X, next.Y].PreviousCell := current;
        queue[queueTail].X := next.X;
        queue[queueTail].Y := next.Y;
        Inc(queueTail);
      end;
    end;
  end;

  if (visited[stop.X, stop.Y].Distance = -1) then
  begin
    SetLength(Result, 0); // No path found, for debugging
    Exit;
  end;

  SetLength(Result, visited[stop.X, stop.Y].Distance + 1);
  current := stop;
  for i := visited[stop.X, stop.Y].Distance downto 0 do
  begin
    Result[i] := current;
    current := visited[current.X, current.Y].PreviousCell;
  end;
end;

procedure MarkPathOnBitmap(const path: array of TPArray); // Visualize the path on the bitmap
var
  i: Integer;
begin
  for i := 0 to Length(path) - 1 do
    bmp.SetPixel(path[i].X, path[i].Y, clBlue);
end;

begin
  bmp.Init();
  bmp.LoadFromFile('A PLACE ON MY COMPUTER U CHEEKY GOON'); // Hi, it's Saber from Discord :)

  start.X := 0;
  start.Y := 0;
  stop.X := 630;
  stop.Y := 480;

  MarkPathOnBitmap(FindShortestPath(LoadMazeFromBitmap));
  bmp.Debug();

  bmp.Free();
end.