From: sm0k3
Now if your going to share a piece of script whith a community and ask question about it
Why then remove it when you get it working ….no fair i was reading that …. :)
infact its good no one got round to helping you .. not being rude but if i had helped fix it i would be
furious now not to see it finished … comon … lol
but anyway shouldnt if(((map.nodes[n.x][n.y+1].isWalkable = 0) and (map.nodes[n.x+dX][n.y+1].isWalkable))
be
if not (map.nodes[n.x][n.y+1].isWalkable) and (map.nodes[n.x+dX][n.y+1].isWalkable) then
you dont need the = 0 just do it whith if not
Sorry i will keep this in mind for next time i ask for help, I didnt think of it like that. I was just a little frustrated because i didnt think anyone looked at the code because it was rather long and thought it was a waste of space.
i started adding = 0 after i found that i lost 60% performance (from 312ms to 515ms per calculation of a path) by using
not or just
if(map.nodes[n.x][n.y+1].isWalkable) iam not sure why this is though.
maybe you could help me :). The original paper is here
http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf.
How can i improve the speed?
i was thinking maybe the way i store the nodes in the open list could be improved since it stores thousands of nodes. Iam currently using a binary heap to store these nodes although iam not so sure about its implementation take a look and tell me what you think.Is there a better way to store and remove items than using a binary heap? before i used insertion sort, but this was much slower. This time i wont remove the code.
type Heap = record
list : TNode;
end;
Function Heap.get(x : Integer): Node;
begin
Result:= Self.list[x];
end;
procedure Heap.setTo(i:Integer; X : Node);
begin
Self.list[i]:=X;
end;
Function Heap.compareFScore(x,y : Integer):boolean;
begin
Result:= Self.list[x].fscore <= Self.list[y].fscore;
end;
Function Heap.Len() : Integer;
begin
Result:=High(Self.list);
end;
procedure Heap.add(i : Node);
var
b : Integer;
temp : Node;
m: Integer;
begin
//add to end of list
SetLength(Self.list,Length(Self.list)+1);
Self.list[Length(Self.list)-1]:=i;
//how many numbers in list
m:=Floor(Self.len div 2); // parent of last in list
b:=self.len;
while m <> 0 do
begin
if(Self.compareFScore(b,m))then
begin
temp:= Self.list[m];
Self.setTo(m,i);
Self.setTo(b,temp);
b:=m;
//Self.list[iParent]:=Self.list
end;
m:=Floor(m div 2);
end;
end;
procedure Heap.delete;
var
i:Integer;
u,v : integer;
temp:Node;
begin
//make last element the first element;
Self.list[1]:= Self.list[Self.len];
SetLength(self.list,Self.len);
//compare the first(new) element with children and swap if lower fcost
v := 1;
while(true) do
begin
u := v;
if(2*u+1 <= Self.len ) then
begin
if(Self.compareFScore(u*2,u)) then
begin
v:=u*2;
end;
if(Self.compareFScore(u*2+1,v)) then
begin
v:=u*2+1;
end;
end else if (2*u <= Self.len) then
begin
if(Self.compareFScore(2*u,u))then
begin
v:=2*u;
end;
end;
//swap
if(u<>v) then
begin
temp:=Self.get(u);
Self.setTo(u,Self.get(v));
Self.setTo(v,temp);
end else
begin
Exit;
end;
end;
end;
procedure Heap.heapify(count : Integer);
var
fin:Integer;
begin
fin:=2;
while (fin<count) do
begin
Self.rise(fin);
fin:=fin+1;
end;
end;
procedure Heap.rise(fin: Integer);
var
b : Integer;
temp : Node;
child: Integer;
parent : Integer;
begin
//get index you want to rise
child:= fin;
while child > 1 do
begin
parent:=floor(child div 2);
if(Self.list[parent].fscore >= Self.list[child].fscore) then
begin
temp:=Self.list[parent];
Self.list[parent]:= Self.list[child];
Self.list[child]:=temp;
child:=parent;
end else begin exit end;
end;
end;
procedure Heap.swap(index : Integer);
var
temp : Node;
begin
temp:=Self.list[1];
Self.list[1]:=Self.list[index];
Self.list[index]:=temp;
end;