by houss  2009.08.02 (update 2009.09.27)

  移植黄金岛斗地主到m8手机,是我第一次给wince平台写程序,过程中遇到了各种各样的问题,也走了很多的弯路;
  我想写这篇文章,可以使更多的人更快速的进入m8的开发队伍;

  对于一些基础问题,请遵循这样的步骤去解决:阅读m8的SDK头文件和帮助文档\使用msdn的帮助文档\网上搜索\论坛问\qq群问;

一:图像显示接口
   给m8写程序,可以使用标准的wince窗口系统和利用GDI来绘图;所以我用几天时间就让斗地主图形界面在m8上跑起来了(当然问题还有很多); 这部分代码在WIN32的环境下也可以编译运行，说明兼容性很不错;  (当然程序也可以直接继承自CMzApp\CMzWnd，代码可以简单很多);
   用GDI遇到了些性能问题;游戏使用BitBlt全屏最快只能跑到6帧;就开始尝试使用DDraw来解决; 这里我建议不要使用flip模式,兼容性不好; 也不要lock住主表面直接往里面写,这也会遇到兼容性问题;而是将游戏画面都先绘制到一个后备表面,然后->Blt到主表面;这样就能兼容所有已经公布的固件了! (成功绕过所有固件驱动bug)
   DDraw表面好像只支持RGB16(r5g6b5)模式,而不能成功启用24位或32位模式(GDI下也只能支持16位色),然而m8的屏幕是支持24位颜色数的! 如果我们的软件不去支持就有点浪费了; 我们可以使用DDraw的覆盖面(Overlay)技术来启用24位色深显示! m8的SDK为我们包装了一个简单易用的类MzDDrawOverlay,使用它就可以实现了;
   在使用DDraw和覆盖图的时候,键盘输入会是个问题:软键盘弹出来了但看不见; 我的解决办法是键盘弹出的时候切换显示到GDI模式;

二:声音播放接口
  我原来的声音播放有一套基于DirectSound技术的实现;但在m8的wince平台上却没有该组件;在网上下载了一个开源的DirectSound组件的替代实现,但播放还是有问题(乱响),没有找到原因; 最后干脆重写了声音播放模块,基于wavOut来实现了; 为了支持同时播放多个声音,需要启动不同的线程来打开(waveOutOpen)声音设备;
  游戏中m8上的声音控制键能够控制耳机的音量,但不能控制外放的音量;  m8上一直都保持一个全局的最大音量值, IMixer接口控制的是全局音量,调节该值可以控制音量,waveOutSetVolume也可以,在程序退出的时候,记得把它恢复成最大值;  其实我不建议这样做;因为万一程序出现崩溃,系统音量就得不到恢复了,影响面太广给用户带来麻烦; 我的方法是自己控制传递给wavOut的pcm数据(乘以一个系数),从而达到控制音量的目的; 用waveOutSetVolume加打开的wavOut句柄做参数应该也可以更简单的做到；

三:网络
  网络我用的TCP\IP协议的socket,
  #include <Winsock2.h>
  #pragma comment (lib, "ws2.lib")
  然后使用标准的socket那套函数,win平台使用前需要WSAStartup;
  m8上,联网前可以用QueryNetWorkStatus来查询网络链接支持情况,如果没有网络链接可以用Dial_StartGprsConnect2来打开GPRS(或EDGE)网络;
  要支持cmwap联网,需要走有代理的http协议,我就没有那么多资源来支持了;
  注意： wince上不支持recv函数的MSG_PEEK方式；

四:文件系统
  我用的c运行库那一套,fopen等等;

五:时间
  获得当前时间GetLocalTime;   启动计时器SetTimer  但他们的精度都太低了,只到秒;
获得系统重启动到现在运行了的时间GetTickCount，精度还不错;
  我建议使用mmtime那套高精度计时器: timeGetTime timeSetEvent   #pragma comment (lib, "mmTimer.lib")

六:多线程
  用的CreateThread那套函数,临界区用的CriticalSection; 都是win32标准的;

七:cab包
  0.9.0.4及以下固件不支持带压缩格式的cab安装包;
  现在用得最多的0.9.0.5固件不支持包里面含有同名文件(当然是不同文件夹);我试过先改名再利用cab的重命名安装命令也没有绕过这个bug(更高版本的固件试了可以安装);估计系统安装的时候先把所有文件解压到一个文件夹(这时重名的文件就被覆盖了);再移动到目的目录;  我的重名文件非常多,没有办法只能自己写了一个简单的文件系统: 将所有文件合并成一个文件,并保存好文件路径和其起始位置; 所有的文件读取请求都先从这个总文件里找;


八:获取固件版本号

  程序可能需要针对不同的固件进行不同的处理;
(谢谢[LBE]小饽)
PLATFORMVERSION pv[4];
    if(!SystemParametersInfo(SPI_GETPLATFORMVERSION, sizeof(pv), pv, SPIF_UpdateINIFILE))
        return FALSE;
    wsprintf(strVersion, L"%d.%d.%d.%d", pv[1].dwMajor, pv[1].dwMinor, pv[2].dwMajor, pv[2].dwMinor);

