/*
** connectst.c  Copyright 1991 Kent Paul Dolan,
**              Mountain View, CA, USA 94039-0755
**
** Written to satisfy an inquiry on USENet's rec.games.programmer newsgroup.
** May be freely used or modified in any non-commercial work.  Copyrighted
** only to prevent patenting by someone else.
*/

#include <stdio.h>
#include "townmaze.h"
#include "townproto.h"

#ifdef __STDC__
void connectstreets()
#else
int connectstreets()
#endif
{
  int targetcell;
  int livewalk, i;
  int deadwalk, lastdead, j, k;
  int cheapdir;
  int nhbrid;

/*
** Sanity check; make sure we don't go spinning off with no work possible.
*/

  if (streetnumct < 1)
  {
    fprintf(stderr,"No streets seeded! Oops!  Logic bomb!\n");
    freespace();
    exit(1);
  }

/*
** Three phase maneuver; phase 1, try to connect streets by using live
** cells to turn into street cells.
*/

#if PROGRESS
  fprintf(stderr,"Streets 1 ");
#endif


  while((streetnumct > 1) && (livect > 0))
  {
    targetcell = RANDOM()%livect;
    livewalk = live;
    for (i = 0; i < (targetcell - 1); i++)
      if (livewalk == NOPOINTER)
      {
        fprintf(stderr,"live list too short in connectstreets\n");
        showdebugmaze();
        freespace();
        exit(1);
      }
      else
      {
        livewalk = statlist[livewalk].next;
      }
/*
** Since this is a live cell, it is supposed to have a street cell
** neighbor; find one and adopt its street number.  If directions
** are implemented, then this has to be expanded to pick a random
** neighbor street fairly and adopt its number and direction.
** [Done in makestreet(), instead, by the "-1" direction parameter..]
*/
    for (nhbrid = 0; nhbrid < 4; nhbrid++)
      if (nhbrexists(livewalk,nhbrid))
        if (statlist[nhbris(livewalk,nhbrid)].status == STREET)
        {
          makestreet(livewalk,
            statlist[nhbris(livewalk,nhbrid)].streetnum,-1);
          break;
        }
  }

/*
** Phase 2: try for a cheap connect by only using dead cells between streets
** with different streetnums; this should get some more streets connected,
** without turning the whole map into streets.
*/

  if ((streetnumct > 1) && (deadct > 0))
  {

#if PROGRESS
  fprintf(stderr,"Streets 2 ");
#endif

    deadwalk = dead;
    for (i = 0; i < deadct; i++)
    {
      if (deadwalk == NOPOINTER) break;
      if (streetnumct <= 1) break;
      lastdead = deadwalk;
      deadwalk = statlist[deadwalk].next;
      if (interiorcell(lastdead))
      {
        for (j = 0; j < 4; j++)
          if (nhbrexists(lastdead,j))
            for (k = 0; k < 4; k++)
            {
              if (j == k) continue;
              if (nhbrexists(lastdead,k))
/*
** The reason this loop doesn't keep trying to make a street out of the
** chosen cell after it has done so once is that makestreet() causes
** all the adjacent streets to be merged and have the same street number,
** so that the next if always fails after the first success.  It can thus
** safely be let run to completion.
*/
                if (   (statlist[nhbris(lastdead,j)].status == STREET)
                    && (statlist[nhbris(lastdead,k)].status == STREET)
                    && (statlist[nhbris(lastdead,j)].streetnum
                        != statlist[nhbris(lastdead,k)].streetnum)
                   )
                {
                  cheapdir = ((j+2)%4);
                  if (statlist[nhbris(lastdead,k)].streetdir == ((k+2)%4))
                    cheapdir = ((k+2)%4); 
                  makestreet(lastdead,statlist[nhbris(lastdead,j)].streetnum,
                             cheapdir);
                }
            }
      }
      
    }
  }

/*
** Phase 3: when out of luck, use brute force (haven't ever seen this
** required, but can't prove it isn't)..
*/

#if PROGRESS
  if (streetnumct > 1) fprintf(stderr,"Streets 3 ");
#endif

  while((streetnumct > 1) && (deadct > 0))
  {
    targetcell = RANDOM()%deadct;
    deadwalk = dead;
    for (i = 0; i < (targetcell - 1); i++)
      if (deadwalk == NOPOINTER)
      {
        fprintf(stderr,"dead list too short in connectstreets\n");
        showdebugmaze();
        freespace();
        exit(1);
      }
      else
      {
        deadwalk = statlist[deadwalk].next;
      }
/*
** Since this is a dead cell, it is necessary to check that it is an interior
** one.  This should again be enhanced when directions are installed.
*/
    if (interiorcell(deadwalk))
    {
      for (nhbrid = 0; nhbrid < 4; nhbrid++)
        if (nhbrexists(deadwalk,nhbrid))
          if (statlist[nhbris(deadwalk,nhbrid)].status == STREET)
          {
            makestreet(deadwalk,
              statlist[nhbris(deadwalk,nhbrid)].streetnum,-1);
            break;
          }
    }
  }

}