A* search algorithm: Difference between revisions
no edit summary
(Undo revision 316212 by Abcxyz12345 (talk)) |
No edit summary |
||
Line 310:
(7, 7)
(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>
Line 845 ⟶ 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)
</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>
| |||