Collision-detection functions

Functions for quadtree collision detection.
When checking an object for a collision with any other object, only relevant objects are checked to save runtime.
Quadtree collision detection is designed to be used with VgaGames3-objects.

Structures and Enumerations

Creating and destroying a quadtree
VG3_coll_q_new()

Create a new quadtree.
VG3_coll_q_free()

Destroy the quadtree.
VG3_coll_q_tag()

Tag the quadtree.

Using the quadtree
VG3_coll_q_insert()

Insert an object into the quadtree.
VG3_coll_q_remove()

Remove an object from the quadtree.
VG3_coll_q_getobj()

Search an object in the quadtree.
VG3_coll_q_getobjs()

Search all occurrences of an object in the quadtree.
VG3_coll_check()

Check whether a moving object collides with another object.
VG3_coll_q_find()

Return a sorted list of objects which collide with an moving object.
VG3_coll_q_mark()

Mark all objects in the quadtree onto the window with a rectangle. Only for debug purposes.

Example

  /* move two created rectangle images until they collide */

  struct vg3_window *wstruct;
  int winw, winh;

  /* open window */
  wstruct = VG3_window_new(argv[0], VGAG3_VGAVERSION_LOW, VGAG3_WINSCALE_BESTSCALE);
  if (wstruct == NULL) { fprintf(stderr, "%s\n", VG3_error()); exit(1); }

  /* get the size of the window */
  VG3_window_getsize(wstruct, &winw, &winh);

  /* create two images of rectangles,
   * move them until they collide
   */
  { const int rtwidth = 10, rtheight = 10;  /* size of images */
    struct vg3_rect rect0, rect1, rect2;
    struct vg3_image *img1, *img2;
    struct vg3_quadtree *qdtr;
    struct vg3_coll coll, *pcoll;
    int maxno;

    /* create quadtree with the size of the window */
    rect0.x = 0;
    rect0.y = 0;
    rect0.w = winw;
    rect0.h = winh;
    qdtr = VG3_coll_q_new(&rect0, 0, 0);
    if (qdtr == NULL) { fprintf(stderr, "%s\n", VG3_error()); goto byebye; }

    /* create first image (yellow rectangle) and put it to the left of the window */
    rect1.x = 0;
    rect1.y = (winh - rtwidth) / 2;
    rect1.w = rtwidth;
    rect1.h = rtheight;
    img1 = VG3_image_create(wstruct, rect1.w, rect1.h);
    if (img1 == NULL) { fprintf(stderr, "%s\n", VG3_error()); goto byebye; }
    VG3_draw_clear(wstruct, img1, VGAG3_COLOR_YELLOW);

    /* put yellow rectangle into the quadtree */
    memset(&coll, 0, sizeof(coll));
    coll.rect = rect1;
    coll.optr = img1;
    snprintf(coll.oid, sizeof(coll.oid), "YELLOW RECTANGLE");
    if (VG3_coll_q_insert(qdtr, &coll) < 0) { fprintf(stderr, "%s\n", VG3_error()); goto byebye; }

    /* create second image (blue rectangle) and put it to the right of the window */
    rect2.x = winw - rtwidth;
    rect2.y = (winh - rtwidth) / 2;
    rect2.w = rtwidth;
    rect2.h = rtheight;
    img2 = VG3_image_create(wstruct, rect2.w, rect2.h);
    if (img2 == NULL) { fprintf(stderr, "%s\n", VG3_error()); goto byebye; }
    VG3_draw_clear(wstruct, img2, VGAG3_COLOR_BLUE);

    /* put blue rectangle into the quadtree */
    memset(&coll, 0, sizeof(coll));
    coll.rect = rect2;
    coll.optr = img2;
    snprintf(coll.oid, sizeof(coll.oid), "BLUE RECTANGLE");
    if (VG3_coll_q_insert(qdtr, &coll) < 0) { fprintf(stderr, "%s\n", VG3_error()); goto byebye; }

    /* game-loop */
    printf("\n");
    VG3_discard_input(wstruct);
    for (;;) {
      /* clear window */
      VG3_draw_clear(wstruct, NULL, VGAG3_COLOR_BLACK);

      /* +++ move yellow rectangle +++ */

      /* remove it from the quadtree */
      VG3_coll_q_remove(qdtr, img1);

      /* check for collision when moving it 2 pixels to the right */
      rect0 = rect1;
      rect0.x += 2;
      maxno = VG3_coll_q_find(qdtr, &rect1, &rect0, &pcoll);
      if (maxno < 0) { fprintf(stderr, "%s\n", VG3_error()); goto byebye; }
      /* collision found? */
      if (maxno > 0) {
        printf("It took %d from %d steps to collide with %s\n",
               pcoll[0].ret.steps, pcoll[0].ret.maxsteps, pcoll[0].oid);
        free(pcoll);
        break;
      }
      free(pcoll);

      /* now move it and put it back into the quadtree */
      rect1 = rect0;
      memset(&coll, 0, sizeof(coll));
      coll.rect = rect1;
      coll.optr = img1;
      snprintf(coll.oid, sizeof(coll.oid), "YELLOW RECTANGLE");
      if (VG3_coll_q_insert(qdtr, &coll) < 0) { fprintf(stderr, "%s\n", VG3_error()); goto byebye; }

      /* draw it to the window */
      VG3_image_copy(wstruct, NULL, img1, rect1.x + (rect1.w / 2), rect1.y + (rect1.h / 2), NULL, 0);


      /* +++ move blue rectangle +++ */

      /* remove it from the quadtree */
      VG3_coll_q_remove(qdtr, img2);

      /* check for collision when moving it 3 pixels to the left */
      rect0 = rect2;
      rect0.x -= 3;
      maxno = VG3_coll_q_find(qdtr, &rect2, &rect0, &pcoll);
      if (maxno < 0) { fprintf(stderr, "%s\n", VG3_error()); goto byebye; }
      /* collision found? */
      if (maxno > 0) {
        printf("It took %d from %d steps to collide with %s\n",
               pcoll[0].ret.steps, pcoll[0].ret.maxsteps, pcoll[0].oid);
        free(pcoll);
        break;
      }
      free(pcoll);

      /* now move it and put it back into the quadtree */
      rect2 = rect0;
      memset(&coll, 0, sizeof(coll));
      coll.rect = rect2;
      coll.optr = img2;
      snprintf(coll.oid, sizeof(coll.oid), "BLUE RECTANGLE");
      if (VG3_coll_q_insert(qdtr, &coll) < 0) { fprintf(stderr, "%s\n", VG3_error()); goto byebye; }

      /* draw it to the window */
      VG3_image_copy(wstruct, NULL, img2, rect2.x + (rect2.w / 2), rect2.y + (rect2.h / 2), NULL, 0);

      /* +++ remainder +++ */

      /* update window and get key-strokes */
      VG3_window_update(wstruct, 0, 0);
      if (VG3_inputevent_update(wstruct) > 0) { break; }
      VG3_wait_time(40);
    }
    VG3_discard_input(wstruct);

    /* free all images */
    VG3_image_unload(wstruct, NULL);

    /* free quadtree */
    VG3_coll_q_free(qdtr);
  }

  /* if an error occurred after creating the window, close it before exiting */
  byebye:
  /* close window */
  VG3_window_free(wstruct);