where : ibrtses delphi

Delphi - backtracking

disclaimer

 the source code of this page may not appear correctly in certain browsers
due to special characters. Have a look at the source of this HTML page
with notepad instead

Introduction

Backtracking is used to solve problems with tree structures. Even problems
seemingly remote to trees such as a walking a maze are actually trees when
the decision 'back-left-straight-right' is considered a node in a tree.

Aims

Backtracking is the approach to find a path in a tree. There are serveral
different aims to be achieved : depending on the algorithm and the problem, 'just a path' is the first solution.
The shortest path can only be determined when all paths are known, hence the
order of the listing.

Implementation considerations

The implementation bases on recursion. Each step has to be reverseable,
hence the state has to be saved somehow. There are two approaches to save
the state : While the former is simpler it uses more stack. The later may be prefered
for bigger problems. Consider a game with 100x100 places. To mark the visited
places as array takes 10k booleans per step. The most unfortunate solution,
where all places have to be visited has 10k steps with 10k booleans each as
state, therefore using 100M booleans on the stack with the first approach.
The later uses several orders of magnitude less stack when just saving the position

Implementation

As usual in a recursion, the recursive function has to contain all the knowledge.
The standard implementaion is :
  1. check if the goal is achieved

    2. REPEAT
  2. check if the next step is possible at all
  3. check if the next step leads to a known position - prevent circles
  4. do this next step

    5. UNTIL (the goal is achieved) or (this position failed)
So the function has to return the success, hence the use of a function.
A prototype may look like : 
function step(..):boolean;	// true if goal reached
begin
 result:=false;
 if goal(..) then     // is this the position of the goal ?
   result:=true
 else begin
  // check all possible next steps
  if (step_possible(next_A))and
     (step_new(next_A)) then result:=step(next_A)
  if (not result) and 
     (step_possible(next_B))and
     (step_new(next_B)) then result:=step(next_B)
  if (not result) and 
     (step_possible(next_C))and
     (step_new(next_C)) then result:=step(next_C)
  if (not result) and 
     (step_possible(next_D))and
     (step_new(next_D)) then result:=step(next_D)
  ..
  ..
end;
This prototype does the basic but is quite useless. We would like to have the walked
path on a stack, named pathstack, which is defined outside : 
function step(..):boolean;	// true if goal reached
begin
 result:=false;
 if goal(..) then begin    	// is this the position the goal ?
   pathstack.push(currentposition); 
   result:=true;
  end;
 else begin
  // check all possible next steps
  if (step_possible(next_A))and
     (step_new(next_A)) then result:=step(next_A)
  if (not result) and 
     (step_possible(next_B))and
     (step_new(next_B)) then result:=step(next_B)
  if (not result) and 
     (step_possible(next_C))and
     (step_new(next_C)) then result:=step(next_C)
  if (not result) and 
     (step_possible(next_D))and
     (step_new(next_D)) then result:=step(next_D)
  ..
  ..
  if result then pathstack.push(currentposition);
end;
To get more specific, let's assume a maze : 
function step(x,y):boolean;	// true if goal reached
begin
 result:=false;
 if goal(x,y) then begin    // is this the position of the goal ?
   pathstack.push(currentposition as x,y); 
   result:=true;
  end;
 else begin
  // check all possible next steps
  if (step_possible(x,y+1))and
     (step_new(x,y+1)) then result:=step(x,y+1)
  if (not result)and
     (step_possible(x,y-1))and
     (step_new(x,y-1)) then result:=step(x,y-1)
  if (not result)and
     (step_possible(x+1,y))and
     (step_new(x+1,y)) then result:=step(x+1,y)
  if (not result)and
     (step_possible(x-1,y))and
     (step_new(x-1,y)) then result:=step(x-1,y)
  if result then pathstack.push(currentposition as x,y);
end;

function step_possible(x,y):boolean;
  knows the boundary and the walls of the maze

function step_new(x,y):boolean;
  returns true if the position (x,y) was not visited before.
  either operates on an array of boolean or on a pathstack 
  being built while walking.

the main :

pathstack.create;
found:=step(startx,starty);
if found then  .. pop the pathstack ..
A two player game would require to save the whole state, but
a maze just requires the vivited places to be saved.
We'll use a single array to store the visited places:
visited_places:array[..,..]of boolean;	// as big as the maze

function step(x,y):boolean;	// true if goal reached
begin
 result:=false;
 visited_places(x,y):=true;	// we're here !!
 if goal(x,y) then begin    	// is this the position of the goal ?
   pathstack.push(currentposition as x,y); 
   result:=true;
  end;
 else begin
  // check all possible next steps
  if (step_possible(x,y+1))and
     (step_new(x,y+1)) then result:=step(x,y+1);
  if (not result)and
     (step_possible(x,y-1))and
     (step_new(x,y-1)) then result:=step(x,y-1);
  if (not result)and
     (step_possible(x+1,y))and
     (step_new(x+1,y)) then result:=step(x+1,y);
  if (not result)and
     (step_possible(x-1,y))and
     (step_new(x-1,y)) then result:=step(x-1,y);
  if result then pathstack.push(currentposition as x,y);
end;

function step_possible(x,y):boolean;
  knows the boundary and the walls of the maze

function step_new(x,y):boolean;
begin
 result:=not visited_places(x,y);
end;

the main :

pathstack.create;
visited_places.clear;
found:=step(startx,starty);
if found then  .. pop the pathstack ..

notes

The above example just shows how to find the first path. Adding a few
lines may lead to a desired solution.
Backtracking is a simple algorithm, a few lines do it once the recursion
is understood


Feedback is welcome




Delphi
home

last updated: 15.july.99


sponsored links




Copyright (99,2000) Ing.Büro R.Tschaggelar