jm_pathfinder.h

本人优化过已成功应用于公司游戏的快速巡路算法,比A*快10-100倍.

#include <vector>
using namespace std;

class JMPathFinder
{
private:
	unsigned char *map_data;
	unsigned char *temp_data;
	int map_width, map_height, map_size;
	int pos_start, pos_end;
	int step;
	int num_steps;

public:
	vector<int> path;

private:
	bool isBlock(unsigned char value){
		return (value==1 || value==2);
	}

	bool SetMarker0(int pos,vector<int> *v,int step_no){
		if (!isBlock(map_data[pos]))
		if (temp_data[pos] == 0 || temp_data[pos] > step_no)
		{
			temp_data[pos] = step_no;
			v->push_back(pos);
			if (pos == pos_start)
				return true;
		}
		return false;
	}

	bool SetMarker(int pos, vector<int> *v, bool &found){
		int up = pos - map_width, 
		down = pos + map_width,
		left = pos - 1,
		right = pos + 1;
		
		int upleft = up - 1;
		int upright= up + 1;
		int downleft=down - 1;
		int downright=down + 1;

		int step_no = step + 1;
		if (up >= 0)
			if(SetMarker0(up,v,step_no)) found = true;
/*
		if (!isBlock(map_data[up]))
		  if (temp_data[up] == 0 || temp_data[up] > step_no)
		  {
		  temp_data[up] = step_no;
		  v->push_back(up);
		  if (up == pos_start)
		  found = true;
		  }
*/
		if (down < map_size)
			if(SetMarker0(down,v,step_no)) found = true;
/*
		if (!isBlock(map_data[down]))
		  if (temp_data[down] == 0 || temp_data[down] > step_no)
		  {
		  temp_data[down] = step_no;
		  v->push_back(down);
		  if (down == pos_start)
		  found = true;
		  }
*/
		if (pos%map_width != 0) //不在左边界上
			if(SetMarker0(left,v,step_no)) found = true;
/*
		if (!isBlock(map_data[left]))
		  if (temp_data[left] == 0 || temp_data[left] > step_no)
		  {
		  temp_data[left] = step_no;
		  v->push_back(left);
		  if (left == pos_start)
		  found = true;
		  }
*/
		if (right%map_width != 0) //不在右边界上,即下一格(右边)不在左边界上
			if(SetMarker0(right,v,step_no)) found = true;
/*
		if (!isBlock(map_data[right]))
		  if (temp_data[right] == 0 || temp_data[right] > step_no)
		  {
		  temp_data[right] = step_no;
		  v->push_back(right);
		  if (right == pos_start)
		  found = true;
		  }
*/
		//左上
		if (pos%map_width != 0 && up >= 0) //不在左上边界
			if(SetMarker0(upleft,v,step_no)) found = true;
/*
		if (!isBlock(map_data[upleft]))
		  if (temp_data[upleft] == 0 || temp_data[upleft] > step_no)
		  {
		  temp_data[upleft] = step_no;
		  v->push_back(upleft);
		  if (upleft == pos_start)
			found = true;
		  }
*/

		//右上
		if (right%map_width != 0 && up >= 0) //不在右上边界
			if(SetMarker0(upright,v,step_no)) found = true;

		//左下
		if (pos%map_width != 0 && down < map_size) //不在左下边界
			if(SetMarker0(downleft,v,step_no)) found = true;

		//右下
		if (right%map_width != 0 && down < map_size) //不在右下边界
			if(SetMarker0(downright,v,step_no)) found = true;
			

			return found;
	}

	bool GetStep0(int pos,int temp_pos){
		if (!isBlock(map_data[temp_pos]))
			if (temp_data[temp_pos] != 0 && temp_data[temp_pos] < temp_data[pos])
				return true;
		return false;
	}

