Snakes - collision detection

Benchmark created by Jake Gordon on

Description

For a dead simple javascript snakes game, where the snake segments are maintained in a simple queue, collision detection must iterate linearly through the queue to check each segment for collision.

This is a simple O(n) algorithm... how large can 'n' be if we need to make this check at least once in every frame (60 fps) for a 64x64 grid

Preparation HTML

<script>
    var size = 64*64, list = null;
    for(var n = 0 ; n < size ; n++)
     list = { x: size-n, y: size-n, next: list }
    
    function check(x, y, head) {
      var segment = head;
      while (segment = segment.next) {
        if ((x == segment.x) && (y == segment.y))
          return true;
      }
      return false
    }
    
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
1. match early
check(100,100,list)
ready
2. match middle
check(size/2,size/2,list)
ready
3. match late
check(size-100,size-100,list)
ready
4. no match
check(42,99,list)
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

  • Revision 1: published by Jake Gordon on