Skip to content

Instantly share code, notes, and snippets.

@FranchuFranchu
Created December 5, 2019 23:20
Show Gist options
  • Save FranchuFranchu/e68f8e76ae05e3d3bd07d5ef8afb3316 to your computer and use it in GitHub Desktop.
Save FranchuFranchu/e68f8e76ae05e3d3bd07d5ef8afb3316 to your computer and use it in GitHub Desktop.
barebones pathfinding
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"]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment