Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

About QuadTree AStar

This topic is 916 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

You can see that the path costs are not uniform, due to the nature of quadtrees.

And I am using 4 directional moves at the moment, On the last step of this dump,

I find the the pathfinder has lost its properties.

 

X: -23.1811 Z 6.16012

is certainly better than

X: -20.7061 Z 13.5007

 

And BTW, I have enough clearance for the agent to get to its destination.

 

 

Any ideas that I can make improvements on this?

 

Update:

Sorry, guys, I know now, I got some unwanted geometries in my scene when generating the grid, so the destination cannot be reached.

Thanks for helping

Src:
m_vPos = 0x000000000cb4e0bc {-18.2310867, 0.000000000, 15.9476185}
 
Dest:
m_vPos = 0x000000000e9f2c5c {-33.6998367, 0.000000000, -22.5906639}
 
From: AStar 1 X: -18.2311 Z15.9476 total_cost 44.9457 path_cost 0 estimated_cost 44.9457

From: AStar ===========
From: AStar 1 X: -18.2311 Z13.5007 total_cost 44.9457 path_cost 2.44687 estimated_cost 42.4988

From: AStar 2 X: -20.7061 Z15.9476 total_cost 46.3955 path_cost 2.475 estimated_cost 43.9205

From: AStar 3 X: -15.7561 Z15.9476 total_cost 48.4458 path_cost 2.475 estimated_cost 45.9708

From: AStar 4 X: -18.2311 Z18.3945 total_cost 49.8394 path_cost 2.44687 estimated_cost 47.3925

From: AStar ===========
From: AStar 1 X: -18.2311 Z11.0539 total_cost 44.9457 path_cost 4.89375 estimated_cost 40.0519

From: AStar 2 X: -20.7061 Z13.5007 total_cost 46.3955 path_cost 4.92188 estimated_cost 41.4736

From: AStar 3 X: -20.7061 Z15.9476 total_cost 46.3955 path_cost 2.475 estimated_cost 43.9205

From: AStar 4 X: -15.7561 Z13.5007 total_cost 48.4458 path_cost 4.92187 estimated_cost 43.524

From: AStar 5 X: -15.7561 Z15.9476 total_cost 48.4458 path_cost 2.475 estimated_cost 45.9708

From: AStar 6 X: -18.2311 Z18.3945 total_cost 49.8394 path_cost 2.44687 estimated_cost 47.3925

From: AStar ===========
From: AStar 1 X: -18.2311 Z8.60699 total_cost 44.9457 path_cost 7.34062 estimated_cost 37.605

From: AStar 2 X: -20.7061 Z11.0539 total_cost 46.3955 path_cost 7.36875 estimated_cost 39.0267

From: AStar 3 X: -20.7061 Z13.5007 total_cost 46.3955 path_cost 4.92188 estimated_cost 41.4736

From: AStar 4 X: -20.7061 Z15.9476 total_cost 46.3955 path_cost 2.475 estimated_cost 43.9205

From: AStar 5 X: -15.7561 Z11.0539 total_cost 48.4458 path_cost 7.36875 estimated_cost 41.0771

From: AStar 6 X: -15.7561 Z13.5007 total_cost 48.4458 path_cost 4.92187 estimated_cost 43.524

From: AStar 7 X: -15.7561 Z15.9476 total_cost 48.4458 path_cost 2.475 estimated_cost 45.9708

From: AStar 8 X: -18.2311 Z18.3945 total_cost 49.8394 path_cost 2.44687 estimated_cost 47.3925

From: AStar ===========
From: AStar 1 X: -18.2311 Z6.16012 total_cost 44.9457 path_cost 9.7875 estimated_cost 35.1582

From: AStar 2 X: -20.7061 Z8.60699 total_cost 46.3955 path_cost 9.81563 estimated_cost 36.5798

From: AStar 3 X: -20.7061 Z11.0539 total_cost 46.3955 path_cost 7.36875 estimated_cost 39.0267

From: AStar 4 X: -20.7061 Z13.5007 total_cost 46.3955 path_cost 4.92188 estimated_cost 41.4736

From: AStar 5 X: -20.7061 Z15.9476 total_cost 46.3955 path_cost 2.475 estimated_cost 43.9205

From: AStar 6 X: -15.7561 Z11.0539 total_cost 48.4458 path_cost 7.36875 estimated_cost 41.0771

