astarfindpath.h

用A形算法寻找迷宫的最短路径,VC实现,非常值得一看

// AStarFindPath.h: interface for the AStarFindPath class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_ASTARFINDPATH_H__847FD17A_85D8_44E6_8247_FB980A8FDB5B__INCLUDED_)
#define AFX_ASTARFINDPATH_H__847FD17A_85D8_44E6_8247_FB980A8FDB5B__INCLUDED_

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#define TILESIZE 1  // change this also to reflect tile size. 64x64.

struct NODE {     // node structure
	double f, h;
	int g;
	int x, y;
	int NodeNum;
	NODE *Parent;
	NODE *Child[8]; // a node may have upto 8+(NULL) children.
	NODE *NextNode;  // for filing purposes
};
struct STACK {      // stack structure
	NODE *NodePtr;
	STACK *NextStackPtr;
};

class AStarFindPath  
{
private:
	NODE *OPEN;    // the node list pointers
	NODE *CLOSED;
	NODE *PATH; // pointer to the best path
	STACK *Stack; 
	int ROWS, // tilemap data members, need to be initialisize
		COLS,         // with current map's width and height
		TOTAL_TILES; // to allocate memory for the
	BYTE *TileMap;  // pointer to the A* own tilemap data array
public:
	int NodeGetY(void);
	int NodeGetX(void);
	BOOL PathNextNode(void);
	NODE* Pop(void);
	void Push(NODE *Node);
	void PropagateDown(NODE *Old);
	void Insert(NODE *Successor);
	NODE* CheckCLOSED(int tilenum);
	NODE* CheckOPEN(int tilenum);
	void GenerateSucc(NODE *BestNode,int x, int y, int sx, int sy);
	void GenerateSuccessors(NODE *BestNode, int sx, int sy);
	NODE * ReturnBestNode(void);
	void FindPath(int sx, int sy, int dx, int dy);
	void FreeNodes(void);
	int FreeTile(int x, int y);// returns 1 = true if we can move on it
	int TileNum(int x, int y);// returns tilenum
	BOOL ReachedGoal(void);
	BOOL NewPath(int sx,int sy, int dx,int dy);
	void InitAstarTileMap(BYTE *pMap, int w,int h);
	AStarFindPath();
	virtual ~AStarFindPath();
};

#endif // !defined(AFX_ASTARFINDPATH_H__847FD17A_85D8_44E6_8247_FB980A8FDB5B__INCLUDED_)