Thursday, 5 March 2015

Procedural Generation : Part Seven : World Data Structure Optimisation

The next version of Dart (1.9) will have some optimisations for the Map class. A discussion about this on the mailing list made me think of the Map used for the Dungeon demo. Dart currently has no 'real' 2D arrays so a simple map was used with a string key of the x and y co-ordinates. Creating and joining those strings takes a bit of work, so perhaps a List of Lists would be a better way. Let's use the Stopwatch class and see if we get an improvement.


class block{}
class point{ int x; int y; point(this.x,this.y);}

main() {
  Map testMap = new Map();
  List testLol = new List();
  List dataPoints = new List();
  Stopwatch watch;

  print("Set up maps.");
  for(int i=0;i<100;i++)
  for(int j=0;j<100;j++){
    testMap["$j-$i"] = new block();
    dataPoints.add(new point(j,i));
  }

  print("Set up list of lists.");
  for(int i=0;i<100;i++){
    List row = new List();
    for(int j=0;j<100;j++){
      row.add(new block());
    }
    testLol.add(row);
  }

  dataPoints.shuffle();

  print("Run tests.");
  watch = new Stopwatch();
  watch.start();
  for(int j=0;j<8000;j++){
    dataPoints.forEach((p) => testMap["${p.x}-${p.y}"]);
  }
  watch.stop();
  print("${watch.elapsed}");

  watch = new Stopwatch();
  watch.start();
  for(int j=0;j<8000;j++){
    dataPoints.forEach((p) => testLol[p.x][p.y]);
  }
  watch.stop();
  print("${watch.elapsed}");

}

Results were the Map taking around 26 seconds and the List taking about 1.4 seconds. This was running from the Dart Editor. From the command line, the map was just under 20 seconds (probably debugging overhead) and the List took about the same time. So moving forward with the world generation, List of Lists seems the way to go!