A*算法实现寻找较优路径-[C++] 对象数组析构时的陷阱-FFLIB之FFXML：极简化TinyXml 读取

当前位置: 编程技术>c/c++/嵌入式

本页文章导读:

▪A*算法实现寻找较优路径【qboy】原创 2013年2月2日好久没回到这里来写了，回家过年之前再写一篇吧。这是在2012年11月到12月之间做的一个游戏中所采用的算法。跟大家分享一下。一、A.........

▪[C++] 对象数组析构时的陷阱对象数组，是形如 ClassA *arr = new ClassA[3]; 这样的声明。其相对应的释放方式为 delete[] arr;陷阱出在哪里？别急，继续往下看。我们声明一个ClassA的子类ClassB，如下：class ClassA{public: ClassA().........

▪FFLIB之FFXML：极简化TinyXml 读取摘要：XML是结构化的标记语言，经常被用来做配置文件。由于XML的具有非常强的自描述属性，使用XML的配置文件往往直观易懂。C++中解析XML已经有一些非常成熟的类库可以使用，TinyXml是最受.........

[1]A*算法实现寻找较优路径

来源: 发布时间: 2013-10-17

【qboy】原创 2013年2月2日

好久没回到这里来写了，回家过年之前再写一篇吧。这是在2012年11月到12月之间做的一个游戏中所采用的算法。跟大家分享一下。

一、A*算法的简介

在大学时，在一个人工智能的选修课，我第一次接触了A*算法，也采用这个算法实现课堂上一个作业8数码问题。

简单的说A*算法的核心就是F=G+H;G为到第i步经过的步数，H为到达目的地预计还需要通过多少步,即是一个可能值（或者排除一切障碍的最优值，视问题情况而定），F即是两者相加，对当前情况下的所有F值进行排序，得到F的最优的一步进行第i+1步，直到H值为0。通过这个公式我们可以看出A*算法照顾了过去，也预测着未来。

二、问题背景

我们游戏的背景是在一个有限的海洋中（可以定义为一个二维数组），敌方船向我方船进行逼近，直到撞到我方船为止。在海洋中，有一些零散的岛屿或者其他是在海洋中的障碍物，有些敌方船会以直线的方式逼近（即不考虑障碍物，撞到障碍会死亡），而另一些船AI较高会绕开障碍物向我方逼近。

如下图所示，五角形是我方船位置，即目标位置，菱形和五边形是敌方船，菱形是直线逼近，无智能，五边形是有AI，每艘船可以沿着八个方向进行行走，黄色方块是障碍物。那么菱形会右下撞向障碍物，五边形以实线方向逼近我方船，而不是走最近虚线。当然游戏是回合制，一次只能走特定的步数。

三、实现步骤

为了解决以上问题，我们采用了A*算法（由于游戏是IOS上，所以很多都是ObjC,不过此方法主要还是采用C语言来实现）。

1、我们设定了一个即二维数组（世界环境），描述各船和障碍物所在的位置。

2、定义在寻路过程中的数据结构：

typedef struct ShipPointAStar

{

ShipPoint point;//所在位置

int GValue;//已经过的步数，G

int HValue;//H值

int FValue;//=G+H

struct ShipPointAStar *prePoint;//前一步，这是为了逆着找到要走的点

}ShipPointAStar;

3、定义H函数和G函数:

//A star 算法中的H

// 输入：curPoint为当前所在点，destPoint为目标点

//输出：H值

//原理是：假设没有障碍的情况下两点之间的最短距离数

CG_INLINE int H(ShipPoint curPoint,ShipPoint destPoint)

{

ShipPoint prePoint = curPoint;

int numStep = 0;//预测的步数

while (!EqualShipPoint(prePoint, destPoint)) {//当前点是否与目标点重合

prePoint = getNextShipPoint(prePoint, destPoint);//获取下一步

numStep++;

}

return numStep;

}

G的求法：

定义：

G(i)=G(i-1)+1;

G(0)=0;

根据数学知识可以推算出G(i)=i;其中i为分解步数。

4、构造可选区域的，由于船最多往8个方向移动，则把当前步下的所有可能方向，并计算出相应的H值和G值，求出F值。

5、对所有的可能情况（未走过的点）进行F值排序，取出F值最小的点进行下一步展开，在这采用的是冒泡排序所以就不贴出来了，有机会再改成快速排序。

当出现点与目标点重合时查找结束，或者当所有的能展开的点都已排除，则查找失败（不可达）。

当找到路径时我们逆着把当前点下一步点返回，这已经不在我们讨论范围了。

以下是算法的程序段：

//通过A*算法得到移动位置

//输入：srcPoint源点, destPoint目标点，arrmap地点二维数组，我们定义1是不可走区域，mapW是二维数组的行数，mapH是二维数组的列数 maxFValue是扩展功能，即最大F值，当超过时不再寻路，0时没有限制。

//输出：船的下个行动点

CG_INLINE ShipPoint getNextShipPointByAStarAndMaxFValue(ShipPoint srcPoint,ShipPoint destPoint,int **arrmap,int mapW,int mapH,int maxFValue)

{

ShipPoint nextPoint = ShipPointCopy(srcPoint);

ShipPointAStar star;

star.GValue = 0;

star.HValue = H(nextPoint, destPoint);

star.FValue = star.GValue+star.HValue;

star.point=nextPoint;

star.prePoint = NULL;

ShipPointAStar* stararr =malloc(sizeof(ShipPointAStar)*mapW*mapH);//我个人觉得最多只有地图中的一半个节点会进入数组

int num = 0;

stararr[num] = star;

num ++;

int pi =0;

while (!EqualShipPoint(stararr[pi].point, destPoint)) //已到达目标

{

nextPoint = stararr[pi].point;

if (maxFValue > 0 && stararr[pi].FValue>maxFValue) {

break;

}

int minX = nextPoint.ShipX > 0 ? nextPoint.ShipX - 1 : 0;

int maxX = nextPoint.ShipX < mapW - 1 ? nextPoint.ShipX + 1 : mapW-1;

int minY = nextPoint.ShipY > 0 ? nextPoint.ShipY - 1 : 0;

int maxY = nextPoint.ShipY < mapH - 1 ? nextPoint.ShipY + 1 : mapH-1;

for (int i = minY ; i <= maxY; i++) {

for (int j = minX; j <= maxX; j++) {

if (arrmap[i][j] == 1) //不可走

{

continue;

}

else

{

ShipPoint p =ShipPointMake(j, i);

bool blExist = NO;

for (int k = 0; k<num; k++) {

if (EqualShipPoint(p, stararr[k].point)) {

blExist = YES;

break;

}

if (!blExist) {

ShipPointAStar s;

s.GValue = stararr[pi].GValue+1;

s.HValue = H(p, destPoint);

s.FValue = s.GValue+s.HValue;

s.point=p;

s.prePoint = &stararr[pi];

stararr[num++] = s;

}

SortShipPointAStar(stararr, num);

pi++;

if (pi>=num) {

break;

}

for (int i = 0; i<num; i++) {

ShipPoint p = stararr[i].point;

FCLOG(@"X = %i Y = %i,GValue = %i,FValue = %i",p.ShipX,p.ShipY,stararr[i].GValue,stararr[i].FValue);

}

FCLOG(@"Arr Num = %i",num);

ShipPoint rstPoint= ShipPointNull();

if (EqualShipPoint(stararr[pi].point, destPoint)) {

FCLOG(@"循路成功");

//往回走路径

[2][C++] 对象数组析构时的陷阱

来源: 发布时间: 2013-10-17

对象数组，是形如 ClassA *arr = new ClassA[3]; 这样的声明。
其相对应的释放方式为 delete[] arr;

陷阱出在哪里？别急，继续往下看。

我们声明一个ClassA的子类ClassB，如下：

class ClassA
{
public:
ClassA() {
printf("Build ClassA\n");
x = 0;
}
~ClassA() {printf("Release ClassA\n");}

int x;
};

class ClassB : public ClassA
{
public:
ClassB() {
printf("Build ClassB\n");
y = 1;
}
~ClassB() {printf("Release ClassB\n");}

int y;
};

调用ClassA *arr = new ClassB[3];时，output中我们会看到

说明成功的定义了三个ClassB对象。

但是，当调用delete[] arr;时，output中显示

问题来了，虽然对象类型是ClassB，但ClassB的析构函数并未被调用！

这个问题仅出现在指针类型和对象类型不同的情况，如果定义ClassB* arr = new ClassB[3]，释放时会正常的调用ClassB的析构函数的。

ClassB的长度是8，而ClassA的长度是4，如果仅调用ClassA的析构函数，应该每个对象的内存只有ClassA的部分会被释放。
在VS2012中我看了一下arr的内存布局，结果是虽然ClassB的析构未被调用，arr对象还是完全地被成功释放了。

看来这个问题不大，编译器已经处理掉了。真的是这样吗？我们给ClassB加上一个指针成员，再来看看

class ClassC
{
public:
ClassC() {
printf("Build ClassC\n");
z = 3;
}
~ClassC() {printf("Release ClassC\n");}

int z;
};

class B : public A
{
public:
B() {
printf("Build ClassB\n");
pc = new ClassC();
}
~B() {
printf("Release ClassB\n");
delete pc;
}

ClassC* pc; // 一个对象指针成员，需要在析构函数中显式将其释放
};

再来执行刚才的定义和释放，输出的结果仍然如上面的两个图。

不同的是，虽然arr能成功的完全释放，但由于ClassB的析构函数没有执行，所以pc所指向的ClassC对象仍然存在于内存中，Memory leaks!

不能理解这是C++的设计使然，还是一个BUG，我是在《深度探索C++对象模型》中看到这个问题的，其中也未能给出解释，只是表示
“最好就是避免以一个base class指针指向一个derived class objects所组成的数组。”

笔者认为，开发中用到ClassA *arr = new ClassB[3]的场景应该不会很多，因为这样带来了一个限制：arr的成员类型只能是ClassB，而不能是别的ClassA的子类，如ClassD, ClassE什么的。
直接定义ClassA *arr[3]，然后再根据条件为成员调用相应的构造函数，这样显得更合理些。析构时循环释放每个成员，也不会有任何问题。

本文链接

[3]FFLIB之FFXML：极简化TinyXml 读取

来源: 发布时间: 2013-10-17

摘要：

XML是结构化的标记语言，经常被用来做配置文件。由于XML的具有非常强的自描述属性，使用XML的配置文件往往直观易懂。C++中解析XML已经有一些非常成熟的类库可以使用，TinyXml是最受欢迎的解析类库之一。尽管TinyXml已经已经封装了解析细节，但是解析、遍历Xml仍然是稍显繁琐。FFXML针对如下需求对TinyXml做了轻量封装：

只把XML当成配置文件，也就是说，只有对XML的读取操作，在我日工作中，都是用XML当做纯配置文件，把XML当成序列化文件或数据文件的情况少之又少。
XML配置文件不会太大，我们假设限制在几千行以内，通常XML配置文件不需要那么大，在这种需求下，的XML的读取效率不是问题，易用性会被放到首位，必须非常容易获取xml中的内容。
我们知道XML是结构化的，有层级的概念，这对于C++中的内存模型多多少少会有区别，所以往往获取XML内容的代码会有各种循环、判断、嵌套。FFXML提供了一种“标记语法”使得获取XML内容可以和XML的结构息息对应，即保障了直观，又很容易修改，比如调整了XML的层级关系，FFXML能够保障大多数情况只需改几个字母，而不是修改嵌套的循环代码.

标记语言：

实现先给出示例的XML内容

<game type = "good">
<scene>happly</scene>
<role ID="123456" pos = "any">
<name nick = "xx" >OhNice</name>
<num>99</num>
</role>
</game>

我们知道，如果使用tinyXml读取XML，每一层都需要使用特定的接口获取，从而必须要写一写循环和判断甚至嵌套。FFXML提供了一种“标记语法”来表示XML中各个层级的关系：

game.scene ffxml通过 “.” 来分割各个层级，game.scene 代表获取root标记下层的scene标记在FFXML中获取scen标记的值简单到一行代码const char* scene_val = ffxml.get(“game.scene”);
game.{type} FFXML通过 “{}”表示属性标记，root.{type}表示获取root标记内的type属性的值, 使用FFXML获取type属性的值的代码仍然只有一行:const char* type_val = ffxml.get(“game.{type}”);
game.@0 获取game标签下的索引0的标签内容,也就是scene的内容,即const char* scene_val = ffxml.get(“game.@0”);
game.&0 获取game标记下索引0的字标记的name，也就是ffxml.get(“game.&0”) == “scene”;
game.{@0} 获取game标记下索引0的属性值
game.{&0} 获取game标记下索引0的属性的name
FFXML 提供size接口获取字标记的数量如ffxml.size(“game.role”) 表示role标记下字子标记的数量=2
size 接口也可以获取属性的数量，如ffxml.size(“game.role.{}”) 表示role标记属性的个个数

示例代码:

#include "xml/ffxml.h"
using namespace ff;

int main(int argc, char* argv[])
{
ffxml_t ffxml;

//! 载入test.xml
if (ffxml.load("test.xml"))
{
printf("test.xml 载入失败\n");
return 1;
}

printf("获取字段 game.scene: %s\n", ffxml.get("game.scene"));
printf("获取字段 game.role.name: %s\n", ffxml.get("game.role.name"));
printf("获取字段 game.role.num: %s\n", ffxml.get("game.role.num"));

printf("获取属性 game.{type}: %s\n", ffxml.get("game.{type}"));
printf("获取属性 game.role.{ID}: %s\n", ffxml.get("game.role.{ID}"));

printf("获取标记数量 game: %u\n", ffxml.size("game"));
printf("获取标记数量 game.role: %u\n", ffxml.size("game.role"));

printf("获取属性数量 game: %u\n", ffxml.size("game.{}