typedef struct _PLATFORMVERSION
{
    DWORD dwMajor;
    DWORD dwMinor;
}PLATFORMVERSION;

  注意: 很多不同的固件使用了相同的版本号!  这时推荐判断alarm.dll的md5值来确认固件版本;


九:  旋转屏幕用ChangeDisplaySettingsEx:  
bool rotateScreen(unsigned long dwRotaion,unsigned long& old_dwRotaion){//0 1 2 4
        DEVMODE settings;
    memset(&settings, 0, sizeof(DEVMODE));
    settings.dmSize = sizeof(DEVMODE);

    settings.dmFields = DM_DISPLAYORIENTATION;
    ChangeDisplaySettingsEx(NULL, &settings, NULL, CDS_TEST, NULL);
    old_dwRotaion = settings.dmDisplayOrientation;
        if (dwRotaion<0) return true;
    if (dwRotaion == old_dwRotaion)
        return true;

   settings.dmDisplayOrientation = dwRotaion;
   return (DISP_CHANGE_SUCCESSFUL == ChangeDisplaySettingsEx(NULL, &settings, NULL, 0, NULL));
}
  m8上横屏代码: rotateScreen(0);

十: 获取唯一机器码
    m8的SDK没有找到这样功能的API;
    也没有实现DEVICEID标准:
        #define IOCTL_HAL_GET_DEVICEID CTL_CODE(FILE_DEVICE_HAL, 21, METHOD_BUFFERED, FILE_ANY_ACCESS)
      BOOL r= KernelIoControl(IOCTL_HAL_GET_DEVICEID,0, 0,buff,nBuffSize,&dwOutBytes);
    不同机器上返回的设备ID是一串相同的字符串;
   
   可以用IMEI号来做唯一机器码标识; 下面这个代码可以获得IMEI和IMSI号
        //Ge DeviceSIMInfo   
        const int nBuffSize = MAX_PATH*2;
        char buff[nBuffSize+1]={0};
        DWORD dwOutBytes=0;

        HLINEAPP hLineApp = 0;
        HLINE hLine = 0;
        DWORD dwNumDevs;
        DWORD dwAPIVersion = TAPI_API_HIGH_VERSION;
        DWORD dwExtVersion = 0;
        DWORD dwMediaMode = LINEMEDIAMODE_DATAMODEM | LINEMEDIAMODE_INTERACTIVEVOICE;
        

        LINEINITIALIZEEXPARAMS lineInitializeExParams;
        lineInitializeExParams.dwTotalSize = sizeof(lineInitializeExParams);
        lineInitializeExParams.dwOptions =  LINEINITIALIZEEXOPTION_USEEVENT; //The application desires to use the Event Handle event notification mechanism
        LONG tapiresult = lineInitializeEx(&hLineApp, 0, 0,TEXT("SimTry"), &dwNumDevs, &dwAPIVersion,&lineInitializeExParams); //returns 0 (SUCCESS)

        LINEGENERALINFO* lineGeneralInfo = (LINEGENERALINFO*)malloc(sizeof(LINEGENERALINFO));//保存设备序列号的信息的结构体
        memset(lineGeneralInfo,0,sizeof(LINEGENERALINFO));
        lineGeneralInfo->dwTotalSize = sizeof(LINEGENERALINFO);

        bool bRes=false;
        for (DWORD dwDeviceID = 0; dwDeviceID < dwNumDevs;++dwDeviceID) {
            tapiresult = lineNegotiateExtVersion(hLineApp, dwDeviceID, dwAPIVersion, EXT_API_LOW_VERSION,EXT_API_HIGH_VERSION, &dwExtVersion); //returns 0 (SUCCESS)
            tapiresult = lineOpen(hLineApp, dwDeviceID,&hLine, dwAPIVersion, 0, 0,LINECALLPRIVILEGE_OWNER, dwMediaMode, 0);           //returns 0 (SUCCESS)
            tapiresult = lineGetGeneralInfo(hLine,lineGeneralInfo); //returns 0 (SUCCESS)
            if((tapiresult == 0) && (lineGeneralInfo->dwNeededSize > lineGeneralInfo->dwTotalSize)){
                //重新获取最新的值
                DWORD dwNeededSize = lineGeneralInfo->dwNeededSize;
                free(lineGeneralInfo);
                lineGeneralInfo = (LINEGENERALINFO*)malloc(dwNeededSize);
                lineGeneralInfo->dwTotalSize = dwNeededSize;
                tapiresult = lineGetGeneralInfo(hLine, lineGeneralInfo);
            }

            if (tapiresult==0){
                //成功 保存设备的IMEI  unicode字符串
                lstrcpy((TCHAR*)&buff[0], (TCHAR*)((char*)lineGeneralInfo+ lineGeneralInfo->dwSerialNumberOffset));
                dwOutBytes=2*lstrlen((TCHAR*)&buff[0]);
                //IMSI
                //if(lineGeneralInfo->dwSubscriberNumberSize > 2) {
                //    for(int j=0;j<(long)lineGeneralInfo->dwSubscriberNumberSize/2;j++)
                //        szIMSI[j] = *((unsigned short *)(lineGeneralInfo) + j + lineGeneralInfo->dwSubscriberNumberOffset/2);
                //}
                bRes=true;
                break;
            }
        }
        //回收资源
        free(lineGeneralInfo);
        if(hLine)
            lineClose(hLine);
        if(hLineApp)
            lineShutdown(hLineApp);

      但是,在开飞行模式的时候,调用会失败;  (注册表里也可以读取到IMEI号和设备码,但飞行模式下,好像也取不到,没有测试过)
     可以用com9的AT指令来获得IMEI和设备码,飞行模式下也没有问题了:
               HANDLE hCOM9 = CreateFile( L"COM9:" , GENERIC_READ|GENERIC_WRITE , FILE_SHARE_READ|FILE_SHARE_WRITE , NULL , OPEN_EXISTING , FILE_ATTRIBUTE_NORMAL , NULL );
            if ( hCOM9 != INVALID_HANDLE_VALUE ){
                DWORD dwBytes;
                char p = 13;//cr
                char q = 10;//lf
                WriteFile( hCOM9 , "AT+CGSN;+CGMM" , 13 , &dwBytes , NULL );
                WriteFile( hCOM9 , &p , 1 , &dwBytes , NULL );
                WriteFile( hCOM9 , &q , 1 , &dwBytes , NULL );
                Sleep(200);
                if (ReadFile( hCOM9 , buff , nBuffSize , &dwBytes , NULL )){
                    //buf中报存了4行文本(ansi字符);  第二行就是IMEI号,第三行是设备码,第四行是"OK";  (某些情况下,第二行之前可能多出一个空行(多出一个换行符13),从而变成5行!)
                }

                CloseHandle( hCOM9 );
            }



