First of all, English is not my primary language,
I'm afraid that there might be some misunderstanding about what I want to say.
But my code will tell the whole truth.
This is about A* algorithm implementation which is used to find a way from
start to goal.
I know that there is another A* implementations in codeproject site.
they are good, but I bet this is most simple and easy implementation for beginners to understand.
There are no unnecessary overplus code in this implementation ,
I just implement the A* algorithm pseudo-code step by step which in very intuitive ways.
About A*
Shorty, A* is the most popular pathfinding algorithm from start to goal based
on effective cost of movement.
You can visit A* Pathfinding for Beginners (http://www.policyalmanac.org/games/aStarTutorial.htm)
to learn how this algorithm works.
You can see pseudocode for A* that I used in this implementation at Justin Heyes-Jones A* tutorial.
Visit here (http://www.geocities.com/jheyesjones/pseudocode.html) to see orginal pseudocode.
Class implementation
Map - This represents map .
Node - This represents each tile on the map. It has two primary methods.
- CompareTo - this allows us to decide which node is better,
we can say current node is better if this method returns negative number ,
which means current node has lower cost to get current its position.
-isMatch - this allows us to check two node's geomatical positions are same.
SortedCostNodeList - This is a list that stores Node object list.
We need to get off the lowest cost node from the list, so this list is implemented as sorted list
order by cost value of the node, and we don't expect the costs of all elements of the list every time
to pop the node which has the lowest cost.
This list has two two primary methods.
- push - add node elements to list at proper position order by node cost. node's CompareTo method is
used internally to sort order by cost.
- pop - just returns the lowest cost node from the list and remove it from the list.
-
A* Algorithm pseudocode
1 Create a node containing the goal state node_goal
2 Create a node containing the start state node_start
3 Put node_start on the open list
4 while the OPEN list is not empty
5 {
6 Get the node off the open list with the lowest f and call it node_current
7 if node_current is the same state as node_goal we have found the solution; break from the while loop
8 Generate each state node_successor that can come after node_current
9 for each node_successor of node_current
10 {
11 Set the cost of node_successor to be the cost of node_current plus the cost to get to node_successor from node_current
12 find node_successor on the OPEN list
13 if node_successor is on the OPEN list but the existing one is as good or better then discard this successor and continue
14 if node_successor is on the CLOSED list but the existing one is as good or better then discard this successor and continue
15 Remove occurences of node_successor from OPEN and CLOSED
16 Set the parent of node_successor to node_current
17 Set h to be the estimated distance to node_goal (Using the heuristic function)
18 Add node_successor to the OPEN list
19 }
20 Add node_current to the CLOSED list
21 }
Map map = new Map ();
ArrayList Solution = new ArrayList();
//Create a node containing the goal state node_goal
Node node_goal = new Node(null,null,1,15,15);
//Create a node containing the start state node_start
Node node_start = new Node(null,node_goal,1,0,0);
//Create OPEN and CLOSED list
SortedCostNodeList OPEN = new SortedCostNodeList ();
SortedCostNodeList CLOSED = new SortedCostNodeList ();
//Put node_start on the OPEN list
OPEN.push (node_start);
//while the OPEN list is not empty
while (OPEN.Count>0)
{
//Get the node off the open list
//with the lowest f and call it node_current
Node node_current = OPEN.pop ();
//if node_current is the same state as node_goal we have found the solution;
//break from the while loop;
if (node_current.isMatch (node_goal))
{
node_goal.parentNode = node_current.parentNode ;
break;
}
//Generate each state node_successor that can come after node_current
ArrayList successors = node_current.GetSuccessors ();
//for each node_successor or node_current
foreach (Node node_successor in successors)
{
//Set the cost of node_successor to be the cost of node_current plus
//the cost to get to node_successor from node_current
//--> already set while we are getting successors
//find node_successor on the OPEN list
int oFound = OPEN.IndexOf (node_successor);
//if node_successor is on the OPEN list but the existing one is as good
//or better then discard this successor and continue
if (oFound>0)
{
Node existing_node = OPEN.NodeAt (oFound);
if (existing_node.CompareTo (node_current) <= 0)
continue;
}
//find node_successor on the CLOSED list
int cFound = CLOSED.IndexOf (node_successor);
//if node_successor is on the CLOSED list but the existing one is as good
//or better then discard this successor and continue;
if (cFound>0)
{
Node existing_node = CLOSED.NodeAt (cFound);
if (existing_node.CompareTo (node_current) <= 0 )
continue;
}
//Remove occurences of node_successor from OPEN and CLOSED
if (oFound!=-1)
OPEN.Remove (oFound);
if (cFound!=-1)
CLOSED.Remove (cFound);
//Set the parent of node_successor to node_current;
//--> already set while we are getting successors
//Set h to be the estimated distance to node_goal (Using heuristic function)
//--> already set while we are getting successors
//Add node_successor to the OPEN list
OPEN.push (node_successor);
}
//Add node_current to the CLOSED list
CLOSED.push (node_current);
}
<H2>Introduction </H2>
<P>This is about A* algorithm implementation which is used to find a way
from<BR>start to goal.<BR>I already know that there is another A*
implementations in codeproject site.<BR>they are good, but I bet this is more
simple and easy implementation for beginners to understand.<BR>There are no
unnecessary overplus code in this implementation, I just implement the A*
algorithm pseudocode step by step in very intuitive ways.</P>
<H2>About A* algorithm</H2>
<P>Shorty, A* is the most popular pathfinding algorithm from start to goal based
<BR>on effective cost of movement.<BR>You can visit A* Pathfinding for Beginners
(<A
href="http://www.policyalmanac.org/games/aStarTutorial.htm">http://www.policyalmanac.org/games/aStarTutorial.htm</A>)
<BR>to learn how this algorithm works.<BR>You can see pseudocode for A* that I
used in this implementation at Justin Heyes-Jones A* tutorial.<BR>Visit here (<A
href="http://www.geocities.com/jheyesjones/pseudocode.html">http://www.geocities.com/jheyesjones/pseudocode.html</A>)
to see orginal pseudocode.</P>
<H2>Class Design</H2>
<P>There are three primary classes in this implementation.</P>
<UL>
<LI><STRONG>Map</STRONG> - This represents map .<BR>
<LI><STRONG>Node</STRONG> - This represents each tile on the map. It has two
primary methods.<BR><CODE>CompareTo</CODE> - this allows us to decide which node
is better, we can say current node is better if this method returns
negative number, which means current node has lower cost to get current its
position.<BR><CODE>isMatch</CODE> - this allows us to check two node's
geomatical positions are same.<BR>
<LI><STRONG>SortedCostNodeList</STRONG> - This is a list that stores Node object
list.<BR>We need to get off the lowest cost node from the list, so this list is
implemented as sorted list order by cost value of the node, and we
don't need to examine the costs of all elements in the list every time
to pop the node which has the lowest cost because they are already sorted. Just
pop one.<BR>This list has two primary methods.<BR><CODE>push</CODE>
- add node elements to list at proper position order by node cost. node's
CompareTo method is used internally to sort order by cost.<BR><CODE>pop</CODE> -
just returns the lowest cost node from the list and remove it from the
list.</LI></UL>
<P> </P>
<H2>Implementation</H2>
<P>This is core loop of the algorithm. </P><PRE>
Map map = new Map ();
ArrayList Solution = new ArrayList();
//Create a node containing the goal state node_goal
Node node_goal = new Node(null,null,1,15,15);
//Create a node containing the start state node_start
Node node_start = new Node(null,node_goal,1,0,0);
//Create OPEN and CLOSED list
SortedCostNodeList OPEN = new SortedCostNodeList ();
SortedCostNodeList CLOSED = new SortedCostNodeList ();
//Put node_start on the OPEN list
OPEN.push (node_start);
//while the OPEN list is not empty
while (OPEN.Count>0)
{
//Get the node off the open list
//with the lowest f and call it node_current
Node node_current = OPEN.pop ();
//if node_current is the same state as node_goal we have found the solution;
//break from the while loop;
if (node_current.isMatch (node_goal))
{
node_goal.parentNode = node_current.parentNode ;
break;
}
//Generate each state node_successor that can come after node_current
ArrayList successors = node_current.GetSuccessors ();
//for each node_successor or node_current
foreach (Node node_successor in successors)
{
//Set the cost of node_successor to be the cost of node_current plus
//the cost to get to node_successor from node_current
//--> already set while we were getting successors
//find node_successor on the OPEN list
int oFound = OPEN.IndexOf (node_successor);
//if node_successor is on the OPEN list but the existing one is as good
//or better then discard this successor and continue
if (oFound>0)
{
Node existing_node = OPEN.NodeAt (oFound);
if (existing_node.CompareTo (node_current) <= 0)
continue;
}
//find node_successor on the CLOSED list
int cFound = CLOSED.IndexOf (node_successor);
//if node_successor is on the CLOSED list but the existing one is as good
//or better then discard this successor and continue;
if (cFound>0)
{
Node existing_node = CLOSED.NodeAt (cFound);
if (existing_node.CompareTo (node_current) <= 0 )
continue;
}
//Remove occurences of node_successor from OPEN and CLOSED
if (oFound!=-1)
OPEN.Remove (oFound);
if (cFound!=-1)
CLOSED.Remove (cFound);
//Set the parent of node_successor to node_current;
//--> already set while we were getting successors
//Set h to be the estimated distance to node_goal (Using heuristic function)
//--> already set while we were getting successors
//Add node_successor to the OPEN list
OPEN.push (node_successor);
}
//Add node_current to the CLOSED list
CLOSED.push (node_current);
}
</PRE>
<P> </P>
<P>dd</P>
<H2>Introduction </H2>
<P>This is about A* algorithm implementation which is about the
way how we can find a best path between two positions.<BR>I
already know that there is another A* implementations in codeproject
site.<BR>they are good, but I bet this is more simple and easy implementation
for beginners to understand.<BR>There are no unnecessary overplus code in this
implementation, I just implement the A* algorithm pseudocode step by
step in very intuitive ways.</P>
<H2>About A* algorithm</H2>
<P>Shorty, A* is the most popular pathfinding algorithm from start to goal based
<BR>on effectiveness of movement cost.<BR>You can visit A* Pathfinding for
Beginners (<A
href="http://www.policyalmanac.org/games/aStarTutorial.htm">http://www.policyalmanac.org/games/aStarTutorial.htm</A>)
<BR>to learn how this algorithm works.<BR>You can see pseudocode for A* that I
used in this implementation at Justin Heyes-Jones A* tutorial.<BR>Visit here (<A
href="http://www.geocities.com/jheyesjones/pseudocode.html">http://www.geocities.com/jheyesjones/pseudocode.html</A>)
to see orginal pseudocode.<BR>The print-out of this pseudocode will
help you a lot to understand this implementation.</P>
<H2>Class Design</H2>
<P>There are three primary classes in this implementation.</P>
<UL>
<LI><STRONG>Map</STRONG> - This class represents map .<BR>
<LI><STRONG>Node</STRONG> - This class represents each tile on the map. It has
two primary methods.<BR><CODE>CompareTo</CODE> - This methods allows us to
decide which node is better. We can say current node is better if this
method returns negative number, which means current node has lower
cost than the other node being compared.<BR><CODE>isMatch</CODE> - this
allows us to check whether two node's geomatical positions are same or not.<BR>
<LI><STRONG>SortedCostNodeList</STRONG> - This is a list that stores Node object
list.<BR>We need to get off the lowest cost node from the list, so this list is
implemented as sorted list order by cost value of the node, and we
don't need to examine the costs of all elements in the list every time
to pop the node which has the lowest cost because they are already sorted. Just
pop one.<BR>This list has two primary methods.<BR><CODE>push</CODE>
- add node elements to list at proper position order by node cost. node's
CompareTo method is used internally to sort order by cost.<BR><CODE>pop</CODE> -
just returns the lowest cost node from the list and remove it from the
list.</LI></UL>
<P> </P>
<H2>Implementation</H2>
<P>This is core loop of the algorithm. </P><PRE>
Map map = new Map ();
ArrayList Solution = new ArrayList();
//Create a node containing the goal state node_goal
Node node_goal = new Node(null,null,1,15,15);
//Create a node containing the start state node_start
Node node_start = new Node(null,node_goal,1,0,0);
//Create OPEN and CLOSED list
SortedCostNodeList OPEN = new SortedCostNodeList ();
SortedCostNodeList CLOSED = new SortedCostNodeList ();
//Put node_start on the OPEN list
OPEN.push (node_start);
//while the OPEN list is not empty
while (OPEN.Count>0)
{
//Get the node off the open list
//with the lowest f and call it node_current
Node node_current = OPEN.pop ();
//if node_current is the same state as node_goal we have found the solution;
//break from the while loop;
if (node_current.isMatch (node_goal))
{
node_goal.parentNode = node_current.parentNode ;
break;
}
//Generate each state node_successor that can come after node_current
ArrayList successors = node_current.GetSuccessors ();
//for each node_successor or node_current
foreach (Node node_successor in successors)
{
//Set the cost of node_successor to be the cost of node_current plus
//the cost to get to node_successor from node_current
//--> already set while we were getting successors
//find node_successor on the OPEN list
int oFound = OPEN.IndexOf (node_successor);
//if node_successor is on the OPEN list but the existing one is as good
//or better then discard this successor and continue
if (oFound>0)
{
Node existing_node = OPEN.NodeAt (oFound);
if (existing_node.CompareTo (node_current) <= 0)
continue;
}
//find node_successor on the CLOSED list
int cFound = CLOSED.IndexOf (node_successor);
//if node_successor is on the CLOSED list but the existing one is as good
//or better then discard this successor and continue;
if (cFound>0)
{
Node existing_node = CLOSED.NodeAt (cFound);
if (existing_node.CompareTo (node_current) <= 0 )
continue;
}
//Remove occurences of node_successor from OPEN and CLOSED
if (oFound!=-1)
OPEN.Remove (oFound);
if (cFound!=-1)
CLOSED.Remove (cFound);
//Set the parent of node_successor to node_current;
//--> already set while we were getting successors
//Set h to be the estimated distance to node_goal (Using heuristic function)
//--> already set while we were getting successors
//Add node_successor to the OPEN list
OPEN.push (node_successor);
}
//Add node_current to the CLOSED list
CLOSED.push (node_current);
}
</PRE>
<P>Once we get to goal ,follow parent nodes to find the solution path.</P><BR><PRE> //follow the parentNode from goal to start node
//to find solution
Node p = node_goal;
while(p != null)
{
Solution.Insert(0,p);
p = p.parentNode ;
}
</PRE><BR>This A* implementation is very simple and good for beginners who want
to know how A* algorithm works.<BR>Change map data in variety of ways, and
check out how AI is smart to find the good path.<BR>Enjoy your programming.<BR>
pppppppppppppppppppppppp
<H2>Introduction </H2>
<P>This is about A* algorithm implementation which is about the
way how we can find a best path between two positions.<BR>I
already know that there is another A* implementations in codeproject
site.<BR>they are good, but I bet this is more simple and easy implementation
for beginners to understand.<BR>There are no unnecessary overplus code in this
implementation, I just implement the A* algorithm pseudocode step by
step in very intuitive ways.</P>
<H2>About A* algorithm</H2>
<P>Shorty, A* is the most popular pathfinding algorithm from start to goal based
<BR>on effectiveness of movement cost.<BR>You can visit A* Pathfinding for
Beginners (<A
href="http://www.policyalmanac.org/games/aStarTutorial.htm">http://www.policyalmanac.org/games/aStarTutorial.htm</A>)
<BR>to learn how this algorithm works.<BR>You can see pseudocode for A* that I
used in this implementation at Justin Heyes-Jones A* tutorial.<BR>Visit here (<A
href="http://www.geocities.com/jheyesjones/pseudocode.html">http://www.geocities.com/jheyesjones/pseudocode.html</A>)
to see orginal pseudocode.<BR>The print-out of this pseudocode will
help you a lot to understand this implementation.</P>
<H2>Class Design</H2>
<P>There are three primary classes in this implementation.</P>
<UL>
<LI><STRONG>Map</STRONG> - This class represents map .<BR>
<LI><STRONG>Node</STRONG> - This class represents each tile on the map. It has
two primary methods.<BR><CODE>CompareTo</CODE> - This methods allows us to
decide which node is better. We can say current node is better if this
method returns negative number, which means current node has lower
cost than the other node being compared.<BR><CODE>isMatch</CODE> - this
allows us to check whether two node's geomatical positions are same or not.<BR>
<LI><STRONG>SortedCostNodeList</STRONG> - This is a list that stores Node object
list.<BR>We need to get off the lowest cost node from the list, so this list is
implemented as sorted list order by cost value of the node, and we
don't need to examine the costs of all elements in the list every time
to pop the node which has the lowest cost because they are already sorted. Just
pop one.<BR>This list has two primary methods.<BR><CODE>push</CODE>
- add node elements to list at proper position order by node cost. node's
CompareTo method is used internally to sort order by cost.<BR><CODE>pop</CODE> -
just returns the lowest cost node from the list and remove it from the
list.</LI></UL>
<P> </P>
<H2>Implementation</H2>
<P>This is core loop of the algorithm. </P><PRE>
ArrayList SolutionPathList = new ArrayList();
//Create a node containing the goal state node_goal
Node node_goal = new Node(null,null,1,15,15);
//Create a node containing the start state node_start
Node node_start = new Node(null,node_goal,1,0,0);
//Create OPEN and CLOSED list
SortedCostNodeList OPEN = new SortedCostNodeList ();
SortedCostNodeList CLOSED = new SortedCostNodeList ();
//Put node_start on the OPEN list
OPEN.push (node_start);
//while the OPEN list is not empty
while (OPEN.Count>0)
{
//Get the node off the open list
//with the lowest f and call it node_current
Node node_current = OPEN.pop ();
//if node_current is the same state as node_goal we have found the solution;
//break from the while loop;
if (node_current.isMatch (node_goal))
{
node_goal.parentNode = node_current.parentNode ;
break;
}
//Generate each state node_successor that can come after node_current
ArrayList successors = node_current.GetSuccessors ();
//for each node_successor or node_current
foreach (Node node_successor in successors)
{
//Set the cost of node_successor to be the cost of node_current plus
//the cost to get to node_successor from node_current
//--> already set while we were getting successors
//find node_successor on the OPEN list
int oFound = OPEN.IndexOf (node_successor);
//if node_successor is on the OPEN list but the existing one is as good
//or better then discard this successor and continue
if (oFound>0)
{
Node existing_node = OPEN.NodeAt (oFound);
if (existing_node.CompareTo (node_current) <= 0)
continue;
}
//find node_successor on the CLOSED list
int cFound = CLOSED.IndexOf (node_successor);
//if node_successor is on the CLOSED list but the existing one is as good
//or better then discard this successor and continue;
if (cFound>0)
{
Node existing_node = CLOSED.NodeAt (cFound);
if (existing_node.CompareTo (node_current) <= 0 )
continue;
}
//Remove occurences of node_successor from OPEN and CLOSED
if (oFound!=-1)
OPEN.Remove (oFound);
if (cFound!=-1)
CLOSED.Remove (cFound);
//Set the parent of node_successor to node_current;
//--> already set while we were getting successors
//Set h to be the estimated distance to node_goal (Using heuristic function)
//--> already set while we were getting successors
//Add node_successor to the OPEN list
OPEN.push (node_successor);
}
//Add node_current to the CLOSED list
CLOSED.push (node_current);
}
</PRE>
<P>Once we get to goal ,follow parent nodes to find the solution path.</P><BR><PRE> //follow the parentNode from goal to start node
//to find solution
Node p = node_goal;
while(p != null)
{
SolutionPathList.Insert(0,p);
p = p.parentNode ;
}
</PRE><BR>This A* implementation is very simple and good for beginners who want
to know how A* algorithm works.<BR>Change map data in variety of ways, and
check out how AI is smart to find the good path.<BR>Enjoy your programming.<BR>
Submit an article or tip