findpt.h

this process is about how to get the shortest path, this process write by VC++.

#include <stdio.h>
#include <conio.h>
#include <assert.h>
#include <stdlib.h>

#define MAPMAXSIZE 300  //地图面积最大为 100x100
#define MAXINT  9000   //定义一个最大整数, 地图上任意两点距离不会超过它8192 
#define STACKSIZE 35000 //保存搜索节点的堆栈大小65536

#define tile_num(x,y) ((y)*map_w+(x))  //将 x,y 坐标转换为地图上块的编号
#define tile_x(n) ((n)%map_w)          //由块编号得出 x,y 坐标
#define tile_y(n) ((n)/map_w)
// 树结构, 比较特殊, 是从叶节点向根节点反向链接
typedef struct node *TREE;

struct node
 {int h;
  int tile;
  TREE father;
 };
typedef struct node2 *LINK;

struct node2
 { TREE node;
   int f;
   LINK next;
 };

class findpt	//
{public:
 findpt();		//构造函数
 virtual~findpt();//析构函数

 public://公有,外部可调用
 int  path[MAXINT];
 char map[MAPMAXSIZE][MAPMAXSIZE];    //地图数据
 int  map_w,map_h;                    //地图宽和高
 int  start_x,start_y,end_x,end_y;    //地点,终点坐标
//////////////////////////////////////////////////////////
 void init_queue();			// 初始化队列
 void findpath(int *path);	// 路径寻找主函数
 int  readmap();				//读地图

 private://私有,类内部使用
 LINK queue;                //保存没有处理的行走方法的节点
 TREE stack[STACKSIZE];     //保存已经处理过的节点(搜索完后释放)
 int stacktop;
 int dis_map[MAPMAXSIZE][MAPMAXSIZE];//保存搜索路径时,中间目标地最优解
///////////////////////////////////////////////////////////////////////
 void enter_queue(TREE node,int f);//待处理节点入队列,依靠对目的地估价距离插入排序
 TREE get_from_queue();//将离目的地估计最近的方案出队列
 void pop_stack();//释放栈顶节点
 void freetree();//释放申请过的所有节点
 int judge(int x,int y);//估价函数,估价x,y到目的地的距离,估计值必须保证比实际值小
 int trytile(int x,int y,TREE father);//尝试下一步移动到x,y可行否
};