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 :
- just a path
- all paths
- the shortest path
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 :
- as full state on the stack
- as reversable action on the stack
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 :
- check if the goal is achieved
REPEAT
- check if the next step is possible at all
- check if the next step leads to a known position - prevent circles
- do this next step
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