From: AStar 7 X: -15.7561 Z8.60699 total_cost 48.4458 path_cost 9.81562 estimated_cost 38.6302

From: AStar 8 X: -15.7561 Z13.5007 total_cost 48.4458 path_cost 4.92187 estimated_cost 43.524

From: AStar 9 X: -15.7561 Z15.9476 total_cost 48.4458 path_cost 2.475 estimated_cost 45.9708

From: AStar 10 X: -18.2311 Z18.3945 total_cost 49.8394 path_cost 2.44687 estimated_cost 47.3925

From: AStar ===========
From: AStar 1 X: -20.7061 Z6.16012 total_cost 46.3955 path_cost 12.2625 estimated_cost 34.133

From: AStar 2 X: -20.7061 Z8.60699 total_cost 46.3955 path_cost 9.81563 estimated_cost 36.5798

From: AStar 3 X: -20.7061 Z11.0539 total_cost 46.3955 path_cost 7.36875 estimated_cost 39.0267

From: AStar 4 X: -20.7061 Z13.5007 total_cost 46.3955 path_cost 4.92188 estimated_cost 41.4736

From: AStar 5 X: -20.7061 Z15.9476 total_cost 46.3955 path_cost 2.475 estimated_cost 43.9205

From: AStar 6 X: -15.7561 Z11.0539 total_cost 48.4458 path_cost 7.36875 estimated_cost 41.0771

From: AStar 7 X: -15.7561 Z6.16012 total_cost 48.4458 path_cost 12.2625 estimated_cost 36.1833

From: AStar 8 X: -15.7561 Z8.60699 total_cost 48.4458 path_cost 9.81562 estimated_cost 38.6302

From: AStar 9 X: -15.7561 Z13.5007 total_cost 48.4458 path_cost 4.92187 estimated_cost 43.524

From: AStar 10 X: -15.7561 Z15.9476 total_cost 48.4458 path_cost 2.475 estimated_cost 45.9708

From: AStar 11 X: -18.2311 Z18.3945 total_cost 49.8394 path_cost 2.44687 estimated_cost 47.3925

From: AStar ===========
From: AStar 1 X: -20.7061 Z8.60699 total_cost 46.3955 path_cost 9.81563 estimated_cost 36.5798

From: AStar 2 X: -20.7061 Z11.0539 total_cost 46.3955 path_cost 7.36875 estimated_cost 39.0267

From: AStar 3 X: -20.7061 Z13.5007 total_cost 46.3955 path_cost 4.92188 estimated_cost 41.4736

From: AStar 4 X: -20.7061 Z15.9476 total_cost 46.3955 path_cost 2.475 estimated_cost 43.9205

From: AStar 5 X: -23.1811 Z6.16012 total_cost 47.8453 path_cost 14.7375 estimated_cost 33.1078

From: AStar 6 X: -15.7561 Z11.0539 total_cost 48.4458 path_cost 7.36875 estimated_cost 41.0771

From: AStar 7 X: -15.7561 Z6.16012 total_cost 48.4458 path_cost 12.2625 estimated_cost 36.1833

From: AStar 8 X: -15.7561 Z8.60699 total_cost 48.4458 path_cost 9.81562 estimated_cost 38.6302

From: AStar 9 X: -15.7561 Z13.5007 total_cost 48.4458 path_cost 4.92187 estimated_cost 43.524

From: AStar 10 X: -15.7561 Z15.9476 total_cost 48.4458 path_cost 2.475 estimated_cost 45.9708

From: AStar 11 X: -18.2311 Z18.3945 total_cost 49.8394 path_cost 2.44687 estimated_cost 47.3925

From: AStar ===========
From: AStar 1 X: -20.7061 Z11.0539 total_cost 46.3955 path_cost 7.36875 estimated_cost 39.0267

From: AStar 2 X: -20.7061 Z13.5007 total_cost 46.3955 path_cost 4.92188 estimated_cost 41.4736

From: AStar 3 X: -20.7061 Z15.9476 total_cost 46.3955 path_cost 2.475 estimated_cost 43.9205

From: AStar 4 X: -23.1811 Z6.16012 total_cost 47.8453 path_cost 14.7375 estimated_cost 33.1078

From: AStar 5 X: -23.1811 Z8.60699 total_cost 47.8453 path_cost 12.2906 estimated_cost 35.5547

From: AStar 6 X: -15.7561 Z11.0539 total_cost 48.4458 path_cost 7.36875 estimated_cost 41.0771

From: AStar 7 X: -15.7561 Z6.16012 total_cost 48.4458 path_cost 12.2625 estimated_cost 36.1833

From: AStar 8 X: -15.7561 Z8.60699 total_cost 48.4458 path_cost 9.81562 estimated_cost 38.6302

From: AStar 9 X: -15.7561 Z13.5007 total_cost 48.4458 path_cost 4.92187 estimated_cost 43.524

From: AStar 10 X: -15.7561 Z15.9476 total_cost 48.4458 path_cost 2.475 estimated_cost 45.9708

From: AStar 11 X: -18.2311 Z18.3945 total_cost 49.8394 path_cost 2.44687 estimated_cost 47.3925

From: AStar ===========
From: AStar 1 X: -20.7061 Z13.5007 total_cost 46.3955 path_cost 4.92188 estimated_cost 41.4736

From: AStar 2 X: -20.7061 Z15.9476 total_cost 46.3955 path_cost 2.475 estimated_cost 43.9205

From: AStar 3 X: -23.1811 Z11.0539 total_cost 47.8453 path_cost 9.84375 estimated_cost 38.0015

From: AStar 4 X: -23.1811 Z6.16012 total_cost 47.8453 path_cost 14.7375 estimated_cost 33.1078

From: AStar 5 X: -23.1811 Z8.60699 total_cost 47.8453 path_cost 12.2906 estimated_cost 35.5547

From: AStar 6 X: -15.7561 Z11.0539 total_cost 48.4458 path_cost 7.36875 estimated_cost 41.0771

From: AStar 7 X: -15.7561 Z6.16012 total_cost 48.4458 path_cost 12.2625 estimated_cost 36.1833

From: AStar 8 X: -15.7561 Z8.60699 total_cost 48.4458 path_cost 9.81562 estimated_cost 38.6302

From: AStar 9 X: -15.7561 Z13.5007 total_cost 48.4458 path_cost 4.92187 estimated_cost 43.524

From: AStar 10 X: -15.7561 Z15.9476 total_cost 48.4458 path_cost 2.475 estimated_cost 45.9708

