Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Good A star algorithm website!

Posted on 2001-06-04
Medium Priority
19,613 Views
I urgently need great websites which can guide me to learn A Star algorithm in deep. I also need to learn :
- how to avoid enemy along the way and
- how to implement predetermined places to go along

Anyone know which websites which tell me how to do this!?
0
Question by:jiminika
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

Accepted Solution

dsreynolds earned 300 total points
ID: 6153899
Gamasutra has an article
http://www.gamasutra.com/features/19990212/sm_04.htm

Here's a cpp file I wrote.  It works fine.

// A Sample by D.S.Reynolds
//
// How It Works:
//
// The basic formula for the A* algorithm is f = g + h.  g represents the cost of
// distance travelled (or gone).  h represents the estimate (or heuristic) of distance
// from current node to the destination.  Some sort of contianers are needed.  Some
// chose stacks, I chose STL vectors and a heap.  I believe the most critical part
// of the formula is the calculation for the heuristic.  Also, Breadth-First and Depth-First
// algorithms are simplified subsets of the A*.
//
//  1.  Create OPEN, CLOSED and PATH containers.
//  2.  Start with the OPEN container containing only the starting node.
//      Set that nodes g value to 0, it's h value to the euclidian difference
//      ((dx - sx)*(dx - sx)) + ((dy - sy)*(dy - sy)), calc the f value and
//      set the parent node to NULL.
//  3.  Until the goal node is found, repeat the following:
//        If no nodes found exit with failure.
//        Select Node on OPEN with the lowest f value.  This is the BestNode.
//        Push BestNode to Closed (This is the only place CLOSED is populated).
//        If BestNode is the destination, exit.  Otherwise, determine the
//        child nodes (adjacents) of BestNode.
//           For each child node do the following:
//           Set each child nodes Parent to BestNode (We'll use this later to
//             get the path.)
//           Calc the cost of g:  Child.g = BestNode.g + 1  (Use other than 1
//             for various terrain)
//           See if child node is already on OPEN.  If so, determine which has
//             the lower g value and use it's other corresponding values.
//           See if child node is already on CLOSED.  If so, determine which
//             has the lower g value and use it's other corresponding values.
//           If the child node was NOT on OPEN or CLOSED, add it to OPEN.
//
///////////////////////////////////////////////////////////
#ifndef ASTAR_HPP
#define ASTAR_HPP

#include <stdlib.h>
#include <iostream>
#include <conio.h>   // for getch
#include <vector>    // STL for Vector
#include <algorithm> // STL for Heap

using namespace std;

#define MAX_CLOSED_NODES 400
#define MIN_MAP_X        0
#define MIN_MAP_Y        0
#define MAX_MAP_X        9
#define MAX_MAP_Y        9

///////////////////////////////////////////////////////////
// Externally use a vecter of multiple Location objects
class CLocation{
public:
int x;
int y;
};

///////////////////////////////////////////////////////////
class CPathNode{
public:
int f, gone, heuristic; // f = gone + heuristic
int x, y;               // Location of node
int px, py;             // Locaton of parent node

void FindPath(int sx, int sy, int dx, int dy, char * pMap, vector<CLocation> *pVector);
};

