65.9K
CodeProject 正在变化。 阅读更多。
Home

Lee 算法迷宫求解器

Shao Voon Wong
starIconstarIconstarIconstarIconstarIcon

5.00/5 (9投票s)

2019年12月22日

CPOL

8分钟阅读

viewsIcon

26456

downloadIcon

1074

MFC 和 Direct2D 中的 Lee 算法迷宫求解器。

目录

screenshot

引言

1999年，我的团队在新加坡机器人比赛(SRG)中赢得了避障机器人(OAR)的一等奖。那已经是20年前了。我没有OAR的照片，但它看起来非常像微型鼠。微型鼠的迷宫是用墙壁构建的，而OAR的迷宫是用障碍物构建的。我们学校的微型鼠和OAR团队都使用 Lee算法 来解决迷宫。Lee算法在20世纪60年代用于路由单层印刷电路板(PCB)，直到Google将其用作面试技术测试，它才在历史上留下了印记。我必须指出，根据我对算法的回忆，维基百科页面和热图中的描述似乎有些问题，按理说，热图在障碍物周围应该会发生变化。Lee算法是一个非常简单的算法，机器人从高值单元格移动到低值单元格。每个单元格的值由其4个相邻单元格的最小值加1确定。不考虑对角线单元格的值。

绿色单元格是起点，黄色单元格是终点。程序无法看到整个障碍物地图。它在探索过程中会更新地图中的障碍物信息。当点击开始按钮时，有两个运行过程：第一个是迷宫求解模式，第二个是优化路径模式。优化路径可能不是最短路径，因为如我所说，它没有完整的地图，优化路径是基于它之前探索过的路径。

最初在20年前用Turbo C++编写的模拟器是DOS版本的。这次，我用MFC和Direct2D写了一个Windows版本。Direct2D用起来令人惊讶地直观。文章的前半部分解释了Lee算法，后半部分讲解了Direct2D代码。

Lee算法用于迷宫求解

选择一个最大值 m 来表示障碍物，例如 0xFF，而未被占用的单元格的默认值是 m-1。为什么是 0xFF？最大值取决于你的迷宫的单元格尺寸，或者(如果是PCB布线，则为网格)。一个16x16单元格的迷宫将是16*16=256(0x100)。换句话说，选择一个在任何情况下都不可能超过的最大值。选择 0xFF 是因为嵌入式硬件的限制，因为二维数组是由 unsigned char 组成的，这是由于主板RAM有限。

  1. 将当前机器人设置在 cell[0][15]。
  2. 将目标单元格 cell[12][3] 的值设置为 0。
  3. 在移动到下一个单元格之前，执行以下步骤来确定下一个单元格。
  4. 将 changed 变量设置为 false。
  5. 如果单元格未被障碍物占据，则将所有空单元格初始化为 m-1。
  6. 对每个空单元格执行以下操作，即跳过被障碍物占据的单元格。通过找到相邻单元格(上、下、左、右)的最小值并加一来计算当前单元格的值，如果新值不等于当前值，则将 changed 设置为 true。将新值设置为单元格的值。
  7. 如果 changed 为 true，则重复步骤4到7，否则执行步骤8。
  8. 移动到具有最小值的下一个相邻单元格。
  9. 如果当前单元格是目标单元格 cell[12][3]，则停止，否则从步骤3开始。

上述伪代码未记录一些默认行为。如果前方单元格与左侧或右侧单元格具有相同的最小值，则倾向于直线前进而不是转弯。如果左侧或右侧单元格具有相同的最小值，则倾向于右转。这些默认设置没有对错之分，取决于迷宫。机器人可能右转导致死胡同，而左转可能导向终点。无论你选择哪种默认行为，都要坚持下去。

这是一个部分加权图(完整地图太大无法显示)，地图中除目标单元格外，所有其他单元格均初始化为 0xFE，而目标单元格设置为 0x00。

FE|FE|FE|FE|FE|FE|FE
FE|FE|FE|FE|FE|FE|FE
FE|FE|FE|FE|FE|FE|FE
FE|FE|FE|00|FE|FE|FE
FE|FE|FE|FE|FE|FE|FE
FE|FE|FE|FE|FE|FE|FE
FE|FE|FE|FE|FE|FE|FE

初始化地图后，通过获取所有相邻单元格并找到它们之间的最小值，加一并将其设置为当前单元格的值来计算加权。生成的(部分)加权图如下所示。