十一:其他
   ansi字符串和unicode字符串的转换可以用这组函数:MultiByteToWideChar\WideCharToMultiByte

   启动执行其他程序可以用ShellExecuteEx;  用"open"方式,我用它来调用浏览器打开一个网页

  另外,我不建议程序修改CPU的自动节能;感觉作用不大,还是让它自己管理吧;


(如果在我移植斗地主之前有这样的一篇文章,我肯定能节省至少一半的时间)
本文章做了一些修正  请参看DreamMiniOne 的一些纠正和补充

 

DreamMiniOne:

 

大侠的文章对大家帮助很多啊，不过小弟有几点想补充一下：
一:图像显示接口
如果是DIB位图的话，BitBlt确实会比较慢，如果楼主用的是SDK中的ImagingHelper，即使在GDI模式下，速度应该也是不错的。一般的兼容位图480x780，在竖屏下作一次BitBlt大概只需要6ms。

二:声音播放接口
不需要把音频数据乘以系数来调整音量，waveOutSetVolume可以针对每一个打开的音频handle独立的调节音量的大小，并且不影响系统的总音量。waveOutSetVolume的参数有点讲究，是一个32位的DWORD值，低16位代表左声道的音量，高16位代表右声道的音量，音量取值范围是0 ~ 0xFFFF，但这个数值的单位貌似是db数，所以人耳听起来音量是非线性调节的，我用的简易公式是这样的，输入参数取值范围是0~100

void SetVolume(DWORD volume)
{
        if (hWaveOut != 0)
        {
                DWORD volumeToSet = (volume <= 0) ? 0 : (0x7FFFU + (volume * (0xFFFFU - 0x7FFFU) / 100));
                MMRESULT ret = waveOutSetVolume(hWaveOut, (volumeToSet & 0xFFFF) | ((volumeToSet & 0xFFFF) << 16));
        }
}

三:网络
如果要使用CMWAP访问网络
那么socket在connect的时候，连的地址的端口就要是代理的地址和端口
然后在第一次发送请求时，返回的数据要全部照收，然后抛弃掉，再重新发送一次，返回来的数据才是正确的。我是广东的移动卡测试的，发送的是http请求。

五:时间
GetTickCount的精度是10ms，其实够用了。

打开后出现这样的格式：

[Config]
Version=1700
LangCount=2
[Language1]
0=English
1=ScheduleTask
2=...
..=...
[Language2]
0=简体中文
1=管它
2=...
..=...

[Config]节中的Version代表的是语言文件的版本，用于程序文件检查对应。此处请不要修改。LangCount表示语言总数，在修改添删语言后注意修改此处（1.7及以后版本需要，之前版本自动判断）。

[Language1]到[LanguageN]是每个语言的节，可以自己添加，数目不限制。
[LanguageN]中0代表语言名称，1代表软件名称（中文叫“管它”，英文叫“ScheduleTask”），软件名可以自行根据“计划任务”的意思翻译。从2开始到最后一个就是程序界面中用到的语言，注意序号所翻译的内容必须和给定的语言对应，字符数尽量简短。

翻译时注意：

1.用记事本保存时不要改变编码类型，也就是保持为“Unicode”编码，这样不会破坏非本地语言的保存。
2.[LanguageN]节中10到16是星期的全称，17到23是星期的简写，简写越短越好，简写不要超过2个字符。
3.如果发现有空的地方请翻译时也留空，这个是为以后新版本新增语言预留的。
4.语言按照规定翻译并保存正确后，启动主程序就会看到以下界面。 

