A* search algorithm: Difference between revisions

Line 2,738:

barriers are simply avoided, rather than costed at 100.

Note that the 23 visited nodes does not count walls, but with them this algorithm exactly matches the 35 of Racket.

<lang Phix>sequence grid = split("""

x:::::::

sequence grid = split("""

::::::::

::::~~###~~:

x:::::::

::#:::#:

::::::::

::#:::#:

::::###:

::#~~###~~#:

::#:::#:

::::::::

::#:::#:

::~~:::::~~:

::#####:

::::::::

""",'\n')

::::::::

""",'\n')

constant permitted = {{-1,-1},{0,-1},{1,-1},

{-1, 0}, {1, 0},

constant permitted = {{-1,-1},{0,-1},{1,-1},

{-1, 1},{0,+1},{1,+1}}

{-1, 0}, {1, 0},

{-1, 1},{0,+1},{1,+1}}

sequence key = {7,0}, -- chebyshev, cost

moves = {{1,1}},

sequence key = {7,0}, -- chebyshev, cost

data = {moves},

moves = {{1,1}},

acta = {} -- actually analysed set

data = {moves},

setd(key,data)

acta = {} -- actually analysed set

bool found = false

setd(key,data)

integer count = 0

bool found = false

while not found do

integer count = 0

if dict_size()=0 then ?"impossible" exit end if

while not found do

key = getd_partial_key(0)

if dict_size()=0 then ?"impossible" exit end if

data = getd(key)

key = getd_partial_key(0)

moves = data[$]

data = getd(key)

if length(data)=1 then

moves = data[$]

deld(key)

if length(data)=1 then

else

deld(key)

data = data[1..$-1]

else

putd(key,data)

data = data[1..$-1]

end if

putd(key,data)

count += 1

end if

acta = append(acta,moves[$])

count += 1

for i=1 to length(permitted) do

acta = append(acta,moves[$])

sequence newpos = sq_add(moves[$],permitted[i])

for i=1 to length(permitted) do

integer {nx,ny} = newpos

sequence newpos = sq_add(moves[$],permitted[i])

if nx>=1 and nx<=8

integer {nx,ny} = newpos

and ny>=1 and ny<=8

if nx>=1 and nx<=8

and grid[nx,ny] = ':' then -- (unvisited)

and ny>=1 and ny<=8

grid[nx,ny] = '.'

and grid[nx,ny] = ':' then -- (unvisited)

sequence newkey = {max(8-nx,8-ny),key[2]+1},

grid[nx,ny] = '.'

newmoves = append(moves,newpos)

sequence newkey = {max(8-nx,8-ny),key[2]+1},

if newpos = {8,8} then

newmoves = append(moves,newpos)

moves = newmoves

if newpos = {8,8} then

found = true

moves = newmoves

exit

found = true

end if

~~integer~~ k = ~~getd_index(newkey)~~

exit

end if

if k=0 then

integer k = getd_index(newkey)

data = {newmoves}

if k=0 then

else

data = {newmoves}

data = append(getd_by_index(k),newmoves)

~~end~~ if

else

data = append(getd_by_index(k),newmoves)

putd(newkey,data)

end if

end if

putd(newkey,data)

end for

end if

end while

end for

if found then

end while

printf(1,"visited %d nodes\ncost:%d\npath:%v\n",{count,length(moves)-1,moves})

if found then

for i=1 to length(acta) do

printf(1,"visited %d nodes\ncost:%d\npath:%v\n",{count,length(moves)-1,moves})

integer {x,y} = acta[i]

for i=1 to length(acta) do

grid[x,y] = '_'

integer {x,y} = acta[i]

end for

grid[x,y] = '_'

for i=1 to length(moves) do

end for

integer {x,y} = moves[i]

for i=1 to length(moves) do

grid[x,y] = 'x'

integer {x,y} = moves[i]

end for

grid[x,y] = 'x'

puts(1,join(grid,'\n'))

end for

end if</lang>

puts(1,join(grid,'\n'))

end if

<pre>

Line 2,829:

Line 2,833:

task author assumed it would, instead the main loop uses a priority queue to obtain the next

lowest cost and a simple dictionary to avoid re-examination/inifinte recursion.

<lang Phix>--~~set_rand(3) -- (for consistent output)~~

