OpenCvSharp解迷宫:《塞尔达传说旷野之息》洛美岛

OpenCvSharp解迷宫:《塞尔达传说旷野之息》洛美岛

《塞尔达传说旷野之息》东北角有一座迷宫,外部看上去是这样的:

最早还没有开这边塔的时候,地图上没有信息,进去也找不到路,后来开了塔可以打开地图看到迷宫:

这迷宫有个问题:不能确定终点。目的地是在中间上方的大方块处,但是连通这个大方块的通路有好几条。起始点是地图最下方的小缺口,同样是通向多个方向有通路。虽然迷宫不是很大,但是起点终点都不能完全确定,走起来还是要费一番功夫的。

作为程序员,当然要想到用技术手段解决,迷宫嘛,就是找通路,dfs和bfs都可以。连通区域用dfs,找最短路用bfs。处理图像可以用.NET的Bitmap诸方法,或者使用open CV,在C#当中,通过Nuget包管理器可以找到OpenCvSharp4 ,是C#风格的open CV,这样可以将openCV对图像处理的强大功能与C#与用户交互结合起来,编写一个易用的探迷宫程序。

C#建立一个WinForm窗体工程,通过Nuget导入OpenCvSharp4。建立全局变量Mat src用来表示我们的迷宫。窗体的Load方法先将src初始化,并将之加载控件上(控件的BackgroudImageLayout提前设置为Stretch):

Mat src;
private void Form1_Load(object sender, EventArgs e)
{
    src = Cv2.ImRead(@"lomesima.jpg");
    pictureBoxIpl1.BackgroundImage= BitmapConverter.ToBitmap(src);
}

这样运行之后原图片就显示在了主控件上。先对其做一些基本的处理:裁剪,二值化、平滑。首先定位到图片的像素,我们需要的是迷宫区域,定位了它的左上和右下坐标,就可以用SubMat方法裁剪下我们需要的 (100,520) 到 (360,920) 区域:

private void Form1_Load(object sender, EventArgs e)
{
    src = Cv2.ImRead(@"lomesima.jpg");
    src=src.SubMat(100,520,360,920);
    pictureBoxIpl1.BackgroundImage= BitmapConverter.ToBitmap(src);
}

这样得到了彩色的地图(深棕色与棕色,以及不重要的蓝色标记)

接下来将迷宫转成二值图,可以使用LUT变换,LUT需要一个映射表lut[],它是一个长度为256的数组,表示将像素值为k的像素映射为lut[k],在opencv中如果图像是三通道的,则lut[]也需要是三通道,如果是图像灰度图单通道,则lut[]就是单通道。我们最终是进行二值化,不需要色彩信息,可以用单通道,就先将src转成灰度:

Cv2.CvtColor(src, src, ColorConversionCodes.BGR2GRAY);

然后选一个数值作为分界,灰度大于这个分界值则为255,小于则为0。经过测试(加一个trackbar控件,其Value值作为这个分界值,动态地看到用各数值的效果)选取57作为分界,这样可以看到二值化的迷宫轮廓。

Mat lut_g2bw;
private void init_lut()
{
    int seprateVal = 57;
    IntPtr p;
    p = Marshal.AllocHGlobal(256);
    for (int i = 0; i < seprateVal; i++)
    {
        Marshal.WriteByte(p, i, 0);
    }
    for (int i = seprateVal; i < 256; i++)
    {
        Marshal.WriteByte(p, i, 255);
    }
    lut_g2bw = new Mat(1, 256, MatType.CV_8U, p);
    Marshal.FreeHGlobal(p);
}
private void Form1_Load(object sender, EventArgs e)
{
    src = Cv2.ImRead(@"lomesima.jpg");
    src=src.SubMat(100,520,360,920);
    init_lut();
    Cv2.LUT(src, lut_g2bw, src);
    pictureBoxIpl1.BackgroundImage= BitmapConverter.ToBitmap(src);
}

二值化之后出现了一些条纹,这是游戏中打开地图自然附带的游戏效果。这些条纹既不美观,重要的是也可能影响探路,比如最上方一些黑色斑点就可能认为是墙,而有的墙上可能因为有白色条纹而误认为是通路。可以通过加入尺寸为5的中值平滑解决:

Cv2.MedianBlur(src, src,5);

图片效果会好很多

