home *** CD-ROM | disk | FTP | other *** search
/ hobbes.nmsu.edu 2008 / 2008-06-02_hobbes.nmsu.edu.zip / new / scummc-0.2.0-os2.zip / ScummC / src / scc_box.c < prev    next >
Encoding:
C/C++ Source or Header  |  2007-12-17  |  6.8 KB  |  291 lines
  1. /* ScummC
  2.  * Copyright (C) 2004-2007  Alban Bedel
  3.  *
  4.  * This program is free software; you can redistribute it and/or
  5.  * modify it under the terms of the GNU General Public License
  6.  * as published by the Free Software Foundation; either version 2
  7.  * of the License, or (at your option) any later version.
  8.  
  9.  * This program is distributed in the hope that it will be useful,
  10.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.  * GNU General Public License for more details.
  13.  
  14.  * You should have received a copy of the GNU General Public License
  15.  * along with this program; if not, write to the Free Software
  16.  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  17.  *
  18.  */
  19.  
  20. /**
  21.  * @file scc_box.c
  22.  * @brief Common box stuff
  23.  */
  24.  
  25. #include "config.h"
  26.  
  27. #include <stdlib.h>
  28. #include <stdio.h>
  29. #include <string.h>
  30. #include <math.h>
  31. #include <inttypes.h>
  32. #include <sys/types.h>
  33. #include <sys/stat.h>
  34. #include <fcntl.h>
  35.  
  36. #include "scc_box.h"
  37.  
  38.  
  39. void scc_box_list_free(scc_box_t* box) {
  40.   scc_box_t* n;
  41.   while(box) {
  42.     n = box->next;
  43.     free(box);
  44.     box = n;
  45.   }
  46. }
  47.  
  48. int scc_box_add_pts(scc_box_t* box,int x,int y) {
  49.   int i;
  50.   if(box->npts >= 4) return 0;
  51.  
  52.   // look if don't alredy have this point
  53.   for(i = 0 ; i < box->npts ; i++)
  54.     if(box->pts[i].x == x && box->pts[i].y == y) return 1;
  55.  
  56.   box->pts[i].x = x;
  57.   box->pts[i].y = y;
  58.  
  59.   box->npts++;
  60.   return 1;
  61. }
  62.  
  63. int scc_box_are_neighbors(scc_box_t* box,int n1,int n2) {
  64.   scc_box_t *a = NULL,*b = NULL,*c;
  65.   int n,m;
  66.   int i,j;
  67.   int f,f2,l,l2;
  68.  
  69.   // box 0 is connected to nothing
  70.   if((!n1) || (!n2)) return 0;
  71.  
  72.   for(n = 1, c = box ; c ; n++,c = c->next) {
  73.     if(n == n1) a = c;
  74.     if(n == n2) b = c;
  75.   }
  76.  
  77.   if(!(a && b)) {
  78.     printf("Failed to find boxes %d and/or %d.\n",n1,n2);
  79.     return 0;
  80.   }
  81.  
  82.   if((a->flags & SCC_BOX_INVISIBLE) || (b->flags & SCC_BOX_INVISIBLE))
  83.     return 0;
  84.  
  85.   for(n = 0 ; n < a->npts ; n++) {
  86.     m = (n+1)%a->npts;
  87.     // is it an vertical side
  88.     if(a->pts[n].x == a->pts[m].x) {
  89.       // look at tho other box
  90.       for(i = 0 ; i < b->npts ; i++) {
  91.     j = (i+1)%b->npts;
  92.     // ignore side which are not on the same vertical
  93.     if((b->pts[i].x != a->pts[n].x) ||
  94.        (b->pts[j].x != a->pts[n].x)) continue;
  95.  
  96.     if(a->pts[n].y < a->pts[m].y)
  97.       f = n, l = m;
  98.     else
  99.       f = m, l = n;
  100.  
  101.     if(b->pts[i].y < b->pts[j].y)
  102.       f2 = i, l2 = j;
  103.     else
  104.       f2 = j, l2 = i;
  105.  
  106.     if((a->pts[l].y < b->pts[f2].y) || 
  107.        (a->pts[f].y > b->pts[l2].y)) continue;
  108.     return 1;
  109.       }
  110.       
  111.     }
  112.     // is it an horizontal line
  113.     if(a->pts[n].y == a->pts[m].y) {
  114.       // look at the other box
  115.       for(i = 0 ; i < b->npts ; i++) {
  116.     j = (i+1)%b->npts;
  117.     if((b->pts[i].y != a->pts[n].y) ||
  118.        (b->pts[j].y != a->pts[n].y)) continue;
  119.  
  120.     if(a->pts[n].x < a->pts[m].x)
  121.       f = n, l = m;
  122.     else
  123.       f = m, l = n;
  124.  
  125.     if(b->pts[i].x < b->pts[j].x)
  126.       f2 = i, l2 = j;
  127.     else
  128.       f2 = j, l2 = i;
  129.  
  130.     if((a->pts[l].x < b->pts[f2].x) || 
  131.        (a->pts[f].x > b->pts[l2].x)) continue;
  132.     return 1;
  133.       }
  134.     }
  135.   }
  136.   return 0;
  137. }
  138.  
  139. // code pumped from scummvm
  140. // changed to make it work with any matrix size
  141. int scc_box_get_matrix(scc_box_t* box,uint8_t** ret) {
  142.   scc_box_t* b;
  143.   int i,j,k,num = 0;
  144.   uint8_t *adjacentMatrix, *itineraryMatrix;
  145.   
  146.   // count the boxes
  147.   for(b = box ; b ; b = b->next) num++;
  148.   // add the box 0
  149.   num++;
  150.  
  151.   // Allocate the adjacent & itinerary matrices
  152.   adjacentMatrix = malloc(num * num);
  153.   itineraryMatrix = malloc(num * num);
  154.  
  155.   // Initialise the adjacent matrix: each box has distance 0 to itself,
  156.   // and distance 1 to its direct neighbors. Initially, it has distance
  157.   // 255 (= infinity) to all other boxes.
  158.   for (i = 0; i < num; i++) {
  159.     for (j = 0; j < num; j++) {
  160.       if (i == j) {
  161.     adjacentMatrix[i*num+j] = 0;
  162.     itineraryMatrix[i*num+j] = j;
  163.       } else if (scc_box_are_neighbors(box,i,j)) {
  164.     adjacentMatrix[i*num+j] = 1;
  165.     itineraryMatrix[i*num+j] = j;
  166.       } else {
  167.     adjacentMatrix[i*num+j] = 255;
  168.     itineraryMatrix[i*num+j] = 255;
  169.       }
  170.     }
  171.   }
  172.  
  173.   // Compute the shortest routes between boxes via Kleene's algorithm.
  174.   for (k = 0; k < num; k++) {
  175.     for (i = 0; i < num; i++) {
  176.       for (j = 0; j < num; j++) {
  177.     uint8_t distIK,distKJ;
  178.     if (i == j)
  179.       continue;
  180.     distIK = adjacentMatrix[num*i+k];
  181.     distKJ = adjacentMatrix[num*k+j];
  182.     if (adjacentMatrix[num*i+j] > distIK + distKJ) {
  183.       adjacentMatrix[num*i+j] = distIK + distKJ;
  184.       itineraryMatrix[num*i+j] = itineraryMatrix[num*i+k];
  185.     }
  186.       }
  187.     }  
  188.   }
  189.  
  190.   free(adjacentMatrix);
  191.   ret[0] = itineraryMatrix;
  192.   return num;
  193. }
  194.  
  195. long long scc_box_adjust_point(scc_box_t* b,int x, int y,
  196.                          int* dst_x, int* dst_y) {
  197.   long long dst_dist = -1;
  198.   scc_box_pts_t dst = { .x = x, .y = y };
  199.   int i,inside = 0;
  200.  
  201.   // Project the point on each side and count
  202.   // how often it is on the inner side.
  203.   for(i = 0 ; i < b->npts ; i++) {
  204.     scc_box_pts_t pts;
  205.     int j = (i+1)%b->npts;
  206.     long long dist;
  207.     int dx = b->pts[j].x - b->pts[i].x;
  208.     int dy = b->pts[j].y - b->pts[i].y;
  209.  
  210.     if(abs(dx) >= abs(dy)) { // Vertical projection
  211.       int left,right;
  212.       if(b->pts[i].x <= b->pts[j].x)
  213.         left = i, right = j;
  214.       else
  215.         left = j, right = i;
  216.       if(x < b->pts[left].x)
  217.         pts = b->pts[left];
  218.       else if(x > b->pts[right].x)
  219.         pts = b->pts[right];
  220.       else {
  221.         pts.x = x;
  222.         pts.y = b->pts[i].y;
  223.         if(dx) pts.y += (x-b->pts[i].x)*dy/dx;
  224.       }
  225.       if((dx >= 0 && pts.y <= y) ||
  226.          (dx < 0  && pts.y >= y))
  227.         inside++;
  228.     } else { // Horizontal projection
  229.       int top,bottom;
  230.       if(b->pts[i].y <= b->pts[j].y)
  231.         top = i, bottom = j;
  232.       else
  233.         top = j, bottom = i;
  234.       if(y < b->pts[top].y)
  235.         pts = b->pts[top];
  236.       else if(y > b->pts[bottom].y)
  237.         pts = b->pts[bottom];
  238.       else {
  239.         pts.y = y;
  240.         pts.x = b->pts[i].x;
  241.         if(dy) pts.x += (y-b->pts[i].y)*dx/dy;
  242.       }
  243.       if((dy >= 0 && pts.x >= x) ||
  244.          (dy < 0  && pts.x <= x))
  245.         inside++;
  246.     }
  247.  
  248.     dx = pts.x-x;
  249.     dy = pts.y-y;
  250.     dist = (long long)dx*dx + (long long)dy*dy;
  251.     if(dst_dist < 0 || dist < dst_dist) {
  252.       dst = pts;
  253.       dst_dist = dist;
  254.     }
  255.   }
  256.   // Inside a box, no need to move the point
  257.   if(inside >= b->npts) {
  258.     *dst_x = x;
  259.     *dst_y = y;
  260.     return -1;
  261.   }
  262.   *dst_x = dst.x;
  263.   *dst_y = dst.y;
  264.   return dst_dist;
  265. }
  266.  
  267. scc_box_t* scc_boxes_adjust_point(scc_box_t* box,int x, int y,
  268.                                   int* dst_x, int* dst_y) {
  269.   scc_box_t* b;
  270.   scc_box_t* dst_box = NULL;
  271.   long long dst_dist = 0;
  272.   scc_box_pts_t dst = { .x = x, .y = y };
  273.   for(b = box ; b ; b = b->next) {
  274.     scc_box_pts_t pts;
  275.     long long dist;
  276.     if((dist = scc_box_adjust_point(b,x,y,&pts.x,&pts.y)) < 0) {
  277.       dst_box = b;
  278.       dst = pts;
  279.       break;
  280.     }
  281.     if(!dst_box || dist < dst_dist) {
  282.       dst_box = b;
  283.       dst = pts;
  284.       dst_dist = dist;
  285.     }
  286.   }
  287.   *dst_x = dst.x;
  288.   *dst_y = dst.y;
  289.   return dst_box;
  290. }
  291.