	int GetStep(int pos)
	{
		//上
		int temp_pos = pos - map_width;
		if (temp_pos >= 0)
			if(GetStep0(pos,temp_pos)) return temp_pos;
/*
		if (!isBlock(map_data[temp_pos]))
		  if (temp_data[temp_pos] != 0 && temp_data[temp_pos] < temp_data[pos])
		  return temp_pos;
*/
		 //下
		temp_pos = pos + map_width;
		if (temp_pos < map_size)
			if(GetStep0(pos,temp_pos)) return temp_pos;
/*
		if (!isBlock(map_data[temp_pos]))
		  if (temp_data[temp_pos] != 0 && temp_data[temp_pos] < temp_data[pos])
		  return temp_pos;
*/
		//左
		temp_pos = pos - 1;
		if (pos%map_width != 0)
			if(GetStep0(pos,temp_pos)) return temp_pos;
/*
		if (!isBlock(map_data[temp_pos]))
		  if (temp_data[temp_pos] != 0 && temp_data[temp_pos] < temp_data[pos])
		  return temp_pos;
*/
		//右
		temp_pos = pos + 1;
		if (temp_pos%map_width != 0)
			if(GetStep0(pos,temp_pos)) return temp_pos;
/*
		if (!isBlock(map_data[temp_pos]))
		  if (temp_data[temp_pos] != 0 && temp_data[temp_pos] < temp_data[pos])
		  return temp_pos;
*/

 
		//左上
		temp_pos = pos - map_width - 1;
		if ( pos%map_width != 0 && temp_pos>= 0 ) 
			if(GetStep0(pos,temp_pos)) return temp_pos;


		//右上
		temp_pos = pos - map_width + 1;
		if ( temp_pos%map_width != 0 && temp_pos>= 0 ) 
			if(GetStep0(pos,temp_pos)) return temp_pos;

		//左下
		temp_pos = pos + map_width - 1;
		if ( pos%map_width != 0 && (pos + map_width) < map_size ) 
			if(GetStep0(pos,temp_pos)) return temp_pos;


		//右下
		temp_pos = pos + map_width + 1;
		if ( temp_pos%map_width != 0 && (pos + map_width) < map_size ) 
			if(GetStep0(pos,temp_pos)) return temp_pos;
			

		return -1;
	}

public:
	JMPathFinder(unsigned char *data, int w, int h){
		temp_data = 0;
		init(data,w,h);
	}

	JMPathFinder(){
		temp_data = 0;
		init(0,0,0);
	}

	~JMPathFinder()
	{
		clear();
	}

	void clear(){
		if (temp_data)
		{
			delete[] temp_data;
			temp_data = NULL;
		}
	}
	void init(unsigned char *data, int w, int h)
	{
		map_width = w;
		map_height = h;
		map_size = w * h;
		map_data = data;
		clear();
		temp_data = new unsigned char[map_size];
		memset(temp_data, 0, map_size);
	}

	bool find(int row1, int col1, int row2 , int col2) //初始化
	{
		pos_start = row1 * map_width + col1;
		pos_end = row2 * map_width + col2;
		step = 1;
		path.resize(0, 0);
		//先在终点设标记
		memset(temp_data, 0, map_size);
		temp_data[pos_end] = 1;

		if(!SetAllMarkers()) return false;

		return true;
	}

	bool SetAllMarkers()
	{
		//是否找到了目地点
		bool found = false;
		//这里用两个向量交替存储位置值,避免对其余空白格子的多余判断
		vector<int> va, vb, *pv;
		va.assign(2*(map_width + map_height), 0);
		vb.assign(2*(map_width + map_height), 0);
		va.resize(0, 0);
		vb.resize(0, 0);
		pv = &va;
		int position;
		va.push_back(pos_end);
		//从终点处开始
		while (!found)
		{
			if (pv == &va)
			{
				while (!pv->empty())
				{
					SetMarker(pv->back(), &vb, found); //结果记录入b中
					pv->pop_back();
				}
				step++;
				//换角色,此时a为空
				pv = &vb;
				if (vb.empty()) //无可行的路径
				{
					found = true;
					return false;
				}
			}
			else
			if (pv == &vb)
			{
				while (!pv->empty())
				{
					position = pv->back();
					SetMarker(position, &va, found);
					pv->pop_back();
				}
				step++;
				//换角色,此时b为空
				pv = &va;
				if (va.empty())
				{
					return false; 
				}
			}
		}
		
		return true;
	}

	void GetNearestPath()
	{
		//从起点处开始
		int position = pos_start;
		path.resize(0, 0);
		do
		{
		position = GetStep(position);
		if (position == -1)
		{
		  abort();
		  return ;
		}
		path.push_back(position);
		if (position == pos_end)
		  break;
		}while (true);
	}
/*
void Show()
{
int i, j;
for (i=0; i<map_height; i++)
{
for (j=0; j<map_width; j++)
  printf(" %02d", temp_data[i * map_width + j]);
cout << endl;
}
}
void DrawPath()
{
vector<int>::iterator i = path.begin();
for (; i != path.end(); ++i)
{
temp_data[*i] = 99;
}
}
*/
};