clspathfinder8db.~h

最小生成树的算法范例

/*
;=============================================================================
; 名称：clsPathFinder8dB
;=============================================================================
; 描述：寻路器 A*算法实现
;=============================================================================
*/
#define VALUE_oblique_direction 14;   //斜四方向行动力价值
#define VALUE_straight_direction 10;  //正四方向行动力价值

class clsPathFinder8dB{
public:
	typePATH FindPath(clsMAP8dB &);                  //寻路主函数
private:
	clsNODE *now_point;                           //当前点的x
	vector<clsNODE *> openlist;                   //开启列表

	int get_father_d(int, int);                   //得到指定点的父方向
	int set_h(clsNODE *, clsMAP8dB &);               //计算指定点的H值
	void openlist_push(clsNODE *);                //向开启列表中添加节点
    void path_convert(typePATH *);                //将得到的最终路径进行转换
	void push_now_point_to_closelist();           //将当前点加入关闭列表
	void scan_1(clsMAP8dB &);                        //扫描1方向节点
	void scan_2(clsMAP8dB &);                        //扫描2方向节点
    void scan_3(clsMAP8dB &);                        //扫描3方向节点
	void scan_4(clsMAP8dB &);                        //扫描4方向节点
	void scan_6(clsMAP8dB &);                        //扫描6方向节点
	void scan_7(clsMAP8dB &);                        //扫描7方向节点
	void scan_8(clsMAP8dB &);                        //扫描8方向节点
	void scan_9(clsMAP8dB &);                        //扫描9方向节点
	void sort_modify(clsNODE *);                  //修改开启节点的G值后排序
	typePATH getpath(clsMAP8dB &);                   //得到最终路径
};
//-----------------------------------------------------------------------------
// 名称：FindPath
// 功能：寻路器主函数
//       需传递地图类
//-----------------------------------------------------------------------------
typePATH clsPathFinder8dB::FindPath(clsMAP8dB &map){
	//将起点加入开启列表
	map.start_point->father_d = 5;
	map.start_point->g = map.start_point->h = map.start_point->f = 0;
	openlist_push(map.start_point);
	//path_exist用来标记是否存在路径
	int path_exist = 0;
	//主循环进行寻路
	while(1){
		//如果开启列表空，则未找到路径，退出
		if(openlist.size() == 0)
			break;
		//取得F值最低点，在使用二叉堆的情况下为首位
		now_point = openlist[0];
		//将当前点加入关闭列表
		push_now_point_to_closelist();
		//如果当前点为终点，则找到路径，退出
		if(now_point == map.finish_point){
			path_exist = 1;
			break;
		}
		//扫描8个方向
		scan_1(map);
		scan_2(map);
		scan_3(map);
		scan_4(map);
		scan_6(map);
		scan_7(map);
		scan_8(map);
		scan_9(map);
	}
	typePATH Path;
	//如果路径存在就生成路径并返回路径
	if(path_exist){
		Path = getpath(map);
		path_convert(&Path);
		return Path;
	}
	return Path;
}
//-----------------------------------------------------------------------------
// 名称：sort_modify
// 功能：修改开启节点的G值后重新排序
//-----------------------------------------------------------------------------
void clsPathFinder8dB::sort_modify(clsNODE *t_point){
	clsNODE *temp_Node;
	int pos = t_point->openlist_id + 1;
	while((pos > 1) && (openlist[pos - 1]->f < openlist[pos / 2 - 1]->f)){
		temp_Node = openlist[pos - 1];
		openlist[pos - 1] = openlist[pos / 2 - 1];
		openlist[pos / 2 - 1] = temp_Node;
		openlist[pos - 1]->openlist_id = pos - 1;
		openlist[pos / 2 - 1]->openlist_id = pos / 2 - 1;
		pos /= 2;
	}
}
//-----------------------------------------------------------------------------
// 名称：path_convert
// 功能：将得到的最终路径进行转换
//-----------------------------------------------------------------------------
void clsPathFinder8dB::path_convert(typePATH *p_path){
	int i;
	typePATH temp_path;
	temp_path = *p_path;
	p_path->clear();
	for(i = temp_path.size() - 1; i >= 0; i--){
		p_path->push_back(10 - temp_path[i]);
	}
}
//-----------------------------------------------------------------------------
// 名称：getpath
// 功能：得到最终路径
//-----------------------------------------------------------------------------
typePATH clsPathFinder8dB::getpath(clsMAP8dB &map){
	typePATH path;
	int father_d;
	clsNODE *t_point = map.finish_point;
	while(1){
		father_d = t_point->father_d;
		switch(father_d){
		case 1 :
			t_point = map.mapData[t_point->x - 1][t_point->y + 1];
			break;
		case 2 :
			t_point = map.mapData[t_point->x][t_point->y + 1];
			break;
		case 3 :
			t_point = map.mapData[t_point->x + 1][t_point->y + 1];
			break;
		case 4 :
			t_point = map.mapData[t_point->x - 1][t_point->y];
			break;
		case 5:
			return path;
		case 6 :
			t_point = map.mapData[t_point->x + 1][t_point->y];
			break;
		case 7 :
			t_point = map.mapData[t_point->x - 1][t_point->y - 1];
			break;
		case 8 :
			t_point = map.mapData[t_point->x][t_point->y - 1];
			break;
		case 9 :
			t_point = map.mapData[t_point->x + 1][t_point->y - 1];
			break;
		}
		path.push_back(father_d);
	}
}
//-----------------------------------------------------------------------------
// 名称：scan_1
// 功能：扫描1方向节点
//-----------------------------------------------------------------------------
void clsPathFinder8dB::scan_1(clsMAP8dB &map){
	if(map.passable(now_point, 1)){
		clsNODE *t_point = map.mapData[now_point->x - 1][now_point->y + 1];
		if(t_point->Flag != 3){
			if(t_point->Flag != 2){
				t_point->g = now_point->g + VALUE_oblique_direction;
				t_point->h = set_h(t_point, map);
				t_point->father_d = 9;
				t_point->f = t_point->g + t_point->h;
				openlist_push(t_point);
			}
			else{
				int new_g = now_point->g + VALUE_oblique_direction;
				if(t_point->g > new_g){
					t_point->g = new_g;
					t_point->f = new_g + t_point->h;
					t_point->father_d = 9;
					sort_modify(t_point);
				}
			}
		}
	}
}
//-----------------------------------------------------------------------------
// 名称：scan_2
// 功能：扫描2方向节点
//-----------------------------------------------------------------------------
void clsPathFinder8dB::scan_2(clsMAP8dB &map){
	if(map.passable(now_point, 2)){
		clsNODE *t_point = map.mapData[now_point->x][now_point->y + 1];
		if(t_point->Flag != 3){
			if(t_point->Flag != 2){
				t_point->g = now_point->g + VALUE_straight_direction;
				t_point->h = set_h(t_point, map);
				t_point->father_d = 8;
				t_point->f = t_point->g + t_point->h;
				openlist_push(t_point);
			}
			else{
				int new_g = now_point->g + VALUE_straight_direction;
				if(t_point->g > new_g){
					t_point->g = new_g;
					t_point->f = new_g + t_point->h;
					t_point->father_d = 8;
					sort_modify(t_point);
				}
			}
		}
	}
}
//-----------------------------------------------------------------------------
// 名称：scan_3
// 功能：扫描3方向节点
//-----------------------------------------------------------------------------
void clsPathFinder8dB::scan_3(clsMAP8dB &map){
	if(map.passable(now_point, 3)){
		clsNODE *t_point = map.mapData[now_point->x + 1][now_point->y + 1];
		if(t_point->Flag != 3){
			if(t_point->Flag != 2){
				t_point->g = now_point->g + VALUE_oblique_direction;
				t_point->h = set_h(t_point, map);
				t_point->father_d = 7;
				t_point->f = t_point->g + t_point->h;
				openlist_push(t_point);
			}
			else{
				int new_g = now_point->g + VALUE_oblique_direction;
				if(t_point->g > new_g){
					t_point->g = new_g;
					t_point->f = new_g + t_point->h;
					t_point->father_d = 7;
					sort_modify(t_point);
				}
			}
		}

	}
	//int t_point_x = now_point_x - 1, t_point_y = now_point_y + 1;
}
//-----------------------------------------------------------------------------
// 名称：scan_4
// 功能：扫描1方向节点
//-----------------------------------------------------------------------------
void clsPathFinder8dB::scan_4(clsMAP8dB &map){
	if(map.passable(now_point, 4)){
		clsNODE *t_point = map.mapData[now_point->x - 1][now_point->y];
		if(t_point->Flag != 3){
			if(t_point->Flag != 2){
				t_point->g = now_point->g + VALUE_straight_direction;
				t_point->h = set_h(t_point, map);
				t_point->father_d = 6;
				t_point->f = t_point->g + t_point->h;
				openlist_push(t_point);
			}
			else{
				int new_g = now_point->g + VALUE_straight_direction;
				if(t_point->g > new_g){
					t_point->g = new_g;
					t_point->f = new_g + t_point->h;
					t_point->father_d = 6;
					sort_modify(t_point);
				}
			}
		}
	}
}
//-----------------------------------------------------------------------------
// 名称：scan_6
// 功能：扫描6方向节点
//-----------------------------------------------------------------------------
void clsPathFinder8dB::scan_6(clsMAP8dB &map){
	if(map.passable(now_point, 6)){
		clsNODE *t_point = map.mapData[now_point->x + 1][now_point->y];
		if(t_point->Flag != 3){
			if(t_point->Flag != 2){
				t_point->g = now_point->g + VALUE_straight_direction;
				t_point->h = set_h(t_point, map);
				t_point->father_d = 4;
				t_point->f = t_point->g + t_point->h;
				openlist_push(t_point);
			}
			else{
				int new_g = now_point->g + VALUE_straight_direction;
				if(t_point->g > new_g){
					t_point->g = new_g;
					t_point->f = new_g + t_point->h;
					t_point->father_d = 4;
					sort_modify(t_point);
				}
			}
		}
	}
}
//-----------------------------------------------------------------------------
// 名称：scan_7
// 功能：扫描7方向节点
//-----------------------------------------------------------------------------
void clsPathFinder8dB::scan_7(clsMAP8dB &map){
	if(map.passable(now_point, 7)){
		clsNODE *t_point = map.mapData[now_point->x - 1][now_point->y - 1];
		if(t_point->Flag != 3){
			if(t_point->Flag != 2){
				t_point->g = now_point->g + VALUE_oblique_direction;
				t_point->h = set_h(t_point, map);
				t_point->father_d = 3;
				t_point->f = t_point->g + t_point->h;
				openlist_push(t_point);
			}
			else{
				int new_g = now_point->g + VALUE_oblique_direction;
				if(t_point->g > new_g){
					t_point->g = new_g;
					t_point->f = new_g + t_point->h;
					t_point->father_d = 3;
					sort_modify(t_point);
				}
			}
		}
	}
}
//-----------------------------------------------------------------------------
// 名称：scan_8
// 功能：扫描8方向节点
//-----------------------------------------------------------------------------
void clsPathFinder8dB::scan_8(clsMAP8dB &map){
	if(map.passable(now_point, 8)){
		clsNODE *t_point = map.mapData[now_point->x][now_point->y - 1];
		if(t_point->Flag != 3){
			if(t_point->Flag != 2){
				t_point->g = now_point->g + VALUE_straight_direction;
				t_point->h = set_h(t_point, map);
				t_point->father_d = 2;
				t_point->f = t_point->g + t_point->h;
				openlist_push(t_point);
			}
			else{
				int new_g = now_point->g + VALUE_straight_direction;
				if(t_point->g > new_g){
					t_point->g = new_g;
					t_point->f = new_g + t_point->h;
					t_point->father_d = 2;
					sort_modify(t_point);
				}
			}
		}
	}
}
//-----------------------------------------------------------------------------
// 名称：scan_9
// 功能：扫描9方向节点
//-----------------------------------------------------------------------------
void clsPathFinder8dB::scan_9(clsMAP8dB &map){
	if(map.passable(now_point, 9)){
		clsNODE *t_point = map.mapData[now_point->x + 1][now_point->y - 1];
		if(t_point->Flag != 3){
			if(t_point->Flag != 2){
				t_point->g = now_point->g + VALUE_oblique_direction;
				t_point->h = set_h(t_point, map);
				t_point->father_d = 1;
				t_point->f = t_point->g + t_point->h;
				openlist_push(t_point);
			}
			else{
				int new_g = now_point->g + VALUE_oblique_direction;
				if(t_point->g > new_g){
					t_point->g = new_g;
					t_point->f = new_g + t_point->h;
					t_point->father_d = 1;
					sort_modify(t_point);
				}
			}
		}
	}
}
//-----------------------------------------------------------------------------
// 名称：set_h
// 功能：计算某点的H值，并返回
//-----------------------------------------------------------------------------
int clsPathFinder8dB::set_h(clsNODE *point, clsMAP8dB &map){
	return (abs(map.finish_point->x - point->x) + abs(map.finish_point->y - point->y)) * 10;
}
//-----------------------------------------------------------------------------
// 名称：openlist_push
// 功能：向开启列表中添加节点
//       需传递x, y, father_d, g, h
//-----------------------------------------------------------------------------
void clsPathFinder8dB::openlist_push(clsNODE *p_Node){
	clsNODE *Node, *temp_Node;
	p_Node->Flag = 2; //设置节点标记为开启列表中
	p_Node->openlist_id = openlist.size();
	openlist.push_back(p_Node);

	int pos = openlist.size();
	
	while((pos > 1) && (openlist[pos - 1]->f < openlist[pos / 2 - 1]->f)){
		temp_Node = openlist[pos - 1];
		openlist[pos - 1] = openlist[pos / 2 - 1];
		openlist[pos / 2 - 1] = temp_Node;
		openlist[pos - 1]->openlist_id = pos - 1;
		openlist[pos / 2 - 1]->openlist_id = pos / 2 - 1;
		pos /= 2;
	}
}
//-----------------------------------------------------------------------------
// 名称：push_now_point_to_closelist
// 功能：将当前点送入关闭列表
//-----------------------------------------------------------------------------
void clsPathFinder8dB::push_now_point_to_closelist(){
	clsNODE *p_tempNode;
	now_point->Flag = 3; //设置节点标记为关闭列表中
	openlist[0] = openlist[openlist.size() - 1];
	openlist[0]->openlist_id = 0;
	openlist.pop_back();
	
	int pos = 1, size = openlist.size();
	size = openlist.size();
	while(1){
		if(pos * 2 <= size && openlist[pos - 1]->f > openlist[pos * 2 - 1]->f){
			if((pos * 2 + 1 <= size && openlist[pos * 2 - 1]->f <= openlist[pos * 2]->f) || pos * 2 == size){
				p_tempNode = openlist[pos - 1];
				openlist[pos - 1] = openlist[pos * 2 - 1];
				openlist[pos * 2 - 1] = p_tempNode;
				openlist[pos - 1]->openlist_id = pos - 1;
				openlist[pos * 2 - 1]->openlist_id = pos * 2 - 1;
				pos *= 2;
				continue;
			}
		}
		if(pos * 2 + 1 <= size && openlist[pos - 1]->f > openlist[pos * 2]->f){
			p_tempNode = openlist[pos - 1];
			openlist[pos - 1] = openlist[pos * 2];
			openlist[pos * 2] = p_tempNode;
			openlist[pos - 1]->openlist_id = pos - 1;
			openlist[pos * 2]->openlist_id = pos * 2;
			pos = pos * 2 + 1;
			continue;
		}
		break;
	}
}