A星寻路C++ Flascc技术实现

#include "astar.h" const int AStar::STRAIGHT = 10; const int AStar::SLANT = 14; void writeInt(char* &bytes,int value){ bytes[0] = (value >> 24) & 0xFF; bytes[1] = (value >> 16) & 0xFF; bytes[2] = (value >> 8) & 0xFF; bytes[3] = value & 0xFF; bytes+=4; } int readInt(char* &bytes){ int re=(( bytes[0] & 0xFF) << 24) | ((bytes[1] & 0xFF) << 16) | ((bytes[2] & 0xFF) << 8) | (bytes[3] & 0xFF); bytes+=4; return re; } void writeBoolean(char* &bytes,bool value){ bytes[0] = value; bytes+=1; } void writeInt8(char* &bytes,int value){ bytes[0] = value; bytes+=1; } bool readBoolean(char* &bytes){ bool re=bytes[0]; bytes+=1; return re; } bool AStar::isBlockPoint(int _x, int _y) { int x=_x/tileSize; int y=_y/tileSize; if (x >= col || x < 0 || y < 0 || y >= row ) { return true; } return blockValue[y][x]>0; } bool AStar::isBlock(int x, int y){ return blockValue[y][x]>0; } WayPoint AStar::findAroundWayPoint(int _x,int _y,int _time){ int x=_x/tileSize; int y=_y/tileSize; DynamicBitset finded; finded.clear(); finded.resize(tileCount); if (x >= col) { x =col - 1; }else if (x <0) { x = 0; } if (y >=row) { y = row - 1; }else if (y <0) { y = 0; } list<WayPoint> list; list.push_back(WayPoint(x,y)); int n=0; while (list.size()>0) { WayPoint point= list.front(); list.pop_front(); int tx = point.x_pos; int ty = point.y_pos; if (tx >= col || tx < 0 || ty < 0 || ty >= row) { continue; } if(finded.test(ty*col+tx)){ continue; } if(_time!=-1&&n>_time){ break; } n++; finded.set(ty*col+tx); if (!isBlock(tx,ty)) { return WayPoint(tx*tileSize,ty*tileSize); }else { list.push_back(WayPoint(tx + 1,ty - 1) ); list.push_back(WayPoint(tx + 1,ty ) ); list.push_back(WayPoint(tx + 1,ty + 1 ) ); list.push_back(WayPoint(tx,ty + 1 ) ); list.push_back(WayPoint(tx - 1,ty + 1 ) ); list.push_back(WayPoint(tx - 1,ty ) ); list.push_back(WayPoint(tx - 1,ty - 1 ) ); list.push_back(WayPoint(tx,ty - 1 ) ); } } return WayPoint(-1,-1); } Way AStar::findWay(int _startx,int _starty,int _endx,int _endy) { /* * 0正常查询 * 1 未初始化 * 2开始点与结束点距离为0 * 3开始点与结束点为障碍点上 * 4没有路径 * 5地图之外 * */ if(tileCount==0){ return Way(1); } int start_x = _startx / tileSize; int start_y = _starty / tileSize; int end_x = _endx / tileSize; int end_y = _endy / tileSize; // 检查距离 if (end_y == start_y && end_x == start_x) { return Way(2); } // 是否在范围里 if (start_x >= col || start_x < 0 || start_y < 0 || start_y >= row || end_y >= col || end_x < 0 || end_y < 0 || end_y >= row) { return Way(5); } // 开始点或结束点是否在障碍物上 if (isBlock(end_x,end_y) || isBlock(start_x,start_y)) { return Way(3); } openList=new Heap(); openExistList.clear(); openExistList.resize(tileCount); AStarMark* mark=new AStarMark(start_x, start_y); openList->addItem(mark); int n = 0; int ix = start_x; int iy=start_y; list<WayPoint> way_points; while(n<tileCount) { n++; addOpenList(end_x, end_y, ix + 1, iy - 1, true , mark); addOpenList(end_x, end_y, ix + 1, iy + 1, true , mark); addOpenList(end_x, end_y, ix - 1, iy + 1, true , mark); addOpenList(end_x, end_y, ix - 1, iy - 1, true , mark); addOpenList(end_x, end_y, ix , iy - 1, false, mark); addOpenList(end_x, end_y, ix + 1, iy , false, mark); addOpenList(end_x, end_y, ix , iy + 1, false, mark); addOpenList(end_x, end_y, ix - 1, iy , false, mark); // 如果开启标记列表为空，则表示目标无法到达。 if(openList->isEmpty()){ break; } // 从开启标记列表中拿取路径评分F最小的节点标记。 mark=openList->pop(); ix = mark->x; iy = mark->y; if (end_x == ix && end_y == iy) { way_points.push_front(WayPoint(_endx,_endy)); mark = mark->parent; int i=1; while (mark != 0) { if (i%curStep == 0) { way_points.push_front(WayPoint(mark->x*tileSize, mark->y*tileSize)); } mark = mark->parent; ++i; } break; } } delete openList; return Way(way_points,way_points.size()==0?4:0); } void AStar::addOpenList( int end_x,int end_y,int posX,int posY,bool isSlant,AStarMark* mark){ if (posY<0 || posY>=row || posX<0 || posX>=col) { return; } if(isBlock(posX,posY)){ return; } if(openExistList.test(posY*col+posX)){ return; } // 是否是斜着走，如果是接下来判断左右或上下是否为障碍。 if (isSlant) { if (isBlock(posX,mark->y) || isBlock(mark->x,posY)) { return; } } // 获取当前位置到目标位置X和Y上的距离。 AStarMark* newMark= new AStarMark(posX, posY, mark, (isSlant ? SLANT : STRAIGHT), (abs(end_x - posX) + abs(posY - end_y)) * STRAIGHT); openList->addItem(newMark); openExistList.set(posX+posY*col); } void AStar::retriveBlockValue(char* &out,int &len){ int bcount=ceil(tileCount/8.0); char *v=new char[bcount]; out=v; len=bcount; memset(v,0,bcount); for (int i=0; i < row; i++) { for (int j = 0; j < col; j++) { int pos=i*col+j; int k=pos/8; int offset=pos%8; if(blockValue[i][j]!=0){ v[k]=v[k]|128>>offset; } } } } int AStar::getBlockRow(){ return row; } int AStar::getBlockCol(){ return col; } int AStar::getBlockTileSize(){ return tileSize; } void AStar::setBlockData(int _row,int _col,int _tileSize,char* _value){ row=_row; col=_col; tileSize=_tileSize; tileCount=row*col; openExistList.clear(); openExistList.resize(tileCount); blockValue.clear(); blockValue.resize(row); for (int i=0; i < row; i++) { vector<unsigned char> rows; rows.resize(col); blockValue[i]=rows; for (int j = 0; j < col; j++) { int pos=i*col+j; int v=_value[pos/8]; int offset=pos%8; v=v&128>>offset; if(v!=0){ blockValue[i][j]=1; }else{ blockValue[i][j]=0; } } } delete[] _value; } UpdateBlockResult AStar::addBlockData(int _startx,int _starty,int _row,int _col,char* _value){ int top =_row; int bottom = 0; int right = 0; int left = _col; vector<int> refline; refline.resize(_col,-1); int pos=-1; for (int i=0;i<_row; i++) { for (int j =0; j < _col; j++) { int ri=i+_starty; int rj=j+_startx; if(ri>0&&ri<row&&rj>0&&rj<col){ pos=i*_col+j; int v=_value[pos/8]; int offset=pos%8; v=v&128>>offset; if(v!=0){ blockValue[ri][rj]++; if(refline[j]==-1){ refline[j]=i; } if (top>i) { top = i; } if (left>j) { left = j; } if (bottom<i) { bottom = i; } if (right<j) { right = j; } } } } } if(pos==-1){ top=0; left=0; } int bid=createUpdateBlockId(); UpdateBlock* updateBlock=new UpdateBlock(bid,_startx,_starty,_row,_col,_value); updateBolcks.push_back(updateBlock); return UpdateBlockResult(bid,top,left,right,bottom,refline); } int AStar::createUpdateBlockId(){ int vid=0; while(true){ list<UpdateBlock*>::iterator it; bool find=false; for ( it=updateBolcks.begin() ; it != updateBolcks.end(); it++ ){ if((*it)->id==vid){ find=true; break; } } if(!find){ break; } vid++; } return vid; } UpdateBlock* AStar::getUpdateBlock(int bid){ list<UpdateBlock*>::iterator it; for ( it=updateBolcks.begin() ; it != updateBolcks.end(); it++ ){ if((*it)->id==bid){ return *it; } } return 0; } void AStar::removeBlockData(int bid){ UpdateBlock* updateBlock=getUpdateBlock(bid); if(update