From: AStar 11 X: -18.2311 Z18.3945 total_cost 49.8394 path_cost 2.44687 estimated_cost 47.3925
AStarPath* AStar::findPath(QuadNode* start, QuadNode* destination, CObject* unit, bool bBackupMode)
{

 
    if (start == NULL || destination == NULL)
        return NULL;
    

    OpenCloseMap<QuadNode> m_ClosedSet;
    OpenCloseMap<QuadNode> m_OpenSet;
    QuadNode* current = NULL;
    bool solved = false;
    int iterations = 0;    
    std::set<QuadNode, QuadSetComparator> m_OrderedOpenSet;

    

    try {
        start->path_cost = 0;
        start->estimated_cost = start->distance(destination);
        start->total_cost = start->estimated_cost;

        m_OpenSet.Add(start);
        m_OrderedOpenSet.insert(*start);
        

        while (!m_OpenSet.IsEmpty())
        {

            
            int i = 1;
            typedef std::set<QuadNode, QuadSetComparator>::const_iterator itr;
            for (itr it = m_OrderedOpenSet.begin(); it != m_OrderedOpenSet.end(); it++) {
                const QuadNode& on = (*it);                
                std::stringstream oss;
                oss << i++ << " X: " << on.m_vPos[0] << " Z: " << on.m_vPos[2] << " total_cost " << on.total_cost << " path_cost " << on.path_cost << " estimated_cost " << on.estimated_cost << endl;
                LogFileSingletonGeneral::print("AStar", oss.str());
            }

            

            LogFileSingletonGeneral::print("AStar", "===========");
            

            current = new QuadNode(*m_OrderedOpenSet.begin());

            if (bBackupMode) {
                m_BackupPool.AddBackupNode(unit->GetName(), current);
            }

            if (current->contains(destination))
            {
                solved = true;
            }


            m_OpenSet.Remove(current);
            m_ClosedSet.Add(current);

            if (!m_OrderedOpenSet.empty())
                m_OrderedOpenSet.erase(m_OrderedOpenSet.begin());

            std::vector<QuadNode*>& neighborNodes = current->neighbours();


            for (int i = 0; i < neighborNodes.size(); i++)
            {
                QuadNode* neighbour = new QuadNode(*neighborNodes[i]);
                iterations++;

                float cost = current->distance(neighbour);

                if (neighbour->status == QuadNode::OBSTRUCTED)
                    continue;

                if (m_ClosedSet.Contains(neighbour))
                    continue;

                // in open list
                if (m_OpenSet.Contains(neighbour))
                {
                    // current is better, update the info
                    if (current->path_cost + cost < neighbour->path_cost)
                    {


                        // neighbour G cost greater than current->G + neighbour cost
                        m_OpenSet.Remove(neighbour);

                        if (!m_OrderedOpenSet.empty())
                            m_OrderedOpenSet.erase(m_OrderedOpenSet.find(*neighbour));

                        // sets the neighbour to the current's neighbour
                        neighbour->ancestor = current;
                        neighbour->path_cost = current->path_cost + cost;
                        neighbour->total_cost = neighbour->path_cost + neighbour->estimated_cost;
                        m_OpenSet.Add(neighbour);
                        m_OrderedOpenSet.insert(*neighbour);


                    }

                }
                else
                {

                    // open a new node
                    neighbour->ancestor = current;
                    neighbour->path_cost = current->path_cost + cost;
                    neighbour->estimated_cost = neighbour->distance(destination);
                    neighbour->total_cost = neighbour->path_cost + neighbour->estimated_cost;
                    m_OpenSet.Add(neighbour);
                    m_OrderedOpenSet.insert(*neighbour);

                }
            }
        }

        if (solved) {
            float totalCost = current->path_cost;
            std::vector<AStarTransition*> transitions;
            while (current->ancestor != NULL) {
                transitions.emplace(transitions.begin(), new AStarTransition(current, current->ancestor));

                // get where it originates from
                current = (QuadNode*)current->ancestor;
            }     
            cout << "Takes " << iterations << endl;



            return new AStarPath(start, transitions, totalCost);
        }
    }
    catch (...) {
        cout << "\nNo Path found " << endl;
        return NULL;
    }
    
    cout << "\nNo Path found " << endl;
    return NULL;
                
 
}
Edited by lucky6969b

Share this post


Link to post
Share on other sites
Advertisement

Hello ApochPiQ,

I believe the astar algorthim is correct and is admissible.

I have debugged it visually, it does open nodes towards the destination.

But one thing I discovered in my algorithm, is in the quadtree, I cannot find a neighbouring node which

is smaller than itself

Like this

I am using the paper described in here

http://www.cs.umd.edu/~hjs/pubs/SameCGIP82.pdf

 

Okay, let me check back, may be it is an obstructed node....

 

Here is a demo.

Edited by lucky6969b

Share this post


Link to post
Share on other sites

Hello,

I don't know why, if the node is in the quadrant same as the requested quadrant,

I keep looping to find its ancestor until it runs out to the root node which is the whole scene

If I understand the pseudocode correctly, should it be coded this way?

 

 

Update:

Some minor fixes

///////////////////////////////////////////
// Returns the neighbour of a quadrant
// which is a diagonal nei of that quadrant
QuadNode* QuadNode::neighbor(Quadrant c) const {
    QuadNode* _neighbor = NULL;

    // Ascent the tree up to a common ancestor.

    cout << "ID is " << this->m_time_independent_id << endl;

    // quadrant returns which quadrant this node is in
    if (quadrant() == OpQuad(c)) {
        _neighbor = parent;
    }    
    else if (quadrant() == c) {
        _neighbor = parent->neighbor(c);
    }
    else {
        // NW NE common side is N
        _neighbor = parent->neighbor(CommonSide(quadrant(), c));
    }

    // Backtrack mirroring the ascending moves.    
    if (_neighbor && !_neighbor->is_leaf()) {
        return _neighbor->child(OpQuad(quadrant()));

    }
    else {
        return _neighbor;
    }    


}
Edited by lucky6969b

Share this post


Link to post
Share on other sites

Do I have to use true distance with QuadTree AStar/TimeAStar? because x and z positions have no true meanings
for a quadtree node. I just can give it an id. Now the QuadTree mode is working. But instead of resolving in a short period of time compared to earlier example, because I am using true distance for the comparator, I find the astar/timeastar
uses a lot of efforts to get to the destinations.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!