“管它”的语言文件下载，其中已经包含English和简体中文：

Version1000:点击下载此文件

Version1700:点击下载此文件

Self-adaptive topological maps were initially inspired by modelling perception systems found in mammalian brain. A perception system involves the reception of external signals and their processing inside the nervous system. The complex mammalian skills, such as seeing and hearing seemed to bear similarity to each other in the way they worked. Namely, the primary characteristic of these systems is that neighbouring neurons encode input signals which are similar to each other. 

General idea of the SOM model  

The Self-Organizing Map (SOM) was introduced by Teuvo Kohonen in 1982. The SOM (also known as the Kohonen feature map) algorithm is one of the best known artificial neural network algorithms. In contrast to many other neural networks using supervised learning, the SOM is based on unsupervised learning.  

The SOM is quite a unique kind of neural network in the sense that it constructs a topology preserving mapping from the high-dimensional space onto map units in such a way that relative distances between data points are preserved. The map units, or neurons, usually form a two-dimensional regular lattice where the location of a map unit carries semantic information. The SOM can thus serve as a clustering tool of high-dimensional data. Because of its typical two-dimensional shape, it is also easy to visualize.  

Another important feature of the SOM is its capability to generalize. In other words, it can interpolate between previously encountered inputs  

The SOM algorithm 

The basic idea of SOM is simple yet effective. The SOM defines a mapping from high dimensional input data space onto a regular two-dimensional array of neurons. Every neuron i of the map is associated with an n-dimensional reference vector , where n denotes the dimension of the input vectors. The reference vectors together form a codebook. The neurons of the map are connected to adjacent neurons by a neighbourhood relation, which dictates the topology, or the structure, of the map. The most common topologies in use are rectangular and hexagonal.

  Map quality measures     

After the SOM has been trained, it is important to know whether it has properly adapted itself to the training data. Because it is obvious that one optimal map for the given input data must exist, several map quality measures have been proposed. Usually, the quality of the SOM is evaluated based on the mapping precision and the topology preservation.

 Mapping precision   

The mapping precision measure describes how accurately the neurons 'respond' to the given data set. For example, if the reference vector of the BMU calculated for a given testing vector xi is exactly the same xi, the error in precision is then 0. Normally, the number of data vectors exceeds the number of neurons and the precision error is thus always different from 0.  

A common measure that calculates the precision of the mapping is the average quantization error over the entire data set:  

Topology preservation  

The topology preservation measure describes how well the SOM preserves the topology of the studied data set. Unlike the mapping precision measure, it considers the structure of the map. For a strangely twisted map, the topographic error is big even if the mapping precision error is small.  

A simple method for calculating the topographic error:  

where   is 1 if the first and second BMUs of are not next to each other. Otherwise   is 0.

 Visualizing the SOM   

The SOM is easy to visualize and over the years, several visualization techniques have been devised. Due to the inherently intricate nature of the SOM, however, not one of the visualization methods discovered so far, has proven to be superior to others. At times, several different visualizations of the same SOM are needed to fully see the state of the map. From this, in can be concluded that every existing visualization method has its merits and demerits. The rest of this section provides an overview to three of them, two of which visualize the reference vectors while the remaining one visualizes the data histograms.  

Visualizing the reference vectors  

The Sammon mapping represents the SOM in much the same way as Figure 6 does. The idea is that the originally high-dimensional reference vector space is compressed into two dimensions, making the visualization of the data possible. The Sammon mapping tries to find an optimum non-linear projection for the high-dimensional data so that the resulting vectors projected onto a two-dimensional surface would still retain the same relative mutual Euclidean distances as they did in the higher dimensionality.  

Unified distance matrix, or u-matrix, is perhaps the most popular method of displaying SOMs. It represents the map as a regular grid of neurons as illustrated in Figure 9. The size and topology of the map can readily be observed from the picture where each element represents a neuron. First, when generating a u-matrix, a distance matrix between the reference vectors of adjacent neurons of two-dimensional map is formed. Then, some representation for the matrix is selected, e.g. a gray-level image. The colors in the figure have been selected so that the lighter the color between two neurons is, the smaller is the relative distance between them. 

Figure 6: The u-matrix visualization of the SOM. The map size is 12 x 8 neurons and the topology is hexagonal. The map has also been labelled.

 Visualizing the data histograms   

The purpose of a data histogram is to show how input data vectors are clustered by the SOM. The data histogram visualization shows how many vectors belong to a cluster defined by each neuron. The histogram can be generated by using a trained SOM and a data set. The BMU is searched for each data vector, after which a hit counter associated with the BMU is increased by one. There are several possible ways of visualizing the resulting histograms, one of which is shown in Figure 7.  

Figure 7: A 3D data histogram visualization. The map size is 12 x 8 neurons and the topology is hexagonal.

 Hierarchical SOMs   

The input of one SOM can be taken from the output of another. The input can also be formed of several output vectors from many SOMs. This kind of structure is referred to as a hierarchical SOM. The topmost SOM in the structure (see Figure 8) clusters the outputs and provides a means of monitoring the operations of the underlying SOMs. As the SOM hierarchy is traversed upwards, the information becomes more and more abstract.

 Figure 8: Hierarchical SOM with the BMUs indicated. The topmost SOM takes input from the outputs of the three lower level SOMs.

 Applications of SOM    

