Tuesday, October 19, 2010

jQuery & JSON to draw single-elimination tournament bracket

Often I see sites that present tournament brackets as an image (even on fairly technical sites, eg http://us.battle.net/sc2/en/blog/936927#blog). Purely out of curiosity, I decided to see what would be involved in merely providing the data from the server and letting an HTML UI build up on the fly using jQuery. To avoid needing to produce a server for this I simply hard-coded in JSON that might have been returned from a server with (very) basic information about the tournament:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-us">
<head>
  <title>MyTournamentName</title>
 <script src='http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js' type='text/javascript'>
 </script>
 <script src='http://ajax.googleapis.com/ajax/libs/jqueryui/1.7.2/jquery-ui.min.js' type='text/javascript'>
 </script>  
  <script type="text/javascript">  
    var matchInfo = {
      "rounds" : [
        { "name": "Round1",
          "matches" : [
            { "id" : 1, "p1" : "mTwDeMuslim", "p2" : "Luffy" },
            { "id" : 2, "p1" : "SeleCT", "p2" : "NEXGenius" },
            { "id" : 3, "p1" : "Fenix", "p2" : "SoftBall" },
            { "id" : 4, "p1" : "White-Ra", "p2" : "Ice" },
            { "id" : 5, "p1" : "HuK", "p2" : "RedArchon" },
            { "id" : 6, "p1" : "Capoch", "p2" : "Loner" },
            { "id" : 7, "p1" : "mTwDIMAGA", "p2" : "MakaPrime" },
            { "id" : 8, "p1" : "TLAF-Liquid`TLO", "p2" : "SEN" }
          ]
        },
        { "name": "Round2",
          "matches" : [
            { "id" : 9, "p1" : null, "p2" : null },
            { "id" : 10, "p1" : null, "p2" : null },
            { "id" : 11, "p1" : null, "p2" : null },
            { "id" : 12, "p1" : null, "p2" : null }
          ]
        },
        { "name": "Round3",
          "matches" : [
            { "id" : 13, "p1" : null, "p2" : null },
            { "id" : 14, "p1" : null, "p2" : null },
          ]
        },
        { "name": "Round4",
          "matches" : [
            { "id" : 15, "p1" : null, "p2" : null },
          ]
        }                
      ]
    };
  </script>
</head>
<body>
  <div>blah blah blah</div>
  <div id="writeHere" class="tournament"></div>
  <div>blah blah blah</div>
</body>
</html>
Next we need to write some jQuery code to fill in the div with id="writeHere" with our purely html-based tournament bracket. Easy enough to do (note that some rudimentary css has been slapped in to show us where which bits are):
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-us">
<head>
  <title>MyTournamentName</title>
 <script src='http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js' type='text/javascript'>
 </script>
 <script src='http://ajax.googleapis.com/ajax/libs/jqueryui/1.7.2/jquery-ui.min.js' type='text/javascript'>
 </script>  
  <style type="text/css">
  .tournament {    
    background-color: #F0F0F0;
    border: dashed 1px solid;
    overflow: auto;
  }
  .tournament .bracket {
    background-color: #DFDFDF;
    min-width: 100px;    
    vertical-align: top;
    float: left;
  }
  
  .tournament .bracket .match {
    background-color: #D0D0D0;
    border-top: 1px solid;
    border-right: 1px solid;
    border-bottom: 1px solid;  
  }
  .tournament .bracket .match .p1 {    
    height: 20px;
  }
  .tournament .bracket .match .p2 {
    height: 20px;
  }    
  .tournament .bracket .match .spacer {
    background-color: #DFDFDF;
    height: 38px;
  }
  .tournament .bracket .spacer {
    height: 80px;
  }
  .tournament .bracket .half-spacer {
    height: 40px;
  }
  .tournament .bracket .small-spacer {
    height: 10px;
    background-color: #F1F1F1;
  }
  
  .left-line {
    border-left: 1px solid;
  }
  
  .tournament .cell {
    min-width: 100px;
    height: 20px;
    float: left;
    background-color: #DFDFDF;    
  }   
  .tournament .l2 {
    background-color: #D0D0D0;
  }     
  .tournament .lmax {
    width: 0px;
    clear: both;
  }    
  </style>
  <script type="text/javascript">
  
    var matchInfo = {
      "rounds" : [
        { "name": "Round1",
          "matches" : [
            { "id" : 1, "p1" : "mTwDeMuslim", "p2" : "Luffy" },
            { "id" : 2, "p1" : "SeleCT", "p2" : "NEXGenius" },
            { "id" : 3, "p1" : "Fenix", "p2" : "SoftBall" },
            { "id" : 4, "p1" : "White-Ra", "p2" : "Ice" },
            { "id" : 5, "p1" : "HuK", "p2" : "RedArchon" },
            { "id" : 6, "p1" : "Capoch", "p2" : "Loner" },
            { "id" : 7, "p1" : "mTwDIMAGA", "p2" : "MakaPrime" },
            { "id" : 8, "p1" : "TLAF-Liquid`TLO", "p2" : "SEN" }
          ]
        },
        { "name": "Round2",
          "matches" : [
            { "id" : 9, "p1" : null, "p2" : null },
            { "id" : 10, "p1" : null, "p2" : null },
            { "id" : 11, "p1" : null, "p2" : null },
            { "id" : 12, "p1" : null, "p2" : null }
          ]
        },
        { "name": "Round3",
          "matches" : [
            { "id" : 13, "p1" : null, "p2" : null },
            { "id" : 14, "p1" : null, "p2" : null },
          ]
        },
        { "name": "Round4",
          "matches" : [
            { "id" : 15, "p1" : null, "p2" : null },
          ]
        }                
      ]
    };
  
    $(document).ready(function($) {       
      var base = $('#writeHere');
      var numTeams = 16;
      var matchesByRound = setupMatchboxes(numTeams);
      
      for (var lvl=0; lvl<matchesByRound.length; lvl++) {                
        var matchBoxes = matchesByRound[lvl];        
        var bracket = checkedAppend('<div class="bracket"></div>', base);
        
        for (var i=0; i<matchBoxes.length; i++) {                     
          var match = matchInfo.rounds[lvl].matches[i];
          var matchHtml = '<div class="match" id="match' + match.id + '">'
            + '<div class="p1">' + fmtName(match.p1) + '</div>'
            + '<div class="spacer"></div>'
            + '<div class="p2">' + fmtName(match.p2) + '</div>';
          checkedAppend(matchHtml, bracket);  
        }
      }      
    });
    
    function fmtName(name) {
      return null != name ? name : '?';
    }
    
    function setupMatchboxes(numTeams) {
      var numLevels = Math.log(numTeams)/Math.LN2;
      var numMatchesForLevel = numTeams / 2;
      var matchBoxes = [];
      
      do {
        var matchesForLevel = [];        
        matchBoxes.push(matchesForLevel);
        
        for (var match=0; match<numMatchesForLevel; match++) {
          matchesForLevel.push(match);
        }
        
        numMatchesForLevel = numMatchesForLevel / 2;
      } while(numMatchesForLevel >= 1);
      return matchBoxes;
    }
    
    function checkedAppend(rawHtml, appendTo) {
      var html = $(rawHtml);
      if (0 == html.length) {
        throw "Built ourselves bad html : " + rawHtml;
      }
      html.appendTo(appendTo);      
      return html;
    }
  </script>
</head>
<body>
  <div>blah blah blah</div>
  <div id="writeHere" class="tournament"></div>
  <div>blah blah blah</div>
</body>
</html>
However, this doesn't line things up quite as nicely as one might hope (to say the least):

We have a couple of clear problems:

  1. We probably want a small vertical space between the first row of matches.
  2. For rows 2..N, a match needs to line up such that its top is at the center of one of the matches on the previous row and its bottom is at the center of another. The specific offset helpfully changes from row to row. It turns out to be a bit of a pain to write css for this so instead we'll just write jQuery code to manually size elements for our first pass. Eg we want something like this (note inconsistent sizing and positioning row to row):
Luckily jQuery provides convenient accessors for height and position so we can write code that literally says "make a vertical spacing div that is half the size of that div and make my div tall enough to stretch from there to there". The main thing that will need an update is that we'll need to keep references to the divs as we go along row by row. This will let us easily set things relative to other things similar to:
var newH = stretchTo.position().top + stretchTo.height()/2 - matchDiv.position().top;
This will ultimately yield the following javascript gibberish:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-us">
<head>
  <title>MyTournamentName</title>
 <script src='http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js' type='text/javascript'>
 </script>
 <script src='http://ajax.googleapis.com/ajax/libs/jqueryui/1.7.2/jquery-ui.min.js' type='text/javascript'>
 </script>  
  <style type="text/css">
  .tournament {    
    background-color: #F0F0F0;
    border: dashed 1px solid;
    overflow: auto;
  }
  .tournament .bracket {
    background-color: #DFDFDF;
    min-width: 100px;    
    vertical-align: top;
    float: left;
  }
  
  .tournament .bracket .match {
    background-color: #D0D0D0;
    border-top: 1px solid;
    border-right: 1px solid;
    border-bottom: 1px solid;  
  }
  .tournament .bracket .match .p1 {    
    height: 20px;
  }
  .tournament .bracket .match .p2 {
    height: 20px;
  }    
  .tournament .bracket .match .spacer {
    background-color: #DFDFDF;
    height: 38px;
  }
  .tournament .bracket .spacer {
    height: 80px;
  }
  .tournament .bracket .half-spacer {
    height: 40px;
  }
  .tournament .bracket .small-spacer {
    height: 10px;
    background-color: #F1F1F1;
  }
  
  .left-line {
    border-left: 1px solid;
  }
  
  .tournament .cell {
    min-width: 100px;
    height: 20px;
    float: left;
    background-color: #DFDFDF;    
  }   
  .tournament .l2 {
    background-color: #D0D0D0;
  }     
  .tournament .lmax {
    width: 0px;
    clear: both;
  }    
  </style>
  <script type="text/javascript">
  
    var matchInfo = {
      "rounds" : [
        { "name": "Round1",
          "matches" : [
            { "id" : 1, "p1" : "mTwDeMuslim", "p2" : "Luffy" },
            { "id" : 2, "p1" : "SeleCT", "p2" : "NEXGenius" },
            { "id" : 3, "p1" : "Fenix", "p2" : "SoftBall" },
            { "id" : 4, "p1" : "White-Ra", "p2" : "Ice" },
            { "id" : 5, "p1" : "HuK", "p2" : "RedArchon" },
            { "id" : 6, "p1" : "Capoch", "p2" : "Loner" },
            { "id" : 7, "p1" : "mTwDIMAGA", "p2" : "MakaPrime" },
            { "id" : 8, "p1" : "TLAF-Liquid`TLO", "p2" : "SEN" }
          ]
        },
        { "name": "Round2",
          "matches" : [
            { "id" : 9, "p1" : null, "p2" : null },
            { "id" : 10, "p1" : null, "p2" : null },
            { "id" : 11, "p1" : null, "p2" : null },
            { "id" : 12, "p1" : null, "p2" : null }
          ]
        },
        { "name": "Round3",
          "matches" : [
            { "id" : 13, "p1" : null, "p2" : null },
            { "id" : 14, "p1" : null, "p2" : null },
          ]
        },
        { "name": "Round4",
          "matches" : [
            { "id" : 15, "p1" : null, "p2" : null },
          ]
        }                
      ]
    };
  
    $(document).ready(function($) {       
      var base = $('#writeHere');
      var numTeams = 16;
      var matchesByRound = setupMatchboxes(numTeams);
      var matchDivsByRound = [];
      
      for (var lvl=0; lvl<matchesByRound.length; lvl++) {                
        var matchBoxes = matchesByRound[lvl];        
        var bracket = checkedAppend('<div class="bracket"></div>', base);
        var matchDivs = [];
        matchDivsByRound.push(matchDivs);
        
        for (var i=0; i<matchBoxes.length; i++) {                     
          var vOffset = checkedAppend('<div></div>', bracket);
        
          var match = matchInfo.rounds[lvl].matches[i];
          var matchHtml = '<div class="match" id="match' + match.id + '">'
            + '<div class="p1">' + fmtName(match.p1) + '</div>'
            + '<div class="spacer"></div>'
            + '<div class="p2">' + fmtName(match.p2) + '</div>';
          matchDiv = checkedAppend(matchHtml, bracket);
          matchDivs.push(matchDiv);
          
          if (lvl > 0) {
            //row 2+; line up with previous row
            var alignTo = matchDivsByRound[lvl-1][i*2];
            //offset to line up tops
            var desiredOffset = alignTo.position().top - matchDiv.position().top;
            
            //offset by half the previous match-height
            desiredOffset += alignTo.height() / 2;
            vOffset.height(desiredOffset);            
          } else {
            checkedAppend('<div class="small-spacer"></div>', bracket);
          }
          
          if (lvl > 0) {
            //tweak our size so we stretch to the middle of the appropriate element
            var stretchTo = matchDivsByRound[lvl-1][i*2+1];
            var newH = stretchTo.position().top + stretchTo.height()/2 - matchDiv.position().top;            
            var deltaH = newH - matchDiv.height();
            matchDiv.height(newH);
            var spacer = matchDiv.find('.spacer');
            spacer.height(spacer.height() + deltaH);
          }          
        }
      }      
    });
    
    function fmtName(name) {
      return null != name ? name : '?';
    }
    
    function setupMatchboxes(numTeams) {
      var numLevels = Math.log(numTeams)/Math.LN2;
      var numMatchesForLevel = numTeams / 2;
      var matchBoxes = [];
      
      do {
        var matchesForLevel = [];        
        matchBoxes.push(matchesForLevel);
        
        for (var match=0; match<numMatchesForLevel; match++) {
          matchesForLevel.push(match);
        }
        
        numMatchesForLevel = numMatchesForLevel / 2;
      } while(numMatchesForLevel >= 1);
      return matchBoxes;
    }
    
    function checkedAppend(rawHtml, appendTo) {
      var html = $(rawHtml);
      if (0 == html.length) {
        throw "Built ourselves bad html : " + rawHtml;
      }
      html.appendTo(appendTo);      
      return html;
    }
  </script>
</head>
<body>
  <div>blah blah blah</div>
  <div id="writeHere" class="tournament"></div>
  <div>blah blah blah</div>
</body>
</html>
On nice modern browsers this yields something like this:

Last of all lets clean up our javascript slightly, in particular making our code a little more directly based on the JSON and a little less on hard-coded test variables like numTeams. And lets add a spot for the final victor:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-us">
<head>
  <title>MyTournamentName</title>
 <script src='http://ajax.googleapis.com/ajax/libs/jquery/1.4.2/jquery.min.js' type='text/javascript'>
 </script>
 <script src='http://ajax.googleapis.com/ajax/libs/jqueryui/1.7.2/jquery-ui.min.js' type='text/javascript'>
 </script>  
  <style type="text/css">
  .tournament {    
    background-color: #F0F0F0;
    border: dashed 1px solid;
    overflow: auto;
  }
  .tournament .bracket {
    background-color: #DFDFDF;
    min-width: 100px;    
    vertical-align: top;
    float: left;
  }
  
  .tournament .bracket .match {
    background-color: #D0D0D0;
    border-top: 1px solid;
    border-right: 1px solid;
    border-bottom: 1px solid;  
  }
  .tournament .bracket .match .p1 {    
    height: 20px;
  }
  .tournament .bracket .match .p2 {
    height: 20px;
  }    
  .tournament .bracket .match .spacer {
    background-color: #DFDFDF;
    height: 38px;
  }
  .tournament .bracket .spacer {
    height: 80px;
  }
  .tournament .bracket .half-spacer {
    height: 40px;
  }
  .tournament .bracket .small-spacer {
    height: 10px;
    background-color: #F1F1F1;
  }
  .tournament .bracket .winner {
    border-bottom: 1px solid;
  }
  
  .left-line {
    border-left: 1px solid;
  }
  
  .tournament .cell {
    min-width: 100px;
    height: 20px;
    float: left;
    background-color: #DFDFDF;    
  }   
  .tournament .l2 {
    background-color: #D0D0D0;
  }     
  .tournament .lmax {
    width: 0px;
    clear: both;
  }    
  </style>
  <script type="text/javascript">
  
    var matchInfo = {
      "rounds" : [
        { "name": "Round1",
          "matches" : [
            { "id" : 1, "p1" : "mTwDeMuslim", "p2" : "Luffy" },
            { "id" : 2, "p1" : "SeleCT", "p2" : "NEXGenius" },
            { "id" : 3, "p1" : "Fenix", "p2" : "SoftBall" },
            { "id" : 4, "p1" : "White-Ra", "p2" : "Ice" },
            { "id" : 5, "p1" : "HuK", "p2" : "RedArchon" },
            { "id" : 6, "p1" : "Capoch", "p2" : "Loner" },
            { "id" : 7, "p1" : "mTwDIMAGA", "p2" : "MakaPrime" },
            { "id" : 8, "p1" : "TLAF-Liquid`TLO", "p2" : "SEN" }
          ]
        },
        { "name": "Round2",
          "matches" : [
            { "id" : 9, "p1" : null, "p2" : null },
            { "id" : 10, "p1" : null, "p2" : null },
            { "id" : 11, "p1" : null, "p2" : null },
            { "id" : 12, "p1" : null, "p2" : null }
          ]
        },
        { "name": "Round3",
          "matches" : [
            { "id" : 13, "p1" : null, "p2" : null },
            { "id" : 14, "p1" : null, "p2" : null },
          ]
        },
        { "name": "Round4",
          "matches" : [
            { "id" : 15, "p1" : null, "p2" : null },
          ]
        } 
      ]
    };
  
    $(document).ready(function($) {       
      var base = $('#writeHere');
      var matchDivsByRound = [];
      
      for (var roundIndex=0; roundIndex<matchInfo.rounds.length; roundIndex++) {    
        var round = matchInfo.rounds[roundIndex];
        var bracket = checkedAppend('<div class="bracket"></div>', base);
        var matchDivs = [];
        matchDivsByRound.push(matchDivs);
        
        //setup the match boxes round by round
        for (var i=0; i<round.matches.length; i++) {                     
          var vOffset = checkedAppend('<div></div>', bracket);
        
          var match = round.matches[i];
          var matchHtml = '<div class="match" id="match' + match.id + '">'
            + '<div class="p1">' + fmtName(match.p1) + '</div>'
            + '<div class="spacer"></div>'
            + '<div class="p2">' + fmtName(match.p2) + '</div>';
          matchDiv = checkedAppend(matchHtml, bracket);
          matchDivs.push(matchDiv);
          
          if (roundIndex > 0) {
            //row 2+; line up with previous row
            var alignTo = matchDivsByRound[roundIndex-1][i*2];
            //offset to line up tops
            var desiredOffset = alignTo.position().top - matchDiv.position().top;
            
            //offset by half the previous match-height
            desiredOffset += alignTo.height() / 2;
            vOffset.height(desiredOffset);            
          } else {
            checkedAppend('<div class="small-spacer"></div>', bracket);
          }
          
          if (roundIndex > 0) {
            //tweak our size so we stretch to the middle of the appropriate element
            var stretchTo = matchDivsByRound[roundIndex-1][i*2+1];
            var newH = stretchTo.position().top + stretchTo.height()/2 - matchDiv.position().top;            
            var deltaH = newH - matchDiv.height();
            matchDiv.height(newH);
            var spacer = matchDiv.find('.spacer');
            spacer.height(spacer.height() + deltaH);
          }          
        }                
      }
      //setup the final winners box; just a space for a name whose bottom is centrally aligned with the last match
      bracket = checkedAppend('<div class="bracket"></div>', base);
      var vOffset = checkedAppend('<div></div>', bracket);
      var alignTo = matchDivsByRound[matchInfo.rounds.length - 1][0]; //only 1 match in the last round
      var html = '<div class="winner">?</div>';
      var winnerDiv = checkedAppend(html, bracket);      
      vOffset.height(alignTo.position().top - winnerDiv.position().top + alignTo.height() / 2 - winnerDiv.height());
    });
    
    function fmtName(name) {
      return null != name ? name : '?';
    }
    
    function checkedAppend(rawHtml, appendTo) {
      var html = $(rawHtml);
      if (0 == html.length) {
        throw "Built ourselves bad html : " + rawHtml;
      }
      html.appendTo(appendTo);      
      return html;
    }
  </script>
</head>
<body>
  <div>blah blah blah</div>
  <div id="writeHere" class="tournament"></div>
  <div>blah blah blah</div>
</body>
</html>

Ugly, but sized and positioned the way we want, ready to actually talk to a server and/or get some dynamic elements (eg the ability to designate a winner and have them promote through the tournament).

Ultimately this will hopefully get rolled up into a practicum project involving tournament management.

8 comments:

Isaac Earl said...

This is awesome. mad props. I might try and work this into a project...

lawrab said...

Awesome, I am going to have a play with this...!

Jamie said...

I'm also using this, thanks for the code assist I had rough drafted out pretty much the same idea as your blog outlines and then I wondered.. I bet someone else has thought of this! Lo and behold, you save me from coding it :)

You can see it here, http://www.sjscomputing.com/dailies/dailies/brackets/?game=Starcraft2

Your JSON array was a pain in the ass to re-create serverside but I managed :P. As well, I promise to pretty the site up so don't worry about your work being used in a poor environment.

Thanks again.

Edward Rustan said...

This is a great approach and I have integrated it into a .Net 4.0 web site with good results. However, I'd like to expand it to support double elimination brackets -- does anyone have an idea on how to do that?

vertu said...

Hi, thanks for the codes.

How can I use this with php and mysql.

for example I have mysql tables like users, tournaments etc.. is there any idea?

Sean Steinhoff said...

Fantastic! Flexible and scalable!

Marley Sporting Dog Supplies said...

Awesome start to something great! Was able to modify it to fit my needs. Thanks again for sharing.

Thanh Dang said...

Great !

How I play a tournament with 13 teams ?

Thanks

Post a Comment