迷宫的路径已经很清楚了,接下来就是先探一下从起点出发有哪些区域是连通着的,编写一个dfs:从鼠标点击的位置开始深度搜索所有可达的区域,可达的区域可以画一个’+’作为标记。是这样的效果:

鼠标点击一个起点,从起点开始会朝上下左右各个方向探路,若新方向上的坐标是白色区域,那么就打一个点,并且在这个点继续向各方向探路。每到一个新点进行探路前进的方向可以是随机的也可以是固定的,图上是随机进行的,对总体影响不大。

既然有鼠标与控件交互,图片可以直接通过Bitmap读取颜色而不需要再转成openCV的Mat。这里有一个线性映射:鼠标点击的位置是控件的位置,而图片某点的坐标是图片尺寸,由于最开始在控件上设定了BackgroudImageLayout是Stretch,图片是拉伸占满控件的,就需要将点击的坐标映射成图片的位置坐标使用。

MouseEventArgs me = (MouseEventArgs)e;
int x=me.X,y=me.Y;
int w = pictureBoxIpl1.Width, h = pictureBoxIpl1.Height;
Bitmap p = (Bitmap)pictureBoxIpl1.BackgroundImage;
int pw = p.Width, ph = p.Height;
int cx = x * pw / w, cy = y * ph / h;

x和y是鼠标事件的坐标,w和h是控件的宽高,pw,ph是图片的宽高,x*pw/w就是鼠标点击位置对应实际图片的位置cx,类似地cy是图上y的位置。用 p.GetPixel(cx, cy) 可以获取控件上x,y位置的像素值。dfs的时候并不需要对每个点都探路,可以按照间隔为_step进行搜索。dir是设定的Point[]数组用以表示接下来走的方向,取值为(0,-1),(0,1),(-1,0),(1,0)。drawCross()是用来标记的,在(x,y)位置画一个’+’符号。

private void drawCross(ref Graphics gr,int x,int y)
{
    int _ll = 7, _ww = 2;            
    gr.DrawLine(new Pen(Brushes.Red, _ww), x - _ll, y, x + _ll, y);
    gr.DrawLine(new Pen(Brushes.Red, _ww), x, y - _ll, x, y + _ll);
}

private void PictureBoxIpl1_Click(object sender, EventArgs e)
{
    MouseEventArgs me = (MouseEventArgs)e;
    int x=me.X,y=me.Y;
    int w = pictureBoxIpl1.Width, h = pictureBoxIpl1.Height;
    Bitmap p = (Bitmap)pictureBoxIpl1.BackgroundImage;
    int pw = p.Width, ph = p.Height;
    int cx = x * pw / w, cy = y * ph / h;

    var gr = pictureBoxIpl1.CreateGraphics();
    drawCross(ref gr, x, y);
    for (int i = 0; i < 900; i++)
    {
        isvisited[i] = new byte[900];
    }
    int idx = 0;
    for (int dx = -1; dx <= 1; dx++)
    {
        for (int dy = -1; dy <= 1; dy++)
        {
            if (dx == 0 && dy == 0)
            {
                continue;
            }
            if (dx * dy ==0)
            {
                dir[idx].X = dx;
                dir[idx].Y = dy;
                idx++;
            }
        }
    }
    dfs(ref p, x, y, ref gr);
}
private int rgb2gray(Color x)
{
    int R = x.R, G = x.G, B = x.B;
    return (R * 30 + G * 59 + B * 11 + 50) / 100;
}
private void dfs(ref Bitmap p,int x,int y,ref Graphics gr)
{

    int _step = 8;
    int pw = p.Width, ph = p.Height;
    int w = pictureBoxIpl1.Width, h = pictureBoxIpl1.Height;
    int cx = x * pw / w, cy = y * ph / h;
    if (rgb2gray(p.GetPixel(cx, cy))>150)
    {
        Random rnd = new Random();
        var startIdx = rnd.Next();
        isvisited[x][y] = 1;
        drawCross(ref gr, x, y);
        for(int i=0;i<8;i++)
        {
            int dx =  dir[(startIdx + i) % 4].X,dy = dir[(startIdx + i) % 4].Y;
            if (isvisited[x + _step * dx][y + _step * dy] == 0)
            {
                dfs(ref p, x + _step * dx, y + _step * dy, ref gr);
            }
        }
    }

}

已经将从起点开始的所有可达通路都标记出来,看出只有1条路是连到终点处的。接下来可以用bfs找最短路径。使用一个qNode结构保存坐标和路径(起点到当前坐标的所有路径),队列中的元素是qNode类型。

