3

I need some help in implementing a distance map in Python.

I have a binary Maze (1=walls, 0=free space) in numpy format in which I would like to implement a distance map which is outgoing from a certain point in the Maze. The distance maps shall not pass through walls.

The Maze that I have looks like this, whereby the distance map should be outgoing from the blue area. The binary map that I have

I think distance map should be evolving outgoing from the blue area and give every voxel in the maze a value which represents the shortest distance. To give you an idea, I think the distace map should be evolving in this way

Does anybody have an idea on how to implement this or maybe even code examples?

Thanks for every help!

I uploaded the numpy in the following WeTransfer link https://wetransfer.com/downloads/63800d0f06667fa7644a4a5d1a68fc5a20200121121741/744d2c

The starting point I use is (56,104)

VincentWin
  • 31
  • 4

2 Answers2

3

You can use a front which is propaging such as :

import matplotlib.pyplot as plt


def cond(x, y, max_x, max_y, maze):
    return 0 <= x < max_x and 0 <= y < max_y and maze[y][x] == 0

def neighbours(point, maze):
    max_x = len(maze[0])
    max_y = len(maze)
    x = point[0]
    y = point[1]

    list_neighbours = [(i, y) for i in (x - 1, x + 1) if cond(i, y, max_x, max_y, maze)] \
                      + [(x, j) for j in (y - 1, y + 1) if cond(x, j, max_x, max_y, maze)]

    return list_neighbours


maze = [
    [0, 0, 1, 1],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0]
]

start = (0, 0)
maze_copy = [[-1] * len(maze[0]) for _ in range(len(maze))]

front = [(0, 0)]
step = 0
while front:
    new_front = []
    for point in front:
        new_front += [p for p in neighbours(point, maze) if maze_copy[p[1]][p[0]] == -1]
        maze_copy[point[1]][point[0]] = step

    step += 1
    front = list(set(new_front))

print(maze_copy)
plt.imshow(maze_copy, cmap='hot', interpolation='nearest')
plt.show()

In the code, 1 represents walls, and 0 crossable parts. I made a copy of the maze to keep tracks to pixels already visited.

The idea is to have a front which will propagate and fill the maze_copy.

Which results in the following filling:

[0, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, -1, -1, -1]
[-1, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, 3, -1, -1]
[3, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, 3, 4, -1]
[3, 4, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, 3, 4, 5]
[3, 4, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, 6]
[2, 3, 4, 5]
[3, 4, -1, 6]

Final result

BlueSheepToken
  • 5,751
  • 3
  • 17
  • 42
  • And how could implement that length of the diagonal distance is worth sqrt(2)? – VincentWin Jan 20 '20 at 14:16
  • @Nathan, can you give me an input ? I cannot reproduce the problem with a loop It runs well on my side. – BlueSheepToken Jan 20 '20 at 14:18
  • @VincentWin Instead of having only the adjacent distances in `list_neighbours`, you could add the diagonal distances aswell, and update accordingly the `maze_copy`. It is kinda straight forward now – BlueSheepToken Jan 20 '20 at 14:19
  • @BlueSheepToken I made a mistake, nvm – Nathan Jan 20 '20 at 14:24
  • @BlueSheepToken, I tried to implement the diagonal with sqrt(2) but unfortunately I failed. Could you help me out here? Thank you very much. Your code already helped a lot :) Unfortunately the computational time is very long in my case, because my array is of size 120,120. You dont have an idea on how to reduce it? – VincentWin Jan 20 '20 at 15:34
  • @VincentWin I will give it a try later on, I am quite busy right now. And I did not profile my code, so I am not sure where exactly it is taking time. But `120*120` does not seem that much – BlueSheepToken Jan 20 '20 at 15:38
  • Thank you, that would be awesome, I will also try to solve it in the meantime! Yes, it is not so big, but it is already running for more than an hour. – VincentWin Jan 20 '20 at 15:54
  • @VincentWin if it has not finish in an hour, this is probably a bug. For a `120*120` I would expect it to run within a couple of minutes – BlueSheepToken Jan 20 '20 at 16:00
  • @BlueSheepToken, Yes it was a bug. I wanted to plt.show() every step So it filled up my memory. But even now that I run it without it takes very long. definetly not in the range of a couple of minutes. – VincentWin Jan 20 '20 at 16:40
  • @BlueSheepToken, I found the error... in the for loop the memory went to full, so i added changed one line a little bit and now it works in a couple of seconds.... new_front += [p for p in neighbours(point, maze, maze_copy) if maze_copy[p[1]][p[0]] == -1 and p not in new_front] – VincentWin Jan 20 '20 at 17:17
  • @VincentWin, nice one, I will update the answer accordingly (taking only uniqs elements as front). If that helped you, do not hesitate to accept the answer :) – BlueSheepToken Jan 21 '20 at 09:24
  • @BlueSheepToken, great. But I am still facing the problem that I would like to implement an diagonal move which should have a move length of sqrt(2). The problem here is that with every front multiple values would have to be given, not just the value of "step". Thanks for your help! – VincentWin Jan 21 '20 at 11:29
  • @BlueSheepToken, I also uploaded a link to the numpy maze in the question. The starting point I use is at point (56,104). Here is the link again https://wetransfer.com/downloads/63800d0f06667fa7644a4a5d1a68fc5a20200121121741/744d2c – VincentWin Jan 21 '20 at 12:22
  • @VincentWin Yeah right, I forgot this one ahah. I ll give it a shot soon. As a side note, you should avoid putting links in your question, it tends to unminify the example (like a maze as the one I provide seems enough, we do not need the full input) – BlueSheepToken Jan 21 '20 at 14:47