06|05|04|03|04|05|06
05|04|03|02|03|04|05
04|03|02|01|02|03|04
03|02|01|00|01|02|03
04|03|02|01|02|03|04
05|04|03|02|03|04|05
06|05|04|03|04|05|06

如果存在此迷宫求解器无法解决的迷宫，请将其保存并发送给我，或在此论坛上给我留言。当然，如果你完全用障碍物围住黄色目标单元格，它将永远运行下去，直到你停止它。以下是当目标单元格被障碍物(用 0xFF 表示)包围时的加权图。

FE|FE|FE|FE|FE|FE|FE
FE|FE|FE|FE|FE|FE|FE
FE|FE|FF|FF|FF|FE|FE
FE|FE|FF|00|FF|FE|FE
FE|FE|FF|FF|FF|FE|FE
FE|FE|FE|FE|FE|FE|FE
FE|FE|FE|FE|FE|FE|FE

重要说明

经典Lee算法文献与本文的区别在于，起点和终点被互换了。经典论文说将起点设置为零，而不是终点。这就是为什么我使用目标单元格而不是终点来避免混淆。在PCB布线中，没有真正的起点和终点的概念，算法只是试图连接两个端点。

Direct2D 代码

在本节中，我们将检查使用的Direct2D代码。Direct2D、DirectWrite和Windows图像组件(WIC)是从头开始设计的，用于取代老化的GDI+，它们的方法调用非常直观，唯一的抱怨是类名有时非常冗长，这是描述性强所带来的副作用。Direct2D和DirectWrite基于组件对象模型(COM)，但不需要 CoInitialize() 和 CoUninitialize() 调用。这个例外规则不适用于WIC，它需要COM运行时。在这个迷宫求解器应用程序中，我们只使用Direct2D，因为不需要文本和图像渲染。要使用Direct2D，我们需要Windows运行时库(WRL)的 ComPtr 智能指针，它在某种程度上类似于ATL的 CComPtr (注意额外的 C 前缀)，它们都通过增加引用计数来保持COM对象存活，通过 IUnknown 接口的 AddRef()，并在引用计数减到零后通过 Release() 销毁它。下面是应用程序所需的头文件列表。

#include <wrl.h>              // Windows Runtime Library for its ComPtr
#include <d2d1.h>             // Direct2D v1 header
#include <stdexcept>          // C++ exception class

#include "ComException.h"
#include "FactorySingleton.h" // Singleton to get Direct2D factories

接下来，我们导入Direct2D库进行链接。

// Direct2D import libraries
#pragma comment(lib, "d2d1")

我们有一个 FactorySingleton 来限制 ID2D1Factory 实例只有一个。

using namespace D2D1;
using namespace Microsoft::WRL;

class FactorySingleton
{
public:
    static ComPtr<ID2D1Factory> GetGraphicsFactory();
private:
    static ComPtr<ID2D1Factory> m_GraphicsFactory;
};

如果 m_GraphicsFactory 是 nullptr，FactorySingleton::GetGraphicsFactory() 会创建工厂。

#include "FactorySingleton.h"

ComPtr<ID2D1Factory> FactorySingleton::m_GraphicsFactory;

ComPtr<ID2D1Factory> FactorySingleton::GetGraphicsFactory()
{
    if (!m_GraphicsFactory)
    {
        D2D1_FACTORY_OPTIONS fo = {};

#ifdef DEBUG
        fo.debugLevel = D2D1_DEBUG_LEVEL_INFORMATION;
#endif

        HR(D2D1CreateFactory(D2D1_FACTORY_TYPE_SINGLE_THREADED,
            fo,
            m_GraphicsFactory.GetAddressOf()));

    }
    return m_GraphicsFactory;
}

接下来是 ComException 和 TestResult 的声明。

#include <Windows.h>
#include <string>

void TestResult(const char* expression, HRESULT hr);

struct ComException
{
    HRESULT const hr;
    std::string where;
    ComException(const char* expression, HRESULT const value) : where(expression), hr(value) {}
    std::string Message() const;
};

定义了 TestResult() 和 ComException::Message() 的主体。TestResult() 实际上在 HR 宏中使用，用于检查失败的 HRESULT。

#include "ComException.h"

void TestResult(const char* expression, HRESULT hr)
{
    if (FAILED(hr)) throw ComException(expression, hr);
}