--set_rand(3) -- (for consistent output)

constant optimal = false,

constant optimal = false,

mtm = true, -- mutli-tile metrics

mtm = true, -- mutli-tile metrics

target = {1,2,3,4,5,6,7,8,0},

target = {1,2,3,4,5,6,7,8,0},

-- <-tile found 0..8->

-- <-tile found 0..8->

mcost = {{0,0,1,2,1,2,3,2,3}, -- position 1

mcost = {{0,0,1,2,1,2,3,2,3}, -- position 1

{0,1,0,1,2,1,2,3,2},

{0,1,0,1,2,1,2,3,2},

{0,2,1,0,3,2,1,4,3},

{0,2,1,0,3,2,1,4,3},

{0,1,2,3,0,1,2,1,2},

{0,1,2,3,0,1,2,1,2},

{0,2,1,2,1,0,1,2,1}, -- ...

{0,2,1,2,1,0,1,2,1}, -- ...

{0,3,2,1,2,1,0,3,2},

{0,3,2,1,2,1,0,3,2},

{0,2,3,4,1,2,3,0,1},

{0,2,3,4,1,2,3,0,1},

{0,3,2,3,2,1,2,1,0},

{0,3,2,3,2,1,2,1,0},

{0,4,3,2,3,2,1,2,1}}, -- position 9

{0,4,3,2,3,2,1,2,1}}, -- position 9

udlr = "udlr",

udlr = "udlr",

dirs = {+3,-3,+1,-1}, -- udlr

dirs = {+3,-3,+1,-1}, -- udlr

lims = {{9,9,9,9,9,9,9,9,9}, -- up

lims = {{9,9,9,9,9,9,9,9,9}, -- up

{1,1,1,1,1,1,1,1,1}, -- down

{1,1,1,1,1,1,1,1,1}, -- down

{3,3,3,6,6,6,9,9,9}, -- left

{3,3,3,6,6,6,9,9,9}, -- left

{1,1,1,4,4,4,7,7,7}} -- right

{1,1,1,4,4,4,7,7,7}} -- right

function get_moves(sequence grid, bool mtm)

function get_moves(sequence grid, bool mtm)

sequence valid = {}

sequence valid = {}

integer p0 = find(0,grid)

integer p0 = find(0,grid)

for dx=1 to length(dirs) do

for dx=1 to length(dirs) do

integer step = dirs[dx],

integer step = dirs[dx],

lim = lims[dx][p0],

lim = lims[dx][p0],

count = 1

count = 1

for i=p0+step to lim by step do

for i=p0+step to lim by step do

valid = append(valid,{step,i,udlr[dx],count})

valid = append(valid,{step,i,udlr[dx],count})

if not mtm then exit end if

if not mtm then exit end if

count += 1

count += 1

end for

end for

end for

end for

return valid

return valid

end function

end function

function make_move(sequence grid, move)

function make_move(sequence grid, move)

integer p0 = find(0,grid),

integer p0 = find(0,grid),

{step,lim} = move

{step,lim} = move

for i=p0+step to lim by step do

for i=p0+step to lim by step do

grid[p0] = grid[i]

grid[p0] = grid[i]

grid[i] = 0

grid[i] = 0

p0 = i

p0 = i

end for

end for

return grid

return grid

end function

end function

function manhattan(sequence grid)

function manhattan(sequence grid)

integer res = 0

integer res = 0

for i=1 to 9 do

for i=1 to 9 do

res += mcost[i][grid[i]+1]

res += mcost[i][grid[i]+1]

end for

end for

return res

return res

end function

end function

sequence problem, grid, new_grid,

sequence problem, grid, new_grid,

moves, next_moves, move

moves, next_moves, move

procedure show_grid()

procedure show_grid()

printf(1,"%s\n",join_by(sq_add(grid,'0'),1,3,""))

printf(1,"%s\n",join_by(sq_add(grid,'0'),1,3,""))

end procedure

end procedure

grid = target

grid = target

for i=1 to 1000 do

for i=1 to 1000 do

-- (initially shuffle as if mtm==true, otherwise

-- (initially shuffle as if mtm==true, otherwise

-- output compares answers to different puzzles)

-- output compares answers to different puzzles)

