A* search algorithm: Difference between revisions
Content added Content deleted
(Undo revision 316212 by Abcxyz12345 (talk)) |
No edit summary |
||
Line 310: | Line 310: | ||
(7, 7) |
(7, 7) |
||
(8, 8) |
(8, 8) |
||
</pre> |
|||
=={{header|C sharp}}== |
|||
<lang csharp> |
|||
using System; |
|||
using System.Collections.Generic; |
|||
namespace A_star |
|||
{ |
|||
class A_star |
|||
{ |
|||
// Coordinates of a cell - implements the method Equals |
|||
public class Coordinates : IEquatable<Coordinates> |
|||
{ |
|||
public int row; |
|||
public int col; |
|||
public Coordinates() { this.row = -1; this.col = -1; } |
|||
public Coordinates(int row, int col) { this.row = row; this.col = col; } |
|||
public Boolean Equals(Coordinates c) |
|||
{ |
|||
if (this.row == c.row && this.col == c.col) |
|||
return true; |
|||
else |
|||
return false; |
|||
} |
|||
} |
|||
// Class Cell, with the cost to reach it, the values g and f, and the coordinates |
|||
// of the cell that precedes it in a possible path |
|||
public class Cell |
|||
{ |
|||
public int cost; |
|||
public int g; |
|||
public int f; |
|||
public Coordinates parent; |
|||
} |
|||
// Class Astar, which finds the shortest path |
|||
public class Astar |
|||
{ |
|||
// The array of the cells |
|||
public Cell[,] cells = new Cell[8, 8]; |
|||
// The possible path found |
|||
public List<Coordinates> path = new List<Coordinates>(); |
|||
// The list of the opened cells |
|||
public List<Coordinates> opened = new List<Coordinates>(); |
|||
// The list of the closed cells |
|||
public List<Coordinates> closed = new List<Coordinates>(); |
|||
// The start of the searched path |
|||
public Coordinates startCell = new Coordinates(0, 0); |
|||
// The end of the searched path |
|||
public Coordinates finishCell = new Coordinates(7, 7); |
|||
// The constructor |
|||
public Astar() |
|||
{ |
|||
// Initialization of the cells values |
|||
for (int i = 0; i < 8; i++) |
|||
for (int j = 0; j < 8; j++) |
|||
{ |
|||
cells[i, j] = new Cell(); |
|||
cells[i, j].parent = new Coordinates(); |
|||
if (IsAWall(i, j)) |
|||
cells[i, j].cost = 100; |
|||
else |
|||
cells[i, j].cost = 1; |
|||
} |
|||
// Adding the start cell on the list opened |
|||
opened.Add(startCell); |
|||
// Boolean value which indicates if a path is found |
|||
Boolean pathFound = false; |
|||
// Loop until the list opened is empty or a path is found |
|||
do |
|||
{ |
|||
List<Coordinates> neighbors = new List<Coordinates>(); |
|||
// The next cell analyzed |
|||
Coordinates currentCell = ShorterExpectedPath(); |
|||
// The list of cells reachable from the actual one |
|||
neighbors = neighborsCells(currentCell); |
|||
foreach (Coordinates newCell in neighbors) |
|||
{ |
|||
// If the cell considered is the final one |
|||
if (newCell.row == finishCell.row && newCell.col == finishCell.col) |
|||
{ |
|||
cells[newCell.row, newCell.col].g = cells[currentCell.row, |
|||
currentCell.col].g + cells[newCell.row, newCell.col].cost; |
|||
cells[newCell.row, newCell.col].parent.row = currentCell.row; |
|||
cells[newCell.row, newCell.col].parent.col = currentCell.col; |
|||
pathFound = true; |
|||
break; |
|||
} |
|||
// If the cell considered is not between the open and closed ones |
|||
else if (!opened.Contains(newCell) && !closed.Contains(newCell)) |
|||
{ |
|||
cells[newCell.row, newCell.col].g = cells[currentCell.row, |
|||
currentCell.col].g + cells[newCell.row, newCell.col].cost; |
|||
cells[newCell.row, newCell.col].f = |
|||
cells[newCell.row, newCell.col].g + Heuristic(newCell); |
|||
cells[newCell.row, newCell.col].parent.row = currentCell.row; |
|||
cells[newCell.row, newCell.col].parent.col = currentCell.col; |
|||
SetCell(newCell, opened); |
|||
} |
|||
// If the cost to reach the considered cell from the actual one is |
|||
// smaller than the previous one |
|||
else if (cells[newCell.row, newCell.col].g > cells[currentCell.row, |
|||
currentCell.col].g + cells[newCell.row, newCell.col].cost) |
|||
{ |
|||
cells[newCell.row, newCell.col].g = cells[currentCell.row, |
|||
currentCell.col].g + cells[newCell.row, newCell.col].cost; |
|||
cells[newCell.row, newCell.col].f = |
|||
cells[newCell.row, newCell.col].g + Heuristic(newCell); |
|||
cells[newCell.row, newCell.col].parent.row = currentCell.row; |
|||
cells[newCell.row, newCell.col].parent.col = currentCell.col; |
|||
SetCell(newCell, opened); |
|||
ResetCell(newCell, closed); |
|||
} |
|||
} |
|||
SetCell(currentCell, closed); |
|||
ResetCell(currentCell, opened); |
|||
} while (opened.Count > 0 && pathFound == false); |
|||
if (pathFound) |
|||
{ |
|||
path.Add(finishCell); |
|||
Coordinates currentCell = new Coordinates(finishCell.row, finishCell.col); |
|||
// It reconstructs the path starting from the end |
|||
while (cells[currentCell.row, currentCell.col].parent.row >= 0) |
|||
{ |
|||
path.Add(cells[currentCell.row, currentCell.col].parent); |
|||
int tmp_row = cells[currentCell.row, currentCell.col].parent.row; |
|||
currentCell.col = cells[currentCell.row, currentCell.col].parent.col; |
|||
currentCell.row = tmp_row; |
|||
} |
|||
// Printing on the screen the 'chessboard' and the path found |
|||
for (int i = 0; i < 8; i++) |
|||
{ |
|||
for (int j = 0; j < 8; j++) |
|||
{ |
|||
// Symbol for a cell that doesn't belong to the path and isn't |
|||
// a wall |
|||
char gr = '.'; |
|||
// Symbol for a cell that belongs to the path |
|||
if (path.Contains(new Coordinates(i, j))) { gr = 'X'; } |
|||
// Symbol for a cell that is a wall |
|||
else if (cells[i, j].cost > 1) { gr = '\u2588'; } |
|||
System.Console.Write(gr); |
|||
} |
|||
System.Console.WriteLine(); |
|||
} |
|||
// Printing the coordinates of the cells of the path |
|||
System.Console.Write("\nPath: "); |
|||
for (int i = path.Count - 1; i >= 0; i--) |
|||
{ |
|||
System.Console.Write("({0},{1})", path[i].row, path[i].col); |
|||
} |
|||
// Printing the cost of the path |
|||
System.Console.WriteLine("\nPath cost: {0}", path.Count - 1); |
|||
// Waiting to the key Enter to be pressed to end the program |
|||
String wt = System.Console.ReadLine(); |
|||
} |
|||
} |
|||
// It select the cell between those in the list opened that have the smaller |
|||
// value of f |
|||
public Coordinates ShorterExpectedPath() |
|||
{ |
|||
int sep = 0; |
|||
if (opened.Count > 1) |
|||
{ |
|||
for (int i = 1; i < opened.Count; i++) |
|||
{ |
|||
if (cells[opened[i].row, opened[i].col].f < cells[opened[sep].row, |
|||
opened[sep].col].f) |
|||
{ |
|||
sep = i; |
|||
} |
|||
} |
|||
} |
|||
return opened[sep]; |
|||
} |
|||
// It finds che cells that could be reached from c |
|||
public List<Coordinates> neighborsCells(Coordinates c) |
|||
{ |
|||
List<Coordinates> lc = new List<Coordinates>(); |
|||
for (int i = -1; i <= 1; i++) |
|||
for (int j = -1; j <= 1; j++) |
|||
if (c.row+i >= 0 && c.row+i < 8 && c.col+j >= 0 && c.col+j < 8 && |
|||
(i != 0 || j != 0)) |
|||
{ |
|||
lc.Add(new Coordinates(c.row + i, c.col + j)); |
|||
} |
|||
return lc; |
|||
} |
|||
// It determines if the cell with coordinates (row, col) is a wall |
|||
public bool IsAWall(int row, int col) |
|||
{ |
|||
int[,] walls = new int[,] { { 2, 4 }, { 2, 5 }, { 2, 6 }, { 3, 6 }, { 4, 6 }, |
|||
{ 5, 6 }, { 5, 5 }, { 5, 4 }, { 5, 3 }, { 5, 2 }, { 4, 2 }, { 3, 2 } }; |
|||
bool found = false; |
|||
for (int i = 0; i < walls.GetLength(0); i++) |
|||
if (walls[i,0] == row && walls[i,1] == col) |
|||
found = true; |
|||
return found; |
|||
} |
|||
// The function Heuristic, which determines the shortest path that a 'king' can do |
|||
// This is the maximum value between the orizzontal distance and the vertical one |
|||
public int Heuristic(Coordinates cell) |
|||
{ |
|||
int dRow = Math.Abs(finishCell.row - cell.row); |
|||
int dCol = Math.Abs(finishCell.col - cell.col); |
|||
return Math.Max(dRow, dCol); |
|||
} |
|||
// It inserts the coordinates of cell in a list, if it's not already present |
|||
public void SetCell(Coordinates cell, List<Coordinates> coordinatesList) |
|||
{ |
|||
if (coordinatesList.Contains(cell) == false) |
|||
{ |
|||
coordinatesList.Add(cell); |
|||
} |
|||
} |
|||
// It removes the coordinates of cell from a list, if it's already present |
|||
public void ResetCell(Coordinates cell, List<Coordinates> coordinatesList) |
|||
{ |
|||
if (coordinatesList.Contains(cell)) |
|||
{ |
|||
coordinatesList.Remove(cell); |
|||
} |
|||
} |
|||
} |
|||
// The main method |
|||
static void Main(string[] args) |
|||
{ |
|||
Astar astar = new Astar(); |
|||
} |
|||
} |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
X....... |
|||
.X...... |
|||
..X.███. |
|||
.X█...█. |
|||
.X█...█. |
|||
.X█████. |
|||
..XXXXX. |
|||
.......X |
|||
Path: (0,0)(1,1)(2,2)(3,1)(4,1)(5,1)(6,2)(6,3)(6,4)(6,5)(6,6)(7,7) |
|||
Path cost: 11 |
|||
</pre> |
</pre> |
||
Line 845: | Line 1,112: | ||
Path cost 11: (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (1, 5) (2, 6) (3, 6) (4, 6) (5, 6) (6, 7) (7, 7) |
Path cost 11: (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (1, 5) (2, 6) (3, 6) (4, 6) (5, 6) (6, 7) (7, 7) |
||
</pre> |
|||
=={{Header|FreeBASIC}}== |
|||
<lang freebasic> |
|||
'############################### |
|||
'### A* search algorithm ### |
|||
'############################### |
|||
'A number big enough to be greater than any possible path cost |
|||
#define MAX_DIST 100000 |
|||
type coordinates |
|||
'coordinates of a cell |
|||
row as integer |
|||
col as integer |
|||
end type |
|||
type listCoordinates |
|||
'list of coordinates |
|||
length as integer |
|||
coord(1 to 64) as coordinates |
|||
end type |
|||
type cell |
|||
'properties of a cell |
|||
cost as integer |
|||
g as integer |
|||
f as integer |
|||
parent as coordinates |
|||
end type |
|||
sub AddCoordinates(list as listCoordinates, c as coordinates) |
|||
'Adds coordinates c to the listCoordinates, checking if it's already present |
|||
dim i as integer, inList as integer = 0 |
|||
if (list.length > 0) then |
|||
for i = 1 to list.length |
|||
if (list.coord(i).row = c.row and list.coord(i).col = c.col) then |
|||
inList = i |
|||
exit for |
|||
end if |
|||
next |
|||
if (inList > 0) then |
|||
exit sub |
|||
end if |
|||
end if |
|||
if (list.length < 64) then |
|||
list.length = list.length + 1 |
|||
list.coord(list.length).row = c.row |
|||
list.coord(list.length).col = c.col |
|||
end if |
|||
end sub |
|||
sub RemoveCoordinates(list as listCoordinates, c as coordinates) |
|||
'Removes coordinates c from listCoordinates |
|||
dim i as integer, inList as integer = 0 |
|||
if (list.length > 0) then |
|||
for i = 1 to list.length |
|||
if (list.coord(i).row = c.row and list.coord(i).col = c.col) then |
|||
inList = i |
|||
exit for |
|||
end if |
|||
next |
|||
if (inList > 0) then |
|||
list.coord(inList).row = list.coord(list.length).row |
|||
list.coord(inList).col = list.coord(list.length).col |
|||
list.length = list.length - 1 |
|||
end if |
|||
end if |
|||
end sub |
|||
function GetOpened(list as listCoordinates, cells() as cell) as coordinates |
|||
'Gets the cell between the open ones with the shortest expected cost |
|||
dim i as integer, minf as integer |
|||
dim rv as coordinates |
|||
minf = 1 |
|||
if (list.length > 1) then |
|||
for i = 2 to list.length |
|||
if (cells(list.coord(i).row, list.coord(i).col).f < cells(list.coord(minf).row, list.coord(minf).col).f) then |
|||
minf = i |
|||
end if |
|||
next |
|||
end if |
|||
rv.row = list.coord(minf).row |
|||
rv.col = list.coord(minf).col |
|||
return rv |
|||
end function |
|||
function Heuristic(byval a as coordinates, byval b as coordinates) as integer |
|||
'In a chessboard, the shortest path of a king between two cells is the maximum value |
|||
'between the orizzontal distance and the vertical one. This could be used as |
|||
'heuristic value in the A* algorithm. |
|||
dim dr as integer, dc as integer |
|||
dr = abs(a.row - b.row) |
|||
dc = abs(a.col - b.col) |
|||
if (dr > dc) then |
|||
return dr |
|||
else |
|||
return dc |
|||
end if |
|||
end function |
|||
function IsACell(r as integer, c as integer) as integer |
|||
'It determines if a couple of indeces are inside the chessboard (returns 1) or outside (returns 0) |
|||
dim isCell as integer |
|||
if (r < 0 or r > 7 or c < 0 or c > 7) then |
|||
isCell = 0 |
|||
else |
|||
isCell = 1 |
|||
end if |
|||
return isCell |
|||
end function |
|||
sub AppendCell(p as listCoordinates, c as coordinates) |
|||
'It appends che coordinates c at the end of the list p |
|||
p.length = p.length + 1 |
|||
p.coord(p.length).row = c.row |
|||
p.coord(p.length).col = c.col |
|||
end sub |
|||
function InList(r as integer, c as integer, p as listCoordinates) as integer |
|||
'It determines if the cell with coordinates (r,c) is in the list p |
|||
dim isInPath as integer = 0 |
|||
dim i as integer |
|||
for i = 1 to Ubound(p.coord) |
|||
if (p.coord(i).row = r and p.coord(i).col = c) then |
|||
isInPath = 1 |
|||
exit for |
|||
end if |
|||
next |
|||
return isInPath |
|||
end function |
|||
'Variables declaration |
|||
'Cost to go to the cell of coordinates (row, column) |
|||
dim costs(0 to 7, 0 to 7) as integer => { _ |
|||
{1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, _ |
|||
{1, 1, 1, 1, 100, 100, 100, 1}, {1, 1, 100, 1, 1, 1, 100, 1}, _ |
|||
{1, 1, 100, 1, 1, 1, 100, 1}, {1, 1, 100, 100, 100, 100, 100, 1}, _ |
|||
{1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}} |
|||
dim start as coordinates, finish as coordinates 'the first and the last cell |
|||
dim opened as listCoordinates, closed as listCoordinates |
|||
dim aCell as coordinates, nCell as coordinates 'the cell evaluates and the next one |
|||
dim cells(0 to 7, 0 to 7) as cell 'the cells of the chessboard |
|||
dim path as listCoordinates 'list used to the path found |
|||
dim i as integer, j as integer |
|||
'MAIN PROCEDURE |
|||
'Fixing the starting cell and the finishing one |
|||
start.row = 0 |
|||
start.col = 0 |
|||
finish.row = 7 |
|||
finish.col = 7 |
|||
opened.length = 0 |
|||
closed.length = 0 |
|||
'Initializing the chessboard |
|||
for i=0 to 7 |
|||
for j=0 to 7 |
|||
cells(i, j).cost = costs(i, j) |
|||
cells(i, j).g = MAX_DIST |
|||
cells(i, j).f = MAX_DIST |
|||
cells(i, j).parent.row = -1 |
|||
cells(i, j).parent.col = -1 |
|||
next |
|||
next |
|||
cells(start.row, start.col).g = 0 |
|||
cells(start.row, start.col).f = Heuristic(start, finish) |
|||
AddCoordinates(opened, start) |
|||
do while (opened.length > 0) |
|||
aCell = GetOpened(opened, cells()) |
|||
for i = -1 to 1 |
|||
for j = -1 to 1 |
|||
if ((i <> 0 or j <> 0) and IsACell(aCell.row + i, aCell.col + j)) then |
|||
nCell.row = aCell.row + i |
|||
nCell.col = aCell.col + j |
|||
if (nCell.row = finish.row and nCell.col = finish.col) then |
|||
'The final cell is reached |
|||
cells(finish.row, finish.col).g = cells(aCell.row, aCell.col).g + cells(finish.row, finish.col).cost |
|||
cells(finish.row, finish.col).parent.row = aCell.row |
|||
cells(finish.row, finish.col).parent.col = aCell.col |
|||
exit do |
|||
end if |
|||
if (InList(nCell.row, nCell.col, opened) = 0 and InList(nCell.row, nCell.col, closed) = 0) then |
|||
'This cell was never visited before |
|||
cells(nCell.row, nCell.col).g = cells(aCell.row, aCell.col).g + cells(nCell.row, nCell.col).cost |
|||
cells(nCell.row, nCell.col).f = cells(nCell.row, nCell.col).g + Heuristic(nCell, finish) |
|||
AddCoordinates(opened, nCell) |
|||
cells(nCell.row, nCell.col).parent.row = aCell.row |
|||
cells(nCell.row, nCell.col).parent.col = aCell.col |
|||
else |
|||
'This cell was visited before, it's reopened only if the actual path is shortest of the previous valutation |
|||
if (cells(aCell.row, aCell.col).g + cells(nCell.row, nCell.col).cost < cells(nCell.row, nCell.col).g) then |
|||
cells(nCell.row, nCell.col).g = cells(aCell.row, aCell.col).g + cells(nCell.row, nCell.col).cost |
|||
cells(nCell.row, nCell.col).f = cells(nCell.row, nCell.col).g + Heuristic(nCell, finish) |
|||
AddCoordinates(opened, nCell) |
|||
RemoveCoordinates(closed, nCell) |
|||
cells(nCell.row, nCell.col).parent.row = aCell.row |
|||
cells(nCell.row, nCell.col).parent.col = aCell.col |
|||
end if |
|||
end if |
|||
end if |
|||
next |
|||
next |
|||
'The current cell is closed |
|||
AddCoordinates(closed, aCell) |
|||
RemoveCoordinates(opened, aCell) |
|||
loop |
|||
if (cells(finish.row, finish.col).parent.row >= 0) then |
|||
'A possible path was found |
|||
'Add the cells of the shortest path to the list 'path', proceding backward |
|||
path.length = 0 |
|||
aCell.row = finish.row |
|||
aCell.col = finish.col |
|||
do while (cells(aCell.row, aCell.col).parent.row >= 0) |
|||
AppendCell(path, aCell) |
|||
nCell.row = cells(aCell.row, aCell.col).parent.row |
|||
aCell.col = cells(aCell.row, aCell.col).parent.col |
|||
aCell.row = nCell.row |
|||
loop |
|||
'Drawing the path |
|||
for i = 0 to 7 |
|||
for j = 0 to 7 |
|||
if (costs(i,j) > 1) then |
|||
print chr(219); |
|||
elseif (InList(i, j, path)) then |
|||
print "X"; |
|||
else |
|||
print "."; |
|||
end if |
|||
next |
|||
print |
|||
next |
|||
'Writing the cells sequence and the path length |
|||
print |
|||
print "Path: " |
|||
for i = path.length to 1 step -1 |
|||
print "("; path.coord(i).row; ","; path.coord(i).col; ")"; |
|||
next |
|||
print |
|||
print |
|||
print "Path cost: "; cells(finish.row, finish.col).g |
|||
print |
|||
else |
|||
print "Path not found" |
|||
end if |
|||
end |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
X....... |
|||
.X...... |
|||
..X.███. |
|||
.X█...█. |
|||
.X█...█. |
|||
.X█████. |
|||
..X..... |
|||
...XXXXX |
|||
Path: |
|||
( 1, 1)( 2, 2)( 3, 1)( 4, 1)( 5, 1)( 6, 2)( 7, 3)( 7, 4)( 7, 5)( 7, 6)( 7, 7) |
|||
Path cost: 11 |
|||
</pre> |
</pre> |
||