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;
                
 
}

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.

Ha.. my fault, it is obstructed...

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;
    }    


}

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.