std::string ComException::Message() const
{
    char buf[800];
    memset(buf, 0, sizeof(buf));
    sprintf_s(buf, "ComException hr:%x, Where:%s", hr, where.c_str());
    std::string str = buf;
    return str;
}

// Macro to test HRESULT and throw ComException for failed HRESULT
#define HR(expression) TestResult(#expression, (expression));

接下来，我们使用 ComPtr 智能指针声明渲染 target(RT) 成员对象和画笔。要在Direct2D中绘制内容，我们需要至少一个渲染目标。但为什么有两个渲染目标呢？m_BmpTarget 是基于位图的离屏RT。当绘制到 m_DCTarget 时，用户可能会看到不完整或部分的绘制，因此所有内容都绘制在离屏的 m_BmpTarget 上，然后 m_DCTarget 会 DrawImage() 这个位图。

ComPtr<ID2D1DCRenderTarget> m_DCTarget;
ComPtr<ID2D1BitmapRenderTarget> m_BmpTarget;

ComPtr<ID2D1SolidColorBrush> m_BmpBlackBrush;
ComPtr<ID2D1SolidColorBrush> m_BmpWhiteBrush;
ComPtr<ID2D1SolidColorBrush> m_BmpYellowBrush;
ComPtr<ID2D1SolidColorBrush> m_BmpGreenBrush;
ComPtr<ID2D1SolidColorBrush> m_BmpRedBrush;

Direct2D的设备相关资源，如画笔，与RT绑定。你不能在另一个RT上使用从一个RT创建的资源。CreateDeviceResources() 是一个创建画笔的函数。调用 ReleaseAndGetAddressOf() 来释放COM对象，并在一个指针的指针参数中返回 ComPtr 封装的原始指针成员的地址，因为即将创建一个新的 brush 对象并分配给这个参数。

void CreateDeviceResources(
    ID2D1RenderTarget* target, 
    ComPtr<ID2D1SolidColorBrush>& brush, 
    D2D1_COLOR_F color)
{
    HR(target->CreateSolidColorBrush(color,
        brush.ReleaseAndGetAddressOf()));
}

接下来，展示了 m_DCTarget 和 m_BmpTarget 的创建。我们需要将 pixelFormat 指定为 DXGI_FORMAT_B8G8R8A8_UNORM，以便与GDI的设备上下文(DC)格式兼容。这就是 m_DCTarget 渲染到DC的原因。Get() 用于返回 ComPtr 智能指针封装的RT的内部原始指针。

// Create a pixel format and initial its format
// and alphaMode fields.
// https://docs.microsoft.com/en-gb/windows/win32/direct2d/
// supported-pixel-formats-and-alpha-modes#supported-formats-for-id2d1devicecontext
D2D1_PIXEL_FORMAT pixelFormat = D2D1::PixelFormat(
    DXGI_FORMAT_B8G8R8A8_UNORM,
    D2D1_ALPHA_MODE_PREMULTIPLIED
);

D2D1_RENDER_TARGET_PROPERTIES props = D2D1::RenderTargetProperties();
props.pixelFormat = pixelFormat;

HR(FactorySingleton::GetGraphicsFactory()->CreateDCRenderTarget(&props,
    m_DCTarget.ReleaseAndGetAddressOf()));

m_DCTarget->BindDC(pDC->GetSafeHdc(), &rect);

HR(m_DCTarget->CreateCompatibleRenderTarget(m_BmpTarget.ReleaseAndGetAddressOf()));

m_BmpTarget->SetAntialiasMode(D2D1_ANTIALIAS_MODE_PER_PRIMITIVE);
m_BmpTarget->SetTextAntialiasMode(D2D1_TEXT_ANTIALIAS_MODE_CLEARTYPE);

CreateDeviceResources(m_BmpTarget.Get(), m_BmpBlackBrush, COLOR_BLACK);
CreateDeviceResources(m_BmpTarget.Get(), m_BmpWhiteBrush, COLOR_WHITE);
CreateDeviceResources(m_BmpTarget.Get(), m_BmpYellowBrush, COLOR_YELLOW);
CreateDeviceResources(m_BmpTarget.Get(), m_BmpGreenBrush, COLOR_GREEN);
CreateDeviceResources(m_BmpTarget.Get(), m_BmpRedBrush, COLOR_RED);

如果你一直在想画笔的颜色是如何定义的，它们列在下面。D2D_COLOR_F 的颜色通道是RGBA格式，使用 float 类型。

D2D_COLOR_F const COLOR_WHITE = { 1.0f,  1.0f,  1.0f,  1.0f };
D2D_COLOR_F const COLOR_BLACK = { 0.0f,  0.0f,  0.0f,  1.0f };
D2D_COLOR_F const COLOR_YELLOW = { 0.99f, 0.85f, 0.0f,  1.0f };
D2D_COLOR_F const COLOR_GREEN = { 0.0f,  1.0f,  0.0f,  1.0f };
D2D_COLOR_F const COLOR_RED = { 1.0f,  0.0f,  0.0f,  1.0f };

要绘制一条白线，需要调用 DrawLine()，并提供一个起点、一个终点和一个白色画笔。

D2D1_POINT_2F p0{ 0.0f, sum };
D2D1_POINT_2F p1{ 50.0f, sum };
m_BmpTarget->DrawLine(p0, p1, m_BmpWhiteBrush.Get());

要绘制一个白色的障碍物，需要调用 FillRectangle()，并提供一个矩形和一个白色画笔。

auto rectTarget = RectF(0.0f, 0.0f, 10.0f, 10.0f);
m_BmpTarget->FillRectangle(&rectTarget, m_BmpWhiteBrush.Get());

避障机器人由一个绿色圆圈表示。要绘制一个圆形的椭圆，需要使用一个中心点和两个相等的 radiusX 和 radiusY 值来初始化 D2D1_ELLIPSE。然后将 D2D1_ELLIPSE 对象连同其画笔一起传递给 FillEllipse()。

D2D1_ELLIPSE ell;
ell.point = Point2F(5.0f, 5.0f);
ell.radiusX = 3.0f;
ell.radiusY = 3.0f;
m_BmpTarget->FillEllipse(ell, m_BmpGreenBrush.Get());

接下来，我们准备实现 OnPaint() 函数。如果 m_DCTarget 是 nullptr，CreateDCTarget() 会同时创建 m_DCTarget 和 m_BmpTarget。在任何绘图调用之前必须调用 BeginDraw()，在所有绘图调用完成后必须调用 EndDraw()。DrawMap() 和 DrawObstacles() 在 m_BmpTarget 上执行。然后 m_DCTarget 与DC绑定，这是每次 OnPaint() 调用都必须执行的操作。在 m_DCTarget 的 BeginDraw() 和 EndDraw() 之间，m_DCTarget 绘制 m_BmpTarget 的内部位图。如果 EndDraw() 因 D2DERR_RECREATE_TARGET 而失败，则重置 m_DCTarget (表示销毁)，Invalidate() 发送 WM_PAINT 消息，使 OnPaint() 再次被调用，此时 m_DCTarget 为空(将被重新创建)。

CPaintDC dc(this);
if (!m_DCTarget)
{
    CreateDCTarget(&dc);
}

ComPtr<ID2D1Bitmap> bitmap;
m_BmpTarget->GetBitmap(bitmap.GetAddressOf());

CRect rectClient;
GetClientRect(&rectClient);

RECT rect;

rect.top = 0;
rect.bottom = rectClient.Height();
rect.left = SHIFT_LEFT;
rect.right = rectClient.Width();

m_BmpTarget->BeginDraw();
DrawMap();
DrawObstacles();
m_BmpTarget->EndDraw();

m_DCTarget->BindDC(dc.GetSafeHdc(), &rect);

m_DCTarget->BeginDraw();

m_DCTarget->DrawBitmap(bitmap.Get());

if (D2DERR_RECREATE_TARGET == m_DCTarget->EndDraw())
{
    m_DCTarget.Reset();
    Invalidate();
    return;
}

最低操作系统应为Windows 7及以上版本，因为没有使用Windows 8及以上版本Direct2D的功能。玩这个程序玩得开心！

代码托管在 GitHub。

参考文献

历史

  • 2024-03-04: 修复了优化路径，提供了障碍物地图的完整视图。
  • 2021-12-04: 添加了10个新的可下载迷宫。注意: 优化路径基于第一次遍历的路径，可能存在未发现的更优路径。机器人没有完整的地图视图。
  • 2020-01-01: 添加了“重要说明”部分
  • 2019-12-22: 首次发布
© . All rights reserved.