Traversing a list of objects that connect to each other in multiple ways

Question

I have an array full of objects, where each object has "exits" leading to other objects in the array. I was wondering how to traverse these items and "follow" each exit.

The basic idea is to create a "map" of the objects in the Array.

Basically, each object is thus (cut down to only show the important parts):

{
    id: 0,
    name: "stary sobor",
    n: -1,
    s: 3,
    e: 1,
    w: -1,
    u: -1,
    d: -1,
}

Essentially, I would like an algorithm to follow any direction (n, s, e, w, u, d) that is greater than -1.

I have tried to map it out myself but I get very confused about what happens when an object has more than one exit.

Here's my fiddle: http://jsfiddle.net/8kxrp/2/

Essentially I would like to traverse the array and output a square on the canvas for each area - so, if area1 has an "exit" east then I'd like to show a square to the right of area1 etc.

Answer 1

You are traversing a graph. The key points here are:

1. You can get to a certain "room" in more than one way; so you need to keep track of which rooms you already visited so you don't try to follow their exits again.
2. Since each room has multiple exits, you need to visit one of them at time while remembering to come back and try the others later.

One simple way is to use recursion to visit all the exits, while storing some flag on rooms you already visited:

var visitRoom = function(rooms, roomId) {
  if (roomId === -1)
    return;

  var room = rooms[roomId];
  if (room.visited)
    return;

  room.visited = true;
  doSomethingWithRoom(room);

  visitRoom(rooms, room.n);
  visitRoom(rooms, room.e);
  visitRoom(rooms, room.s);
  visitRoom(rooms, room.w);
  visitRoom(rooms, room.u);
  visitRoom(rooms, room.d);  
};

visitRoom(rooms, 0); // assuming you're starting at the first room

The problems here are:

• Storing room.visited is a little messy, since it pollutes the original data with intermediate state required by the traversal algorithm.

• This code assumes each room's ID is equal to its index in the array. If this is not the case, you'd want to find a way to get a room by its ID. A map between room IDs and the room objects is more useful in this case than an array.

• A recursive approach would exhaust the stack memory in large-enough maps. This can be remedied by using an iterative approach where instead of visiting a room by recursion, you add its ID to a list of rooms-to-visit, then continually visit the first room in the list until it's empty. Keeping a list of unvisited rooms takes less memory than storing the stack frame for the recursive call.

Here's another approach, which addresses these issues:

var visitAll = function(rooms) {
  var toVisit = [0];
  var visited = {};

  while (toVisit.length > 0) {
    var roomId = toVisit.pop();

    var room = findRoomById(rooms, roomId); 

    doSomethingWithRoom(room);
    visited[roomId] = true;

    ["n", "s", "e", "w", "u", "d"].forEach(function(exit) {
      var exitId = room[exit];
      if (exitId !== -1 && !visited[exitId])
        toVisit.push(exitId);
    });    
  }
}

var findRoomById = function(rooms, roomId) {
  // do whatever you need to find the room with the correct ID
  return rooms[roomId]; 
}

var doSomethingWithRoom = function(room) {
  // do what you want here; this will be called once per visited room
}

visitAll(rooms);

If you also want to keep track of the spatial coordinates of each room, you could do that too by assigning each room its location when you first encounter it, based on the coordinates of the previous room and the direction of the exit you followed.

Answer 2

It really depends on how you WANT to handle multiple exits.

var dirs = ["n", "e", "s", "w", "u", "d"];
var visited = {};
for(var i = 0; i < Areas.length; i++){
  for (var j = 0; j < dirs.length; j++) {
    if(Areas[i][dirs[j]] > -1){
      doSomething(array[i].id, dirs[j], array[i][dirs[j]);
    }
  };
}

function doSomething(roomID, exitDirection, exitID){

  //Called for every exit for every room.

  if(visited[exitID]!== true){
    visited[exitID] = true;

    //Do whatever unique stuff you want to do here.
    //This will get called for every new exit room but you may not want that if you're building doors or something.
  }      
}

Answer 3

http://jsfiddle.net/8kxrp/5/

This will add to each element an "others" field, structured multidimensional Object with all reachable elements step by step, and an allothers array with a plain list of reachable elements.

var Chernarus = [
    {
        id: 0,
        name: "stary sobor",
        description: "",
        smell: "",
        objects: [],
        items: [],
        clothes: [],
        food: [],
        barricades: [],
        n:-1,s:3,e:1,w:-1,
        u:-1,d:-1,
        z:0,
        bg:"img/centre.jpg"
    },{
        id: 1,
        name: "novy sobor",
        description: "",
        smell: "",
        objects: [],
        items: [],
        clothes: [],
        food: [],
        barricades: [],
        n:-1,s:2,e:-1,w:0,
        u:-1,d:-1,
        z:0,
        bg:"img/centre.jpg"
    },{
        id: 2,
        name: "mogilevka",
        description: "",
        smell: "",
        objects: [],
        items: [],
        clothes: [],
        food: [],
        barricades: [],
        n:1,s:3,e:-1,w:-1,
        u:-1,d:-1,
        z:0,
        bg:"img/centre.jpg"
    },{
        id: 3,
        name: "dubky",
        description: "",
        smell: "",
        objects: [],
        items: [],
        clothes: [],
        food: [],
        barricades: [],
        n:2,s:4,e:-1,w:-1,
        u:-1,d:-1,
        z:0,
        bg:"img/centre.jpg"
    },{
        id: 4,
        name: "novo selky",
        description: "",
        smell: "",
        objects: [],
        items: [],
        clothes: [],
        food: [],
        barricades: [],
        n:3,s:5,e:-1,w:-1,
        u:-1,d:-1,
        z:0,
        bg:"img/centre.jpg"
    },{
        id: 5,
        name: "chernogorsk",
        description: "",
        smell: "",
        objects: [],
        items: [],
        clothes: [],
        food: [],
        barricades: [],
        n:4,s:-1,e:-1,w:6,
        u:-1,d:-1,
        z:0,
        bg:"img/centre.jpg"
    }
];

var toCheck=["n","s","e","w"];
var maxSteps=100;

function getOthers(element,recursion,alreadyDone,alreadyArr) {

    if(recursion>maxSteps) return "TOO MANY:INFINITE?";
    if(Chernarus[element]==undefined)  return "NOT FOUND: "+element;
    var item=Chernarus[element];
    if(alreadyDone[element]!=undefined) return element+" ALREADY DONE";
    alreadyDone[element]=true;
    alreadyArr.push(element);
    var out={};
    for (var ch=0;ch<4;ch++) {
        var tc=toCheck[ch];
        var dir=item[toCheck[ch]];
        if(dir>0) {
            out[tc]={pos:dir,others:getOthers(dir,recursion+1,alreadyDone,alreadyArr)};
        }
    }
    return out;
}


for (var i=0;i<Chernarus.length;i++) {
    var allothers=[]
    Chernarus[i]['others']=getOthers(i,1,[],allothers);
    Chernarus[i]['allothers']=allothers;
}







alert(dump(Chernarus,""));

function dump(obj,spc) {
    if(obj==undefined) return "<undefined>";
    if((typeof obj)=="object") { // obj instanceof Array || obj.toString()=="[object Object]"
        var out="";
        for(var it in obj) if(obj.hasOwnProperty(it)) {
            out+=spc+it+"= {\n";
            out+= dump(obj[it],spc+"    ");
            out+=spc+"}\n";
        }
        return out;
    } else return spc+(obj.toString())+"\n";
}