Add support for multiple-thread

[franva]

Hi there,

Thanks for this fantastic library. It solves my problem quite well.

I am following this example https://scikit-mpe.readthedocs.io/en/latest/examples.html#maze

It works well when the maze is small, but when working on a maze like the blow

It takes ages to finish its job.(Actually I started running the code 7 minutes before I submitted this issue and up until now, it's still running.)

Is it possible to make the code multi-threading?

one possible approach to make the maze path finding multi-threading is to at least launch 2 workers, one from start point to endpoint and one from end point to start point, once they meet each other, the path is found.

I am looking forward to your response.

Cheers,

Winston

[espdev]

@franva,

Thanks for reporting the issue. Could you give me the beginning and ending points in the maze? I want to profile the code. Although I roughly understand what the issue is. SciPy ODE solvers are slow because its code is pure Python. However, I want to make sure of this.

Relative to parallel code. In pure Python we can only use multiprocessing for CPU-bound tasks but not threading, because GIL. With multiprocessing also we have some limitations and overhead.

[franva]

Hi @espdev thanks for the timely response :)

Sorry, I should point out that the start and end points are those green arrows(yes, they are tiny!!!) on the image.

So the start point is on the top of the maze in the middle of the image and the end point is at the right bottom corner.

Hope this helps. Let me know if you could not find them.

Cheers,

Winston

[franva]

btw, I got the result of path finding on this maze.

It errors out, saying reaching 100000 seconds etc.

[espdev]

Why can't you use algorithms like A* for the task? In the case with a binary maze such algorithms would more effective.

Also you might consider specialized packages for solving maze problems. For example:

• https://github.com/mikepound/mazesolving
• https://github.com/jostbr/pymaze
• https://github.com/theJollySin/mazelib

[franva]

hi @espdev I have tried the 1st option, but with all different methods provided by the 1st option, they all failed.

I guess the reason could be that my maze picture is not perfectly aligned straight upwards, it's bit rotated and warped. Perssumingly, the 1st repo just considers the perfect maze image, thus it's not a robust solution for me. In this case, your repo is better.

Hopefully, the improved version could come out.

Cheers,

Winston

[espdev]

I tried a few experiments with your image.

It seems the following code works (on my machine it took around 8 seconds):

import time

import numpy as np
from skimage.io import imread
from skimage.exposure import rescale_intensity
from matplotlib import pyplot as plt

from skmpe import mpe, parameters, OdeSolverMethod

image_file = '114673282-5dfd8000-9d49-11eb-8f22-f7ac7fe66a89.png'

def main():
    img = imread(image_file, as_gray=True).astype(np.float_)
    spd_img = rescale_intensity(img, out_range=(0.0, 1.0))
    spd_img[spd_img < 0.5] = 0.0001

    start_point = (73, 799)
    end_point = (964, 1408)

    t1 = time.monotonic()

    with parameters(
            ode_solver_method=OdeSolverMethod.RK23,
            integrate_min_step=1.0,
            integrate_max_step=2.0,
            integrate_time_bound=100000) as p:
        print(p)
        result = mpe(spd_img, start_point, end_point)

    t2 = time.monotonic() - t1
    print('elapsed time:', t2)

    plt.imshow(spd_img, cmap='gray')
    plt.plot(result.path[:, 1], result.path[:, 0], '-r', linewidth=2)
    plt.plot(*start_point[::-1], 'oy')
    plt.plot(*end_point[::-1], 'og')
    plt.axis('off')
    plt.show()

if __name__ == '__main__':
    main()

For the algorithm it is very important how the speed image was calculated and its values. Also we may also need to tune some parameters: ODE solver method, integration step and integration time bound. You might experiment with it if you want.

PS: It seems to me "be unique" phrase is encoded in the maze. :)

[franva]

btw, I found that it's super hard to deploy my project to pretty much any cloud platform, due to the use of scikit-fmm which is a dependency of scikit-mpe.

I have created a SOF question: https://stackoverflow.com/questions/67135650/no-where-to-deploy-python-flask-api-project

Hopefully you could help. thanks,

Winston

[espdev]

@franva,

scikit-fmm contains C-extension modules which require C-compiler for building (usually gcc on Linux) (If you install the module from the sources). There are no any manylinux prebuilt wheel packages for scikit-fmm on PyPI, so the package requires the compilation of C-extensions while installing. Please check your environment and installed required -dev packages. You might check python3-dev firstly. Also you might enable verbose mode of pip install (pip install -vvv scikit-fmm) to print more logs/info about the installation process.