Silverlight MMORPG网页游戏开发课程[一期] 第七课：场景之地形与寻径
时间：2010-09-20 来源：深蓝色右手
在上一课实现场景遮挡效果的基础上如能有机的融合相应的地形系统，那么整个场景才能算做是个有机整体。传统的2D-RPG游戏场景按视角划分可分为横向、直角(垂直横纵)与斜向的，本节我将分别向大家介绍如何搭建基于直角坐标系及斜视角的RPG游戏场景，并在此基础上实现精灵的完美寻径功能。
7.1基于直角坐标系之场景与寻径实现 (交叉参考：传说中的A*寻径算法 完美实现A*寻径动态动画 2D游戏角色在地图上的移动 第一部分拓展小结篇 地图编辑器诞生啦！ 地图编辑器的初步使用)
2）A*算法对于初学者来说比较复杂，网上有关于它非常详细的算法原理介绍；本课程以通过Silverlight快速开发网页RPG游戏为目的，因此我不会再对该算法的实现进行讲解。感兴趣的同学可以在课后自行研究或重新编写。
言归正传，我们首先在Logic类库中新建一个名为Algorithm的文件夹，以及在该文件夹下再新建一个名为AStar的文件夹后将A*算法源码添加进AStar文件夹中。
接下来我需要对该A*算法在游戏中的使用稍做些简单说明。
核心使用代码类似如下：
3）为寻路对象pathFinderFast设置寻路参数，其中最重要的有4个：Formula（A*具体算法类型）、Diagonals（是否允许斜向取径）、HeuristicEstimate（智能化）、SearchLimit（寻路次数上限）。建议大家对这4个参数分别变换不同值测试下，然后进行对比分析从而深刻理解它们在不同场合的应用及适用情况。
4）开始寻路pathFinderFast.FindPath(起点,终点)。
5）寻路结果为一个List<PathFinderNode> 节点表，最后判断该节点表中是否存在节点，若>1的话则可编写相关逻辑引导精灵按节点表的逆序顺次移动(即节点表的最后一个节点是才是寻路的起点)。
将该配置文件中对应的参数复制到场景的Info.xml配置文件中(命名稍微改动了下)：
代码
<?xml version="1.0" encoding="utf-8" ?>
代码
<Scene FullName="龙门镇" MapWidth="3200" MapHeight="1320" TerrainGridSize="10" TerrainMatrixDimension="512" Terrain="298_0,299_0,300_0,301_0,302_0,303_0,304_0,305_0,306_0,307_0,297_1,298_1,307_1,296_2,297_2,305_2,306_2,307_2,295_3,296_3,304_3,305_3,294_4,295_4,303_4,304_4,293_5,294_5,302_5,303_5,292_6,293_6,301_6,302_6,292_7,301_7,292_8,300_8,301_8,291_9,292_9,299_9,300_9,291_10,299_10,290_11,291_11,299_11,145_12,146_12,147_12,148_12,149_12,150_12,151_12,152_12,153_12,186_12,187_12,188_12,189_12,289_12,290_12,299_12,144_13,145_13,153_13,184_13,185_13,186_13,189_13,190_13,289_13,299_13,138_14,139_14,140_14,141_14,142_14,143_14,144_14,153_14,184_14,190_14,191_14,192_14,......">
<Masks>
<Mask Code="0" Opacity="0.5" X="155" Y="462" Z="630" />
<Mask Code="1" Opacity="0.5" X="499" Y="618" Z="919" />
<Mask Code="2" Opacity="0.5" X="1331" Y="175" Z="470" />
<Mask Code="3" Opacity="0.5" X="1923" Y="411" Z="838" />
</Masks>
</Scene>
同时在场景类中加上相应的属性：
/// <summary>
/// 获取或设置地形单位格尺寸(单位:像素)
/// </summary>
public int TerrainGridSize { get; set; }
/// <summary>
/// 获取或设置地形二维矩阵
/// </summary>
public byte[,] TerrainMatrix { get; set; }
以及修改场景配置Info.xml下载完后对地形的解析：
代码
TerrainGridSize = (int)xScene.Attribute("TerrainGridSize");TerrainMatrix = new byte[(int)xScene.Attribute("TerrainMatrixDimension"), (int)xScene.Attribute("TerrainMatrixDimension")];
string[] terrain = xScene.Attribute("Terrain").Value.Split(',');
for (int y = 0; y < TerrainMatrix.GetUpperBound(1); y++) {
for (int x = 0; x < TerrainMatrix.GetUpperBound(0); x++) {
//设置默认值,可以通过的均在矩阵中用1表示
TerrainMatrix[x, y] = 1;
}
}
for (int i = 0; i < terrain.Count(); i++) {
if (terrain[i] != "") {
string[] position = terrain[i].Split('_');
TerrainMatrix[Convert.ToInt32(position[0]), Convert.ToInt32(position[1])] = 0;
}
}
剩下的就是实现精灵的寻路移动方法了：
/// <summary>
/// A*寻路向目的地跑动
/// </summary>
/// <param name="destination">目的地坐标</param>
/// <param name="terrainMatrix">地形二维矩阵</param>
/// <param name="terrainGridSize">地形单位格尺寸</param>
void AStarRunTo(Point destination, byte[,] terrainMatrix, int terrainGridSize) {
Point2D start = new Point2D() {
X = (int)(Coordinate.X / terrainGridSize),
Y = (int)(Coordinate.Y / terrainGridSize)
};
Point2D end = new Point2D() {
X = (int)(destination.X / terrainGridSize),
Y = (int)(destination.Y / terrainGridSize)
};
PathFinderFast pathFinderFast = new PathFinderFast(terrainMatrix) {
Formula = HeuristicFormula.Manhattan,
Diagonals = true,
HeuristicEstimate = 2,
SearchLimit = terrainMatrix.GetUpperBound(0) * 2, //寻径限度(太小可能导致找不到)
};
List<PathFinderNode> path = pathFinderFast.FindPath(start, end);
if (path == null || path.Count <= 1) {
//路径不存在
return;
//Stand();
} else {
//创建系列关键帧
PointAnimationUsingKeyFrames pointAnimationUsingKeyFrames = new PointAnimationUsingKeyFrames() {
Duration = new Duration(TimeSpan.FromMilliseconds((path.Count - 1) * Speed * terrainGridSize))
};
Storyboard.SetTarget(pointAnimationUsingKeyFrames, this);
Storyboard.SetTargetProperty(pointAnimationUsingKeyFrames, new PropertyPath("Coordinate"));
//加入第一帧
pointAnimationUsingKeyFrames.KeyFrames.Add(
new LinearPointKeyFrame() {
KeyTime = KeyTime.FromTimeSpan(TimeSpan.FromMilliseconds(0)),
Value = Coordinate
}
);
//加入中间匀速帧
for (int i = path.Count - 2; i >= 1; i--) {
pointAnimationUsingKeyFrames.KeyFrames.Add(
new LinearPointKeyFrame() {
KeyTime = KeyTime.FromTimeSpan(TimeSpan.FromMilliseconds((path.Count - 1 - i) * Speed * terrainGridSize)),
Value = new Point(path[i].X * terrainGridSize, path[i].Y * terrainGridSize)
}
);
}
//加入结束帧
pointAnimationUsingKeyFrames.KeyFrames.Add(
new LinearPointKeyFrame() {
KeyTime = KeyTime.FromTimeSpan(TimeSpan.FromMilliseconds((path.Count - 1) * Speed * terrainGridSize)),
Value = destination
}
);
storyboard.Pause();
storyboard.Completed -= storyboard_Completed;
storyboard = new Storyboard();
storyboard.Children.Add(pointAnimationUsingKeyFrames);
storyboard.Completed += new EventHandler(storyboard_Completed);
storyboard.Begin();
Run();
}
}
关于A*寻路及动画实现对于初学者来说比较复杂，为了提高性能代码中引入了单元格尺寸(TerrainGridSize)这个属性，用它首先缩小起点与终点的坐标，然后在缩小的坐标系中计算出路径并赋予到关键帧动画的各帧上(这里用到Storyboard的关键帧动画，即依照找到的路径以每个节点为一个关键帧串联起来实现动画)，最后在计算花费时间及各帧的真实坐标时再重新放大，如还是感觉很难理解的朋友建议参阅一下本节的交叉参考，里面有更详细的说明。
此时运行游戏大家会发现主角移动得特别别扭，因为A*寻路算法找到的路径是僵硬的，为了还原游戏中的真实情形，我们还得多考虑如何将直线移动与这个A*寻路移动有机的智能融合起来。这里我选择路径预测法中的两点线段检测法+A*寻路算法组合。
别被名字吓到了，其实逻辑处理相当简单，大致是截取起点与终点之间所有可能存在的路径坐标点，并逐个判断是否为障碍，如果有则使用寻路移动直接饶过去。
/// <summary>
/// 跑动
/// </summary>
public void RunTo(Point destination, byte[,] terrainMatrix, int terrainGridSize) {
//判断目的地坐标是否超出地形数组范围
if (destination.X < 0 || destination.Y < 0 || (destination.X / terrainGridSize) > terrainMatrix.GetUpperBound(0) || (destination.Y / terrainGridSize) > terrainMatrix.GetUpperBound(0)) { return; }
//采用路径预测法中的(两点线段检测法+A*寻路算法组合)
bool findObstacle = false;
#region 直线等分逐测算法
double angle = Global.GetAngle(Coordinate, destination); //与目标之间的角度
int detectNum = (int)(Global.GetDistance(Coordinate, destination) / terrainGridSize); //需要检测的数量
for (int i = 0; i <= detectNum; i++) {
int x = (int)(Math.Cos(angle) * i + destination.X / terrainGridSize);
int y = (int)(Math.Sin(angle) * i + destination.Y / terrainGridSize);
if (terrainMatrix[x, y] == 0) {
findObstacle = true;
break;
}
}
#endregion
//#region DDA算法
//int dx = (int)(Coordinate.X - destination.X), dy = (int)(Coordinate.Y - destination.Y), steps, k;
//double xIncrement, yIncrement, x = destination.X, y = destination.Y;
//if (Math.Abs(dx) > Math.Abs(dy)) {
// steps = Math.Abs(dx);
//} else {
// steps = Math.Abs(dy);
//}
//xIncrement = (double)dx / steps;
//yIncrement = (double)dy / steps;
//for (k = 0; k < steps; k++) {
// x += xIncrement;
// y += yIncrement;
// if (terrainMatrix[(int)(x / terrainGridSize), (int)(y / terrainGridSize)] == 0) {
// findObstacle = true;
// break;
// }
//}
//#endregion
if (findObstacle) {
AStarRunTo(destination, terrainMatrix, terrainGridSize);
} else {
StraightRunTo(destination);
}
}
大家是否有注意到被我注释掉的一段代码，它实现的是与直线等分逐测算法一样的功能，该用于绘制直线的DDA算法也一样适用于此处，至于性能方面大家可自性测试孰优孰劣。
到此我们就完成了整个基于直角坐标系场景地形的构造与寻路功能实现，相比6.2中的移动，这时精灵移动时场景的遮挡效果与地形匹配才算完美：
void LayoutRoot_MouseLeftButtonDown(object sender, MouseButtonEventArgs e) {
Point destination = e.GetPosition(scene);
hero.RunTo(destination, scene.TerrainMatrix, scene.TerrainGridSize);
}
7.2基于2.5D斜视角之场景与寻径实现(交叉参考：斜度α地图的构造及算法 游戏中斜视角的原理与分析 场景编辑器让游戏开发更美好 场景编辑器之开源畅想)
<?xml version="1.0" encoding="utf-8" ?>
<Scene FullName="龙门镇" MapWidth="3200" MapHeight="1320" OffsetX="1600" OffsetY="-1600" TerrainGridSize="30" TerrainGradient="60" TerrainMatrixDimension="128" Terrain="36_97_0,36_98_0,37_95_0,37_96_0,37_97_0,37_98_0,37_99_0,38_94_0,38_95_0,38_99_0,38_100_0,39_94_0,39_100_0,39_101_0,40_92_0,40_93_0,40_94_0,40_101_0,40_102_0,41_92_0,41_102_0,41_103_0,42_91_0,42_92_0,42_103_0,42_104_0,43_90_0,43_91_0,43_104_0,43_105_0,44_87_0,44_88_0,44_89_0,44_90_0,44_100_0,44_101_0,44_102_0,44_103_0,44_104_0,44_105_0,44_106_0,45_83_0,45_84_0,45_85_0,45_86_0,45_87_0,45_100_0,45_106_0,45_107_0,46_83_0,46_100_0,46_107_0,46_108_0,47_82_0,47_83_0,47_98_0,47_99_0,47_100_0,47_103_0,47_104_0,......">
<Masks>
<Mask Code="0" Opacity="0.5" X="155" Y="462" Z="630" />
<Mask Code="1" Opacity="0.5" X="499" Y="618" Z="919" />
<Mask Code="2" Opacity="0.5" X="1331" Y="175" Z="470" />
<Mask Code="3" Opacity="0.5" X="1923" Y="411" Z="838" />
</Masks>
</Scene>
针对斜视角，场景类中我们还得新增Offset及TerrainGradient属性，同时3个主要属性需要静态化(场景的核心参数，场景中的其他类都可能会用到)：
代码
/// <summary>/// 获取或设置地图与坐标系的相对偏移量
/// </summary>
public Point2D Offset { get; set; }
/// <summary>
/// 获取或设置地形单位格尺寸(单位:像素)
/// </summary>
public static int TerrainGridSize { get; set; }
/// <summary>
/// 获取或设置地形斜度(单位:角度)
/// </summary>
public static double TerrainGradient { get; set; }
/// <summary>
/// 获取或设置地形二维矩阵
/// </summary>
public static byte[,] TerrainMatrix { get; set; }
另外修改相应的解析逻辑：
代码
Offset = new Point2D((int)xScene.Attribute("OffsetX"), (int)xScene.Attribute("OffsetY"));this.RenderTransform = new TranslateTransform() { X = Offset.X, Y = Offset.Y };
map.RenderTransform = new TranslateTransform() { X = -Offset.X, Y = -Offset.Y };
TerrainGridSize = (int)xScene.Attribute("TerrainGridSize");
TerrainGradient = (double)xScene.Attribute("TerrainGradient");
TerrainMatrix = new byte[(int)xScene.Attribute("TerrainMatrixDimension"), (int)xScene.Attribute("TerrainMatrixDimension")];
string[] terrain = xScene.Attribute("Terrain").Value.Split(',');
for (int y = 0; y < TerrainMatrix.GetUpperBound(1); y++) {
for (int x = 0; x < TerrainMatrix.GetUpperBound(0); x++) {
//设置默认值,可以通过的均在矩阵中用1表示
TerrainMatrix[x, y] = 1;
}
}
for (int i = 0; i < terrain.Count(); i++) {
if (terrain[i] != "") {
string[] position = terrain[i].Split('_');
TerrainMatrix[Convert.ToByte(position[0]), Convert.ToByte(position[1])] = Convert.ToByte(position[2]);
}
}
遮挡物的坐标也需要相应的减去场景的偏移量，否则会导致位置出错：
代码
/// <summary>/// 场景实际地图背景下载完毕
/// </summary>
void realMapDownloader_Completed(object sender, DownloaderEventArgs e) {
Downloader realMapDownloader = sender as Downloader;
realMapDownloader.Completed -= realMapDownloader_Completed;
int code = realMapDownloader.TargetCode;
//呈现实际地图背景
map.Source = Global.GetWebImage(string.Format("Scene/{0}/RealMap.jpg", code));
//加载遮挡物
string key = string.Format("Scene{0}", code);
IEnumerable<XElement> iMask = Global.ResInfos[key].Element("Masks").Elements();
for (int i = 0; i < iMask.Count(); i++) {
XElement xMask = iMask.ElementAt(i);
Mask mask = new Mask() {
Source = Global.GetWebImage(string.Format("Scene/{0}/Mask/{1}.png", code, xMask.Attribute("Code").Value)),
Opacity = (double)xMask.Attribute("Opacity"),
Coordinate = new Point((double)xMask.Attribute("X") - Offset.X, (double)xMask.Attribute("Y") - Offset.Y),
Z = (int)xMask.Attribute("Z") - Offset.Y
};
AddMask(mask);
}
}
斜视角场景中的坐标以菱形方格为单位，于是我们需要为场景添加两个静态方法用于窗口像素坐标系与游戏菱形斜视角坐标系之间的坐标转换：
/// <summary>
/// 将窗口坐标系中的坐标换算成游戏坐标系中的坐标
/// </summary>
public static Point GetGameCoordinate(Point p) {
double radian = Global.GetRadian(TerrainGradient);
return new Point(
(int)((p.Y / (2 * Math.Cos(radian)) + p.X / (2 * Math.Sin(radian))) / TerrainGridSize),
(int)((p.Y / (2 * Math.Cos(radian)) - p.X / (2 * Math.Sin(radian))) / TerrainGridSize)
);
}
/// <summary>
/// 将游戏坐标系中的坐标换算成窗口坐标系中的坐标
/// </summary>
public static Point GetWindowCoordinate(Point p) {
double radian = Global.GetRadian(TerrainGradient);
return new Point(
(p.X - p.Y) * Math.Sin(radian) * TerrainGridSize,
(p.X + p.Y) * Math.Cos(radian) * TerrainGridSize
);
}
根据斜视角原理，为了匹配上斜视角地形移动，此时的精灵坐标属性Cooridinate非同以往，它代表的是基于斜视角的新场景坐标(以菱形方格为单位)：
代码
static void ChangeCoordinateProperty(DependencyObject d, DependencyPropertyChangedEventArgs e) {Sprite sprite = d as Sprite;
Point coordinate = Scene.GetWindowCoordinate((Point)e.NewValue);
Canvas.SetLeft(sprite, coordinate.X - sprite.Center.X);
Canvas.SetTop(sprite, coordinate.Y - sprite.Center.Y);
Canvas.SetZIndex(sprite, (int)coordinate.Y);
if (sprite.CoordinateChanged != null) { sprite.CoordinateChanged(sprite, e); }
}
当然，RunTo及其相关方法也避免不了需要重写的：
代码
List<PathFinderNode> path;/// <summary>
/// 向目标点跑去
/// </summary>
/// <param name="destination">目标点(窗口坐标系)</param>
public void RunTo(Point destination) {
//采用路径预测法中的(两点线段检测法+A*寻路算法组合)
bool findObstacle = false;
Point start = Scene.GetWindowCoordinate(Coordinate);
//直线等分逐测算法
double angle = Global.GetAngle(start, destination);
int detectNum = (int)(Global.GetDistance(start, destination));
for (int i = 0; i <= detectNum; i++) {
int x = (int)(Math.Cos(angle) * i + destination.X);
int y = (int)(Math.Sin(angle) * i + destination.Y);
Point p = Scene.GetGameCoordinate(new Point(x, y));
if (Scene.TerrainMatrix[(int)p.X, (int)p.Y] == 0) {
findObstacle = true;
break;
}
}
destination = Scene.GetGameCoordinate(destination);
if (findObstacle) {
PathFinderFast pathFinderFast = new PathFinderFast(Scene.TerrainMatrix) {
Formula = HeuristicFormula.Manhattan,
Diagonals = false,
HeuristicEstimate = 2,
SearchLimit = Scene.TerrainMatrix.GetUpperBound(0) * 2, //寻径限度(太小可能导致找不到路径)
};
List<PathFinderNode> pathTemp = pathFinderFast.FindPath(new Point2D((int)Coordinate.X, (int)Coordinate.Y), new Point2D((int)destination.X, (int)destination.Y));
if (pathTemp != null && pathTemp.Count > 1) {
path = pathTemp;
path.Remove(path[path.Count - 1]);
StraightRunTo(new Point(path[path.Count - 1].X, path[path.Count - 1].Y));
}
} else {
if (path != null) { path.Clear(); }
StraightRunTo(destination);
}
}
Storyboard storyboard = new Storyboard();
/// <summary>
/// 直线向目地跑动
/// </summary>
/// <param name="destination">目标点(游戏坐标系)</param>
void StraightRunTo(Point destination) {
SetDirection(Scene.GetWindowCoordinate(Coordinate), Scene.GetWindowCoordinate(destination));
int duration = Convert.ToInt32(Math.Sqrt(Math.Pow((destination.X - Coordinate.X), 2) + Math.Pow((destination.Y - Coordinate.Y), 2)) * Speed);
PointAnimation animation = new PointAnimation() {
To = destination,
Duration = new Duration(TimeSpan.FromMilliseconds(duration)),
};
Storyboard.SetTarget(animation, this);
Storyboard.SetTargetProperty(animation, new PropertyPath("Coordinate"));
storyboard.Pause();
storyboard.Completed -= storyboard_Completed;
storyboard = new Storyboard();
storyboard.Children.Add(animation);
storyboard.Completed += new EventHandler(storyboard_Completed);
storyboard.Begin();
Run();
}
void storyboard_Completed(object sender, EventArgs e) {
Storyboard storyboard = sender as Storyboard;
storyboard.Completed -= storyboard_Completed;
if (path != null && path.Count != 0) {
path.Remove(path[path.Count - 1]);
if (path.Count != 0) {
StraightRunTo(new Point(path[path.Count - 1].X, path[path.Count - 1].Y));
} else {
Stand();
}
} else {
Stand();
}
}
注意了，本节我去掉了关键帧动画，取而代之的是用队列移动的形式来实现A*寻路，同时精灵朝向的变化也改放到了每次的直线移动方法中；不仅逻辑代码得到优化，精灵的整个移动过程将更显优美而均匀平滑。
另外还有一些需要重视的细节，比如为场景添加一个ConfigReady事件以实现配置文件加载完毕后进行相应的逻辑处理；以及注册游戏窗体尺寸改变事件以适应浏览器或窗口模式时窗体尺寸无论如何变化主角将永远居中：
/// <summary>
/// 主角坐标改变时触发场景相反移动以实现镜头跟随效果
/// </summary>
void hero_CoordinateChanged(Sprite sprite, DependencyPropertyChangedEventArgs e) {
scene.RelativeOffsetTo(hero.Coordinate);
textBlock0.Text = string.Format("主角当前坐标: X {0} Y {1}", (int)hero.Coordinate.X, (int)hero.Coordinate.Y);
}
void LayoutRoot_MouseLeftButtonDown(object sender, MouseButtonEventArgs e) {
hero.RunTo(e.GetPosition(scene));
}
本课小结：地图编辑器是游戏框架的核心，场景编辑器则体现着游戏架构的思想精髓；然而这两款编辑器仅仅是我早期作品，更为优秀的游戏编辑器应该是建立在两者完美融合的基础上再糅合更多的比如资源管理等功能，它的存在不仅能提升程序员的开发效率，同样写得好的算法及功能可大副减少美工团队的重复工作，这也是游戏后期新内容拓展所必不可少的辅助工具，我相信不久的将来它毕定诞生于大家之手。
教程Demo在线演示地址：http://silverfuture.cn
相关阅读 更多 +