0

You can do this using this algorhytm:

  1. Set all distances to some large number, eg 9e99 except for the starting point (which obviously has distance 0).
  2. You loop over all cells, each cell gets the value of min(i + 1) for i in all adjacent cells (except walls)
  3. You repeat step number 2. untill no values change

A slightly more complex but faster approach would be to do the same, but only looping over cells adjacent to cells that were updated in the previous iteration

For example, my maze:

0, 0, 0
0, 1, 0
0, 1, 0

Here 1 is wall and 0 is non-wall. Top left is my starting point. Distances are:

 0, 9e9, 9e9
9e9, 9e9, 9e9
9e9, 9e9, 9e9

Iterate:

 0,   1, 9e9
 1, 9e9, 9e9
9e9, 9e9, 9e9

 0,   1, 2
 1, 9e9, 9e9
 2, 9e9, 9e9

 0,   1, 2
 1, 9e9, 3
 2, 9e9, 9e9

 0,   1, 2
 1, 9e9, 3
 2, 9e9, 4

 0,   1, 2
 1, 9e9, 3
 2, 9e9, 4

Stop

Nathan
  • 3,558
  • 1
  • 18
  • 38
  • The code is in `O(n^2*m)` with n represents the size of the maze, and m the number of steps. As a side note, you can use `float('inf')` instead of arbitrary large numbers – BlueSheepToken Jan 20 '20 at 13:17
  • @BlueSheepToken I'd write that as O(n^1.5) (n being the total number of pixels). If you implement the slightly more complex version it becomes O(n) – Nathan Jan 20 '20 at 13:54
  • If I understand well, my `n^2` is your `n`. I struggle to see where `n^0.5` comes from, could you provide a bit more details plz ? – BlueSheepToken Jan 20 '20 at 14:04
  • That sounds good! but how do I implement the stopping condition? And how could implement that length of the diagonal distance is worth sqrt(2)? – VincentWin Jan 20 '20 at 14:07
  • @BlueSheepToken the n^0.5 is your m, replacing it with the more complex approach (your `front`) removes it – Nathan Jan 20 '20 at 14:08
  • @VincentWin BlueSheepToken has the exact same approach but with actual code. – Nathan Jan 20 '20 at 14:08
  • @Nathan Why does the number of steps is `n^0.5` ? Btw, thanks for the add of a plot ! – BlueSheepToken Jan 20 '20 at 14:21
  • 1
    It's a square, so distance from one corner to the other is 2 * n^0.5 (if there are no loops) going to the left n^0.5 and down n^0.5 (if it's a square), obviously there are worst case scenarios, but this will be pretty accurate – Nathan Jan 20 '20 at 14:27