找出具有动画输出的迷宫求解器的最佳解决方案

Question

Abstract

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

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

Details

我是CE的第一个c ++ /算法类的cachelors。

正如我们一直在学习图形，dijkstra等，在看完Computerphile关于Maze解决的视频后，我决定最后几周，试图将理论付诸实践。

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

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

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

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

我还为传递给gif-library的每个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;
}

Problems

问题是，在缩放它们时需要花费很长的时间来进行扩展，即使使用50x50像素的“小”迷宫，当试图将它们缩放到300x300时也是如此。我花了很多时间使代码尽可能高效和快速，但在我添加了缩放之后，过去需要花费10分钟的代码，现在需要数小时。

在fltk中我使用Fl_Anim_Gif库来显示GIF动画，但是它不会加载已经放大的迷宫GIF（仍在对此进行故障排除）。

My real questions

是否有可能改进缩放功能，以便它不需要永远？或者这是一个完全错误的方法？

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

我只是熟悉fltk。现在使用像Qt这样的东西会更容易吗？从长远来看，就学习GUI库而言，这会更有益吗？

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

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

Answer 1

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

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