What kind of data structure is good for decision trees?

A decision tree is a branching structure in which decisions lead to other decisions or consequences.

A classic example of a decision tree are the old Choose your Own Adventure books in which you moved through a story on the basis of your choices. Naturally, most of your choices resulted in your own death.

There are some really awesome visualizations of Choose your Own Adventure stories out there.

In computerized versions of decision trees, there is a data structure that works well. It breaks the decisions down into individual nodes. These nodes will be things like using a key or picking up a book. Each node will have certain possible actions attached to it. Each of these actions will link to a new node, with it's own actions and links.

As the adventure starts, it begins with nodeObj.start:

start: {
	description: "You see a door.",
	choices: {
		'Open the door': 'openDoor',
		'Stay here and do nothing': 'stayHere'
	}
},

Opening the door will trigger nodeObj.displayNode( nodeObj.openDoor );. Staying and doing nothing will trigger nodeObj.displayNode( nodeObj.stayHere );

The scary door!

A choose your own adventure

Source code

<script>
            //
            // Inspired by: 
            // https://en.wikibooks.org/wiki/Choose_Your_Own_Pyventure
            //
            // nodeObj OBJECT
            // properties:
            //      the node data object for a choose your own adventure
            //      looks like this:
            //
            //      nodeName: {
            //           description: "Description to display",
            //              choices: {
            //                  'Choice description 1': 'resultNode1'  
            //                  'Choice description 2': 'resultNode2'  
            //                  'Choice description 3': 'resultNode3'  
            //              }
            //          }
            //
            //      nodeObj.start
            //      nodeObj.openDoor
            //      nodeObj.walkDownCorridor
            //      nodeObj.leanAgainstDoor
            //      nodeObj.stayHere
            //
            // methods:
            //      nodeObj.displayNode( nodeName );
            //      nodeObj.generateButtons( nodeName );
            //
            var nodeObj = {
                start: {
                    description: "You see a door.",
                    choices: {
                        'Open the door': 'openDoor',
                        'Stay here and do nothing': 'stayHere'
                    }
                },
                openDoor: {
                    description: "You see a corridor ahead",
                    choices: {
                        'Walk down the corridor': 'walkDownCorridor',
                        'Lean against door': 'leanAgainstDoor'
                    }
                },
                walkDownCorridor: {
                    description: "You walk down the corridor, "
                                + "find $20 and go for lunch",
                    choices: {
                        'Start again': 'start'
                    }
                },
                leanAgainstDoor: {
                    description: "You lean against the door. " 
                                + "You get a tiny sliver that you do not " 
                                + "take care of and you die.",
                    choices: {
                        'Start again': 'start'
                    }
                },
                stayHere: {
                    description: "You eventually run out of food and pass out.",
                    choices: {
                        'Start again': 'start'
                    }
                },
                
                //OUTPUT: the description and choices for this node of the adventure
                displayNode: function ( node ) {
                    console.log( 'in displaynodeObj...node=' + node );
                    
                    document.getElementById( "descriptionId" ).innerHTML 
                        = this[ node ].description;
                    
                    var buttonHTML = this.generateButtons( node );
                    
                    document.getElementById( "choicesId" ).innerHTML = buttonHTML;
                },
                
                // PROCESS: create the buttons for each possible choice for this node
                generateButtons: function ( node ) {
                    console.log( 'in generateButtons...node=' + node );
                    
                    // create a variable to hold the button code
                    var buttonHTML = "";
                    
                    //LOOP: through each choice for this node
                    for ( i in this[ node ].choices ) {
                        // and create a button for this choice 
                        buttonHTML 
                            = buttonHTML
                            + "<button onclick='nodeObj.displayNode(\""
                            + this[ node ].choices[ i ]
                            + "\");'>"
                            + i
                            + "</button> "
                    }
                    
                    return buttonHTML;
                }
            };
            
            // triggered when the page has finished loading
            document.body.onload = function () {
                nodeObj.displayNode( 'start' );
            }       
        </script>