vc++游戏编程指南(34页).doc

-vc+游戏编程指南-第 34 页第七章 我没有想好名字如果你只靠上面几章所讲述的知识编了个游戏，喜欢的人恐怕会不多J，为什么？因为没有人会玩一个控制不流畅而且声音效果不佳的游戏。为了在游戏中更好地管理各种输入设备，我们需要使用DirectInput。而通过使用DirectX Audio可以在游戏中实现各种更逼真的音乐效果。它们都是DirectX的重要组成部分。使用DirectInput前我们需要#include <dinput.h>并在工程中加入dinput8.lib和dxguid.lib，而使用DirectX Audio前我们需要#include <dmusici.h>并在工程中加入dsound.lib和dxguid.lib。7.1 读取键盘数据首先，我们必须创建一个DirectInput8对象Audio做多大改动），就像这样：LPDIRECTINPUT8 pInput; DirectInput8Create(GetModuleHandle(NULL), DIRECTINPUT_VERSION,IID_IDirectInput8,(void*)&pInput,NULL); 然后，我们需要创建一个DirectInput设备：LPDIRECTINPUTDEVICE8 pDev;pInput->CreateDevice(GUID_SysKeyboard, &pDev, NULL); 设置好它的数据格式：pDev->SetDataFormat(&c_dfDIKeyboard); 设置它的协作级，这里设为独占设备+前台：pDev->SetCooperativeLevel(hwnd,DISCL_EXCLUSIVE|DISCL_FOREGROUND);获取设备：pDev->Acquire();像上面那样初始化后，我们就已经把Windows对键盘的控制权剥夺了，以后的键盘消息将不会被送入消息循环，我们可以把消息循环中处理键盘消息的语句拿掉了。当然，这时我们需要在程序的适当地方，比如说在刷新游戏时，加入对键盘数据进行读取和处理的语句，就像下面的一段程序：#define KEYDOWN(key) (bufferkey & 0x80) /定义一个宏，方便处理键盘数据char buffer256; /键盘数据pDev->GetDeviceState(sizeof(buffer),(LPVOID)&buffer); /得到键盘数据if (KEYDOWN(DIK_XXX) /如果XXX键被按下（请参阅附录二） /处理之 /处理其它键哈哈，真是挺方便的。有时候真的有点怀疑DirectX是不是一种回到遥远的可爱的DOS时代的“倒退”。因为无论是DirectInput还是DirectDraw都是太像DOS下的做法了。7.2 读取鼠标数据读取鼠标数据和读取键盘数据的步骤差不多，首先也是要创建设备：pInput->CreateDevice(GUID_SysMouse, &pDev, NULL);设置数据格式：pDev->SetDataFormat(&c_dfDIMouse);设置协作级：pDev->SetCooperativeLevel(hwnd,DISCL_EXCLUSIVE | DISCL_FOREGROUND);获取设备：pDev->Acquire();那么怎样读取鼠标数据呢？如果要取得鼠标的当前状态，这样即可：DIMOUSESTATE mouse_stat; /鼠标状态/得到鼠标状态pDev->GetDeviceState(sizeof(DIMOUSESTATE),(LPVOID)&mouse_stat);得到的mouse_stat是一个DIMOUSESTATE类型的结构，它有四个成员：lX，lY，lZ和rgbButtons4。其中lX、lY和lZ分别是自上次调用此函数以来鼠标在X轴、Y轴和Z轴（滚轮）方向上移动的距离，而不是鼠标此时的坐标；其距离单位不是像素，但你完全可以把它看做以像素为单位。所以，我们需要定义两个变量mousex=0和mousey=0，然后把lX和lY累加上去即可。这样做的好处是鼠标坐标不再受屏幕的制约，而且屏幕中心的mousex和mousey值可以永远是0，不随屏幕分辨率而改变。rgbButtons是一个存储哪些鼠标键被按下的数组，我们可以这样做来读取它：/定义一个宏，方便处理鼠标数据#define MOUSEBUTTONDOWN(b) (mouse_stat.rgbButtonsb&0x80)if (MOUSEBUTTONDOWN(0) /如果左键被按下 /处理之 /处理右键(1)和中键(2)7.3 恢复和关闭DirectInput 恢复DirectInput设备就像在DirectDraw中那样，使用DirectInput的程序被最小化时DirectInput设备会出现"丢失"现象。恢复的办法很干脆：先关闭DirectInput再重新初始化即可。 关闭DirectInput关闭DirectInput也是非常简单的（SAFE_RELEASE的定义在4.8节）：pDev->Unacquire( );SAFE_RELEASE(pDev);SAFE_RELEASE(pInput);7.4 初始化和关闭DirectX Audio 初始化DirectX Audio使用DirectX Audio前，按规矩还是要先初始化。在下面的这段初始化程序中要用到三个DXAudio提供的对象：IDirectMusicLoader8、IDirectMusicPerformance8和IDirectMusicSegment8。IDirectMusicLoader8顾名思义是用来调入音乐的，IDirectMusicPerformance8可以认为是音频设备，而IDirectMusicSegment8就是代表音乐。#include <dmusici.h>IDirectMusicLoader8* pLoader= NULL;IDirectMusicPerformance8*pPerf = NULL;IDirectMusicSegment8* pSeg = NULL;CoInitialize(NULL); /初始化COMCoCreateInstance(CLSID_DirectMusicLoader, NULL, CLSCTX_INPROC, IID_IDirectMusicLoader8, (void*)&pLoader); /创建pLoader对象CoCreateInstance(CLSID_DirectMusicPerformance, NULL, CLSCTX_INPROC, IID_IDirectMusicPerformance8, (void*)&pPerf ); /创建pPerf对象pPerf->InitAudio( NULL, /这里可以是一个指向IDirectMusic*对象的指针 NULL, /这里可以是一个指向IDirectSound*对象的指针 hwnd, /窗口句柄 DMUS_APATH_SHARED_STEREOPLUSREVERB, /AudioPath类型/这里打开了立体声及混响，效果很不错 64, /音乐通道数 DMUS_AUDIOF_ALL, /使用声卡的所有特性 NULL /可以指向一个DMUS_AUDIOPARAMS对象，更详细地说明各种参数 关闭DirectX Audio关闭DXAudio还是老思路，先按节的办法停止音乐，然后Release即可：pPerf->CloseDown(); /关闭SAFE_RELEASE(pLoader); /释放对象SAFE_RELEASE(pPerf);SAFE_RELEASE(pSeg);CoUninitialize(); /停止使用COM7.5 播放MIDI和WAV音乐MIDI音乐和WAV音乐在游戏编程中经常用到。其中前者一般是用作背景音乐，而后者多是用在各种音效方面，如发射导弹等等。虽然我们可以用节的方法，但使用DXAudio可以更充分地利用硬件资源，从而实现更少的CPU占用率。方法如下： 调入MIDI和WAV文件在播放音乐之前，第一步当然是调入音乐文件：CHAR strSoundPathMAX_PATH; /存储音乐所在路径GetCurrentDirectory(MAX_PATH, strSoundPath); /得到程序所在路径strcat(strSoundPath, "Sounds"); /这里设置音乐在程序路径下的Sounds子目录WCHAR wstrSoundPathMAX_PATH; /存储UNICODE形式的路径/将路径转为UNICODE形式MultiByteToWideChar(CP_ACP, 0,strSoundPath, -1, wstrSoundPath, MAX_PATH);pLoader->SetSearchDirectory(GUID_DirectMusicAllTypes, /搜索所有支持的格式wstrSoundPath,FALSEWCHAR wstrFileNameMAX_PATH; /存储UNICODE形式的文件名/将文件名转为UNICODE形式MultiByteToWideChar(CP_ACP, 0, "a.mid", -1, wstrFileName, MAX_PATH);pLoader->LoadObjectFromFile( CLSID_DirectMusicSegment, /文件类型 IID_IDirectMusicSegment8, /目标对象类型 wstrFileName, /文件名，同样应为UNICODE形式 (LPVOID*) &pSeg /目标对象 播放MIDI和WAV文件调入完音乐之后，在适当的时候可以开始播放音乐：pSeg->SetRepeats(音乐要重复的次数); /DMUS_SEG_REPEAT_INFINITE为无限次pSeg->Download( pPerf ); /将音乐数据传给pPerfpPerf->PlaySegmentEx( pSeg, /要播放的音乐 NULL, /现在只能是NULL NULL, 0, 0, NULL, NULL, NULL /Audiopath，现在先不要管它是什么 停止播放停止播放音乐也是非常简单的：pPerf->Stop( NULL, /停止哪个通道，NULL代表所有通道 NULL, 0, /经过多少时间才停止播放 07.6 在3D空间中播放音乐我们的下一个问题是如何使音乐更逼真，最好能使音乐3D化，这将大大加强真实性。要实现这个其实也不难，首先我们要设定所谓的AudioPath，它可以指定音乐的播放方式。IDirectMusicAudioPath8* pPath; /AudioPathpPerf->CreateStandardAudioPath( /创建AudioPathDMUS_APATH_DYNAMIC_3D, /3D的64, /通道数TRUE, /是否立即激活AudioPath&pPath /要创建的AudioPath然后，我们要从AudioPath中得到一个"3D缓存"，它将存储音乐的播放位置等信息。IDirectSound3DBuffer8* pBuffer; /3D缓存pPath->GetObjectInPath(DMUS_PCHANNEL_ALL, /搜索全部通道DMUS_PATH_BUFFER, /为DirectSound 缓存0, GUID_NULL,0,IID_IDirectSound3DBuffer8, /缓存类型 (LPVOID*) &pBuffer /要创建的缓存下一步是设定音乐在3D空间的何处播放。例如：pBuffer->SetPosition( , , , DS3D_IMMEDIATE );这条指令把音乐的播放位置设为(-0.1f, 0.0f, 0.0f)，由于默认的听众位置在坐标(0, 0, 0)处，脸朝着Z轴的正方向，头朝着Y轴正方向，所以其效果将是听众的右耳听得到声音但左耳听不到声音，就像音乐是从自己的正右方发出。如果把最后一个参数设为DS3D_DEFERRED，此操作将被挂起直到调用IDirectSound3DListener8 : CommitDeferredSettings( )为止，这样可以一次处理多个设定防止反复计算。我们还可以设置音乐源的速度及其播放角度：pBuffer->SetVelocity(vx,vy,vz,DS3D_IMMEDIATE);/设置在x,y,z轴方向的速度/设置播放角度大小(度)，inncone为内角度，outcone为外角度/音乐在内角度范围内不衰减，在内外角度之间慢慢衰减，超出外角度时消失pBuffer->SetConeAngles(inncone, outcone, DS3D_IMMEDIATE);pBuffer->SetConeOrientation(x, y, z, DS3D_IMMEDIATE); /设置朝哪个方向播放那么我们如何设定听众的位置呢？可以这样：IDirectSound3DListener8* pListener;pPath->GetObjectInPath( /创建听众0,DMUS_PATH_PRIMARY_BUFFER,0, GUID_NULL,0,IID_IDirectSound3DListener8, (LPVOID*) &pListener/设置听众面向(x1,y1,z1)，头朝着(x2,y2,z2)pListener->SetOrientation(x1,y1,z1,x2,y2,z2,DS3D_IMMEDIATE);pListener->SetPosition(x,y,z,DS3D_IMMEDIATE); /听众位置pListener->SetVelocity(vx,vy,vz,DS3D_IMMEDIATE); /听众速度7.7 播放MP3音乐MIDI音乐的问题是对声卡的依赖性过大，好声卡和差声卡的播放效果实在相差太远。WAV音乐虽然绝对足够精确，但占用的空间之大不可小视。MP3恐怕是一个较好的解决方案。值得注意的是，播放MP3并不需要DirectX Audio，需要的是DirectShow。所以，我们要#include <dshow.h>，并在工程中加入strmiids.lib。 调入MP3文件下面把初始化DirectShow和调入MP3合起来说说吧。首先，我们要定义三个对象，其中IGraphBuilder*类型的可以认为是媒体播放设备，IMediaControl*类型的变量负责媒体的播放控制，而IMediaPosition*类型的变量负责媒体的播放位置设定。IGraphBuilder* pGBuilder;IMediaControl* pMControl;IMediaPosition* pMPos;CoInitialize(NULL); /初始化COM/创建各个对象CoCreateInstance(CLSID_FilterGraph, NULL,CLSCTX_INPROC, IID_IGraphBuilder, (void*)&pGBuilder);pGBuilder->QueryInterface(IID_IMediaControl, (void*)&pMControl);pGBuilder->QueryInterface(IID_IMediaPosition, (void*)&pMPos);CHAR strSoundPathMAX_PATH; /存储音乐所在路径WCHAR wstrSoundPathMAX_PATH; /存储UNICODE形式的路径GetCurrentDirectory(MAX_PATH, strSoundPath);strcat(strSoundPath, "Sounds");strcat(strSoundPath, "a.mp3"); MultiByteToWideChar(CP_ACP, 0, strSoundPath, -1,wstrSoundPath, MAX_PATH);pGBuilder->RenderFile(wstrSoundPath, NULL); /调入文件 播放MP3文件播放MP3的方法十分简单：pMPos->put_CurrentPosition(0); /移动到文件头pMControl->Run(); /播放 停止播放和释放对象最后，我们要停止播放音乐并释放各个对象：pMControl->Stop(); /停止播放/释放对象SAFE_RELEASE(pMControl);SAFE_RELEASE(pMPos);SAFE_RELEASE(pGBuilder);CoUninitialize(); /释放COM第八章 支撑游戏的基石在这一章中，我们将看看数据结构，算法和人工智能在游戏中的应用。我想每个人都知道“人工智能”这个字眼吧，但数据结构和算法是干什么的呢？说简单点，数据结构就是在程序中各种数据的组织形式，而算法就是处理这些数据的方法。Niklaus Wirth曾说过“数据结构+算法=程序”，可见其重要性。8.1 链表链表是一种灵活的数据结构，它可以说是把指针用到了极致。最简单的链表是由一个个像这样的节点组成的：struct node /节点int data; /节点数据node* next; /指向下一个节点的指针一个个链表的节点就像一节节火车车厢一样通过next指针一个接一个地连接着，当我们在链表中查找数据时，我们也要一个接一个地往下找。可以想象，在链表的任何位置添加新节点都是十分简单的，而删除链表中的某个节点时也只要把它的父节点指向它的子节点即可。正因为链表有这些特点，它被广泛地应用于各种元素的个数或是元素的排列顺序经常需要改变的场合。我们还可以使用双向链表，即再使用一个指向上一个节点的指针。这将使链表变得更加方便可以从后往前查找节点，但同时也增大了链表的大小。链表在游戏编程中有不少应用，例如组织游戏中像精灵（Sprite，指游戏中会移动的东西）这样的经常需要修改的元素。8.2 哈希表使用哈希表(Hash Table)可以大大减少查找工作的时间。举一个简单的例子，如果你要在一本字典中找某单词，那你应该怎样做呢？如果不使用哈希表，那么你似乎只能一个个找下去。当然，我们知道字典是排好序的，所以大可使用二分查找等更快的方法。但如果是职工编号等完全无序的数据呢？这时，我们需要一张哈希表。怎么建立哈希表呢？所谓哈希表，其实是一个很简单的东西，它可以说是为数据建立了一个索引。还是上面那个例子，我们首先应该通过某一个函数的变换，把字典里的所有单词变成一些尽量不相同的数。如果能做到完全不相同的话，这个函数就是一个完美的哈希函数。当然，这显然比较难。一个比较糟糕的哈希函数我们给它起个名字叫f(x) 就是按单词的头一个字母，把单词转换成0到25之间的数，就像我们平常查字典时那样。好一点的解决方案是把单词的所有字母都这样转换一下，然后再加起来，对某一个大数取模。下一步，我们建立一个大数组HashTable，它的大小要能容纳所有哈希函数的可能取值，对于f(x)，我们要开一个HashTable26。然后我们把这个数组的每一个元素都变成一个链表，把对应的单词一个接一个地放进去（其实把单词转换成数后就应该立刻把它放进数组）。此时HashTable0的内容就像这样："a"à"Aachen"à"Aalborg"à"aardvark"à现在大家看出来了吧，是的，我们只要把我们要找的单词通过f(x)转换成一个数，然后再在HashTablef(x)中查找即可。哈希函数取得越好，相同哈希函数的单词就越少，我们的查找就越快。然而不容忽视的是，数组很可能也变大了。所以哈希表是用空间换时间。关于哈希函数的选取，和如果有两个元素哈希函数值相同时的处理，现在都研究得比较多。比如说有一种办法是：在HashTablef(x)已被其它元素占据时，看看HashTableg(f(x)是否是空的，如果还不行就看HashTableg(g(f(x)，直到行为止。g(x)可以是x+1之类。显然，如果使用这种办法，HashTable的大小要比元素的个数多。这种办法避免了链表的使用，但增加了计算g(x)的花费。总之，一切要根据实际情况选择。最后给一个比较好用的Hash函数给大家吧，它能将一个单词转为一个整数：int Hashf(const char *s)int hash, i, l;hash = 0;l = strlen(s);for(i=0; i<l; i+)hash=(hv*26+si-'a')%size; /size为hash表大小return hv;8.3 快速排序最常用的算法之一是排序算法。由于对排序算法的速度要求较高，我们通常使用快速排序。其算法如下：void QuickSort(int begin, int end) /对数组a排序，start为开始排序的位置，end为排 /序结束位置，例如a10则start=0，end=9。int p=begin;int q=end;int mid=ap; /标准数int temp;while(p<q)while (ap<mid) p+; /数组左边的数小于等于标准数while (aq>mid) q-; /数组右边的数大于等于标准数if (p<=q) temp=ap;ap=aq;aq=temp; /交换ap、aq。p+; q-;if (q>begin) QuickSort(begin,q);/继续对前半部分排序if (p<end) QuickSort(p,end); /继续对后半部分排序其实快速排序的思路是不难理解的，首先在头尾设置两个指针然后向中间移动，发现两指针所指的数交换会改善排序状况则交换，如两指针到达或越过了对方那么就表明已经把数分成了两组，再递归调用自己对这两组分别实施同一过程即可。8.4 深度优先搜索下面就讲讲图的搜索算法，它们在找路和AI中都很有用。最常用的图搜索算法是深度优先搜索(DFS)和广度优先搜索(BFS)。深度优先搜索，即能走就走，若有多条路可走则按照一定的次序选择（如上下左右），但不走回头路。如果无路可走就退回。显然这种方法不一定能找到最短的路径，但它对内存的要求很小。由于与真实的找路过程有相似之处，所以可以让精灵直接按搜索的过程移动，不需任何等待。不过由于上下左右的次序太机械，精灵一开始并不是朝着最短的路线走去，所以移动路线还不够真实，特别在比较空阔的时候会容易找不到路。例如，下面的地图(黑色的格子代表墙，其它格子都是可以行走的)如果要从左上角走到右下角，深度优先搜索的次序如下(A->Z->a->o)： g g g c c g g g g g g gg g c g c c g g g g c c g g g g g g g g g g g g g g g g g g g g g g g下面就是标准的深度优先搜索程序：#include <iostream>#include <memory>using namespace std;#define SX10 /宽#define SY10 /长int dx4=0,0,-1,1; /四种移动方向对x和y坐标的影响int dy4=-1,1,0,0;char BlockSYSX= /障碍表0,1,0,0,0,0,0,0,0,0, 0,1,1,0,1,1,1,0,0,0, 0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,1,1,0,0,1,0,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,1,1,1,0,1,1,0,1,1,0,0,0,0,0,0,1,0,0,0;int MaxAct=4; /移动方向总数char TableSYSX=0; /是否已到过int Level=-1; /第几步int LevelComplete=0; /这一步的搜索是否完成int AllComplete=0; /全部搜索是否完成char Act1000=0; /每一步的移动方向，搜索1000步int x=0,y=0; /现在的x和y坐标int TargetX=9,TargetY=9; /目标x和y坐标void Test( );void Back( );int ActOK( );void main( )Tableyx=1; /做已到过标记while (!AllComplete) /是否全部搜索完Level+;LevelComplete=0; /搜索下一步while (!LevelComplete)ActLevel+; /改变移动方向if (ActOK( ) /移动方向是否合理Test( ); /测试是否已到目标LevelComplete=1; /该步搜索完成elseif (ActLevel>MaxAct) /已搜索完所有方向Back( ); /回上一步if (Level<0) /全部搜索完仍无结果LevelComplete=AllComplete=1; /退出void Test( )if (x=TargetX)&&(y=TargetY) /已到目标for (int i=0;i<=Level;i+)cout<<(int)Acti; /输出结果LevelComplete=AllComplete=1; /完成搜索int ActOK( )int tx=x+dxActLevel-1; /将到点的x坐标int ty=y+dyActLevel-1; /将到点的y坐标if (ActLevel>MaxAct) /方向错误？return 0;if (tx>=SX)|(tx<0) /x坐标出界？return 0;if (ty>=SY)|(ty<0) /y坐标出界？return 0;if (Tabletytx=1) /已到过？return 0;if (Blocktytx=1) /有障碍？return 0;x=tx;y=ty; /移动Tableyx=1; /做已到过标记return 1;void Back( )x-=dxActLevel-1-1;y-=dyActLevel-1-1; /退回原来的点Tableyx=0; /清除已到过标记ActLevel=0; /清除方向Level-; /回上一层8.5 广度优先搜索与深度优先搜索相对应的是广度优先搜索。这种方法的思路很简单，就是先搜索一步可到的点，再搜索两步可到的点.如此直到找到目标点为止。这种搜索方法显然能保证走的是最短路径，搜索速度也较快，不过对空间的占用较大。请看标准广度优先搜索程序：#include <iostream>#include <memory>using namespace std;#define SX10 /宽#define SY10 /长int dx4=0,0,-1,1; /四种移动方向对x和y坐标的影响int dy4=-1,1,0,0;char BlockSYSX= /障碍表0,1,0,0,0,0,0,0,0,0, 0,1,1,0,1,1,1,0,0,0, 0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,1,0,0,1,0,0,1,0,1,1,1,0,0,1,0,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,1,1,1,0,1,1,0,1,1,0,0,0,0,0,0,1,0,0,0;intAllComplete=0; /全部完成标志intLevelNow=1, /搜索到第几层Act, /现在的移动方向ActBefore, /现在的节点的父节点MaxAct=4, /移动方向总数ActNow, /现在的节点 tx,ty; /当前坐标intLevelFoot200 = 0, /每一层最后的节点ActHead3000 = 0; /每一个节点的父节点char AllAct3000 = 0; /每一个节点的移动方向char ActX3000 = 0, ActY3000 = 0; /按节点移动后的坐标char TableSYSX = 0; /已到过标记char TargetX=9,TargetY=9; /目标点int ActOK( );int Test( );int ActOK( )tx=ActXActBefore+dxAct-1; /将到点的x坐标ty=ActYActBefore+dyAct-1; /将到点的y坐标if (tx>=SX)|(tx<0) /x坐标出界？return 0;if (ty>=SY)|(ty<0) /y坐标出界？return 0;if (Tabletytx=1) /已到过？return 0;if (Blocktytx=1) /有障碍？return 0;return 1;int Test( )if (tx=TargetX)&&(ty=TargetY) /已到目标int act=ActNow;while (act!=0)cout<<(int)AllActact; /一步步向前推出所有移动方向act=ActHeadact; /所以输出倒了过来return 1;return 0;void main()LevelNow=1;LevelFoot1=0;LevelFoot0=-1;ActX0=0;ActY0=0;while (!AllComplete)LevelNow+; /开始搜索下一层LevelFootLevelNow=LevelFootLevelNow-1;/新一层的尾节点先设为与上一层相同for (ActBefore=LevelFootLevelNow-2+1;ActBefore<=LevelFootLevelNow-1;ActBefore+) /对上一层所有节点扩展for (Act=1;Act<=MaxAct;Act+) /尝试所有方向if (ActOK( ) && (!AllComplete) /操作可行?LevelFootLevelNow+; /移动尾指针准备加入新节点ActNow=LevelFootLevelNow; /找到加入新节点位置ActHeadActNow=ActBefore; /置头指针AllActActNow=Act; /加入新节点ActXActNow=tx;ActYActNow=ty; /存储移动后位置Tabletytx=1; /做已到过标记if (Test( ) AllComplete=1; /完成?使用DFS和BFS可解决各式各样的问题。下面就给大家出一道著名的中学生计算机竞赛题，看看你能不能较快地解决它：有三个没有刻度的桶，容量分别为3升、5升、8升。现在8升的桶是满的，你可以将水在桶中倒来倒去。例如，首先8->3，那么8升桶内将会有5升水，3升桶会被装满；然后3->5，那么3升桶将被倒空，5升桶内将有3升水。你的目标是平分这8升水，即使5升桶和8升桶内均有4升水。8.6 启发式搜索大家听过一个叫A*的东东吗？A*就是一种启发式搜索方法。当然，你没听过也不要紧，下面就讲讲启发式搜索。启发式搜索的核心是一个估价函数F(x)，扩展节点时先扩展F(x)值小的