好久都没更新博客了。。。。。。。。这段时间主要是忙着百度之星的A*坦克大战。。。。。。。虽然成绩不理想但还是让我感到欣喜的就是学到了A*算法。。。。。。。其实A*的思想很简单。。。。就是从上下左右4个方向寻找离终点步数最少的那个节点取出来。。。。。。这里就涉及了一个排序的问题。。。。。额。。。本人数据结构学的不是很扎实所以初期写了一个A*效率太低几乎没用。。。。。。。这里发一个由我的室友杨XX的改进版。。。利用了堆排序了。。。。效率提高了很多。。。。。。征求他的同意这里将实现代码发出来。。。。大家互相学习学习:
defin.h
////////////////////////////////////
#ifndef DEFINE_H
#define DEFINE_H

#include <iomanip>
#include <iostream>

using namespace std;
#define mapwidth 15
#define mapheight 13
#define mapsize (mapwidth*mapheight)

void showpath(const int *map);
void a_find(const int *map,int size,int beginpos,int endpos);
int get_len(int beginbos,int endpos);

#endif
//////////////////////////////////////////////

heap.h堆类
////////////////////////////////
#ifndef HEAP_H
#define HEAP_H

#include<iostream>
using namespace std;

template<typename T>
class Heap
{
public:
 Heap():m_size(0),max_size(100),h(NULL),m_ismax(true){}
 ~Heap(){if(h)delete[] h;}
 inline int size(){return m_size;}
 inline bool isempty();
 inline void add(T item);
 inline bool pop(T& item);
 inline void resize(int size);
 //////////////////////////////////堆排序
 inline void build(int k);
 inline void change_compare(bool ismax=true); 

private:
 bool m_ismax;
 int m_size;
 int max_size;
 void shift(int m);
 T *h;
};

template<typename T>
void Heap<T>::change_compare(bool ismax)
{
 m_ismax=ismax;
}

template<typename T>
void Heap<T>::add(T item)
{
 if(isempty())
 {
  h=new T[max_size];
 }
 h[m_size]=item;
 m_size++;
 build(m_size); 
 if(m_size>=max_size)
  resize(max_size*2); 
}

template<typename T>
bool Heap<T>::pop(T& item)
{
 if(m_size<1)
  return false;
 item=h[0];
 h[0]=h[m_size-1];
 m_size--;
 build(m_size);
 return true;
}

template<typename T>
void Heap<T>::build(int k)
{
 k/=2;
 for(int i=k-1;i>=0;i=(i+1)/2-1)
 {
  shift(i);
  if(!i)
   break;
 }
  
 
}

template<typename T>
void Heap<T>::resize(int Size)
{
 T* t=h;
 h=new T[Size];
 max_size=Size;
 for(int i=0;i<size();i++)
  h[i]=t[i];
 delete[] t;
}

template<typename T>
bool Heap<T>::isempty()
{
 if(m_size)
  return false;
 else
  return true;
}

template<typename T>
void Heap<T>::shift(int m)
{
 int j,n=size()-1;
 T t;
 t=h[m];
 j=2*m+1;
 if(m_ismax)
 {
  while(j<=n)
  {
   if((j<n) && (h[j]<h[j+1]))
    j++;
   if(t<h[j])
   {
    h[m]=h[j];
    m=j;
    j=2*m+1;
   }
   else
    j=n+1;
  }
 }
 else
 {
  while(j<=n)
  {
   if((j<n) && (h[j]>h[j+1]))
    j++;
   if(t>h[j])
   {
    h[m]=h[j];
    m=j;
    j=2*m+1;
   }
   else
    j=n+1;
  }
 }
 h[m]=t;
}
#endif
////////////////////////////////////////////////////

open_node.h 节点类
///////////////////////////////////////////////////
#ifndef open_node_H
#define open_node_H
class open_node
{
public:
 open_node():nowpos(0),nextpos(0),score(0),from_start(0){}
 inline open_node& operator = (const open_node&);
 inline bool operator > (const open_node&);
 inline bool operator < (const open_node&);

 int nowpos;
 int nextpos;
 int score;
 int from_start;
 
};

open_node& open_node :: operator = (const open_node& node)
{
 nowpos=node.nowpos;
 nextpos=node.nextpos;
 from_start=node.from_start;
 score=node.score;
 return *this;
}

bool open_node ::operator > (const open_node& node)
{ 
 return score>node.score ? true:false;
}

bool open_node ::operator < (const open_node& node)
{
 return score<node.score ? true:false;
}
#endif
///////////////////////////////////////////////////////


find.cpp实现A*
//////////////
#include "define.h"
#include "open_node.h"
#include "heap.h"

