PathFinder
所属分类:*行业应用
开发工具:C++
文件大小:753KB
下载次数:122
上传日期:2004-09-24 19:15:40
上 传 者:
gemingxin
说明: 路径探索算法,该算法为国外的一个牛人写的
(trails to explore algorithm for a foreign person to write the cattle)
文件列表:
PathFinder2D (0, 2003-07-17)
PathFinder2D\arrow.cur (326, 2003-06-10)
PathFinder2D\Astar.cpp (16866, 2003-07-17)
PathFinder2D\AStar.h (2830, 2003-07-11)
PathFinder2D\AStarArray.cpp (16251, 2003-07-17)
PathFinder2D\AStarArray.h (2308, 2003-07-10)
PathFinder2D\AStarComplete.cpp (21922, 2003-07-17)
PathFinder2D\AStarComplete.h (2757, 2003-07-05)
PathFinder2D\AStarHeap.cpp (20597, 2003-07-17)
PathFinder2D\AStarHeap.h (2555, 2003-07-13)
PathFinder2D\AStarHeapInteger.cpp (21002, 2003-07-17)
PathFinder2D\AStarHeapInteger.h (2607, 2003-07-13)
PathFinder2D\AStarLinkedList.cpp (21057, 2003-07-17)
PathFinder2D\AStarLinkedList.h (2663, 2003-07-10)
PathFinder2D\author.tga (36281, 2003-07-05)
PathFinder2D\BestFirst.cpp (17040, 2003-07-13)
PathFinder2D\BestFirst.h (2441, 2003-07-13)
PathFinder2D\braid_maze.tga (43997, 2003-07-17)
PathFinder2D\BreadthFirst.cpp (11782, 2003-07-13)
PathFinder2D\BreadthFirst.h (1421, 2003-07-13)
PathFinder2D\cavern_maze.tga (46395, 2003-07-17)
PathFinder2D\chi.tga (26093, 2003-07-05)
PathFinder2D\circle_maze.tga (39339, 2003-07-05)
PathFinder2D\clutter.tga (15725, 2003-07-05)
PathFinder2D\crack_maze.tga (48513, 2003-07-17)
PathFinder2D\cretan_labyrinth.tga (13071, 2003-07-17)
PathFinder2D\DepthFirst.cpp (12176, 2003-07-13)
PathFinder2D\DepthFirst.h (1370, 2003-07-13)
PathFinder2D\Development.cpp (17050, 2003-07-13)
PathFinder2D\Development.h (2719, 2003-07-07)
PathFinder2D\DFS.cpp (383, 2003-06-27)
PathFinder2D\DFS.h (288, 2003-06-27)
PathFinder2D\diagonal_maze.tga (56588, 2003-07-17)
PathFinder2D\Dijkstra.cpp (14366, 2003-07-17)
PathFinder2D\Dijkstra.h (1682, 2003-07-05)
PathFinder2D\DStar.cpp (397, 2003-07-08)
PathFinder2D\DStar.h (482, 2003-07-08)
PathFinder2D\flower.tga (6962, 2003-07-05)
PathFinder2D\Generic.cpp (14584, 2003-07-13)
PathFinder2D\Generic.h (2028, 2003-07-13)
... ...
todo v1.20
! if leaf>max_leafs remove last leaf, then add new leaf
? presearch for all no-paths and mark as permantly_no_path if start/end there
!! consider hot-queuing if over f (or n-nodes) to prevent heaps with levels greater than x (say 6 to 7).
todo v1.14/1.15
MUST
fix a* complete.
fix A* p.q.
//fix A* array bugs
redo AIs handling
general cleanup
MAYBE
fix hlp?
DFS
add bilinear scaling to Load.
add registry load/save settings
//#define DISPLAY_AIS
enum
{
MAX_AIS=1000,
MAX_ROUTES=512,
MAX_RUNLENGTH=32
};
typedef struct _ROUTE
{
BYTE route :3; //0-7
BYTE runlength :5; //0-31 +1
} ROUTE;
typedef struct _AIROUTE
{
// debugging
DWORD color;
// processing
BYTE priority; //0=done
BYTE active :1; //0=no ai, 1=ai
BYTE uncompressed :1;
// walking
WORD walk_point; //at what point in the path-ways are we?
WORD walk_runlength_step; //and if on a runlength at what step?
// encoding/decoding
WORD startyx;
WORD endyx;
WORD start; //0 to MAX_PATH_LENGTH-1
WORD count; //if count==0 then not used
ROUTE route[MAX_ROUTES];
} AIROUTE;
///////////////////////////////////////////////////////////////////////////
//
void Generic::Paint_All(LPBYTE pwBits, HDC hdc,HWND hWnd)
{
if(pwBits)
{
//
RECT rt;
GetClientRect(hWnd, &rt);
int clientwidth = (rt.right-rt.left);
int clientheight = (rt.bottom-rt.top);
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);
//
_RGBA *pbegin=(_RGBA *)pwBits+(clientwidth>>1)-(WIDTH)+ ((clientheight>>1)-(HEIGHT))*clientwidth;
_RGBA *pend=pbegin+clientwidth*(HEIGHT<<1);
DWORD *tmp;
// draw world map
_RGBA *ppush;
int y,x;
ppush=pbegin;
tmp=(DWORD *)pbegin;
for(y=0;yworld[y][x].terrain_cost<<4));
DWORD d=(b<<16) | (b<<8) | b;
*tmp=d;
*(tmp+1)=d;
*(tmp+clientwidth)=d;
*(tmp+clientwidth+1)=d;
tmp+=2;
}
ppush+=(clientwidth<<1);
tmp=(DWORD *)ppush;
}
// draw all know ai routes
#ifdef DISPLAY_AIS
TCHAR szRoutes[4096];
TCHAR sztmp[128];
#endif
GetClientRect(hWnd, &rt);
int maxai=gamemode?MAX_AIS:1;
for(int a=0;acount);
#endif
int countcheck=0;
if(airoute->count>0)
{
//
int yx=airoute->startyx;
int count=airoute->count;
int position=airoute->start;
while(count--)
{
int runlength=airoute->route[position].runlength;
int route=airoute->route[position].route;
#ifdef DISPLAY_AIS
sprintf(sztmp,"%d(%d) ",route,runlength);
if(strlen(sztmp)+strlen(szRoutes)<4096-1)
strcat(szRoutes,sztmp);
#endif
while(runlength-->=0)
{
countcheck++;
tmp=(DWORD *)(pbegin+(yx>>YSHIFT)*(clientwidth<<1)+((yx&XMASK)<<1));
if(tmp>(DWORD *)pbegin && tmp<(DWORD *)pend)
{
*tmp=airoute->color;
*(tmp+1)=airoute->color;
*(tmp+clientwidth)=airoute->color;
*(tmp+clientwidth+1)=airoute->color;
}
yx+=DXY[route].yx;
};
position++;
}
}
#ifdef DISPLAY_AIS
sprintf(sztmp," = countcheck %d ",countcheck);
if(strlen(sztmp)+strlen(szRoutes)<4096-1)
strcat(szRoutes,sztmp);
rt.top=16*a;
DrawText(hdc, szRoutes, strlen(szRoutes), &rt, DT_RIGHT);
#endif
}
}
}
///////////////////////////////////////////////////////////////////////////
// TYPE A
void Dijkstra::PackRoute()
{
if(no_path)
{
airoute->count=0;
return;
}
//
airoute->start=MAX_ROUTES;
WORD yx=endyx;
int runlength;
WORD route=NO_ROUTE;
do
{
if(route==world[yx].route && runlengthroute[airoute->start].route=DXY[route].route;
airoute->route[airoute->start].runlength=runlength++;
}
else
{
runlength=0;
airoute->start--;
airoute->route[airoute->start].route=DXY[world[yx].route].route;
airoute->route[airoute->start].runlength=runlength;
}
if(yx==startyx) break;
route=world[yx].route;
yx+=DXY[route].yx;
} while(airoute->start>0 && world[yx].route!=NO_ROUTE);
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;
}
///////////////////////////////////////////////////////////////////////////
// TYPE B
void AStar::PackRoute()
{
if(no_path)
{
airoute->count=0;
return;
}
//
airoute->start=MAX_ROUTES;
WORD yx=endyx;
int runlength;
WORD route=NO_ROUTE;
do
{
if(route==world[yx].route && runlengthroute[airoute->start].route=route;
airoute->route[airoute->start].runlength=runlength++;
}
else
{
runlength=0;
airoute->start--;
airoute->route[airoute->start].route=world[yx].route;
airoute->route[airoute->start].runlength=runlength;
}
if(yx==startyx) break;
route=world[yx].route;
yx+=DXY[DXY[route].route].yx;
} while(airoute->start>0 && world[yx].route!=NO_ROUTE);
airoute->start++;
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;
}
/*
inline void AStar::movedown_heap(int k)
{
while(NOTEMPTY_DOWN(k))
{
int leftk=LEFT(k);
int rightk=RIGHT(k);
if(NOTEMPTY_DOWN(leftk) && NOTEMPTY_DOWN(rightk) )
{
if(nodes[heap[leftk]].f < nodes[heap[rightk]].f)
{
if(nodes[heap[leftk]].f < nodes[heap[k]].f)
{
swap_heap(k,leftk);
k=leftk;
}
else
break;
}
else
{
if(nodes[heap[rightk]].f < nodes[heap[k]].f)
{
swap_heap(k,rightk);
k=rightk;
}
else
break;
}
}
else if(NOTEMPTY_DOWN(leftk))
{
if(nodes[heap[leftk]].f < nodes[heap[k]].f)
{
swap_heap(k,leftk);
k=leftk;
}
else
break;
}
else
break;
}
}
*/
inline void AStar::movedown_heap(int k)
{
while(NOTEMPTY_DOWN(k))
{
int leftk=LEFT(k);
int rightk=RIGHT(k);
if(NOTEMPTY_DOWN(leftk) && NOTEMPTY_DOWN(rightk) )
{
if(nodes[heap[leftk]].f < nodes[heap[rightk]].f)
{
if(nodes[heap[leftk]].f < nodes[heap[k]].f)
{
swap_heap(k,leftk);
k=leftk;
}
else
break;
}
else
{
if(nodes[heap[rightk]].f < nodes[heap[k]].f)
{
swap_heap(k,rightk);
k=rightk;
}
else
break;
}
}
else if(NOTEMPTY_DOWN(leftk))
{
if(nodes[heap[leftk]].f < nodes[heap[k]].f)
{
swap_heap(k,leftk);
k=leftk;
}
else
break;
}
else
break;
}
}
inline void AStar::moveup_heap(int k)
{
if(!EMPTY(k))
{
int parentk=PARENT(k);
if(!EMPTY(parentk))
{
if(nodes[heap[k]].f <= nodes[heap[parentk]].f)
{
swap_heap(k,parentk);
moveup_heap(parentk);
}
}
}
}
inline void AStar::movedown_heap(int k)
{
if(!EMPTY(k))
{
register int leftk=LEFT(k);
register int rightk=RIGHT(k);
if(!EMPTY(leftk) && !EMPTY(rightk) )
{
if(nodes[heap[leftk]].f <= nodes[heap[rightk]].f)
{
if(nodes[heap[leftk]].f <= nodes[heap[k]].f)
{
swap_heap(k,leftk);
movedown_heap(leftk);
}
}
else
{
if(nodes[heap[rightk]].f <= nodes[heap[k]].f)
{
swap_heap(k,rightk);
movedown_heap(rightk);
}
}
}
else if(!EMPTY(leftk))
{
swap_heap(k,leftk);
movedown_heap(leftk);
}
}
}
--
/*
{ //backtrack
register int node=last_node;
register int index=last_index;
current_node=EMPTY_NODE;
do
{
while(open_node_index[index]==EMPTY_NODE && index>0) index--;
node=open_node_index[index];
if(node==EMPTY_NODE) break;
if(
nodes[node].open &&
nodes[node].ancestor!=EMPTY_NODE &&
nodes[node].f<=nodes[current_node].f
)
{
current_node=node;
}
} while(--index>0);
if(current_node==EMPTY_NODE) no_path=true;
}
*/
/*
{ //backtrack
register float best_f=MAX_F;
register int node=last_node;
do
{
if(nodes[node].open && nodes[node].ancestor!=EMPTY_NODE && nodes[node].f<=best_f)
{
best_f=nodes[node].f;
current_node=node;
}
} while(node--!=EMPTY_NODE);
if(node==EMPTY_NODE)
no_path=true;
}
*/
近期下载者:
相关文件:
收藏者: