简单的寻路算法

❶ 游戏中的常用的寻路算法有哪些

f(n)=g(n)+h(n) 从起始点到目的点的最佳评估值
– 每次都选择f(n)值最小的结点作为下一个结点，
直到最终达到目的结点
– A*算法的成功很大程度依赖于h(n)函数的构建
?;) = g(n? 在各种游戏中广泛应用 Open列表和Closed列表
– Open列表
A*算法
? h(n) = 从结点n到目的结点的耗费评估值，启发函数
?，程序返回n
else 生成结点n的每一个后继结点n;
foreach 结点n的后继结点n;{
将n’的父结点设置为n
计算启发式评估函数h(n‘)值，评估从n‘到node_goal的费用
计算g(n‘) = g(n) + 从n’到n的开销
计算f(n?? 在算法启动时，Closed列表为空 A* 算法伪代码初始化OPEN列表
初始化CLOSED列表
创建目的结点；称为node_goal
创建起始结点；称为node_start
将node_start添加到OPEN列表
while OPEN列表非空{
从OPEN列表中取出f(n)值最低的结点n
将结点n添加到CLOSED列表中
if 结点n与node_goal相等then 我们找到了路径;)
if n‘位于OPEN或者CLOSED列表and 现有f(n)较优then丢弃n’ ;) + h(n?? 包含我们还没有处理到的结点
? g(n) = 从初始结点到结点n的耗费
?? 包含我们已经处理过的结点
，处理后继n’
将结点n‘从OPEN和CLOSED中删除
添加结点n‘到OPEN列表
}
}
return failure （我们已经搜索了所有的结点?? 启发式搜索
– 在搜索中涉及到三个函数
??? 我们最开始将起始结点放入到Open列表中
– Closed列表
?

❷ 模拟游戏一般用什么算法

用寻路算法。
1.小型游戏可以用的简单的寻路算法；
2.随机寻路算法:当NPC不管是遇到障碍物还是遇到了边界(利用碰撞检测),都会随机选取一个前进的方向,继续行走
3.跟踪算法:当游戏中的主角进入到NPC 的“警戒区域”后,游戏的AI 可轻易获得目
4.大型游戏一般使用A*寻路算法:使用最广泛的一种寻路算法,简单说一下A*寻路算法；
5.DFS、BFS也常用于求最优方法这类问题。

❸ 即时战略游戏中实用的寻路算法都有哪些

Potential Field，它是将地图用一个矩阵来表示，矩阵储存着大小不同的电势（整数）。例如，正电势表示吸引，负电势表示排斥。而游戏中的单位本身是一个负电势，游戏以一个数组储存所有单位的电势和位置。这样，在计算一个单位需要怎么从A点到B点时，我们可以用一个新的矩阵将目的地B点设成正电势，并以不同方式（如圆形、四边形等）辐射开来，离B点越远电势越低，直到0。然后将地图矩阵，目的地矩阵，和所有单位数组的电势相加，得出一个新的、反映当前游戏世界的电势矩阵，然后单位再选择周围所有电势点中的最高电势点去走。不过这里坑很多，因为它本质上是Greedy Algorithm，所以它未必能找出解。然而在某些设定中，例如在没有过于复杂地形，并且需要单位自动不相互覆盖的情况下，Potential Field还是可以完成任务。

Flocking Behavior，在对于一大群单位的寻路，计算量是很大的，而且往往会有很多的重复，这些都是可以避免的。如果单位的移动是利用Steering Behavior来实现的话，那么就可以为其中一个单位，称之为Leader，计算路径（例如用导航网格），然后其他单位按照以下Flocking原则来移动：1. 分离，避开相邻单位2. 一致，和整体的移动方向一致，这里应该是Leader的移动方向3. 聚合，向整体的平均位置靠拢这样的话，就可以降低寻路的计算量，并且得到更加真实的群体单位行进效果。

❹ 星际争霸2的寻路算法思路是怎样的

首先地图整体开始前，会用多层可达矩阵算法，算出路径关键点
2，创建关键节点可达矩阵
3，再每个兵当前位置对关键节点进行路径计算
这样可以最小化资源占用就可以完成路径计算了，高数的离散数学，挺容易解的

❺ A* 寻路算法

A*算法
�6�1 启发式搜索
– 在搜索中涉及到三个函数
�6�1 g(n) = 从初始结点到结点n的耗费
�6�1 h(n) = 从结点n到目的结点的耗费评估值，启发函数
�6�1 f(n)=g(n)+h(n) 从起始点到目的点的最佳评估值
– 每次都选择f(n)值最小的结点作为下一个结点，
直到最终达到目的结点
– A*算法的成功很大程度依赖于h(n)函数的构建
�6�1 在各种游戏中广泛应用 Open列表和Closed列表
– Open列表
�6�1 包含我们还没有处理到的结点
�6�1 我们最开始将起始结点放入到Open列表中
– Closed列表
�6�1 包含我们已经处理过的结点
�6�1 在算法启动时，Closed列表为空 A* 算法伪代码初始化OPEN列表
初始化CLOSED列表
创建目的结点；称为node_goal
创建起始结点；称为node_start
将node_start添加到OPEN列表
while OPEN列表非空{
从OPEN列表中取出f(n)值最低的结点n
将结点n添加到CLOSED列表中
if 结点n与node_goal相等then 我们找到了路径，程序返回n
else 生成结点n的每一个后继结点n'
foreach 结点n的后继结点n'{
将n’的父结点设置为n
计算启发式评估函数h(n‘)值，评估从n‘到node_goal的费用
计算g(n‘) = g(n) + 从n’到n的开销
计算f(n') = g(n') + h(n')
if n‘位于OPEN或者CLOSED列表and 现有f(n)较优then丢弃n’ ，处理后继n’
将结点n‘从OPEN和CLOSED中删除
添加结点n‘到OPEN列表
}
}
return failure （我们已经搜索了所有的结点，但是仍然没有找到一条路径）

❻ 游戏寻路算法

1.四种算法是DFS,BFS,Heuristic DFS, Heuristic BFS 这是建立在VC基础上的

2.高数和线代是必须的，还牵涉到数分和运筹学的知识

❼ C++寻路算法

迷宫寻找路径要不。。。。。。#include <iostream>
#include<iomanip>
using namespace std;
#define M 10
#define N 10
typedef enum{X=0,up,dn,rt,lt} tDir; //搜索方向
class Migong
{
public:
int tag; /*0 1*/
tDir comeDir; /*退回*/
int up,rt,dn,lt; //方向
int back;
};int m[M][N]={ //初始化通道数据
{0,0,1,1,1,1,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1},
{1,0,0,0,1,0,1,1,1,1},
{1,1,1,0,1,1,1,1,1,1},
{1,0,0,0,1,0,0,0,1,1},
{1,0,1,1,1,0,1,0,1,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,0,0,1,1,0,1,0,1},
{1,1,1,1,1,1,0,1,0,1},
{1,1,1,1,1,1,1,1,0,0},
}; int ini=0,inj=0; //入点
int outi=9,outj=9; //出口
int cnt=0; //从入口到出口需多少步
int path[M][N]; //记录找到路径后的迷宫
Migong maze[10][10]; void initmaze(Migong mz[][10]) //初始化迷宫数据
{
int i;
int j;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
{
mz[i][j].tag=m[i][j];
mz[i][j].comeDir=X;
mz[i][j].up=0;
mz[i][j].dn=0;
mz[i][j].rt=0;
mz[i][j].lt=0;
mz[i][j].back=0;
}
}int find(Migong mz[][10],int i,int j,tDir dir) //搜索路径
{
if(i==outi&&j==outj)
return 1; ////if 当前节点是出口 then return 1;
if(dir!=X) //if 不是是回退到本节点,then 记录来的方向 根据来的方向设定其相对方向已走
{
mz[i][j].comeDir=dir;
if(dir==up)
mz[i][j].dn=1; //向N方向没有走&&可以走，则向N递归走
if(dir==dn)
mz[i][j].up=1; //向E方向没有走&&可以走，则向N递归走
if(dir==rt)
mz[i][j].lt=1; //向S方向没有走&&可以走，则向N递归走
if(dir==lt)
mz[i][j].rt=1; //向W方向没有走&&可以走，则向N递归走
}
if(mz[i][j].up==0) //if 向up方向没走&&不越界&&可以走 则向up递归走
{
int ni;
int nj;
mz[i][j].up=1; //记录本节点
ni=i-1;
nj=j; //ni,nj表示i,j的上一个坐标
if(ni>=0 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,up))
return 1;
}
if(mz[i][j].dn==0) //if 向dn方向没走&&不越界&&可以走 则向dn递归走
{
int ni;
int nj;
mz[i][j].dn=1; //记录本节点
ni=i+1;
nj=j; //ni,nj表示i,j的下一个坐标
if(ni<10 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,dn))
return 1;
}
if(mz[i][j].rt==0) //if 向rt方向没走&&不越界&&可以走 则向rt递归走
{
int ni;
int nj;
mz[i][j].rt=1; //记录本节点
ni=i;
nj=j+1; //ni,nj表示i,j的右一个坐标
if(nj<10 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,rt))
return 1;
}
if(mz[i][j].lt==0) //if 向lt方向没走&&不越界&&可以走 则向lt递归走
{
int ni;
int nj;
mz[i][j].lt=1; //记录本节点
ni=i;
nj=j-1; //ni,nj表示i,j的左一个坐标
if(nj>=0 && mz[ni][nj].tag==0)
if(find(maze,ni,nj,lt))
return 1;
}

