时间戳

首页 > 解决方案 > 找出迷宫求解器的最佳解决方案，并带有动画输出

c++ - 找出迷宫求解器的最佳解决方案，并带有动画输出

问题描述

抽象的

我的最终目标是使用 Fltk 获取用户输入的像素，显示生成的迷宫（我自己的，或者从细节中提到的网站获取），然后显示动画解决方案。

这是我到目前为止所管理的： https ://giant.gfycat.com/VioletWelloffHatchetfish.webm

细节

我在 CE 学士学位的第一个 c++/算法课程中。

由于我们一直在学习图表、dijkstra 等。上周，我在观看了 Computerphile 的关于迷宫求解的视频后决定尝试将理论付诸实践。

起初我想从这个站点输出一个迷宫，http://hereandabove.com/maze/mazeorig.form.html，带有绘制的解决方案。我选择墙壁和路径应该是 1x1 像素，以便更容易制作成 2D 向量，然后是图形。

这很顺利，我的程序输出了一个已解决的 .png 文件，使用 dijkstra 查找最短路径。

然后我想把整个解决方案放在一个动画 gif 中。

这也很有效。对于它颜色为绿色/黄色的每个像素，它将一个 RGBA 向量传递给一个 gif 库，最后我得到了一个动画逐步解决方案。

我还为每个传递给 gif 库的 RGBA 向量，首先使用此函数将其放大：

//Both the buffer and resized buffer are member variables, and for each //plotted pixel in the path it updates 'buffer', and in this function makes a //larger version of it to 'resized_buffer'
// HEIGHT and WIDTH are the original size
// nHeight and nWidth are the new size.
bool Maze_IMG::resample(int nWidth, int nHeight)
{
    if (buffer.size() == 0) return false;
        
    resized_buffer.clear();
    
    
    for (int i = 0; i < nWidth * nHeight * 4; i++) resized_buffer.push_back(-1);

    double scaleWidth = (double)nWidth / (double)WIDTH;
    double scaleHeight = (double)nHeight / (double)HEIGHT;

    for (int cy = 0; cy < nHeight; cy++)
    {
        for (int cx = 0; cx < nWidth; cx++)
        {
            int pixel = (cy * (nWidth * 4)) + (cx * 4);
            int nearestMatch = (((int)(cy / scaleHeight) * (WIDTH * 4)) + ((int)(cx / scaleWidth) * 4));

            resized_buffer[pixel] = buffer[nearestMatch];
            resized_buffer[pixel + 1] = buffer[nearestMatch + 1];
            resized_buffer[pixel + 2] = buffer[nearestMatch + 2];
            resized_buffer[pixel + 3] = buffer[nearestMatch + 3];
        }
    }
    return true;
}

问题

问题是，在尝试将它们缩放到 300x300 时，即使是 50x50 像素的“小”迷宫，在放大它们时也需要很长时间才能做到这一点。我花了很多时间使代码尽可能高效和快速，但是在我添加缩放之后，过去需要 10 分钟的东西现在需要几个小时。

在 fltk 中，我使用 Fl_Anim_Gif 库来显示动画 gif，但它不会加载已按比例放大的迷宫 gif（仍在解决此问题）。

我的真实问题

是否可以改进缩放功能，使其不会永远花费？或者这是一个完全错误的方法？

尝试在 fltk 中将其显示为 gif 是否是一个愚蠢的想法，直接在 fltk 中绘制会更容易，还是我应该尝试在 fltk 中一个接一个地显示图像？

我只是让自己熟悉 fltk。现在使用 Qt 之类的东西会更容易吗？从长远来看，学习 GUI 库会更有益吗？

我这样做主要是为了学习，并在我毕业时开始建立某种投资组合。为此制作一个 gui 是否有益，还是浪费时间？

任何想法或意见将不胜感激。

标签： c++gifmazefltk

解决方案

无论您使用什么图形包，性能都会相似。这取决于你如何处理内部结构。例如，

  1. 如果将其写入缓冲区并将其 BLT 到屏幕，这将比直接写入屏幕更快。
  2. 如果你只在绘制事件上进行 BLT，它会比每次屏幕数据更改时强制和更新更快。
  3. 如果您预先分配缓冲区，则系统不必在缓冲区空间用完时继续重新分配。
  4. 假设空间是预先分配的，可以在不先清除的情况下写入。它将被写入的每个单元格，因此无需清除、分配和重新分配。

推荐阅读