Freeze when trying to add an object to a list

ID:2348089
 
Feb 23 2018, 2:16 am
Problem description:
I was trying to calculate mob's distance to a certain tile using breadth-first search, but when I click a mob the proccess freezes. Through some further testing I found out that it has something to do with the line which adds the node to the queue list(If all 4 lines are commented out, the code runs fine). I'm unable to see the reason behind that freeze, but I suspect it might be infinite recursion I somehow missed, any ideas?

P.S. the breadth-first search algorithm is adapted from the Forum_Account's region library.

Code:
var
    map_size_x = 10
    map_size_y = 10

mob/Click()
    var/map = new /list(map_size_y, map_size_x)

    //Init
    for(var/i = map_size_y, i >= 1, i--)
        for(var/j = 1, j <= map_size_x, j++)
            if(src.x == j && src.y == i)
                map[i][j] = "S"
            else
                map[i][j] = -1
    usr << "init complete"
    ShowArray(map)

    //Breadth-first search
    var/node/source = new /node //source node
    source.loc_x = src.x
    source.loc_y = src.y
    var/list/visited = list() //Visited nodes
    var/list/queue = new/list()//Queue to expand
    queue.Add(source)

    usr << "preparations complete"

    while(queue.len)
        var/node/N = queue[1] //Grab the first node
        usr << "first node acquired"
        queue.Cut(1, 2)
        usr << "queue cut"

        //
        if(N.loc_x + 1 <= map_size_x)
            var/node/Ne = new /node
            Ne.loc_x = N.loc_x + 1
            Ne.loc_y = N.loc_y
            Ne.dist = N.dist + 1
            Ne.name = "[Ne.loc_x] [Ne.loc_y] [Ne.dist]"
            map[Ne.loc_y][Ne.loc_x] = Ne.dist
            if(!visited[Ne])
                visited[Ne] = 1
                queue += Ne
            usr << "eastern neighbour calculated"
        if(N.loc_x - 1 >= 1)
            var/node/Nw = new /node
            Nw.loc_x = N.loc_x - 1
            Nw.loc_y = N.loc_y
            Nw.dist = N.dist + 1
            Nw.name = "[Nw.loc_x] [Nw.loc_y] [Nw.dist]"
            map[Nw.loc_y][Nw.loc_x] = Nw.dist
            if(!visited[Nw])
                visited[Nw] = 1
                queue += Nw
            usr << "western neighbour calculated"
        if(N.loc_y + 1 <= map_size_y)
            var/node/Nn = new /node
            Nn.loc_x = N.loc_x
            Nn.loc_y = N.loc_y + 1
            Nn.dist = N.dist + 1
            Nn.name = "[Nn.loc_x] [Nn.loc_y] [Nn.dist]"
            map[Nn.loc_y][Nn.loc_x] = Nn.dist
            if(!visited[Nn])
                visited[Nn] = 1
                queue += Nn
            usr << "northern neighbour calculated"
        if(N.loc_y - 1 >= 1)
            var/node/Ns = new /node
            Ns.loc_x = N.loc_x
            Ns.loc_y = N.loc_y - 1
            Ns.dist = N.dist + 1
            Ns.name = "[Ns.loc_x] [Ns.loc_y] [Ns.dist]"
            map[Ns.loc_y][Ns.loc_x] = Ns.dist
            if(!visited[Ns])
                visited[Ns] = 1
                queue += Ns
            usr << "southern neighbour calculated"
        for(var/node/NN in visited)
            usr << "NN=[NN] visited\[NN]=[visited[NN]]"
    ShowArray(map)

proc/ShowArray(var/list/A)
    for(var/i = map_size_y, i >= 1, i--)
        var/line = ""
        for(var/j = 1, j <= map_size_x, j++)
            line += "[A[i][j]] "
        usr << line
    usr << ""

node
    parent_type = /obj
    var
        loc_x
        loc_y
        dist = 0
Feb 23 2018, 11:44 am (Edited on Feb 24 2018, 12:55 am)
Definitely an infinite loop. Your nodes are always being detected as unique by your if(!visited) statements because you're checking for the newly made node, not if one already existed there. Your code can also check the same tile multiple times, but the dist value can be different the next time it's checked. To solve both of these I removed dist from the name you generate and used the name as an association. Example:

Nn.name = "[Nn.loc_x] [Nn.loc_y]"
map[Nn.loc_y][Nn.loc_x] = Nn.dist
if(!visited[Nn.name])
    visited[Nn.name] = 1
    queue += Nn


9 10 9 8 7 6 5 4 3 2
10 9 8 7 6 5 4 3 2 3
11 10 9 8 7 6 5 4 3 4
12 11 10 9 8 7 6 5 4 5
13 12 11 10 9 8 7 6 5 6
14 13 12 11 10 9 8 7 6 7
15 14 13 12 11 10 9 8 7 8
16 15 14 13 12 11 10 9 8 9
17 16 15 14 13 12 11 10 9 10
16 17 16 15 14 13 12 11 10 9

That's the result I got standing in the very top right. If that's the result you were looking for, I don't know. My goal was just to solve your freeze problem. :)
Feb 25 2018, 3:49 am
In response to Reformist
Thank you! The end result wasn't exactly what I needed, but now that the infinite loop is gone, I managed to get it to what I needed it to be, which is something like this: http://prntscr.com/ijgyel