barebones pathfinding

pathfinding.js

function containsObject(obj, list) {
    var i;
    for (i = 0; i < list.length; i++) {
        if (list[i] === obj) {
            return true;
        }
    }

    return false;
}

function pathfind(from, to) {
    
    // Dijkstra's algorithm
    var path =  [];
    var traversed =  {};
    var distanceToThis =  0;

    traversed[from.name] = distanceToThis
    cameFrom = {}

    possibleExits = from.connections.slice()
    var iter = 0
    while (iter < possibleExits.length) {
        possibleExits = possibleExits.sort((a, b) => a[1] > b[1])
        var conn = possibleExits[iter]

        var distanceToThat = distanceToThis + conn[1]
        if (!containsObject(conn[0].name, Object.keys(traversed)))  {
            traversed[conn[0].name] = distanceToThat
            cameFrom[conn[0].name] = [conn[2].name, conn[3], conn[1]]
            if (to == conn[0]) {
                function getPath(conn, i) {
                    if (conn == from.name) {
                        return []
                    } else {
                        l = getPath(cameFrom[conn][0], i + 1)
                        l.push(cameFrom[conn])
                        return l
                    }
                }
                break;
            }


            path.push([conn[0], conn[3]])
            for (var i = 0; i < conn[0].connections.length; i++) {
                possibleExits.push([conn[0].connections[i][0], conn[0].connections[i][1] +distanceToThat, conn[0], conn[0].connections[i][3]])
            }
            path.pop()
        }


        iter++
    }
    if (to == undefined) {
        return undefined
    }
    var r = getPath(to.name)
    console.log(conn)
    r.push([conn[0].name, conn[3], conn[1]])
    return r
}

// Speed of each connection type in blocks per second
speedObj = {
  "ice": 40,
  "blue_ice": 70,
  "nether_ice": 320,
}

function getDistance(from, to) {
  return 4; // In the actual version of the map, this function would be longer
}

function connect(from, to, type) {
    from.connections.push([to, getDistance(from, to) / speedObj[type], from, type])
    to.connections.push([from, getDistance(from, to) / speedObj[type], to, type])
    from.connections.sort((el1, el2) => el1[1] > el2[1])
    to.connections.sort((el1, el2) => el1[1] > el2[1])
}

towns_example = ["London", "Paris", "Berlin", "Madrid"]
connections = {
  "ice": [
    ["London", "Paris"],
    ["Paris", "Berlin"],
    ["Madrid", "Paris"],
]
}

town_data = {}


for (var i = 0; i < towns_example.length; i++) {
    town_data[towns_example[i]] = {"name": towns_example[i], connections: []}
}

Object.keys(connections).forEach(function(type) {
    cities = connections[type]
    for (var i = 0; i < cities.length; i++) {
        connect(town_data[cities[i][0]], town_data[cities[i][1]], type)
    }
});

console.log(pathfind(town_data["Madrid"], town_data["London"]))