#include <math.h>
#include <poll.h>
#include <curses.h>
#include <stdlib.h>

#include "util.h"
#include "vars.h"
#include "dice.h"
#include "pline.h"
#include "structs.h"

#include "explosion.h"

#define ROOT2 1.414213562373095048801688724209698078569671875376948073176679738
#define EPSILON 1e-6

/*
 * Common code for ball-style explosions that funnel through corridors
 *  and such.
 *
 * Generate an explosion such as is appropriate for a wand of fireball.
 *  g0 is the epicentre of the explosion (the name comes from "ground
 *  zero"), cells is the number of cells the explosion is good for, and
 *  effect is called for each affected cell.
 *
 * This algorithm generates `circles' that tend to be octagonal, but
 *  the difference is slight, to the point where it's not visible until
 *  the balls get much larger than anything of use here (multiple
 *  hundreds of cells, at least - it's really obvious around several
 *  thousand cells).  And this algorithm is much easier to adapt to
 *  confinement by walls and the like.
 */
void ball_explosion(LOC *g0, int cells, void (*effect)(LOC *), int mse, int msa)
{
 typedef struct ballptd BALLPTD;
 typedef struct ballpt BALLPT;
 struct ballpt {
   unsigned short int x;
   unsigned short int y;
   } ;
 struct ballptd {
   BALLPTD *link;
   double d;
   int npt;
   int apt;
   BALLPT *pts;
   } ;
 BALLPTD *dlist;
 int x;
 int y;
 BALLPT pt;
 LOC *l;
 LEVEL *lv;

 void addpt(LOC *l, double d)
  { BALLPTD *e;
    BALLPTD **ep;
    if (!l || ((d > 0) && !occupiable(l))) return;
    ep = &dlist;
    if (l->flags & LF_FLAG) return;
    do <"have">
     { do <"add">
	{ while (1)
	   { e = *ep;
	     if (! e) break <"add">;
	     if (fabs(e->d-d) < EPSILON) break <"have">;
	     if (e->d > d) break <"add">;
	     ep = &e->link;
	   }
	} while (0);
       e = malloc(sizeof(BALLPTD));
       e->d = d;
       e->npt = 0;
       e->apt = 0;
       e->pts = 0;
       e->link = *ep;
       *ep = e;
     } while (0);
    if (e->npt >= e->apt) e->pts = realloc(e->pts,(e->apt+=8)*sizeof(BALLPT));
    e->pts[e->npt++] = (BALLPT){.x=l->x,.y=l->y};
  }

 lv = g0->on;
 for (x=0;x<LEV_X;x++)
  { LOC *l;
    l = &lv->cells[x][0];
    for (y=0;y<LEV_Y;y++) l++->flags &= ~LF_FLAG;
  }
 dlist = 0;
 addpt(g0,0);
 // dlist can be nil; consider a ball of size >11 in a vault.
 while ((cells > 0) && dlist)
  { if (dlist->npt < 1)
     { BALLPTD *d;
       d = dlist;
       dlist = d->link;
       free(d->pts);
       free(d);
       continue;
     }
    x = (dlist->npt < 2) ? 0 : rnd(dlist->npt);
    pt = dlist->pts[x];
    dlist->npt --;
    if (x != dlist->npt) dlist->pts[x] = dlist->pts[dlist->npt];
    if ((pt.x >= LEV_X) || (pt.y >= LEV_Y)) panic("explosion off edge of level");
    l = &lv->cells[pt.x][pt.y];
    if (l->flags & LF_FLAG) continue;
    l->flags |= LF_FLAG;
    if (!debug_warp && (l->flags & LF_VISIBLE))
     { mvaddch(l->y+dispoy,l->x+dispox,'*');
       if (mse)
	{ move(you->loc->y+dispoy,you->loc->x+dispox);
	  refresh();
	  poll(0,0,mse);
	}
     }
    (*effect)(l);
    cells --;
    addpt(movecell(l,1,0,0),dlist->d+1);
    addpt(movecell(l,0,1,0),dlist->d+1);
    addpt(movecell(l,-1,0,0),dlist->d+1);
    addpt(movecell(l,0,-1,0),dlist->d+1);
    addpt(movecell(l,1,1,0),dlist->d+ROOT2);
    addpt(movecell(l,1,-1,0),dlist->d+ROOT2);
    addpt(movecell(l,-1,1,0),dlist->d+ROOT2);
    addpt(movecell(l,-1,-1,0),dlist->d+ROOT2);
  }
 if (msa && !debug_warp)
  { move(you->loc->y+dispoy,you->loc->x+dispox);
    refresh();
    poll(0,0,msa);
  }
}