moves = get_moves(grid,true)

moves = get_moves(grid,true)

move = moves[rand(length(moves))]

move = moves[rand(length(moves))]

grid = make_move(grid,move)

grid = make_move(grid,move)

end for

end for

problem = grid

problem = grid

printf(1,"problem (manhattan cost is %d):\n",manhattan(grid))

printf(1,"problem (manhattan cost is %d):\n",manhattan(grid))

show_grid()

show_grid()

integer todo = pq_new(),

integer todo = pq_new(),

seen = new_dict()

seen = new_dict()

pq_add({{grid,{}},iff(optimal?0:manhattan(grid))},todo)

pq_add({{grid,{}},iff(optimal?0:manhattan(grid))},todo)

setd(grid,true,seen)

setd(grid,true,seen)

atom t1 = time()+1

atom t1 = time()+1

bool found = false

bool found = false

integer count = 0, mc

integer count = 0, mc

while not found do

while not found do

if pq_size(todo)=0 then ?"impossible" exit end if

if pq_size(todo)=0 then ?"impossible" exit end if

{{grid,moves},mc} = pq_pop(todo)

{{grid,moves},mc} = pq_pop(todo)

if time()>t1 then

if time()>t1 then

string m = iff(optimal?"moves":"manhattan")

string m = iff(optimal?"moves":"manhattan")

printf(1,"searching (count=%d, %s=%d)\r",{count,m,mc})

printf(1,"searching (count=%d, %s=%d)\r",{count,m,mc})

t1 = time()+1

t1 = time()+1

end if

end if

next_moves = get_moves(grid,mtm)

next_moves = get_moves(grid,mtm)

count += length(next_moves)

count += length(next_moves)

integer l = length(moves)

integer l = length(moves)

for i=1 to length(next_moves) do

for i=1 to length(next_moves) do

move = next_moves[i]

move = next_moves[i]

new_grid = make_move(grid,move)

new_grid = make_move(grid,move)

mc = manhattan(new_grid)

mc = manhattan(new_grid)

if mc=0 then

if mc=0 then

if new_grid!=target then ?9/0 end if

if new_grid!=target then ?9/0 end if

moves = append(moves,move)

moves = append(moves,move)

found = true

found = true

exit

exit

end if

end if

if getd_index(new_grid,seen)=NULL then

if getd_index(new_grid,seen)=NULL then

if optimal then mc = l+1 end if

if optimal then mc = l+1 end if

pq_add({{new_grid,append(moves,move)},mc},todo)

pq_add({{new_grid,append(moves,move)},mc},todo)

setd(new_grid,true,seen)

setd(new_grid,true,seen)

end if

end if

end for

end for

end while

end while

if found then

if found then

string s = iff(length(moves)=1?"":"s")

string s = iff(length(moves)=1?"":"s")

if optimal then

if optimal then

s &= sprintf(" (max shd be %d)",iff(mtm?24:31))

s &= sprintf(" (max shd be %d)",iff(mtm?24:31))

end if

end if

grid = problem

grid = problem

string soln = ""

string soln = ""

for i=1 to length(moves) do

for i=1 to length(moves) do

move = moves[i]

move = moves[i]

grid = make_move(grid,move)

grid = make_move(grid,move)

integer {{},{},ch,c} = move

integer {{},{},ch,c} = move

soln &= ch

soln &= ch

if c>1 then soln&='0'+c end if

if c>1 then soln&='0'+c end if

-- show_grid() -- (set the initial shuffle to eg 5 first!)

-- show_grid() -- (set the initial shuffle to eg 5 first!)

end for

end for

-- show_grid() -- (not very educational!)

-- show_grid() -- (not very educational!)

if grid!=target then ?9/0 end if

if grid!=target then ?9/0 end if

printf(1,"solved in %d move%s:%s\n",{length(moves),s,soln})

printf(1,"solved in %d move%s:%s\n",{length(moves),s,soln})

end if

end if

printf(1,"count:%d, seen:%d, queue:%d\n",{count,dict_size(seen),pq_size(todo)})</lang>

printf(1,"count:%d, seen:%d, queue:%d\n",{count,dict_size(seen),pq_size(todo)})

Note: The solutions are non-optimal (far from it, in fact), since it searches lowest manhattan() first.