The most important practical applications of SOMs are in exploratory data analysis, pattern recognition, speech analysis, robotics, industrial and medical diagnostics, instrumentation and control. The SOM can also be applied to hundreds of other tasks where large amounts of unclassified data is available.

Download Word Document(Package Uing WinRAR):

点击下载此文件

---

 A* Pathfinding for Beginners

By Patrick Lester (Updated July 18, 2005)

The A* (pronounced A-star) algorithm can be complicated for beginners. While there are many articles on the web that explain A*, most are written for people who understand the basics already. This article is for the true beginner. 

This article does not try to be the definitive work on the subject. Instead it describes the fundamentals and prepares you to go out and read all of those other materials and understand what they are talking about. Links to some of the best are provided at the end of this article, under Further Reading.

Finally, this article is not program-specific. You should be able to adapt what's here to any computer language. As you might expect, however, I have included a link to a sample program at the end of this article. The sample package contains two versions: one in C++ and one in Blitz Basic. It also contains executables if you just want to see A* in action. 

But we are getting ahead of ourselves. Let's start at the beginning ...

Introduction: The Search Area

Let’s assume that we have someone who wants to get from point A to point B. Let’s assume that a wall separates the two points. This is illustrated below, with green being the starting point A, and red being the ending point B, and the blue filled squares being the wall in between.

The first thing you should notice is that we have divided our search area into a square grid. Simplifying the search area, as we have done here, is the first step in pathfinding. This particular method reduces our search area to a simple two dimensional array. Each item in the array represents one of the squares on the grid, and its status is recorded as walkable or unwalkable. The path is found by figuring out which squares we should take to get from A to B. Once the path is found, our person moves from the center of one square to the center of the next until the target is reached. 

These center points are called “nodes”. When you read about pathfinding elsewhere, you will often see people discussing nodes. Why not just call them squares? Because it is possible to divide up your pathfinding area into something other than squares. They could be rectangles, hexagons, triangles, or any shape, really. And the nodes could be placed anywhere within the shapes – in the center or along the edges, or anywhere else. We are using this system, however, because it is the simplest.

Starting the Search

Once we have simplified our search area into a manageable number of nodes, as we have done with the grid layout above, the next step is to conduct a search to find the shortest path. We do this by starting at point A, checking the adjacent squares, and generally searching outward until we find our target. 

We begin the search by doing the following:

1. Begin at the starting point A and add it to an “open list” of squares to be considered. The open list is kind of like a shopping list. Right now there is just one item on the list, but we will have more later. It contains squares that might fall along the path you want to take, but maybe not. Basically, this is a list of squares that need to be checked out.  
2. Look at all the reachable or walkable squares adjacent to the starting point, ignoring squares with walls, water, or other illegal terrain. Add them to the open list, too. For each of these squares, save point A as its “parent square”. This parent square stuff is important when we want to trace our path. It will be explained more later.  
3. Drop the starting square A from your open list, and add it to a “closed list” of squares that you don’t need to look at again for now.

At this point, you should have something like the following illustration. In this illustration, the dark green square in the center is your starting square. It is outlined in light blue to indicate that the square has been added to the closed list. All of the adjacent squares are now on the open list of squares to be checked, and they are outlined in light green. Each has a gray pointer that points back to its parent, which is the starting square. 

  [Figure 2]

Next, we choose one of the adjacent squares on the open list and more or less repeat the earlier process, as described below. But which square do we choose? The one with the lowest F cost.

Path Scoring

The key to determining which squares to use when figuring out the path is the following equation:

F = G + H 

where

• G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there. 
• H = the estimated movement cost to move from that given square on the grid to the final destination, point B. This is often referred to as the heuristic, which can be a bit confusing. The reason why it is called that is because it is a guess. We really don’t know the actual distance until we find the path, because all sorts of things can be in the way (walls, water, etc.). You are given one way to calculate H in this tutorial, but there are many others that you can find in other articles on the web.

Our path is generated by repeatedly going through our open list and choosing the square with the lowest F score. This process will be described in more detail a bit further in the article. First let’s look more closely at how we calculate the equation.

As described above, G is the movement cost to move from the starting point to the given square using the path generated to get there. In this example, we will assign a cost of 10 to each horizontal or vertical square moved, and a cost of 14 for a diagonal move. We use these numbers because the actual distance to move diagonally is the square root of 2 (don’t be scared), or roughly 1.414 times the cost of moving horizontally or vertically. We use 10 and 14 for simplicity’s sake. The ratio is about right, and we avoid having to calculate square roots and we avoid decimals. This isn’t just because we are dumb and don’t like math. Using whole numbers like these is a lot faster for the computer, too. As you will soon find out, pathfinding can be very slow if you don’t use short cuts like these. 

Since we are calculating the G cost along a specific path to a given square, the way to figure out the G cost of that square is to take the G cost of its parent, and then add 10 or 14 depending on whether it is diagonal or orthogonal (non-diagonal) from that parent square. The need for this method will become apparent a little further on in this example, as we get more than one square away from the starting square.

