pursuer.c

source code to compute the visibility polygon of a point in a polygon.

/* Brian O'Connor
 *
 * pursuer.c: main file for coordinating pursuers to find an
 * unpredictable evader.
 */

#include <stdio.h>
#include <assert.h>
#include "pursuer.h"
#include "cell.h"
#include "input.h"
#include "movieoutput.h"
#include "vispoly.h"
#include "pgraph.h"
#include "rebuild.h"

void BuildVisPolys(PInfo *pInfo);
void PrintSolution(PInfo *pInfo, PGNode *node);
void BuildSolution(PInfo *pInfo, PGNode *node);
void BuildBestSolution(PInfo *pInfo, PGNode *node);
int SelectSearchStart(PInfo *pInfo);
void TryTwoPursuers(PInfo *pInfo, int argc, char **argv);

void main(int argc, char **argv)
{
	PInfo *pInfo;
 	PGNode *node;

	if( argc < 2 ) {
		printf("Usage: %s <environment>, argv[0]\n");
		exit(1);
	} else {
	        pInfo = new PInfo;
		pInfo->cellInfo = new CellInfo;
		assert( pInfo->cellInfo != NULL );
		BuildDecomposition(argv[1], pInfo);
		BuildVisPolys(pInfo);
		pInfo->pg = new PursuerGraph(pInfo->cellInfo, 
			SelectSearchStart(pInfo) );
                //pInfo->pg->Print();
		if( (node = pInfo->pg->Search()) != NULL ) {
                  //PrintSolution(pInfo, node);
                  BuildSolution(pInfo, node);
		  MakeMovie(argv, argc, pInfo);
		  printf("******* SUCCESSFUL *******\n");
		} else {
		  printf("Failed: best node = (%f, %f)\n",
		    pInfo->pg->Best()->NodeCell()->pt->x,
		    pInfo->pg->Best()->NodeCell()->pt->y);
		    TryTwoPursuers(pInfo, argc, argv);
                }
	}

	exit(0);
}

/* build the visibility polygon for every cell */
void BuildVisPolys(PInfo *pInfo)
{
	int i;
	for( i = 0; i < pInfo->cellInfo->nCells; i++ ) {
		pInfo->cellInfo->cells[i]->vPoly = new VPoly;
		if( !MakeVisPoly(pInfo->edgeInfo, 
                  pInfo->cellInfo->cells[i]->pt,
		  pInfo->cellInfo->cells[i]->vPoly ) ) {
		// bad cell; need to get rid of it & continue.
		  RemoveCell(pInfo->cellInfo, i);
		  i--; /* when we inc. we will retry this entry */
		}
		  int j, nGaps, nCombos;
		  VPoly *vpoly;

		  nGaps = 0;
		  vpoly= pInfo->cellInfo->cells[i]->vPoly;
		  for( j = 0; j < vpoly->nEdges; j++ ) {
		    if( vpoly->edges[j]->bGap ) nGaps++;
		  }
		  pInfo->cellInfo->cells[i]->nGapEdges = nGaps;
	}
}

void BuildSolution(PInfo *pInfo, PGNode *node)
{
  PGNode *start = node;
  int i = 0;
  while( node != NULL ) {
    node = node->Predecessor();
    i++;
  }

  pInfo->nSteps = i;
  pInfo->sln = new (PGNode *)[i];

  node = start;
  for( i = pInfo->nSteps - 1; i >= 0; i-- ) {
    pInfo->sln[i] = node;
    node = node->Predecessor();
  }
}

void BuildBestSolution(PInfo *pInfo)
{
  PGNode *start = pInfo->pg->Best();
  PGNode *node = pInfo->pg->Best();
  int i = 0;
  while( node != NULL ) {
    node = node->Predecessor();
    i++;
  }

  pInfo->nSteps = i;
  pInfo->sln = new (PGNode *)[i];

  node = start;
  for( i = pInfo->nSteps - 1; i >= 0; i-- ) {
    pInfo->sln[i] = node;
    node = node->Predecessor();
  }
}

void PrintSolution(PInfo *pInfo, PGNode *node)
{
  PGNode **arr;
  PGNode *start = node;
  int i = 0;
  int j = 0;
  while( node != NULL ) {
    node = node->Predecessor();
    i++;
  }

  pInfo->nSteps = i;
  arr = new (PGNode *)[i];

  node = start;
  for( i = pInfo->nSteps - 1; i >= 0; i-- ) {
    arr[i] = node;
    node = node->Predecessor();
  }

  for( i = 0; i < pInfo->nSteps; i++ ) {
    printf("Step %d:  ", i);
    printf("Position: (%f, %f)\n", arr[i]->NodeCell()->pt->x,
		arr[i]->NodeCell()->pt->y);
    printf("State: ");
    PrintBitmap(arr[i]->NodeState());

    printf("Gaps:\n");
    for(j = 0; j < arr[i]->NodeCell()->vPoly->nEdges ; j++) {
      if( arr[i]->NodeCell()->vPoly->edges[j]->bGap ) {
        printf("(%f, %f), (%f, %f)\n", 
          arr[i]->NodeCell()->vPoly->edges[j]->A->x,
          arr[i]->NodeCell()->vPoly->edges[j]->A->y,
          arr[i]->NodeCell()->vPoly->edges[j]->B->x,
          arr[i]->NodeCell()->vPoly->edges[j]->B->y);
      }
    }

  }
}

int SelectSearchStart(PInfo *pInfo)
{
  int i;
  i = (pInfo->cellInfo->nCells - 1) / 3;
  assert( i >= 0 );
  return(3);
  return(i);
}

/* if our first try at a solution failed, then try again.  We will
 * rebuild the decomposition and vispolys for an environment that has
 * the space the last pursuer had cleared.  If this succeeds (and it only
 * will in a small subset of all possible multiple pursuer cases) then we
 * will combine the two solutions (start->best, best->finish).
 */
void TryTwoPursuers(PInfo *oldpInfo, int argc, char **argv)
{
  PInfo *pInfo;
  PGNode *node;
  
  pInfo = new PInfo;
  pInfo->cellInfo = new CellInfo;
  assert( pInfo->cellInfo != NULL );
  RebuildDecomposition(oldpInfo, pInfo);
  BuildVisPolys(pInfo);

  pInfo->pg = new PursuerGraph(pInfo->cellInfo, 
			       SelectSearchStart(pInfo) );
  //pInfo->pg->Print();
  if( (node = pInfo->pg->Search()) != NULL ) {
    //PrintSolution(pInfo, node);
    BuildBestSolution(oldpInfo);
    BuildSolution(pInfo, node);

    MakeMultiMovie(argv, argc, oldpInfo, pInfo);
    printf("******* SUCCESSFUL *******\n");
  } else {
    printf("Failed: best node = (%f, %f)\n",
	   pInfo->pg->Best()->NodeCell()->pt->x,
	   pInfo->pg->Best()->NodeCell()->pt->y);
    /* in theory we could continue applying this algorithm, but I don't 
       have time to implement that so instead I'll stop here.  There
       aren't any algorithmic problems with reapplying this function
       recursively, but it is much easier to hardcode a movie generator
       for the case of max 2 pursuers. */
  }

}