A* search algorithm: Difference between revisions
→{{header|Phix}}: manhattan heuristic
m (→{{header|Phix}}: (forgot total cost)) |
(→{{header|Phix}}: manhattan heuristic) |
||
Line 1,090:
..x.x...
...x.xxx
</pre>
With a simple manhattan distance heuristic, however, it becomes completely deterministic:
<lang Phix>sequence grid = split("""
x:::::::
::::::::
::::###:
::#:::#:
::#:::#:
::#####:
::::::::
::::::::
""",'\n')
constant permitted = {{-1,-1},{0,-1},{1,-1},
{-1, 0}, {1, 0},
{-1, 1},{0,+1},{1,+1}}
sequence key = {0,14}, -- cost, manhattan
moves = {{1,1}},
data = {moves}
setd(key,data)
bool found = false
while not found do
if dict_size()=0 then ?"impossible" exit end if
key = getd_partial_key(0)
data = getd(key)
moves = data[$]
if length(data)=1 then
deld(key)
else
data = data[1..$-1]
putd(key,data)
end if
for i=1 to length(permitted) do
sequence newpos = sq_add(moves[$],permitted[i])
integer {nx,ny} = newpos
if nx>=1 and nx<=8
and ny>=1 and ny<=8
and grid[nx,ny] = ':' then
grid[nx,ny] = '.'
sequence newkey = {key[1]+1,8-nx+8-ny},
newmoves = append(moves,{nx,ny})
if {nx,ny} = {8,8} then
moves = newmoves
found = true
exit
end if
integer k = getd_index(newkey)
if k=0 then
data = {newmoves}
else
data = append(getd_by_index(k),newmoves)
end if
putd(newkey,data)
end if
end for
end while
if found then
printf(1,"%d moves:",length(moves))
?moves
for i=1 to length(moves) do
integer {x,y} = moves[i]
grid[x,y] = 'x'
end for
puts(1,join(grid,'\n'))
end if</lang>
{{out}}
<pre>
12 moves:{{1,1},{2,2},{3,3},{4,2},{5,2},{6,2},{7,3},{8,4},{8,5},{8,6},{8,7},{8,8}}
x.......
.x......
..x.###.
.x#...#.
.x#...#.
.x#####.
..x.....
...xxxxx
</pre>
| |||