📄 astarlinkedlist.cpp
字号:
DXY[n].cost_multiplier=diagonal_cost*median_terrain_cost;
}
}
else
{
for(n=0;n<4;n++)
{
DXY[n].cost_multiplier=1.0f*cost;
}
for(n=4;n<8;n++)
{
DXY[n].cost_multiplier=diagonal_cost*cost;
}
}
}
///////////////////////////////////////////////////////////////////////////
// TYPE B
void AStarLinkedList::PackRoute()
{
if(no_path)
{
airoute->count=0;
return;
}
//
memset(airoute->route,0,MAX_ROUTES); //clear routes
//
airoute->active=1;
airoute->compression=0;
//
WORD yx=endyx;
int start=MAX_ROUTES-1;
BYTE route=NO_ROUTE;
while(yx!=startyx)
{
// route=DXY[world[yx].route].route;
route=world[yx].route;
yx+=DXY[DXY[route].route].yx;
airoute->route[start]=route;
if(--start<0) start=MAX_ROUTES-1;
};
airoute->start=start+1;
airoute->count=MAX_ROUTES-airoute->start;
//
airoute->startyx=startyx;
airoute->endyx=endyx;
//
airoute->walk_point=airoute->start;
airoute->walk_runlength_step=0;
//
if(airoute->start==0) airoute->count=0;
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
/*
This is the function that paints the graphics to the screen.
Called by PathFinder.
Localized to respective Setup classes v1.6.
*/
//
void AStarLinkedList::Paint(LPBYTE pwBits, HDC hdc,HWND hWnd)
{
if(pwBits) // && vSetup->map_loaded)
{
//
RECT rt;
GetClientRect(hWnd, &rt);
int clientwidth = (rt.right-rt.left);
COLORREF background;
COLORREF foreground;
vSetup->get_colorscheme_colors(background,foreground);
HBRUSH hbrBkGnd = CreateSolidBrush(background);
FillRect(hdc, &rt, hbrBkGnd);
DeleteObject(hbrBkGnd);
SetBkColor(hdc,background);
SetTextColor(hdc,foreground);
//
int starty=startyx>>YSHIFT;
int startx=startyx&XMASK;
int endy=endyx>>YSHIFT;
int endx=endyx&XMASK;
TCHAR szStatusLine[1024];
_RGBA *p,*ppush;
_RGBA *pbegin=(_RGBA *)pwBits;
int y,x;
int yx;
int node;
int count;
register _RGBA *tmp;
//
int used_nodes=0;
float smallest_f, smallest_g, smallest_h;
float largest_f, largest_g, largest_h;
smallest_f = smallest_g = smallest_h = 1048576.0f;
largest_f = largest_g = largest_h = 0.0001f;
if(open_nodes>0)
{
count=MAX_NODE;
node=best_node;
do
{
if(nodes[node].f>largest_f) largest_f=nodes[node].f;
if(nodes[node].f<smallest_f) smallest_f=nodes[node].f;
if(nodesdata[node].g>largest_g) largest_g=nodesdata[node].g;
if(nodesdata[node].g<smallest_g) smallest_g=nodesdata[node].g;
float h=nodes[node].f-nodesdata[node].g;
if(h>largest_h) largest_h=h;
if(h<smallest_h) smallest_h=h;
node=nodes[node].next;
used_nodes++;
} while(node!=best_node && node!=EMPTY_NODE && --count>=0);
}
count=MAX_NODE;
node=closed_node;
do
{
if(nodes[node].f>largest_f) largest_f=nodes[node].f;
if(nodes[node].f<smallest_f) smallest_f=nodes[node].f;
if(nodesdata[node].g>largest_g) largest_g=nodesdata[node].g;
if(nodesdata[node].g<smallest_g) smallest_g=nodesdata[node].g;
float h=nodes[node].f-nodesdata[node].g;
if(h>largest_h) largest_h=h;
if(h<smallest_h) smallest_h=h;
used_nodes++;
node=nodes[node].prev;
} while(node!=EMPTY_NODE && --count>=0);
//
int length=0;
count=MAX_NODE;
node=closed_node;
do
{
length++;
node=nodesdata[node].ancestor;
} while(node!=EMPTY_NODE && --count>=0);
// stats
GetClientRect(hWnd, &rt);
sprintf(szStatusLine,
"-- A* Linked List (v2) --\nf %f ... %f\ng %f ... %f\nh %f ... %f\n\nstruct size %d bytes\n(world %d B)\n(node %d B)\n(used node %d B)\n\nMAX NODES %d\nBest Node\n(%d < %d > %d)\nf %f\ng %f\nh %f\nClosed Node\n(%d < %d > %d)\nf %f\ng %f\nh %f\n\npath found? %s\nlength= %d\n\nstart -> current\nf %f -> %f\ng %f -> %f\nh %f -> %f\n%s\n",
smallest_f, largest_f,
smallest_g, largest_g,
smallest_h, largest_h,
sizeof(nodes)+sizeof(nodesdata) + sizeof(world),
sizeof(world),
sizeof(nodes)+sizeof(nodesdata),
used_nodes*(sizeof(_NODES)+sizeof(_NODESDATA)),
MAX_NODE,
nodes[best_node].prev,
best_node,
nodes[best_node].next,
nodes[best_node].f,
nodesdata[best_node].g,
nodes[best_node].f-nodes[best_node].f,
nodes[closed_node].prev,
closed_node,
nodes[closed_node].next,
nodes[closed_node].f,
nodesdata[closed_node].g,
nodes[closed_node].f-nodes[closed_node].f,
no_path?"NO PATH!":(path_found?"YES!":"Not yet..."),
length,
nodes[1].f,nodes[closed_node].f,
nodesdata[1].g,nodesdata[closed_node].g,
nodes[1].f-nodesdata[1].g,nodes[closed_node].f-nodesdata[closed_node].g,
(nodes[closed_node].f<=nodes[1].f)?"ADMISSIBLE":"not admissible"
);
DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_RIGHT);
// composite
GetClientRect(hWnd, &rt);
rt.top=HEIGHT;
rt.right=WIDTH;
sprintf(szStatusLine,"shortest path");
DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
p=ppush=pbegin;
for(y=0;y<HEIGHT;y++)
{
for(x=0;x<WIDTH;x++)
{
BYTE b=(BYTE)(255-(world[y*WIDTH+x].terrain_cost<<4));
p->red=b; p->green=b; p->blue=b;
p++;
}
ppush+=clientwidth;
p=ppush;
}
for(y=-1;y<=1;y++) //starting point
{
for(x=-1;x<=1;x++)
{
tmp=(pbegin+(starty+y)*clientwidth+startx+x);
tmp->red=255;
tmp->green=0;
tmp->blue=0;
}
}
for(y=-1;y<=1;y++) //end/goal point
{
for(x=-1;x<=1;x++)
{
tmp=(pbegin+(endy+y)*clientwidth+endx+x);
tmp->red=0;
tmp->green=255;
tmp->blue=0;
}
}
p=pbegin;
count=MAX_NODE;
node=closed_node;
while(node!=EMPTY_NODE && --count>=0)
{
tmp=(p+(nodesdata[node].yx>>YSHIFT)*clientwidth+(nodesdata[node].yx&XMASK));
tmp->red=255;
tmp->green=0;
tmp->blue=0;
node=nodesdata[node].ancestor;
};
// f
GetClientRect(hWnd, &rt);
rt.top=HEIGHT;
rt.left=WIDTH+4;
rt.right=WIDTH+4+WIDTH;
sprintf(szStatusLine,"f (red closed/blue open)");
DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
p=pbegin+(WIDTH+4);
if(open_nodes>0)
{
count=MAX_NODE;
node=best_node;
do
{
tmp=(p+(nodesdata[node].yx>>YSHIFT)*clientwidth+(nodesdata[node].yx&XMASK));
tmp->red=0;
tmp->green=0;
tmp->blue=(BYTE)((nodes[node].f/largest_f)*255.0f);
node=nodes[node].prev;
} while(node!=best_node && node!=EMPTY_NODE && --count>=0);
}
count=MAX_NODE;
node=closed_node;
while(node!=EMPTY_NODE && --count>=0)
{
tmp=(p+(nodesdata[node].yx>>YSHIFT)*clientwidth+(nodesdata[node].yx&XMASK));
tmp->red=(BYTE)((nodes[node].f/largest_f)*255.0f);
tmp->green=0;
tmp->blue=0;
node=nodes[node].prev;
};
// open
GetClientRect(hWnd, &rt);
rt.top=HEIGHT*2+16;
rt.left=0;
rt.right=WIDTH;
sprintf(szStatusLine,"open nodes %d",open_nodes);
DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
if(open_nodes>0)
{
p=pbegin+(HEIGHT+16)*clientwidth;
count=MAX_NODE;
node=best_node;
do
{
BYTE f=(BYTE)((nodes[node].f/largest_f)*255.0f);
BYTE g=(BYTE)((nodesdata[node].g/largest_g)*255.0f);
BYTE h=(BYTE)(((nodes[node].f-nodesdata[node].g)/largest_h)*255.0f);
tmp=(p+(nodesdata[node].yx>>YSHIFT)*clientwidth+(nodesdata[node].yx&XMASK));
tmp->red=h;
tmp->green=g;
tmp->blue=f;
node=nodes[node].prev;
} while(node!=best_node && node!=EMPTY_NODE && --count>=0);
}
// closed
GetClientRect(hWnd, &rt);
rt.top=HEIGHT*2+16;
rt.left=WIDTH+4;
rt.right=WIDTH+4+WIDTH;
sprintf(szStatusLine,"closed nodes %d",closed_nodes);
DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
p=pbegin+WIDTH+4+(HEIGHT+16)*clientwidth;
count=MAX_NODE;
node=closed_node;
while(node!=EMPTY_NODE && --count>=0)
{
BYTE f=(BYTE)((nodes[node].f/largest_f)*255.0f);
BYTE g=(BYTE)((nodesdata[node].g/largest_g)*255.0f);
BYTE h=(BYTE)(((nodes[node].f-nodesdata[node].g)/largest_h)*239.0f);
tmp=(p+(nodesdata[node].yx>>YSHIFT)*clientwidth+(nodesdata[node].yx&XMASK));
tmp->red=h;
tmp->green=g;
tmp->blue=f;
node=nodes[node].prev;
};
// state
GetClientRect(hWnd, &rt);
rt.top=HEIGHT;
rt.left=(WIDTH+4)*2;
rt.right=(WIDTH+4)*2+WIDTH;
sprintf(szStatusLine,"state (g=open b=closed r=impass)");
DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
p=pbegin+(WIDTH+4)*2;
for(y=0;y<HEIGHT;y++)
{
for(x=0;x<WIDTH;x++)
{
yx=(y<<YSHIFT)+x;
tmp=(p+y*clientwidth+x);
tmp->green=(BYTE)((world[yx].state==OPEN)?255:0);
tmp->blue=(BYTE)((world[yx].state==CLOSED)?255:0);
tmp->red=(BYTE)((world[yx].state==IMPASSABLE)?255:0);
}
}
// successors & routing
GetClientRect(hWnd, &rt);
rt.top=HEIGHT*2+16;
rt.left=(WIDTH+4)*2;
rt.right=(WIDTH+4)*2+WIDTH;
sprintf(szStatusLine,"successors and routes");
DrawText(hdc, szStatusLine, strlen(szStatusLine), &rt, DT_CENTER);
//
p=pbegin+(WIDTH+4)*2+(HEIGHT+16)*clientwidth;
//routing
for(y=0;y<HEIGHT;y++)
{
for(x=0;x<WIDTH;x++)
{
tmp=(p+y*clientwidth+x);
tmp->red=0;
switch(world[(y<<YSHIFT)+x].route)
{
case 0: tmp->green=0; tmp->blue=255; break; // n
case 1: tmp->green=127; tmp->blue=255; break; // e
case 2: tmp->green=255; tmp->blue=0; break; // s
case 3: tmp->green=255; tmp->blue=127; break; // w pink
case 4: tmp->green=0; tmp->blue=255; break; // ne
case 5: tmp->green=127; tmp->blue=255; break; // se
case 6: tmp->green=255; tmp->blue=0; break; // sw
case 7: tmp->green=255; tmp->blue=127; break; // nw
};
}
}
// successors
int diff=(directions==8)?31:63;
if(open_nodes>0)
{
count=MAX_NODE;
node=best_node;
do
{
int successors=0;
for(register int i=0;i<directions;i++)
{
if(nodesdata[node].successor[i]!=EMPTY_NODE)
successors+=diff;
}
tmp=(p+(nodesdata[node].yx>>YSHIFT)*clientwidth+(nodesdata[node].yx&XMASK));
tmp->red=(BYTE)successors;
node=nodes[node].prev;
} while(node!=best_node && node!=EMPTY_NODE && --count>=0);
}
count=MAX_NODE;
node=closed_node;
while(node!=EMPTY_NODE && --count>=0)
{
int successors=0;
for(register int i=0;i<directions;i++)
{
if(nodesdata[node].successor[i]!=EMPTY_NODE)
successors+=diff;
}
tmp=(p+(nodesdata[node].yx>>YSHIFT)*clientwidth+(nodesdata[node].yx&XMASK));
tmp->red=(BYTE)successors;
node=nodes[node].prev;
};
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -