The long road to adjacency.

Posted on February 25, 2012 | 9 minute read

I am so fricking happy right now. I’m happy enough to take a commemorative picture of myself pointing at a screen. That’s how happy I am.

Adjacency

It took me two days to get this working. But it’s working.

Adjacency.

In a previous post I said that while the player was now able to select paths by clicking on nodes and then click Go to spawn entities that move to the destination entity, I’d have to figure out a way to specify or detect what nodes are adjacent to each other and only allow the player to click on those nodes. I’m drawing paths, you see, so they can’t just click all over the place.

Yesterday I sat down and scratched my head a lot. I had a jumble of ideas and none of them made any sense to me. It felt kind of like that moment where you wake up and barely remember a dream, but can’t seem to get a good hold on it. My brainstorming looked something like this:

Adjacency brainstorm

James suggested reading up on the Voronoi diagram and Delaunay triangulation, which I did. I learned a lot, even though I didn’t end up using them. Over the past two days I’ve just felt completely helpless and lost with this one issue. I had this jumble of potential solutions, but no idea how to implement them - to the point where I had no clue where to even put my code, whatever code that was going to be. The original idea was to find a list of points between each node and check if there was another node anywhere in that line. If not, the two points were adjacent.

I went into the Impact IRC channel to ask for advice about how to best approach this and the awesome Graphikos worked through a potential solution with me. He had a function that he slightly tweaked and explained to me. This function sounded like exactly what I was looking for - finding if there’s a node anywhere between two points. I went to sleep certain that I would make this solution work, but in the morning I wasn’t so confident that my original approach was the best option. Finding adjacent nodes dynamically not only seems like it would leave more room for error, but also seems like it would give me less control over my road placement (each node is the end of a road, as I think I mentioned before).

So all day today I’ve been walking around the house and writing random code snippets, completely fricking lost as to what I’m doing. I thought the path following stuff (selecting nodes etc) was the toughest part of this game, but no - this was (and I’m sure tomorrow something else will be, but whatever).

My mind kept wandering back to when Baz and I discussed adjacency lists. The problem was that I had no idea how to make an adjacency list or even where to put it. I then looked into adjacency matrices, but the same problem - this stuff was way over my head. I’m not a fricking programmer, I’m just stumbling along here - how the heck am I supposed to figure this out?

A small breakthrough

The good thing I noticed about being so stuck and working through it without asking someone who knows what they’re doing for help is that as you experiment and look into things, you learn basic stuff that you should really have learned earlier. And because there’s no one else around you’re kind of forced to make yourself comprehend it. As someone who’s self-learning I never had a proper introduction to things like passing arguments between functions. And then suddenly something clicked and I “got” it. I’m not saying my understanding isn’t shaky here, but I can now pass a variable from my node.js file to my player-controller.js file without having to declare a global variable. This means that I can likely do away with some of the globals I’ve been using all over the place! Not only did it get me closer to my adjacency goal, but having this click in my head will allow me to improve the rest of my code, too.

A second breakthrough

The second breakthrough was bigger. When looking up matrices I stumbled across a forum post about multidimensional arrays and tried creating one in my controller class.  I created the arrays in a new function called adjacencyList and triggered it when a node was clicked. It wasn’t doing anything to influence the state of the node itself, just printing to the console. And it ran! So now I had a function with three arrays (for three of my nodes in the level, just as a sample), each of which held IDs of their adjacent nodes (every entity in the level is assigned a unique ID, which is what I’m using to identify each instance of each entity).

And it worked! After a lot of fiddling around I now successfully had the adjacencyList function printing “Valid” or “Invalid” in the console depending on if it found an adjacent node in the relevant array or not.

I thought “Great! Now the rest will be easy. Just a matter of having the entity activate when it’s ‘Valid’”. I created an “active” attribute in the node entity and in the if statement that triggers the node selection added && this.active as a requirement. That should work…right?

Nope.

Several hours later and I was still ripping my hair out. For some reason the wrong instance of the entity was being activated. Not the one I just clicked, but the last instance in my list of adjacency arrays. I was at the end of my rope here. So close, and yet so far.

Another for loop and three arrays later…

I have no idea if this is a good way to do this. I have no idea if I’m missing something very simple. But I got it working and I got it working like this:

I created a for loop that loops through an array of every instance of every node and picks out the ID of the instance that matches the ID that I passed through to the adjacencyList function earlier (the one that was just clicked). It works!

The next minor problem was including the destination entity in the equation. The destination entity is the last one in the path (until it’s selected the player can’t press Go), but is a separate entity from the node. So in destination.js file I replicated the function call that I have in the node.js file and passed the destination entity’s ID just like I do with the node entity. Then, I created an array of destination entities just like the array with all of the nodes (even though there is only one destination entity…I’m sure I’m missing something that will make this more efficient later) and combined the two arrays into one all_nodes array.

It works!

So now it works. I can specify which nodes are adjacent to each other and have only those nodes be selectable.

Disadvantages

The biggest disadvantage I see to this is that I will have to specify adjacency arrays for every node in every level. The good news is that there won’t be that many nodes and that this does seem to give me more control over my paths.

The code

Finally, here’s my code…I commented the crap out of it as it confuses even me. Writing this took hours as I kept running into things I’ve missed and thinking of the next steps as I went, so if I’m afraid that if I don’t make enough comments for myself I will have no fricking idea what I wrote the next time I look at this:

[crayon title="player-controller.js”] /* LEVEL ADJACENCY DATA */

Matrix: function() { this.rows = new Array(); },

adjacencyList: function(id) { var m = new ig.game.playerController.Matrix(); // Manually define adjacent nodes for each node in each level. Integers are instance IDs. switch (ig.game.currentLevel){ case LevelMain: m.rows[12] = new Array (18, 14); m.rows[14] = new Array (12, 16); m.rows[16] = new Array (14, 17); m.rows[18] = new Array (18, 12); m.rows[19] = new Array (19, 20); m.rows[20] = new Array (19, 21); m.rows[21] = new Array (20, 22); m.rows[22] = new Array (21, 17); m.rows[17] = new Array (22, 16); break;

    default: console.log('Not in a level');
}

// The ID of the clicked instance is passed through from that node or destination entity. 
// Loop through every element in the array that corresponds with the clicked instance using the instance's ID
for (var i = m.rows[id].length-1; i >= 0; i--) {
    // If the loop finds an element ID that matches the ID of the last element in the path array, do this:
    if (m.rows[id][i] == ig.game.path_array[ig.game.path_array.length-1].id) {
        // Create arrays of all node and destination entities in the level, then join them into one array
        var node_entities = ig.game.getEntitiesByType( EntityNode );
        var destination_entities = ig.game.getEntitiesByType( EntityDestination );
        var all_nodes = node_entities.concat(destination_entities);
        // Loop through the one array 
        for (var j = all_nodes.length-1; j >=0; j--){
            // If the ID of one of these entities matches the id of the instance that was just clicked
            if (all_nodes[j].id == id) {
                // Activate that node:
                all_nodes[j].active = true;
            }
        }
        break;
    }
}

} [/crayon]

Then in both the node.js and destination.js clicked functions, I have this:

[crayon title="node.js”] clicked: function() { // Trigger function to check for adjacency, passing this instance’s ID to function. ig.game.playerController.adjacencyList(this.id);

    // If a base is clicked and this node is adjacent, do this:
    if (this.clickcount == 0 && ig.game.path_array.length > 0 && this.active) {
        // ...etc etc, do stuff and activate the node and such...

[/crayon]

So…it’s probably not very efficient, and most likely not the best way that I could have done this. But this is the way that works, which is better than what I had a few hours ago - no way at all. I’m sure it will change and be tweaked or maybe even completely scrapped down the line, but for now it does just what I need it to do and I learned an absolute crapload in the process, so I’m happy.




Categories:game dev dev games
comments powered by Disqus