H can be estimated in a variety of ways. The method we use here is called the Manhattan method, where you calculate the total number of squares moved horizontally and vertically to reach the target square from the current square, ignoring diagonal movement, and ignoring any obstacles that may be in the way. We then multiply the total by 10, our cost for moving one square horizontally or vertically. This is (probably) called the Manhattan method because it is like calculating the number of city blocks from one place to another, where you can’t cut across the block diagonally.

Reading this description, you might guess that the heuristic is merely a rough estimate of the remaining distance between the current square and the target "as the crow flies." This isn't the case. We are actually trying to estimate the remaining distance along the path (which is usually farther). The closer our estimate is to the actual remaining distance, the faster the algorithm will be. If we overestimate this distance, however, it is not guaranteed to give us the shortest path. In such cases, we have what is called an "inadmissible heuristic."

Technically, in this example, the Manhattan method is inadmissible because it slightly overestimates the remaining distance. But we will use it anyway because it is a lot easier to understand for our purposes, and because it is only a slight overestimation. On the rare occasion when the resulting path is not the shortest possible, it will be nearly as short. Want to know more? You can find equations and additional notes on heuristics here.

F is calculated by adding G and H. The results of the first step in our search can be seen in the illustration below. The F, G, and H scores are written in each square. As is indicated in the square to the immediate right of the starting square, F is printed in the top left, G is printed in the bottom left, and H is printed in the bottom right.

   
  [Figure 3] 

So let’s look at some of these squares. In the square with the letters in it, G = 10. This is because it is just one square from the starting square in a horizontal direction. The squares immediately above, below, and to the left of the starting square all have the same G score of 10. The diagonal squares have G scores of 14. 

The H scores are calculated by estimating the Manhattan distance to the red target square, moving only horizontally and vertically and ignoring the wall that is in the way. Using this method, the square to the immediate right of the start is 3 squares from the red square, for a H score of 30. The square just above this square is 4 squares away (remember, only move horizontally and vertically) for an H score of 40. You can probably see how the H scores are calculated for the other squares. 

The F score for each square, again, is simply calculated by adding G and H together.

Continuing the Search

To continue the search, we simply choose the lowest F score square from all those that are on the open list. We then do the following with the selected square:

4) Drop it from the open list and add it to the closed list.

Small Rant 

Notes on Implementation 