void a_find(const int *map,int size,int beginpos,int endpos)
{
 int path[mapsize];
    int countofpath=0;
 int val=1;                //地形消耗(array)
 
 int Open_Close[mapsize]; 
 
 open_node node[mapsize];
 int countofnode=0;

 open_node node_pre;
 int iter;
 
 Heap<open_node> open_heap;
 open_heap.change_compare(false);
 
 //memcpy(Open_Close,map,sizeof(int)*mapsize);
 
 node_pre.nowpos=beginpos;
 node_pre.score=node_pre.from_start+get_len(beginpos,endpos);
 open_heap.add(node_pre);
 

 while(open_heap.size())
 { 
  countofnode++; 
  open_heap.pop(node[countofnode]);  
  
  if(node[countofnode].nowpos==endpos)
   break;
  else
  {
   Open_Close[node[countofnode].nowpos]=0;
   int up=node[countofnode].nowpos-mapwidth;
   int down=node[countofnode].nowpos+mapwidth;
   int left=node[countofnode].nowpos-1;
   int right=node[countofnode].nowpos+1;   
   //up
   if(up>=0)
   {
    if(Open_Close[up])
    {     
     node_pre.nextpos=countofnode;
     node_pre.nowpos=up; 
     node_pre.from_start=node[countofnode].from_start+val;
     node_pre.score=node_pre.from_start+get_len(node_pre.nowpos,endpos);     
     open_heap.add(node_pre);     
    }
   }
   
   //down
   if(down<mapsize)
   {
    if(Open_Close[down])
    {
     node_pre.nextpos=countofnode;
     node_pre.nowpos=down; 
     node_pre.from_start=node[countofnode].from_start+val;
     node_pre.score=node_pre.from_start+get_len(node_pre.nowpos,endpos);      
     open_heap.add(node_pre);
    }
   }
   
   //left
   if((node[countofnode].nowpos%mapwidth)!=0)
   {
    if(Open_Close[left])
    {
     node_pre.nextpos=countofnode;
     node_pre.nowpos=left; 
     node_pre.from_start=node[countofnode].from_start+val;
     node_pre.score=node_pre.from_start+get_len(node_pre.nowpos,endpos); 
     open_heap.add(node_pre);
    }
   }
   
   //right
   if((right%mapwidth)!=0)
   {
    if(Open_Close[right])
    {     
     node_pre.nextpos=countofnode;
     node_pre.nowpos=right; 
     node_pre.from_start=node[countofnode].from_start+val;
     node_pre.score=node_pre.from_start+get_len(node_pre.nowpos,endpos);     
     open_heap.add(node_pre);
    }
   }   
  }
 }
 iter=countofnode;
 while(iter)
 {
  path[countofpath++]=node[iter].nowpos;
  iter=node[iter].nextpos;
 }
 showpath(map);
 int mmp[mapsize];
 memset(mmp,0,sizeof(int)*mapsize);
 for(int i=0;i<countofpath;i++)
 {
  mmp[path[i]]=1;  
 }
 cout<<"路线："<<endl;
 for(int iy=0;iy<mapheight;iy++)
 {
  for(int ix=0;ix<mapwidth;ix++)
   cout<<setw(3)<<mmp[iy*mapwidth+ix];
  cout<<endl;
 }

 
}

int get_len(int beginpos,int endpos)
{
 int x,y;
 x=(endpos-beginpos)%mapwidth;
 x=x>0?x:-x;
 y=(endpos-beginpos)/mapwidth;
 y=y>0?y:-y;
 return x+y; 
}

void showpath(const int *mapdata)
{ 
 cout<<"原始地图："<<endl;
 for(int iy=0;iy<mapheight;iy++)
 {
  for(int ix=0;ix<mapwidth;ix++)
   cout<<setw(3)<<mapdata[iy*mapwidth+ix];
  cout<<endl;
 }
}
//////////////////////////////

main.cpp 调用
///////////////////////////////

#include"define.h"

//////////////////////////////////////////////////////////////

void main()
{
/* const int mapdata[mapsize]={
  1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,
     1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,
  1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,
  1,1,0,0,0,1,1,1,0,0,0,1,1,1,1,
  1,1,0,0,0,1,1,1,0,0,0,1,1,1,1,
  1,1,1,1,0,1,1,1,1,0,0,1,1,1,1,
  0,1,1,1,1,1,1,1,1,1,0,0,0,1,0,
  0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,
  0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,
  0,1,1,1,1,1,1,1,1,1,0,0,1,1,0,
  0,0,1,0,0,0,0,0,1,0,0,0,1,1,1,
  0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,
  0,0,0,0,0,0,0,0,0,1,1,1,1,1,1
 };
*/
 const int mapdata[mapsize]={
  2,2,2,2,0,0,0,0,0,1,1,1,1,1,1,
  1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,
  1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,
  1,1,0,0,0,1,1,1,0,0,0,1,1,1,1,
  1,1,0,0,0,1,1,1,0,0,0,1,1,1,1,
  1,1,1,1,0,1,1,1,1,0,0,1,1,1,1,
  0,1,1,1,1,1,1,1,1,1,0,0,0,1,0,
  0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,
  0,0,0,0,0,0,0,0,2,1,0,0,1,1,0,
  0,1,1,1,1,1,1,1,1,1,0,0,1,1,0,
  0,0,1,0,0,0,0,0,1,0,0,0,1,1,1,
  0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,
  0,0,0,0,0,0,0,0,0,1,1,1,1,1,1
 };

 int beginpos=0;
    int endpos=mapsize-1;

 a_find(mapdata,mapsize,beginpos,endpos);

}
/////////////////////////////////////////////
这就是A*全部实现代码。。。。。。。。。。。。最后再次感谢下我的室友杨XX给我的帮助....................
                                                                                                                                                                 记于2010年6月14日 下午