private void bfs(ref Bitmap p, int s_x, int s_y,ref Graphics gr)
{
    System.Drawing.Point[] pfarr;
    int _step = 12;
    int pw = p.Width, ph = p.Height;
    int w = pictureBoxIpl1.Width, h = pictureBoxIpl1.Height;
    int x , y , cx , cy ;

    Random rnd = new Random();
    queue Q1 = new queue();
    qNode curr;
    curr.x = s_x;
    curr.y = s_y;
    curr.path = String.Format("{0},{1}", curr.x, curr.y);
    isvisited[s_x][s_y] = 1;
    Q1.enqueue(curr);
    while(!Q1.isEmpty())
    {
        curr = Q1.dequeue();
        x = curr.x;
        y = curr.y;
        var oldPath = curr.path;
        cx = x * pw / w;
        cy = y * ph / h;
        if (192 < cx && cx < 372 &&
        149 < cy && cy < 391)
        {
            string[] posPair = oldPath.Split(';');
            pfarr = new System.Drawing.Point[posPair.Length];

            for(int k=0;k<posPair.Length;k++)
            {
                string[] pos = posPair[k].Split(',');
                pfarr[k].X = Convert.ToInt32(pos[0]);
                pfarr[k].Y = Convert.ToInt32(pos[1]);
            }
            gr.DrawCurve(new Pen(Brushes.Red,3), pfarr,0.6f);

            return;
        }
        var startIdx = rnd.Next();
        for (int i = 0; i < 4; i++)
        {
            int dx = dir[(startIdx + i) % 4].X, dy = dir[(startIdx + i) % 4].Y;
            if (isvisited[x + _step * dx][y + _step * dy] == 0)
            {
                cx = x * pw / w;
                cy = y * ph / h;
                if (rgb2gray(p.GetPixel(cx, cy)) > 150)
                {
                    isvisited[x][y] = 1;

                    curr.x = x + _step * dx;
                    curr.y = y + _step * dy;
                    curr.path = oldPath + String.Format(";{0},{1}", curr.x, curr.y);
                    Q1.enqueue(curr);
                }
            }
        }
    }
}

但是实际只能对比较短的有效,总路程太长用bfs会消耗很多时间还没有运行出结果。

即使得到了最短路也非常慢。不妨退一步,未必去找最短路,只要它是一条通路就行。从之前用dfs找出的那个唯一终点开始,探到中间的白色大矩形即结束。用带状态的dfs输出这个路径试一下,这次打标记用markHere()画个小圆点:

{
    gr.DrawEllipse(new Pen(Brushes.Gold, 3), x - 2, y - 2, 4, 4);
}
private bool dfs_withPath(ref Bitmap p, int x, int y, ref Graphics gr)
{

    int _step = 9;
    int pw = p.Width, ph = p.Height;
    int w = pictureBoxIpl1.Width, h = pictureBoxIpl1.Height;
    int cx = x * pw / w, cy = y * ph / h;
    if (193 < cx && cx < 374 &&
    149 < cy && cy < 395)
    {
        return true;
    }
    if (rgb2gray(p.GetPixel(cx, cy)) > 150)
    {
        Random rnd = new Random();
        var startIdx = rnd.Next();
        isvisited[x][y] = 1;
        for (int i = 0; i < 8; i++)
        {
            int dx = dir[(startIdx + i) % 4].X, dy = dir[(startIdx + i) % 4].Y;
            if (isvisited[x + _step * dx][y + _step * dy] == 0)
            {
                bool res = dfs_withPath(ref p, x + _step * dx, y + _step * dy, ref gr);
                if (res)
                {
                    markHere(ref gr, x , y );
                    return res;
                }
            }
        }
    }
    return false;

}

由于是随机探路,并且dfs并不一定到最短最短路,dfs的话只要这个路径最终能达到目的地就会返回true而将所经过的所有位置都打上标记,并且有些时候可能绕远路。为了省去那些远路,可以重复多次运行,看那些必经之路,则可以得到一个“较优解”。

找到这条路之后去游戏中发现迷宫只是俯视图,有一些铁箱子的通路,图上表现不出来。图上的位置可以跳到上层,里边有骑士之剑和骑士之盾。实际入口应该是在图上点对称的那边,移开铁箱子上楼梯才可以。

发表评论

电子邮件地址不会被公开。 必填项已用*标注