///////////////////////////////////////////////////////////
void CPathNode::FindPath(int sx, int sy, int dx, int dy, char * pMap, vector<CLocation> *pVector)
{
vector<CPathNode> OPEN;                 // STL Vectors chosen because of rapid
vector<CPathNode> CLOSED;               // insertions/deletions at back,
CPathNode Node, BestNode;               // Temporary Node and BestNode
bool bNodeFound = false;                // Flag if node is found in container

Node.x = sx;                            // Create the start node
Node.y = sy;
Node.gone = 0;
Node.heuristic = ((dx - sx)*(dx - sx)) + ((dy - sy)*(dy - sy));
Node.f = Node.gone + Node.heuristic;    // The classic formula f = g + h
Node.px = NULL;                         // No parent for start location
Node.py = NULL;                         // No parent for start location
OPEN.push_back(Node);                   // Populate the OPEN container with the first location
make_heap( OPEN.begin(), OPEN.end() );  // Create a heap from OPEN for sorting

while (!OPEN.empty())
{
sort_heap(OPEN.begin(), OPEN.end());// Ascending sort based on overloaded operators below
BestNode = OPEN.front();            // Set the Node with lowest f value to BESTNODE
pop_heap(OPEN.begin(), OPEN.end()); // Pop off the heap.  Actually this moves the
// far left value to the far right.  The node
// is not actually removed since the pop is to
// the heap and not the container.
OPEN.pop_back();                    // Remove node from right (the value we pop_heap'd)
CLOSED.push_back(BestNode);         // Push the BestNode onto CLOSED

// If at destination, break and create path below
if ((BestNode.x == dx) && (BestNode.y == dy))
{
//bPathFound = true; // arrived at destination...
break;
}

// Set limit to break if looking too long
if ( CLOSED.size() > MAX_CLOSED_NODES )
break;

// Check adjacent locations (This is done in a clockwise order to lessen jaggies)
for (int i=1; i<9; i++)
{
switch(i)
{
case 1:
Node.x = BestNode.x;
Node.y = BestNode.y - 1;
break;
case 2:
Node.x = BestNode.x + 1;
Node.y = BestNode.y - 1;
break;
case 3:
Node.x = BestNode.x + 1;
Node.y = BestNode.y;
break;
case 4:
Node.x = BestNode.x + 1;
Node.y = BestNode.y + 1;
break;
case 5:
Node.x = BestNode.x;
Node.y = BestNode.y + 1;
break;
case 6:
Node.x = BestNode.x - 1;
Node.y = BestNode.y + 1;
break;
case 7:
Node.x = BestNode.x - 1;
Node.y = BestNode.y;
break;
case 8:
Node.x = BestNode.x - 1;
Node.y = BestNode.y - 1;
break;
}

if ((Node.x >= MIN_MAP_X) && (Node.x <= MAX_MAP_X) &&
(Node.y >= MIN_MAP_Y) && (Node.y <= MAX_MAP_Y))
{
// Determine cost of distance travelled
if ( pMap[Node.x + (Node.y*10)] == 'X' ) // If location is obstruction
Node.gone = 1000;
else
Node.gone = BestNode.gone + 1;

// Determine the Heuristic.  Probably the most crucial aspect
// Heuristic by Simple Euclidian method
// Node.heuristic = ((dx - Node.x)*(dx - Node.x)) + ((dy - Node.y)*(dy - Node.y));
// Heuristic by my own Orthogonal/Diagonal + Euclidian modifier
int DX = abs(dx - Node.x);
int DY = abs(dy - Node.y);
int Orthogonal = abs(DX - DY);
int Diagonal = abs(((DX + DY) - Orthogonal)/2);
Node.heuristic = Diagonal + Orthogonal + DX + DY;

// The A* formula
Node.f = Node.gone + Node.heuristic;
Node.px = BestNode.x; // Point parent to last BestNode (pushed onto CLOSED)
Node.py = BestNode.y; // Point parent to last BestNode (pushed onto CLOSED)

bNodeFound = false;

// Check to see if already on OPEN
for (int i=0; i<OPEN.size(); i++)
{
if ((Node.x == OPEN.at(i).x) &&
(Node.y == OPEN.at(i).y))
{   // If already on OPEN
if (Node.gone < OPEN.at(i).gone)
{
OPEN.at(i).gone = Node.gone;
OPEN.at(i).f = Node.gone + OPEN.at(i).heuristic;
OPEN.at(i).px = Node.px;
OPEN.at(i).py = Node.py;
}
bNodeFound = true;
break;
}
}
{
// Check to see if already on CLOSED
for (i=0; i<CLOSED.size(); i++)
{
if ((Node.x == CLOSED.at(i).x) &&
(Node.y == CLOSED.at(i).y))
{   // If on CLOSED, Which has lower gone?
if (Node.gone < CLOSED.at(i).gone)
{
CLOSED.at(i).gone = Node.gone;
CLOSED.at(i).f = Node.gone + CLOSED.at(i).heuristic;
CLOSED.at(i).px = Node.px;
CLOSED.at(i).py = Node.py;
}
bNodeFound = true;
break;
}
}
}

if (!bNodeFound ) // If Node NOT found on OPEN or CLOSED
{
OPEN.push_back(Node);                  // Push NewNode onto OPEN
push_heap( OPEN.begin(), OPEN.end() ); // Push NewNode onto heap
make_heap( OPEN.begin(), OPEN.end() ); // Re-Assert heap, or will be short by one

/*
// Display OPEN and CLOSED containers (For Debugging)
int i;
cout << "OPEN:   ";
for (i=0; i<OPEN.size(); i++)
{
cout << OPEN.at(i).x << "," << OPEN.at(i).y << ",";
cout << OPEN.at(i).gone << "," << OPEN.at(i).heuristic << "  ";
}
cout << endl;
cout << "CLOSED:   ";
for (i=0; i<CLOSED.size(); i++)
{
cout << CLOSED.at(i).x << "," << CLOSED.at(i).y << ",";
cout << CLOSED.at(i).gone << "," << CLOSED.at(i).heuristic << "  ";
}
cout << endl << endl;
int ch = _getch();
//*/
}
}
}
}

if (CLOSED.size() > 0)
{
// Create the path from elements of the CLOSED container
PATH.clear();
PATH.push_back(CLOSED.back());
CLOSED.pop_back();

while (!CLOSED.empty())
{
if ((CLOSED.back().x == PATH.back().px) &&
(CLOSED.back().y == PATH.back().py))
PATH.push_back(CLOSED.back());

CLOSED.pop_back();
}

// Populate the vector that was passed in by reference
CLocation Fix;
pVector->clear();
for (int i=(PATH.size()-1); i>=0; i--)
//for (container::iterator i=PATH.begin(); i!= PATH.end(); ++i)
{
Fix.x = PATH.at(i).x;
Fix.y = PATH.at(i).y;
pVector->push_back(Fix);
}
}
}

///////////////////////////////////////////////////////////
// Needed because the template doesn't know what a PathNode is
bool operator<(const CPathNode &a, const CPathNode &b)
{
return a.f < b.f;
}

///////////////////////////////////////////////////////////
// Needed because the template doesn't know what a PathNode is
bool operator>(const CPathNode &a, const CPathNode &b)
{
return a.f > b.f;
}

#endif

0

Author Comment

ID: 6164528
Thanks
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
In response to a need for security and privacy, and to continue fostering an environment members can turn to for support, solutions, and education, Experts Exchange has created anonymous question capabilities. This new feature is available to our Pr…
Is your data getting by on basic protection measures? In today’s climate of debilitating malware and ransomware—like WannaCry—that may not be enough. You need to establish more than basics, like a recovery plan that protects both data and endpoints.…
###### Suggested Courses
Course of the Month9 days, 16 hours left to enroll