不需要地图建模的寻路算法
按键精灵游戏寻路不用打开地图就寻路过去这种脚本要怎么做？
按键精灵游戏寻路不用打开地图就寻路过去这种脚本要怎么做？
(除了找图和找色） 如果能找到走路call的话，就ok了~不过这个也很难用按键那你选几个点在1杀完在地图上点下跑到2，2杀完在地图点下跑到3，3杀完跑到1再开始循环杀。智能的话不借助其他东西，应该很难完成
遍历法和蚁群算法编程MATLAB谁更简单？
蚁群算法是模拟蚁群觅食行为的一种优化算法。在整个觅食过程中蚂蚁散播信息素，蚂蚁通过感知到的信息素多少，来决定所要选择的下一个栅格。
在初始阶段，由于地面上没有信息素，因此蚁群的行走路径是随机的，蚂蚁在行走的过程中会不断释放信息素，标识自己行走的路径。随着时间的推移，有若干只蚂蚁找到了食物，此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为轨迹是随机分布的，因此在单位时间内，短路径上的蚂蚁数量比长路径上的蚂蚁密度要大，短路径留下的信息素浓度也越高。这为后面的蚂蚁们提供了有力的方向指引，越来越多的蚂蚁聚集到最短的路径上去。对于单个蚂蚁来说，它并没有要寻找最短路径，只是根据概率选择；对于整个蚁群系统来说，它们却达到了寻找到最优路径的客观上的效果。
假设蚁群中蚂蚁的总数为M，各蚂蚁在栅格环境下移动，并且根据状态转移规则选择下一个栅格，假设在时刻t时，蚂蚁k位于栅格i，那么蚂蚁k选择下一个栅格j的概率为：
(1)式中：V表示蚂蚁K可以选择下一个栅格的集合；Alpha为信息素浓度启发因子,Alpha越大，表明蚂蚁K越趋向于选择多数蚂蚁走过的路径；Beta表示期望启发因子，反映了能见度信息对蚂蚁选择下一步位置所起作用的大小，Beta值越大，表明蚂蚁K越趋向于选择距离目标点近的栅格，越倾向于往能见度程。表示t时刻路径(i,j)上的信息素浓度；表示t时刻路径(i,j)上的启发信息，其定义为：
蚁群算法的核心部分在于模拟了蚁群的转移概率选择行为，通过使用信息素和启发式函数值进行转移概率计算。其中蚂蚁状态转移过程中以节点到目标点之间的距离的倒数作为启发信息，不利于障碍物的预先规避。并且在复杂的路径规划环境下，蚁群算法在一个庞大的空间中搜索，在优化初期路径上的信息素浓度较小，正向反馈信息不明显尤其是随机解产生的过程中的“盲目搜索”产生大量的局部交叉路径，降低蚁群算法的运行效率，且容易陷入局部最优，搜索进行到一定程度后，容易出现停滞现象，所有个体发现的解完全一致，不能进行进一步搜索，不利于发现更好的解。
matlab仿真
绘制方格图举例：
G[ 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 1 1 0 0 0 1 0 0
0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
]
MM size(G,1)
figure(3)
axis([0,MM,0,MM])
for i1:MM
for j1:MM
if G(i,j)1
x1j-1y1MM-i
x2jy2MM-i
x3jy3MM-i 1
x4j-1y4MM-i 1
fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.3,0.3,0.3])
hold on
else
x1j-1y1MM-i
x2jy2MM-i
x3jy3MM-i 1
x4j-1y4MM-i 1
fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1])
hold on
end
end
end
完整代码以及注释如下：
DG2D(G) %把栅格地图转为邻接矩阵
Nsize(D,1)%N表示问题的规模（象素个数）返回矩阵D行数
MMsize(G,1)%返回G的行数
a1%小方格象素的边长
Exa*(mod(E,MM)-0.5)%终止点横坐标 a乘以变量E对MM（行）取余(得到列)后减0.5 即所处列
if Ex-0.5
ExMM-0.5
end
Eya*(MM 0.5-ceil(E/MM))%E/MM结果取整 终止点纵坐标
Etazeros(1,N)%启发式信息，取为至目标点的直线距离的倒数 初始信息素矩阵
%下面构造启发式信息矩阵
for i1:N
ixa*(mod(i,MM)-0.5)%a乘以变量i对MM取余后减0.5 列
if ix-0.5
ixMM-0.5
end
iya*(MM 0.5-ceil(i/MM))il将结果朝正无穷方向取整
if i~E %i是否等于E
Eta(1,i)((ix-Ex)^2 (iy-Ey)^2)^(0.5) %与终点的直线距离的倒数，启发信息
else
Eta(1,i)0.01
end
end
ROUTEScell(K,M)%用细胞结构存储每一代的每一只蚂蚁的爬行路线 蚂蚁个数*迭代次数矩阵，每个元素是一个结构
PLzeros(K,M)%用矩阵存储每一代的每一只蚂蚁的爬行路线长度
%% -----------启动K轮蚂蚁觅食活动，每轮派出M只蚂蚁--------------------
tic
for k1:K
%disp(k)
for m1:M
%% 第一步：状态初始化
WS%当前节点初始化为起始点
PathS%爬行路线初始化
PLkm0%爬行路线长度初始化
TABUkmones(1,N) %生成禁忌列表,所有节点均未走过，所以都置为1
TABUkm(S)0%已经在初始点了，因此要排除
DDD%邻接矩阵初始化
%% 第二步：下一步可以前往的节点
DWDD(W,:) %把矩阵DD的第W行所有列赋值给DW
% DW1find(DWltinf)
% for j1:length(DW1)
% if TABUkm(DW1(j))0
% end
% end
LJDfind(DWltinf)%可选节点集 即返回可以走的节点坐标lt矩阵编号gt
Len_LJDlength(LJD)%计数 可选节点的个数
%% 觅食停止条件：蚂蚁未遇到食物或者陷入死胡同
while W~EampampLen_LJDgt1
%% 第三步：转轮赌法选择下一步怎么走
PPzeros(1,Len_LJD) %遍历可选节点
for i1:Len_LJD
% PP(i)(Tau(W,LJD(i))^Alpha)*((1/(DD(W,LJD(i)) Eta(1,LJD(i))))^Beta)
PP(i)(Tau(W,LJD(i))^Alpha)*((1/Eta(1,LJD(i)))^Beta) %w行i个节点
end
PPPP/(sum(PP))%建立概率分布 把各个路径的概率统一到和为1；
Pcumcumsum(PP) %PP累计值
Selectfind(Pcumgtrand)%产生任意0~1之间的随机数，轮盘赌算法，尽量避免陷入局部最优解
to_visitLJD(Select(1))%下一步将要前往的节点
%% 第四步：状态更新和记录
Path[Path,to_visit]%路线节点增加
PLkmPLkm DD(W,to_visit)%路径长度增加，记录本次迭代最佳路线长度，每只蚂蚁都有自己走过的长度记录在向量中。
Wto_visit%蚂蚁移到下一个节点
%N：所有点
for kk1:N
if TABUkm(kk)0 %禁忌列表
DD(W,kk)inf %在此次循环中设置为不可达
DD(kk,W)inf
end
end
TABUkm(W)0%已访问过的节点从禁忌表中删除
DWDD(W,:)
LJDfind(DWltinf)%可选节点集
Len_LJDlength(LJD)%可选节点的个数
end
%% 第五步：记下每一代每一只蚂蚁的觅食路线和路线长度
ROUTES{k,m}Path %第k次迭代 第m只蚂蚁的路线
if Path(end)E
PL(k,m)PLkm %到达目标点的路线长度
else
PL(k,m)inf %进入死胡同
end
end
%% 第六步：更新信息素
Delta_Tauzeros(N,N)%更新量初始化
for m1:M %M只蚂蚁
if PL(k,m)ltinf %顺利到达目标点的蚂蚁路线长度
ROUTROUTES{k,m} %具体路线
TSlength(ROUT)-1 %跳数 蚂蚁转移次数
PL_kmPL(k,m)%路线长度
for s1:TS
xROUT(s) %上一个节点
yROUT(s 1) %下一个节点
Delta_Tau(x,y)Delta_Tau(x,y) Q/PL_km %(x,y)即两个节点之间的关系(信息素量) 系数除以路线长度
Delta_Tau(y,x)Delta_Tau(y,x) Q/PL_km
end
end
end
Tau(1-Rho).*Tau Delta_Tau%信息素挥发一部分，新增加一部分
end
toc
%% ---------------------------绘图--------------------------------
plotif1 %是否绘图的控制参数
if plotif1
%绘收敛曲线
meanPLzeros(1,K) %k：迭代次数
minPLzeros(1,K)
for i1:K
PLKPL(i,:) %将第i次迭代爬行路线长度赋值给PLK
Nonzerofind(PLKltinf)%返回一系列可行路线的编号
if length(Nonzero)~0
PLKPLKPLK(Nonzero)%留下可行路线，重新排列
meanPL(i)mean(PLKPLK) %求取这次可行路径的平局值
minPL(i)min(PLKPLK)%提出最小路径
end
end
% % figure(1)
% % minPL(find(minPL0))[]%将等于0的点删除
% % meanPL(find(meanPL0))[]%将等于0的点删除
% % plot(minPL,k )
% % hold on
% % plot(meanPL,r)
% % grid on %on添加网格 off去掉网格
% % title(收敛曲线（平均路径长度和最小路径长度）)
% % xlabel(迭代次数)
% % ylabel(路径长度)
%绘爬行图
% figure(2)
%绘制方格图形
% axis([0,MM,0,MM])
% for i1:MM
% for j1:MM
% if G(i,j)1
% x1j-1y1MM-i
% x2jy2MM-i
% x3jy3MM-i 1
% x4j-1y4MM-i 1
% fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2])%（x坐标，y坐标，颜色）
% hold on
% else
% x1j-1y1MM-i
% x2jy2MM-i
% x3jy3MM-i 1
% x4j-1y4MM-i 1
% fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1])
% hold on
% end
% end
% end
% hold on
% ROUTROUTES{K,M}
% RxROUT
% RyROUT
% LENROUTlength(ROUT)
% for ii1:LENROUT
% Rx(ii)a*(mod(ROUT(ii),MM)-0.5)
% if Rx(ii)-0.5
% Rx(ii)MM-0.5
% end
% Ry(ii)a*(MM 0.5-ceil(ROUT(ii)/MM))
% end
% plot(Rx,Ry)
end
% plotif21%绘各代蚂蚁爬行图
% if plotif21
% figure(3)
% axis([0,MM,0,MM])
% for i1:MM
% for j1:MM
% if G(i,j)1
% x1j-1y1MM-i
% x2jy2MM-i
% x3jy3MM-i 1
% x4j-1y4MM-i 1
% fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2])
% hold on
% else
% x1j-1y1MM-i
% x2jy2MM-i
% x3jy3MM-i 1
% x4j-1y4MM-i 1
% fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1])
% hold on
% end
% end
% end
% for k1:K %迭代次数
% PLKPL(k,:) %将第k次迭代爬行路线长度赋值给PLK
% minPLKmin(PLK) %求得本次迭代最短路径长度
% posfind(PLKminPLK) %找出与最短路径长度相等的路径，返回标号
% mpos(1)%选择其中第一个标号
% ROUTROUTES{k,m} %将最短路径的路线赋值给ROUT
%
% LENROUTlength(ROUT) %求得路线长度
%
% RxROUT
% RyROUT
% for ii1:LENROUT
% Rx(ii)a*(mod(ROUT(ii),MM)-0.5)
% if Rx(ii)-0.5
% Rx(ii)MM-0.5
% end
% Ry(ii)a*(MM 0.5-ceil(ROUT(ii)/MM))
% end
% plot(Rx,Ry)
% hold on
% end
% end
plotif31%绘最短蚂蚁爬行图
if plotif31
figure(2)
axis([0,MM,0,MM])
for i1:MM
for j1:MM
if G(i,j)1
x1j-1y1MM-i
x2jy2MM-i
x3jy3MM-i 1
x4j-1y4MM-i 1
fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2])
hold on
else
x1j-1y1MM-i
x2jy2MM-i
x3jy3MM-i 1
x4j-1y4MM-i 1
fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1])
hold on
end
end
end
minmumPLKinf
for k1:K
PLKPL(k,:) %将第k次迭代爬行路线长度赋值给PLK
minPLKmin(PLK)
if(minPLKltminmumPLK)
posfind(PLKminPLK) %找到与最短爬行路线长度相等的路径标号
minmumPLKminPLK
minmpos(1)
minkk %迭代k次
end
end
ROUTROUTES{mink,minm} %找出最小路径路线
LENROUTlength(ROUT)
RxROUT
RyROUT
for ii1:LENROUT
Rx(ii)a*(mod(ROUT(ii),MM)-0.5)
if Rx(ii)-0.5
Rx(ii)MM-0.5
end
Ry(ii)a*(MM 0.5-ceil(ROUT(ii)/MM))
end
plot(Rx,Ry)
hold on
end
运行图如下：
————————————————