1.  Other Units (collision avoidance): If you happen to look closely at my example code, you will notice that it completely ignores other units on the screen. The units pass right through each other. Depending on the game, this may be acceptable or it may not. If you want to consider other units in the pathfinding algorithm and have them move around one another, I suggest that you only consider units that are either stopped or adjacent to the pathfinding unit at the time the path is calculated, treating their current locations as unwalkable. For adjacent units that are moving, you can discourage collisions by penalizing nodes that lie along their respective paths, thereby encouraging the pathfinding unit to find an alternate route (described more under #2).

If you choose to consider other units that are moving and not adjacent to the pathfinding unit, you will need to develop a method for predicting where they will be at any given point in time so that they can be dodged properly. Otherwise you will probably end up with strange paths where units zig-zag to avoid other units that aren't there anymore.

You will also, of course, need to develop some collision detection code because no matter how good the path is at the time it is calculated, things can change over time. When a collision occurs a unit must either calculate a new path or, if the other unit is moving and it is not a head-on collision, wait for the other unit to step out of the way before proceeding with the current path.

These tips are probably enough to get you started. If you want to learn more, here are some links that you might find helpful:

• Steering Behavior for Autonomous Characters: Craig Reynold's work on steering is a bit different from pathfinding, but it can be integrated with pathfinding to make a more complete movement and collision avoidance system.
• The Long and Short of Steering in Computer Games: An interesting survey of the literature on steering and pathfinding. This is a pdf file.
• Coordinated Unit Movement: First in a two-part series of articles on formation and group-based movement by Age of Empires designer Dave Pottinger.
  
• Implementing Coordinated Movement: Second in Dave Pottinger's two-part series.

2. Variable Terrain Cost: In this tutorial and my accompanying program, terrain is just one of two things – walkable or unwalkable. But what if you have terrain that is walkable, but at a higher movement cost? Swamps, hills, stairs in a dungeon, etc. – these are all examples of terrain that is walkable, but at a higher cost than flat, open ground. Similarly, a road might have a lower movement cost than the surrounding terrain.

This problem is easily handled by adding the terrain cost in when you are calculating the G cost of any given node. Simply add a bonus cost to such nodes. The A* pathfinding algorithm is already written to find the lowest cost path and should handle this easily. In the simple example I described, when terrain is only walkable or unwalkable, A* will look for the shortest, most direct path. But in a variable-cost terrain environment, the least cost path might involve traveling a longer distance – like taking a road around a swamp rather than plowing straight through it.

An interesting additional consideration is something the professionals call “influence mapping.” Just as with the variable terrain costs described above, you could create an additional point system and apply it to paths for AI purposes. Imagine that you have a map with a bunch of units defending a pass through a mountain region. Every time the computer sends somebody on a path through that pass, it gets whacked. If you wanted, you could create an influence map that penalized nodes where lots of carnage is taking place. This would teach the computer to favor safer paths, and help it avoid dumb situations where it keeps sending troops through a particular path, just because it is shorter (but also more dangerous).

Yet another possible use is penalizing nodes that lie along the paths of nearby moving units. One of the downsides of A* is that when a group of units all try to find paths to a similar location, there is usually a significant amount of overlap, as one or more units try to take the same or similar routes to their destinations. Adding a penalty to nodes already 'claimed' by other units will help ensure a degree of separation, and reduce collisions. Don't treat such nodes as unwalkable, however, because you still want multiple units to be able to squeeze through tight passageways in single file, if necessary. Also, you should only penalize the paths of units that are near the pathfinding unit, not all paths, or you will get strange dodging behavior as units avoid paths of units that are nowhere near them at the time. Also, you should only penalize path nodes that lie along the current and future portion of a path, not previous path nodes that have already been visited and left behind.

3. Handling Unexplored Areas: Have you ever played a PC game where the computer always knows exactly what path to take, even though the map hasn't been explored yet? Depending upon the game, pathfinding that is too good can be unrealistic. Fortunately, this is a problem that is can be handled fairly easily.

The answer is to create a separate "knownWalkability" array for each of the various players and computer opponents (each player, not each unit -- that would require a lot more computer memory). Each array would contain information about the areas that the player has explored, with the rest of the map assumed to be walkable until proven otherwise. Using this approach, units will wander down dead ends and make similar wrong choices until they have learned their way around. Once the map is explored, however, pathfinding would work normally.

4. Smoother Paths: While A* will automatically give you the shortest, lowest cost path, it won't automatically give you the smoothest looking path. Take a look at the final path calculated in our example (in Figure 7). On that path, the very first step is below, and to the right of the starting square. Wouldn't our path be smoother if the first step was instead the square directly below the starting square?

There are several ways to address this problem. While you are calculating the path you could penalize nodes where there is a change of direction, adding a penalty to their G scores. Alternatively, you could run through your path after it is calculated, looking for places where choosing an adjacent node would give you a path that looks better. For more on the whole issue, check out Toward More Realistic Pathfinding, a (free, but registration required) article at Gamasutra.com by Marco Pinter.

5. Non-square Search Areas: In our example, we used a simple 2D square layout. You don't need to use this approach. You could use irregularly shaped areas. Think of the board game Risk, and the countries in that game. You could devise a pathfinding scenario for a game like that. To do this, you would need to create a table for storing which countries are adjacent to which, and a G cost associated with moving from one country to the next. You would also need to come up with a method for estimating H. Everything else would be handled the same as in the above example. Instead of using adjacent squares, you would simply look up the adjacent countries in the table when adding new items to your open list.

Similarly, you could create a waypoint system for paths on a fixed terrain map. Waypoints are commonly traversed points on a path, perhaps on a road or key tunnel in a dungeon. As the game designer, you could pre-assign these waypoints. Two waypoints would be considered "adjacent" to one another if there were no obstacles on the direct line path between them. As in the Risk example, you would save this adjacency information in a lookup table of some kind and use it when generating your new open list items. You would then record the associated G costs (perhaps by using the direct line distance between the nodes) and H costs (perhaps using a direct line distance from the node to the goal). Everything else would proceed as usual.

Amit Patel has written a brief article delving into some alternatives. For another example of searching on an isometric RPG map using a non-square search area, check out my article Two-Tiered A* Pathfinding.

6. Some Speed Tips: As you develop your own A* program, or adapt the one I wrote, you will eventually find that pathfinding is using a hefty chunk of your CPU time, particularly if you have a decent number of pathfinding units on the board and a reasonably large map. If you read the stuff on the net, you will find that this is true even for the professionals who design games like Starcraft or Age of Empires. If you see things start to slow down due to pathfinding, here are some ideas that may speed things up: 

• Consider a smaller map or fewer units.
• Never do path finding for more than a few units at a time. Instead put them in a queue and spread them out over several game cycles. If your game is running at, say, 40 cycles per second, no one will ever notice. But they will notice if the game seems to slow down every once in a while when a bunch of units are all calculating paths at the same time.
• Consider using larger squares (or whatever shape you are using) for your map. This reduces the total number of nodes searched to find the path. If you are ambitious, you can devise two or more pathfinding systems that are used in different situations, depending upon the length of the path. This is what the professionals do, using large areas for long paths, and then switching to finer searches using smaller squares/areas when you get close to the target. If you are interested in this concept, check out my article Two-Tiered A* Pathfinding.
• For longer paths, consider devising precalculated paths that are hardwired into the game.
• Consider pre-processing your map to figure out what areas are inaccessible from the rest of the map. I call these areas "islands." In reality, they can be islands or any other area that is otherwise walled off and inaccessible. One of the downsides of A* is that if you tell it to look for paths to such areas, it will search the whole map, stopping only when every accessible square/node has been processed through the open and closed lists. That can waste a lot of CPU time. It can be prevented by predetermining which areas are inaccessible (via a flood-fill or similar routine), recording that information in an array of some kind, and then checking it before beginning a path search.
• In a crowded, maze-like environment, consider tagging nodes that don't lead anywhere as dead ends. Such areas can be manually pre-designated in your map editor or, if you are ambitious, you could develop an algorithm to identify such areas automatically. Any collection of nodes in a given dead end area could be given a unique identifying number. Then you could safely ignore all dead ends when pathfinding, pausing only to consider nodes in a dead end area if the starting location or destination happen to be in the particular dead end area in question.

7. Maintaining the Open List: This is actually one of the most time consuming elements of the A* pathfinding algorithm. Every time you access the open list, you need to find the square that has the lowest F cost. There are several ways you could do this. You could save the path items as needed, and simply go through the whole list each time you need to find the lowest F cost square. This is simple, but really slow for long paths. This can be improved by maintaining a sorted list and simply grabbing the first item off the list every time you need the lowest F-cost square. When I wrote my program, this was the first method I used.

This will work reasonably well for small maps, but it isn’t the fastest solution. Serious A* programmers who want real speed use something called a binary heap, and this is what I use in my code. In my experience, this approach will be at least 2-3 times as fast in most situations, and geometrically faster (10+ times as fast) on longer paths. If you are motivated to find out more about binary heaps, check out my article, Using Binary Heaps in A* Pathfinding.

Another possible bottleneck is the way you clear and maintain your data structures between pathfinding calls. I personally prefer to store everything in arrays. While nodes can be generated, recorded and maintained in a dynamic, object-oriented manner, I find that the amount of time needed to create and delete such objects adds an extra, unnecessary level of overhead that slows things down. If you use arrays, however, you will need to clean things up between calls. The last thing you will want to do in such cases is spend time zero-ing everything out after a pathfinding call, especially if you have a large map.

I avoid this overhead by creating a 2d array called whichList(x,y) that designates each node on my map as either on the open list or closed list. After pathfinding attempts, I do not zero out this array. Instead I reset the values of onClosedList and onOpenList in every pathfinding call, incrementing both by +5 or something similar on each path finding attempt. This way, the algorithm can safely ignore as garbage any data left over from previous pathfinding attempts. I also store values like F, G and H costs in arrays. In this case, I simply write over any pre-existing values and don't bother clearing the arrays when I'm done.

Storing data in multiple arrays consumes more memory, though, so there is a trade off. Ultimately, you should use whatever method you are most comfortable with.

8. Dijkstra's Algorithm: While A* is generally considered to be the best pathfinding algorithm (see rant above), there is at least one other algorithm that has its uses - Dijkstra's algorithm. Dijkstra's is essentially the same as A*, except there is no heuristic (H is always 0). Because it has no heuristic, it searches by expanding out equally in every direction. As you might imagine, because of this Dijkstra's usually ends up exploring a much larger area before the target is found. This generally makes it slower than A*.

So why use it? Sometimes we don't know where our target destination is. Say you have a resource-gathering unit that needs to go get some resources of some kind. It may know where several resource areas are, but it wants to go to the closest one. Here, Dijkstra's is better than A* because we don't know which one is closest. Our only alternative is to repeatedly use A* to find the distance to each one, and then choose that path. There are probably countless similar situations where we know the kind of location we might be searching for, want to find the closest one, but not know where it is or which one might be closest.

Further Reading

Okay, now you have the basics and a sense of some of the advanced concepts. At this point, I’d suggest wading into my source code. The package contains two versions, one in C++ and one in Blitz Basic. Both versions are heavily commented and should be fairly easy to follow, relatively speaking.  Here is the link.

• Sample Code: A* Pathfinder (2D) Version 1.9

If you do not have access to C++ or Blitz Basic, two small exe files can be found in the C++ version. The Blitz Basic version can be run by downloading the free demo version of Blitz Basic 3D (not Blitz Plus) at the Blitz Basic web site.

You should also consider reading through the following web pages. They should be much easier to understand now that you have read this tutorial.

• Amit’s A* Pages: This is a very widely referenced page by Amit Patel, but it can be a bit confusing if you haven’t read this article first. Well worth checking out. See especially Amit's own thoughts on the topic.
• Smart Moves: Intelligent Path Finding: This article by Bryan Stout at Gamasutra.com requires registration to read. The registration is free and well worth it just to reach this article, much less the other resources that are available there. The program written in Delphi by Bryan helped me learn A*, and it is the inspiration behind my A* program. It also describes some alternatives to A*.
• Terrain Analysis: This is an advanced, but interesting, article by Dave Pottinger, a professional at Ensemble Studios. This guy coordinated the development of Age of Empires and Age of Kings. Don’t expect to understand everything here, but it is an interesting article that might give you some ideas of your own. It includes some discussion of mip-mapping, influence mapping, and some other advanced AI/pathfinding concepts.

Some other sites worth checking out:

• aiGuru: Pathfinding
• Game AI Resource: Pathfinding
• GameDev.net: Pathfinding

I also highly recommend the following books, which have a bunch of articles on pathfinding and other AI topics. They also have CDs with sample code. I own them both. Plus, if you buy them from Amazon through these links, I'll get a few pennies from Amazon. :)

Well, that’s it. If you happen to write a program that uses any of these concepts, I’d love to see it. I can be reached at 

Until then, good luck!