这一个小节我们说一说传说中的A×算法，其实之前也上传过类似的小件件，这里我们就去剖析一下它
毕竟在游戏程序，我们要从一点移动到另一点，并得到最短路程的轨迹，类似这种算法还有好几种，执行效率都差不多，不过大多不能得到轨迹
首先，从一点移动到另一点，最快就是直接走过去了，就像小男生爱上小女生，最好的办法就是直接走到她面前说：我爱你
不过理想状态，几乎是没有的，弯路那是必然的经过，有曲线，其实更美……
那么弯路该怎么走呢，是不是先去背景看下毛主席，再去三亚晒个太阳，再回来告诉她外面的世界好美，不，不，不……
再怎么弯的曲线，越接近直接，越好，所以步骤是：
1.向周围4个或8个方向，所有不是边界的点，记录这些点到目标的距离，从开始到这个点的距离，上一个到这里的点
2.根据两个距离和最小为标准，依次“递归”所有的点直到目标点
3.反向得到路径，就是最近的曲线路径
问：会不会到达同一个点，存在不同的距离
答：是，但是根据最近距离标准递推下去，更远距离的将被丢弃
问：递归为什么加引号
答：用队列实现堆栈，也算是递归，但是不会耗尽线程堆栈
为了，方便在推箱子中检测是否能打到某个点，我修改下代码实现不记录上一个点，加速执行
不过后来就没有使用这个功能，主要代码如下：
alpha.cpp
// ****************************************************************************************************// 文件: alpha.cpp// 注释:// A*寻路算法模块, 判断两点之间是否通行, 并得到路径和各节点的权值// 扩展不保存路径提速, 不使用Dijkstra, 参见// ****************************************************************************************************//#include <stdlib.h>#include <malloc.h>#define __LATTICE_DLL_INC_// DLL内部编译#include "api.h"// 创建一个场景, 并初始化V32API PSCENE __stdcall AlphaInit(long dwSizeX, long dwSizeY, long dwMaxCost, UINT dwFlags){PSCENE ps = (PSCENE)malloc(sizeof(SCENE));if(ps == NULL){return NULL;}V32Clear32(ps, 0, sizeof(SCENE));// memset, 自动计算DWORD数量ps->NodeCount = dwSizeX * dwSizeY;// 节点数量ps->Nodes = (PNODE)malloc(ps->NodeCount * sizeof(NODE));if(ps->Nodes == NULL){AlphaExit(ps, 0xFFFFFFFF);return NULL;}ps->Matrix = (PBYTE)malloc(ps->NodeCount * sizeof(BYTE));// 场景矩阵if(ps->Matrix == NULL){AlphaExit(ps, 0xFFFFFFFF);return NULL;}ps->Steps = (PSTEP)malloc(ps->NodeCount * sizeof(STEP));if(ps->Steps == NULL){AlphaExit(ps, 0xFFFFFFFF);return NULL;}if(dwMaxCost <= 0){dwMaxCost = dwSizeX * dwSizeY;// 相邻格子逐个走遍}ps->MaxCost = dwMaxCost * CDC_PROP_NEAR;// 最大消耗(距离值)ps->SizeY = dwSizeY;ps->SizeX = dwSizeX;ps->Flags = dwFlags;return ps;}// 编辑场景数据V32API int __stdcall AlphaEdit(PSCENE pScene, long dwPosX, long dwPosY, void *lpValue){PBYTE p;if(dwPosX < 0 && dwPosY < 0){// 读取p = pScene->Scene;if(p == NULL) p = pScene->Matrix;*(PBYTE)lpValue = p[dwPosY * pScene->SizeX + dwPosX];return 2;}if(dwPosX < 0 || dwPosY < 0){// 使用外部数据指针pScene->Scene = (PBYTE)lpValue;return 3;}// 设置字节数值if(dwPosX >= pScene->SizeX || dwPosY >= pScene->SizeY){//memcpy(pScene->Matrix, lpValue, pScene->NodeCount);return 0;}p = pScene->Scene;if(p == NULL) p = pScene->Matrix;if(lpValue == NULL){return p[dwPosY * pScene->SizeX + dwPosX];// 读取}else{p[dwPosY * pScene->SizeX + dwPosX] = *(PBYTE)lpValue;// 写入}return 1;}inline long AlphaCalc(PSTAR pStar1, PSTAR pStar2){// 直接使用坐标差和代替三角函数开方if(pStar1->X > pStar2->X){if(pStar1->Y > pStar2->Y)return (pStar1->X – pStar2->X) + (pStar1->Y – pStar2->Y);elsereturn (pStar1->X – pStar2->X) + (pStar2->Y – pStar1->Y);}else{if(pStar1->Y > pStar2->Y)return (pStar2->X – pStar1->X) + (pStar1->Y – pStar2->Y);elsereturn (pStar2->X – pStar1->X) + (pStar2->Y – pStar1->Y);}//return dX + dY;}inline void AlphaNode(PSCENE pScene, long dwIndex, long dwPrevId, long dwCost, long dwLast, long dwPosX, long dwPosY){// 开始和循环各调用一次，dwIndex在调用之后自加，初始为0if(dwIndex >= pScene->NodeCount)return;//pScene->Nodes[dwIndex].Star = *pStar;// 是否会创建临时结构体??pScene->Nodes[dwIndex].Star.X = dwPosX;pScene->Nodes[dwIndex].Star.Y = dwPosY;pScene->Nodes[dwIndex].Prev = dwPrevId;if(dwPrevId != -1)pScene->Nodes[dwIndex].Step = pScene->Nodes[dwPrevId].Step + 1;elsepScene->Nodes[dwIndex].Step = 1;pScene->Nodes[dwIndex].Cost = dwCost;pScene->Nodes[dwIndex].Last = dwLast * 10;// 每次dwLen重新计算得到格子数pScene->Nodes[dwIndex].Flags = SNF_PROP_READY;return;}inline BYTE fnAlphaUnit(PSCENE pScene, PSTAR ps){BYTE *pUnit = pScene->Scene;if(pUnit == NULL) pUnit = pScene->Matrix;return pUnit[ps->Y * pScene->SizeX + ps->X];}inline PSTEP fnAlphaStep(PSCENE pScene, PSTAR ps){return &pScene->Steps[ps->Y * pScene->SizeX + ps->X];}// 寻路指定场景V32API int __stdcall AlphaStar(PSCENE pScene, PSTAR lpStart, PSTAR lpTarget, long *pdwStep){PSTEP pStep;long lCurCost, nMaxCost;// 暂存消耗，最大列表long i, j;// temp & looping varSTAR tps, cps;// test pos, current poslong dwValue;long dwIndex = 0;long dwNode = 0;// 当前Node数long dwLoop;long dwLen;// 与终点距离// check for memory address accessableif(lpStart == NULL || lpTarget == NULL){return 0;// 始末坐标无效}dwLen = AlphaCalc(lpStart, lpTarget);// dwLen = ΔX + ΔYif(dwLen == 0){return -1;// 始末坐标相同}// zero step memory(cell prop list)V32Clear32(pScene->Steps, 0, pScene->NodeCount * sizeof(STEP));// 添加第一个点dwNode = 0;AlphaNode(pScene, dwNode, -1, 0, dwLen, lpStart->X, lpStart->Y);dwNode++;// enter loop – check around cellswhile(1){nMaxCost = pScene->MaxCost;// 不可能比这个大dwIndex = -1;for(dwLoop = 0; dwLoop < dwNode; dwLoop++){if(pScene->Nodes[dwLoop].Flags != SNF_PROP_ERROR){//找未关闭中最小路程和的点lCurCost = pScene->Nodes[dwLoop].Cost + pScene->Nodes[dwLoop].Last;if(lCurCost < nMaxCost){nMaxCost = lCurCost;// 调整最大距离dwIndex = dwLoop;// 保存节点序号//break;// 所有节点都要计算}}}if(dwIndex == -1){return -2;// there is no path exist!}cps.X = pScene->Nodes[dwIndex].Star.X;cps.Y = pScene->Nodes[dwIndex].Star.Y;if((cps.X == lpTarget->X)&&(cps.Y == lpTarget->Y)){break;// 当前点已是终点, 跳出while循环}//sprintf(szText, "select best cell:[%d,%d] for check:", cps.X, cps.Y);for(i = -1; i <= 1; i++){for(j = -1; j <= 1; j++){//if(i == 0 && j == 0) continue;// 允许走对角线，只要两个不同时为零(即不是自身)if(i == 0 && j == 0) continue;if(i != 0 && j != 0) continue;// 禁止走对角线，必有且只有一个为零{[(i & j) == 0]&&[(i | j) != 0]}tps.X = cps.X + i;tps.Y = cps.Y + j;if(tps.X < 0) continue;// 左边越界if(tps.X >= pScene->SizeX)continue;// 右边越界if(tps.Y < 0) continue;// 顶边越界if(tps.Y >= pScene->SizeY) continue;// 底边越界// 该点坐标在矩阵范围内if(fnAlphaUnit(pScene, &tps) & (BYTE)pScene->Flags){continue;// 消除特殊位以后仍然不可通行(独立程序: 仅允许空格或目标)}pStep = fnAlphaStep(pScene, &tps);switch(pStep->Flags){case SSF_PROP_UNKNOW:// it'v not been checkdwValue = pScene->Nodes[dwIndex].Cost;//if(i * j != 0)//dwValue += CDC_PROP_AWAY;// 横纵坐标都是非零, 对角//elsedwValue += CDC_PROP_NEAR;// 任何一个坐标为零, 相邻dwLen = AlphaCalc(&tps, lpTarget);//dwLen = ΔX + ΔYAlphaNode(pScene, dwNode, dwIndex, dwValue, dwLen, tps.X, tps.Y);pStep->Flags = SSF_PROP_OPENED;// open itpStep->Index = dwNode++;// sprintf(szText, "add cell:[%d,%d] for check:", tps.X, tps.Y);break;case SSF_PROP_OPENED:// this cell is validdwValue = pStep->Index;dwLen = pScene->Nodes[dwIndex].Cost;dwLen += CDC_PROP_NEAR;// 只能相邻if(dwLen < pScene->Nodes[dwValue].Cost){pScene->Nodes[dwValue].Cost = dwLen;pScene->Nodes[dwValue].Prev = dwIndex;pScene->Nodes[dwValue].Step = pScene->Nodes[dwIndex].Step + 1;//change level}//sprintf(szText, "change pID for cell:[%d,%d] to %d.", tps.X, tps.Y, nID);break;default://end if(lpOGrid[tps.X][tps.Y].State..break;}//end if((lpCell..//end if((tps.X..//end if(((i..}//next j}//next i// it will continue if any path and not at targetpStep = fnAlphaStep(pScene, &cps);pScene->Nodes[dwIndex].Flags = SNF_PROP_ERROR;pStep->Flags = SSF_PROP_CLOSED;// close it//sprintf(szText, "close cell:[%d,%d] ok.", cps.X, cps.Y);}// 函数malloc()和realloc()时间消耗大，用空间换取时间dwValue = pScene->Nodes[dwIndex].Cost + pScene->Nodes[dwIndex].Last;if(pdwStep == NULL){// 不需要结果详情return dwValue;// return cost to get here}//sprintf(szText, "best path found in cost %d.", dwValue);pScene->StarCount = pScene->Nodes[dwIndex].Step;SafeFree(pScene->Stars);// release old pathpScene->Stars = (PSTAR)malloc(pScene->StarCount * sizeof(STAR));if(pScene->Stars == NULL){return -3;// Out of memory}// …dwLoop = pScene->StarCount;*pdwStep = dwLoop;// set the stepswhile(dwLoop > 0)// it can also base on dwIndex{dwLoop–;//pScene->m_pStarPath[dwLoop].X = pScene->Nodes[dwIndex].Star.X;//pScene->m_pStarPath[dwLoop].Y = pScene->Nodes[dwIndex].Star.Y;pScene->Stars[dwLoop] = pScene->Nodes[dwIndex].Star;dwIndex = pScene->Nodes[dwIndex].Prev;// parent id//sprintf(szText, "the %d cell:[%d,%d] added to path.", i, lpRoad[i].X, lpRoad[i].Y);}return dwValue;// return cost to get here}V32API int __stdcall AlphaData(PSCENE pScene, UINT dwPropId, long dwIndex){VAR v;v.pValue = (void*)pScene;v.dwValue += dwPropId;if(dwIndex < 0){return (int)*v.plValue;// 直接定位成员}v.dwValue = *v.pdwValue;v.dwValue += dwIndex;return (int)*v.plValue;}// 销毁一个场景, 释放资源V32API int __stdcall AlphaExit(PSCENE pScene, UINT dwFlags){if(pScene){SafeFree(pScene->Stars);pScene->StarCount = 0;SafeFree(pScene->Steps);pScene->Scene = NULL;// 外部数据指针SafeFree(pScene->Matrix);SafeFree(pScene->Nodes);pScene->NodeCount = 0;free(pScene);//pScene = NULL;}return 1;}其中V32API是一个宏定义，在v32/api.h中因此依赖V32.dll
这是我的一个基础类库的基类，包括常用的C语言函数和C++封装类，还有一些宏定义
函数大多是内联汇编的裸函数，宏定义一般是快速释放内存用的，如
#define SafeDelete(p)if(p){delete p; p = NULL;}C++只是封装C函数为类，同时扩展了C++特效，比如智能指针等，，详见有关头文件
当你感到悲哀痛苦时，最好是去学些什么东西。
