[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖

[原创代码] [Perl]迷宫寻路 野生算法

本帖最后由 523066680 于 2016-7-1 18:42 编辑

来自 http://迷路.jp 的图片
ありがとう「迷路.jp」2周年の迷路

以下图片,另存为 2.bmp


没看过相关算法书籍,自己写的,算法也非全自动,需要自己指定入口(那些专搞图形的家伙可以做
到自动锚定红色箭头和蓝色箭头),我的代码经过暴力调节使其恰好能跑出去(真是弱爆了 。。。

下面三个变量指定入口坐标和初始方向
    state $ox = 137;
    state $oy = 500 - 451;
    state $ang = 70.0/360.0 * $PIx2;

此外运行还需要 OpenGL 模块的支持 ( ppm install opengl )
如果您真的搭建环境并运行了程序,按a b c d获得不同的速度

效果演示:


顺便推销一下论坛 http://www.open-gl.org/  正在改版中 。。。
验证问题答案分别是  'float'  'open-gl.org'  '12'  和 '多边形'
  1. =info
  2.     Code: vicyang
  3.     Mail: 523066680@163
  4.     Date: 2016-05
  5.     算法: 野生的
  6. =cut
  7. use v5.16;
  8. use feature "state";
  9. use IO::Handle;
  10. use OpenGL qw/ :all /;
  11. use OpenGL::Config;
  12. use Time::HiRes 'sleep','time';
  13. STDOUT->autoflush(1);
  14. use utf8;
  15. use Encode;
  16. use IO::Handle;
  17. STDOUT->autoflush(1);
  18. binmode(STDOUT, ":encoding(gbk)");
  19. our $WinID;
  20. our $win_x = 500;
  21. our $win_y = 500;
  22. our $PI = 3.1415927;
  23. our $PIx2 = $PI * 2;
  24. my $file = "2.bmp";
  25. my $READ;
  26. open $READ, "<:raw", $file or die "$!";
  27. my $v;
  28. read($READ, $v, 14, 0);
  29. our ($type, $bfSize, $res1, $res2, $offset) = (unpack 'SLSSL', $v);
  30. read($READ, $v, 4+4+4+2+2, 0);
  31. our ($headSize, $width, $height, $planes, $bitCount) = (unpack 'L3S2', $v);
  32. our $Compoments_per_pixel = $bitCount / 8;
  33. #有可能是RGBA,4个字节 => 32位情况下
  34. #有可能是RGB, 3个字节 => 24位情况下
  35. printf "文件字节数:%04x -> %d\n", $bfSize, $bfSize;
  36. printf "位图偏移量:%04x -> %d\n", $offset, $offset;
  37. printf "   宽 × 高:%d×%d\n", $width, $height;
  38. printf "  位图色深:%d 位\n", $bitCount;
  39. #实际宽度
  40. #Windows的BMP规定一个扫描行所占的字节数必须是 4字节的倍数,不足的以0填充
  41. my $rowLen = ($bfSize - $offset) / $height;
  42. my $rowCut = ($width * $Compoments_per_pixel) % 4; #RGBA的情况下自然为0
  43. #跳过文件头
  44. seek($READ, $offset, 0);
  45. my ($R, $G, $B);
  46. my $col = 0;
  47. my $lines = 0;
  48. my $j = 0;
  49. my @Colors;
  50. our %Coord;
  51. our @step;
  52. our %badway;
  53. our %way;
  54. =way struct
  55.     {
  56.         "ox oy" =>
  57.             {
  58.                 "ang" => $ang,   #当前ang
  59.                 "way" => [ratio1, ratio2, ratio3]
  60.             }
  61.     }
  62. =cut
  63. our $theVortex;
  64. our $delay;
  65. our $WRT;
  66. open $WRT,">:raw", "log.txt";
  67. while ( read( $READ, $v, $Compoments_per_pixel, 0) )
  68. {
  69.     $col++;
  70.     ($B, $G, $R) = unpack("C$Compoments_per_pixel", $v);  #C4
  71.     $Colors[$j++] =
  72.     {
  73.         'R'=>$R/255.0,
  74.         'G'=>$G/255.0,
  75.         'B'=>$B/255.0,
  76.         'X'=>$col,
  77.         'Y'=>$lines
  78.     };
  79.     #@{$Coord{$col}{$lines}{'R','G','B'}} = ($R, $G, $B);  #problem, keys => RGB
  80.     $Coord{$col}{$lines} =
  81.     {
  82.         'R' => $R,
  83.         'G' => $G,
  84.         'B' => $B,
  85.     };
  86.     if ($col == $width)
  87.     {
  88.         seek($READ, $rowCut, 1);     #从当前去掉多余的填充字节
  89.         $col = 0;
  90.         $lines++;
  91.     }
  92. }
  93. close $READ;
  94. my @xrr;
  95. my @yrr;
  96. for my $info (@Colors)
  97. {
  98.     if ($info->{'R'} < 0.5 and $info->{'G'} < 0.5 and $info->{'B'} < 0.5 )
  99.     {
  100.         push @xrr, $info->{'X'};
  101.         push @yrr, $info->{'Y'};
  102.     }
  103. }
  104. #print join(", ", @xrr),"\n";
  105. #print join(", ", @yrr);
  106. #exit;
  107. &Main();
  108. sub display
  109. {
  110.     state $times = 0;
  111.     our $WinID;
  112.     our %coord;
  113.     our @step;
  114.     our %badway;
  115.     our %way;
  116.     our $PI;
  117.     our $PIx2;
  118.     my $radDelta = $PIx2 / 50.0 ;
  119.     my $limit = 120.0/360.0*$PIx2 ;
  120.     my $len = 8.0;
  121.     my $testlen = 10.0;
  122.     my $ratio;
  123.     my $rad;
  124.     my $angx;
  125.     my $ref;
  126.     state $ox = 137;
  127.     state $oy = 500 - 451;
  128.     state $ang = 70.0/360.0 * $PIx2;
  129.     my ($tx, $ty);
  130.     my ($n_x, $n_y);
  131.     glPushMatrix();
  132.         glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
  133.         
  134.         glCallList($theVortex);
  135.         my $flag;
  136.         my $ways = 0;
  137.         if (not defined $way{"$ox $oy"} )
  138.         {
  139. LV1:        for ( $ratio = -$limit; $ratio <= $limit; $ratio += $radDelta )
  140.             {
  141.                 $angx = $ang + $ratio;
  142.                 $flag = linetest( $ox, $oy, $len, $angx );
  143.                 if ($flag == 1)
  144.                 {
  145.                     $ways++;
  146.                     #走中间线
  147.                     $rad = 0.0;
  148.                     do
  149.                     {
  150.                         $rad += $radDelta;
  151.                     }
  152.                     while ( (linetest( $ox, $oy, $testlen, $angx+$rad ) == 1) and ($rad < $PI) );
  153.                     $angx += $rad/2;  #中间位置
  154.                     $ratio += $rad + (10.0/360.0*$PIx2);   #略过这个连续区域
  155.                     $tx = $ox + around( $len * cos($angx) );
  156.                     $ty = $oy + around( $len * sin($angx) );
  157.                     glColor4f(1.0, 0.0, 1.0, 0.7);
  158.                     draw_line($ox, $oy, $tx, $ty, 1.0);
  159.                     push @{$way{"$ox $oy"}{'way'}},
  160.                             {
  161.                                 'angx' => $angx,
  162.                                 'tx'   => $tx,
  163.                                 'ty'   => $ty,
  164.                             };
  165.                 }
  166.             }
  167.         }
  168.         
  169.         glBlendFunc(GL_DST_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
  170.         glBegin(GL_LINE_STRIP);
  171.         glColor4f(0.0, 0.2, 0.2, 0.8);
  172.         for my $i ( 0 .. $#step )
  173.         {
  174.             glVertex3f( $step[$i]->[0], $step[$i]->[1], 1.0 );
  175.         }
  176.         glEnd();
  177.         
  178.         $ref = $way{"$ox $oy"}{'way'};
  179.         if ( $#{$ref} >= 0 )  #存在多条路径的时候,存储当前节点,回退的时候用
  180.         {
  181.             push @step, [$ox, $oy, $ang];
  182.         }
  183.         printf "%3d %3d %7.3f times :%d step: %d ways: %d \n",
  184.             $ox, $oy, $ang ,$times, $#step+1, $ways;
  185.         #print $ref->[0]{'ty'};
  186.             #exit;
  187.         if ( $#{$ref} >= 0 )
  188.         {
  189.             draw_line($ox, $oy, $ref->[0]{'tx'}, $ref->[0]{'ty'}, 1.0);
  190.             $ox = $ref->[0]{'tx'};
  191.             $oy = $ref->[0]{'ty'};
  192.             $ang = $ref->[0]{'angx'};
  193.             shift @{$ref};
  194.         }   
  195.         else
  196.         {
  197.             print "there is no way!\n";
  198.             #pop @step;
  199.             ($ox, $oy, $ang) = @{ $step[$#step] };
  200.             pop @step;
  201.         }
  202.         
  203.     glPopMatrix();
  204.     glutSwapBuffers();
  205.     $times++;
  206. }
  207. sub init
  208. {
  209.     glClearColor(0.0, 0.0, 0.0, 1.0);
  210.     our $t=1.0;
  211.     our $delay;
  212.     $delay = 0.1;
  213.     glPointSize(1.0);
  214.     glLineWidth(2.0);
  215.     glEnable(GL_DEPTH_TEST);
  216.     glEnable(GL_BLEND);
  217.     glEnable(GL_POINT_SMOOTH);
  218.     glEnable(GL_LINE_SMOOTH);
  219.     $theVortex=glGenLists(1);
  220.     glNewList($theVortex, GL_COMPILE);
  221.     drawbmp();
  222.     glEndList();
  223. }
  224. sub drawbmp()
  225. {
  226.         glBegin(GL_POINTS);
  227.         for my $c (@Colors)
  228.         {
  229.             glColor4f( @$c{'R','G','B'}, 1.0 );
  230.             glVertex3f( $c->{'X'}, $c->{'Y'}, 0.0);
  231.         }
  232.         glEnd();
  233. }
  234. sub idle
  235. {
  236.     sleep $delay;
  237.     glutPostRedisplay();
  238. }
  239. sub Reshape
  240. {
  241.     our $width;
  242.     our $height;
  243.     glViewport(0.0, 0.0, $win_x, $win_y);
  244.     glMatrixMode(GL_PROJECTION);
  245.     glLoadIdentity();
  246.     glOrtho(0.0, 500.0, 0.0, 500.0, 0.0,200.0);
  247.     glMatrixMode(GL_MODELVIEW);
  248.     glLoadIdentity();
  249.     gluLookAt(0.0,0.0,100.0,0.0,0.0,0.0, 0.0,1.0,100.0);
  250. }
  251. sub hitkey
  252. {
  253.     our $WinID;
  254.     our %badway;
  255.     my $keychar = lc(chr(shift));
  256.     given ( $keychar )
  257.     {
  258.         when (/q/i) { glutDestroyWindow($WinID); dump_data( \%badway, "batway.txt" ); }
  259.         when (/a/i) { $delay = 2.0; }
  260.         when (/b/i) { $delay = 1.0; }
  261.         when (/c/i) { $delay = 0.5; }
  262.         when (/d/i) { $delay = 0.01; }
  263.         when (/f/i) { glutPostRedisplay()  }
  264.     }
  265. }
  266. sub mouse
  267. {
  268.     our %Coord;
  269.     my (undef, undef, $x, $y) = @_;
  270.     printf "Position %d %d, Color: %d %d %d\n",
  271.         $x, $y,
  272.         $Coord{$x}{500-$y}{'R'},
  273.         $Coord{$x}{500-$y}{'G'},
  274.         $Coord{$x}{500-$y}{'B'},
  275.     ;
  276. }
  277. sub Main
  278. {
  279.     glutInit();
  280.     glutInitDisplayMode( GLUT_DEPTH | GLUT_RGBA | GLUT_DOUBLE );
  281.     glutInitWindowSize($win_x, $win_y);
  282.     glutInitWindowPosition(1,1);
  283.     our $WinID = glutCreateWindow("title");
  284.     &init();
  285.     glutDisplayFunc(\&display);
  286.     glutReshapeFunc(\&Reshape);
  287.     glutKeyboardFunc(\&hitkey);
  288.     glutMouseFunc(\&mouse);
  289.     glutIdleFunc(\&idle);
  290.     glutMainLoop();
  291. }
  292. =Function
  293. =cut
  294. sub around
  295. {
  296.     my $num = shift;
  297.     my $n = int($num);
  298.     if ( $num - $n >= 0.5)
  299.     {
  300.         return $n + 1;
  301.     }
  302.     else
  303.     {
  304.         return $n;
  305.     }
  306. }
  307. sub dump_data
  308. {
  309.     use Data::Dumper;
  310.     my ($hashref, $file) = @_;
  311.     open WRT, ">:raw:crlf", $file or warn "$!";
  312.     print WRT Data::Dumper->Dump([$hashref], ['*badway']);
  313.     close WRT;
  314.     no YAML;
  315. }
  316. sub linetest
  317. {
  318.     our %coord;
  319.     my ($ox, $oy, $len, $angx) = @_;
  320.     my $ref;
  321.     my $flag;
  322.     my $tx;
  323.     my $ty;
  324.     $flag = 1;
  325.     for my $test (1 .. $len+1)
  326.     {
  327.         for my $w ( -1..1 )
  328.         {
  329.             $tx = $ox + around( $test * cos( $angx ) -    $w * sin( $angx)  );
  330.             $ty = $oy + around(    $w * cos( $angx ) + $test * sin ($angx)  );
  331.             if ($ty < 0 or $tx < 0)
  332.             {
  333.                 die "What?\n"
  334.             }
  335.             $ref = $Coord{ $tx }{ $ty };
  336.             
  337.             if ( $ref->{'R'} < 150 and $ref->{'G'} < 150 and $ref->{'B'} < 150 )
  338.             {
  339.                 $flag = 0;
  340.             }
  341.             else
  342.             {
  343.                 # glColor4f(0.5, 0.0, 0.5, 1.0);
  344.                 # glBegin(GL_LINES);
  345.                 # glVertex3f( $ox, $oy, 0.5);
  346.                 # glVertex3f( $tx, $ty, 0.5);
  347.                 # glEnd();
  348.             }
  349.         }
  350.     }
  351.     return $flag;
  352. }
  353. sub draw_line
  354. {
  355.     my ($ox, $oy, $tx, $ty, $z) = @_;
  356.     glBegin(GL_LINES);
  357.         glVertex3f( $ox, $oy, $z);
  358.         glVertex3f( $tx, $ty, $z);
  359.     glEnd();
  360. }
复制代码
1

评分人数

本帖最后由 523066680 于 2016-7-2 18:09 编辑

回复 6# aa77dd@163.com


    之前见过一种方法是用PHOTOSHOP 模糊填充
这种方法原理是沿着迷宫的墙壁一直走,总能走出去。上面的图是个例外!

TOP

回复 5# aa77dd@163.com


    关于找箭头的事情,我又看到一个这样的,真是啥情况都有,不过好在,除了箭头 其他都是黑白
业余还是玩不动,我去看点书好了

TOP

回复 4# codegay


    正准备修改问题,还没想好

TOP

本帖最后由 523066680 于 2016-7-2 14:43 编辑

回复 7# aa77dd@163.com


    业界良心

而且看上面很多特殊的形状:一些动漫人物、日常物品的轮廓   就能感觉到至少是人工参与设计的。

TOP

迷路生成アルゴリズムなどは使わず、手作業で道順を作っています。

迷宫生成算法等不使用,手工制作的路线。


居然真是手工制作的路线!!!

TOP

关于迷宫(做成水平面流体槽形), 流体从入口注入, 在重力作用下, 无论迷宫如何复杂宠大, 流体最后都会从出口流出, 流体并没有意识, 但在重力压强的作用下, 完成了对迷宫的广度优先式搜索算法, 最终从出口流出, 在流到出口之前, 会将所有入口能通达的路径全部并行填充. 即使找到一个出口后, 只要其他路径还能继续流动(没有探索完全),  就会继续向前探索, 直到所有非出口分支都不可流动.

TOP

回复 3# 523066680

以前 用 PASCAL 写过解迷宫, 后来也写过迷宫生成 WIKIPEDIA 上有些算法, 比较好奇: 这个站的迷宫图都是用什么东东生成的, 因为我不愿相信那是手工一点点绘制的

另外, 关于那个箭头呢, 基本琢磨了一下, 不是很妙的方法, 但觉得可行:

1. 按边缘算法对整图分区, 好多区的话效率并不高.

2. 在填色为 蓝色/红色 的封闭(边缘都在图内部, 没有开放边缘--也就是以图片边缘为边缘)区内, 边缘寻迹, 需要直线判定, 角判定,

那个箭头的特征是: 5 凸角, 2凹角, 并要依照 凸凸凸凹凸凸凹, 这样一个环形次序. 要更精确, 还可对相关边作平行检测

这样就能把箭头识别出来, 根据填色确定 入/出口

TOP

我想说你论坛之前的注册问题太难了。
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

回复 2# aa77dd@163.com


    谢谢捧场

TOP

回复 1# 523066680


从2 小时 到 3 小时了, KA, 还是我第一个来哦

TOP

返回列表