... Atleast I thought so. For some reason, when the operator is defined like this

bool node::operator<(const node *right) const{
return (costF < right->costF);
}

it is beeing completly ignored by the priority queue. Deleting it doesn't give me ">operator not defined".

const node * is a pointer, not a reference. const node & is a reference.

You are right ... I shouldn't try coding this late at night.

But changing it didn't increase the speed of openList.push() at all.

So, we are back were we began

EDIT: I also tried what TiagoCosta mentioned, but it didn't increase the speed by a noticable amount.

Hello.

Have you tryed a std::list for your Prioityqueue this way you can incert the lowest cost it works fast for me, my maps are a grid 1000 X 1000 plus cells

std::list<Cell *> Priorityqueue;//ordered list

For testing, I use

clock();

I did compare with other implementations, but they were all much slower than mine. The graph is represented by a 2D array of nodes.

I went through several mapsizes, currently 256x256 is the only one that performs close to an acceptable speed, but still is kinda to slow when a player wants to path over the full map in one go(2-3 sec). On short or midrange paths it seems ok though.

I'm not exactly sure how NPC-movement is handled in onlinegames. They have to path too, so the server would have to comptue their paths - and that rather frequently. That really would impact that servers performance, right?

@ankhd

I don't really understand what you want to say. You suppose a std::list is faster than a priority-queue in terms of pushing? How fast do you manage to path over a 1kx1k grid from edge to edge?

But I can't do that with pointers - as soon as I try to update a value on a node that I pushed onto the openlist, I end up with the "invalid heap" runtime error.

Hello, sorry for my late reply.

I was profiling in a debug build, I didn't think of that beeing able to influence the performance. Switching it improved the speed by like 25%.

I never used a profiler before, but if you are able to point me to a good one, I'd be willing to give it a try.

I'm still pushing twice instead of updateing the nodes. I take it you suggest updating rather than doing that?

I'm storing the nodes in a simple 2D array

node *map[size][size];

Here is the .h of the node class:

 
 
class node{
public:
node *parent;
int2 pos;
D3DXVECTOR2 posInNode;
bool isOpen;
 
bool isOnClosedList, isOnOpenList; // not using closedlist, and isOnOpenList lets me skip the sorting through the openlist when I want to see if a node is on it
int costF, costG, costH;
 
bool pushedOntoQueue;
 
public:
node(){
resetData();
isOpen = true;
pos = int2(0, 0);
}
node(int2 posIn){
pos = posIn;
isOpen = true;
resetData();
}
~node(){}
 
// reset for reusing
void resetData(){
posInNode = D3DXVECTOR2(-1, -1);
parent = NULL;
costF = costG = costH = 0;
isOnClosedList = false;
isOnOpenList = false;
 
pushedOntoQueue = false;
}
};
 

This is what I use in the priorityqueue instead of the full Node:

struct nodePH{
int2 pos;
int costF;
bool operator<(const nodePH &right) const{
return (costF > right.costF);
}
};