where : ibrtses delphi

due to special characters. Have a look at the source of this HTML page

with notepad instead

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.

different aims to be achieved :

- just a path
- all paths
- the shortest path

The shortest path can only be determined when all paths are known, hence the

order of the listing.

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

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

The standard implementaion is :

- check if the goal is achieved
- 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

REPEAT

UNTIL (the goal is achieved) or (this position failed)

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 ..

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