Solved

Good A star algorithm website!

Posted on 2001-06-04
2
19,528 Views
Last Modified: 2013-12-26
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
Comment
Question by:jiminika
2 Comments
 

Accepted Solution

by:
dsreynolds earned 100 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,
    vector<CPathNode> PATH;                 // and Direct access to any element.
    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;
                    }
                }
                if (!bNodeFound ) // If Node NOT found on OPEN
                {
                    // 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

by:jiminika
ID: 6164528
Thanks
0

Featured Post

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

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 …
Artificial Intelligence comes in many forms, and for game developers, Path-Finding is an important ability for making an NPC (Non-Playable Character) maneuver through terrain.  A* is a particularly easy way to approach it.  I’ll start with the algor…
This Micro Tutorial will teach you how to censor certain areas of your screen. The example in this video will show a little boy's face being blurred. This will be demonstrated using Adobe Premiere Pro CS6.
Established in 1997, Technology Architects has become one of the most reputable technology solutions companies in the country. TA have been providing businesses with cost effective state-of-the-art solutions and unparalleled service that is designed…

776 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question