//四个方向都走完了还没有结果

if(i==ini && j==inj) // if 是入口 return 0
return 0;
else // else 则回退
{
mz[i][j].back=1;
if(mz[i][j].comeDir=up) //如果回退的值等于up的值，则向up方向搜索
{
int ni;
int nj;
ni=i+1;
nj=j; //ni,nj表示i,j的下一个坐标
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=dn) //如果回退的值等于dn的值，则向dn方向搜索
{
int ni;
int nj;
ni=i-1;
nj=j; //ni,nj表示i,j的上一个坐标
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=rt) //如果回退的值等于rt的值，则向rt方向搜索
{
int ni;
int nj;
ni=i;
nj=j-1; //ni,nj表示i,j的左一个坐标
if(find(maze,ni,nj,X))
return 1;
}
if(mz[i][j].comeDir=lt) //如果回退的值等于lt的值，则向lt方向搜索
{
int ni;
int nj;
ni=i+1;
nj=j+1; //ni,nj表示i,j的左下角一个坐标
if(find(maze,ni,nj,X))
return 1;
}
}
return 0;
}int onway( Migong nd) //判断点是否在路径上
{
if(nd.tag!=0)
return 0; //墙
if(nd.up==0&&nd.dn==0&&nd.rt==0&&nd.lt==0)
return 0; //没访问过
if(nd.up==1&&nd.dn==1&&nd.rt==1&&nd.lt==1&&nd.back==1)
return 0; //访问过但不通
return 1;
}//打印
void print( Migong mz[][10]) //打印原迷宫
{
int i;
int j;
cout<<"0表示可通过，1表示墙"<<endl;
cout<<"-------------------------------";
cout<<endl<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
for(i=0;i<10;i++)
{
cout<<setw(10)<<"▎ ";
for(j=0;j<10;j++)

cout<<mz[i][j].tag;
cout<<" ▎"<<endl;

}
cout<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
}void print1( Migong mz[][10]) //打印含路径迷宫
{
int i;
int j;
cout<<endl<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;

for(i=0;i<10;i++)
{
cout<<setw(10)<<"▎ ";
for(j=0;j<10;j++)
{
if(i==9 && j==9) //出口
{
cnt++;
cout<<"*";
path[i][j]=0;
}
else
if(onway(mz[i][j]))
{
cout<<"*"; //*表示路径
cnt++;
path[i][j];
}
else
{
cout<<mz[i][j].tag;
path[i][j]=1; //path[i][j]=0表示可通过，path[i][j]=1表示墙
} }
cout<<" ▎"<<endl;
}cout<<" ";
cout<<"▂▂▂▂▂▂▂▂"<<endl;
}void print2( Migong mz[][10]) //打印路径坐标
{
int i;
int j;
int di;
int dj; //di,dj的值为-1，0，1，为了搜索坐标i,j附近的坐标
int pi;
int pj; //pi,pj为上一个路径坐标
int r;
int count; //统计输出了多少个坐标
i=0;
j=0;
pi=1;
pj=0;
count=0; cout<<endl<<"路径坐标为:"<<endl<<endl;
for(r=0;r<cnt;r++)
{
if(i>=10 || j>=10) //i,j的值不可能大于10
continue;
else
{
for(di=-1;di<2;di++)
for(dj=-1;dj<2;dj++)
{
if(di==dj ) //path[i][j]的下一步不可能在它的左上角和右下角
continue;
if(di==1 && dj==-1) //path[i][j]的下一步不可能在它的左下角
continue;
if(di==-1 && dj==1) //path[i][j]的下一步不可能在它的右上角
continue;
if((i+di)<0 ||(j+dj)<0) //i+di,j+dj小于0时不符
continue;
if(path[i+di][j+dj]!=0) //i+di,j+dj不是路径上的坐标
continue;
if((i+di)==i && (j+dj)==j ) //path[i][j]的下一步不可能是它本身
continue;
else
if((i+di)==pi && (j+dj)==pj) //path[i][j]的下一步不可能是它的上一步
continue;
else
{if(i==9&&j==9)<br> cout<<"(9,9)";<br> else<br> {<br> <br> cout<<"("<<i<<","<<j<<")"<<"->";<br> count++;<br> if(count%5==0)<br> cout<<endl;<br> }
pi=i;
pj=j;
i=i+di;
j=j+dj; }
}
}
}
}int main()
{
initmaze(maze); //初始化迷宫
cout<<endl<<endl<<"原迷宫如下："<<endl;
print(maze); //打印原迷宫
if (find(maze,ini,inj,rt)) //如果迷宫有路径
{

cout<<"-------------------------------";
cout<<endl<<"含路径的迷宫,*表示通道"<<endl;
cout<<"-------------------------------";
print1(maze); // 输出含路径的迷宫
cout<<endl<<"-------------------------------"<<endl;
print2(maze); //输出路径坐标
}
else
cout<<"no way!"; //如果迷宫没路径，输出no way
cout<<endl<<endl<<endl;
cout<<"从入口到出口需"<<cnt<<"步";
cout<<endl<<endl;
return 0;
}