/*
 *  Copyright (C) 1999 Peter Amstutz
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as
 *  published by the Free Software Foundation; either version 2 of *the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
 *  02111-1307 USA 
 */

#include <time.h>
#include <stdlib.h>
#include "terrain.h"
#include "ballistics.h"
#include "log.h"

/*int terraintable[9]={1, 1, 1, 5, 10, 50, 75, 150, 250};*/
/*int ter_table[9]={1, 6, 6, 30, 60, 300, 450, 900, 1500};*/
int ter_table[9] = { 1, 3, 3, 15, 30, 150, 225, 450, 750 };
int ter_depth = 8;
int ter_sizex = 2000, ter_sizey = 1500;
TerrainSpans_ter ter_data[MAXTERRAINSIZE];

int terCalcDirtFall()
{
    unsigned i;
    register TerrainSpans_ter *tmp, *t2;
    int ret = 0;

    for(i = 0; i < ter_sizex; i++)
    {
	for(tmp = &(ter_data[i]); tmp; tmp = tmp->nexthigher)
	{
	    if(tmp->nextlower || (tmp->nextlower == NULL && tmp->start > 0))
	    {
		tmp->vy -= bal_grav / bal_lerp_tweak;
		ret = 1;
		logPrintf(SPAM,
			  "CalcDirtFall: tmp->start=%i; tmp->height=%i; tmp->vy=%lf\n",
			  tmp->start, tmp->height, tmp->vy);
		if(tmp->nextlower)
		{
		    if(tmp->nextlower->start + tmp->nextlower->height >=
		       tmp->start + tmp->vy)
		    {
			tmp->nextlower->nexthigher = tmp->nexthigher;
			if(tmp->nexthigher)
			    tmp->nexthigher->nextlower = tmp->nextlower;
			t2 = tmp->nextlower;
			t2->height += tmp->height;
			free(tmp);
			tmp = t2;
			if(tmp->vy == 0)	/* force client redraw */
			    tmp->vy = 1;
		    }
		    else
			tmp->start += tmp->vy;
		}
		else
		{
		    if(tmp->start + tmp->vy > 0)
			tmp->start += tmp->vy;
		    else
			tmp->start = 0;
		}
	    }
	    else
		tmp->vy = 0;
	}
    }
    return ret;
}

void terCircleAddSpans(int xo, int yo, int x, int y)
{
    if(xo + x >= 0 && xo + x < ter_sizex)
	terAddSpan(&ter_data[xo + x], yo - y, y * 2);
    if(xo + y >= 0 && xo + y < ter_sizex)
	terAddSpan(&ter_data[xo + y], yo - x, x * 2);
    if(xo - x >= 0 && xo - x < ter_sizex)
	terAddSpan(&ter_data[xo - x], yo - y, y * 2);
    if(xo - y >= 0 && xo - y < ter_sizex)
	terAddSpan(&ter_data[xo - y], yo - x, x * 2);
}

void terAddCircle(int xo, int yo, int r)
{
    int x = 0;
    int y = r;
    int d = 1 - r;
    int deltaE = 3;
    int deltaSE = -2 * r + 5;

    terCircleAddSpans(xo, yo, x, y);
    while(y > x)
    {
	if(d < 0)
	{
	    d += deltaE;
	    deltaE += 2;
	    deltaSE += 2;
	}
	else
	{
	    d += deltaSE;
	    deltaE += 2;
	    deltaSE += 4;
	    y--;
	}
	x++;
	terCircleAddSpans(xo, yo, x, y);
    }
}

void terCircleClearSpans(int xo, int yo, int x, int y)
{
    if(xo + x >= 0 && xo + x < ter_sizex)
	terDelSpan(&ter_data[xo + x], yo - y, y * 2);
    if(xo + y >= 0 && xo + y < ter_sizex)
	terDelSpan(&ter_data[xo + y], yo - x, x * 2);
    if(xo - x >= 0 && xo - x < ter_sizex)
	terDelSpan(&ter_data[xo - x], yo - y, y * 2);
    if(xo - y >= 0 && xo - y < ter_sizex)
	terDelSpan(&ter_data[xo - y], yo - x, x * 2);
}

void terClearCircle(int xo, int yo, int r)
{
    int x = 0;
    int y = r;
    int d = 1 - r;
    int deltaE = 3;
    int deltaSE = -2 * r + 5;

    terCircleClearSpans(xo, yo, x, y);
    while(y > x)
    {
	if(d < 0)
	{
	    d += deltaE;
	    deltaE += 2;
	    deltaSE += 2;
	}
	else
	{
	    d += deltaSE;
	    deltaE += 2;
	    deltaSE += 4;
	    y--;
	}
	x++;
	terCircleClearSpans(xo, yo, x, y);
    }
}

int terGetHeight(TerrainSpans_ter * sp)
{
    register TerrainSpans_ter *tmp = sp;

    while(tmp->nexthigher != NULL)
    {
	tmp = tmp->nexthigher;
    }
    return (TER_ENDPT(tmp));
}

int terCheckSpan(TerrainSpans_ter * sp, int y, int h)
{
    register TerrainSpans_ter *tmp;
    int yh = y + h;

    for(tmp = sp; tmp; tmp = tmp->nexthigher)
	if(y >= tmp->start && (yh - tmp->start) <= tmp->height)
	    return 1;
    return 0;
}

int terCheckPos(TerrainSpans_ter * sp, int x, int y)
{
    if(x >= 0 && x < ter_sizex)
	return terCheckSpan(&sp[x], y, 0);
    else
	return 0;
}

void terFreeCol(register TerrainSpans_ter * ptr)
{
    register TerrainSpans_ter *nxt;

    while(ptr)
    {
	nxt = ptr->nexthigher;
	free(ptr);
	ptr = nxt;
    }
}

/* This algorithm is a pain in the ass */
void terAddSpan(register TerrainSpans_ter * sp, int s, int h)
{
    register TerrainSpans_ter *tmp, *end;

    /* span already exists */
    if(terCheckSpan(sp, s, h))
	return;
    for(; sp->nexthigher && sp->start + sp->height < s; sp = sp->nexthigher) ;
    if(sp->nextlower && sp->start > s + h)
	sp = sp->nextlower;
    /* case 1: no overlap */
    if(TER_ENDPT(sp) < s && (!(sp->nexthigher) ||
			     sp->nexthigher->start > (s + h)))
    {
	tmp = (TerrainSpans_ter *) malloc(sizeof(TerrainSpans_ter));
	tmp->start = s;
	tmp->height = h;
	tmp->vy = 0;
	tmp->nextlower = sp;
	tmp->nexthigher = sp->nexthigher;
	if(tmp->nextlower)
	    tmp->nextlower->nexthigher = tmp;
	if(tmp->nexthigher)
	    tmp->nexthigher->nextlower = tmp;
	return;
    }
    /* find endpoint and free intervening (but not end, yet) */
    for(end = sp; end->nexthigher && TER_ENDPT(end) < s + h;)
    {
	tmp = end;
	end = end->nexthigher;
	if(tmp != sp)
	    free(tmp);
    }
    if(end->nextlower && end->start > s + h)
	end = end->nextlower;
    /* adjust height */
    if(sp != end)
    {
	sp->nexthigher = end->nexthigher;
	if(end->nexthigher)
	    end->nexthigher->nextlower = sp;
	if(TER_ENDPT(end) > (s + h))
	    h += TER_ENDPT(end) - (s + h);
	free(end);
    }
    /* adjust overlapping span */
    if(sp->start > s)
    {
	sp->height =
	    (s + h) >
	    (sp->height + sp->start) ? h : (sp->height + sp->start) - s;
	sp->start = s;
    }
    else
    {
	sp->height += h - (TER_ENDPT(sp) - s);
    }
}

void terDelSpan(register TerrainSpans_ter * sp, int s, int h)
{
    register TerrainSpans_ter *tmp, *nxt;

    for(tmp = sp; tmp;)
    {
	/* case 1: this span is to be complete deleted */
	if(tmp->start >= s && TER_ENDPT(tmp) <= (s + h))
	{
	    if(tmp == sp)
	    {
		sp->height = 0;
		tmp = tmp->nexthigher;
	    }
	    else
	    {
		nxt = tmp->nexthigher;
		tmp->nextlower->nexthigher = tmp->nexthigher;
		if(tmp->nexthigher)
		    tmp->nexthigher->nextlower = tmp->nextlower;
		free(tmp);
		tmp = nxt;
	    }
	    continue;
	}
	/* case 2: lower part of this span needs to be pulled up */
	if(tmp->start >= s && tmp->start <= (s + h))
	{
	    tmp->height -= (s + h) - tmp->start;
	    tmp->start = s + h;
	    tmp = tmp->nexthigher;
	    continue;
	}
	/* case 3: upper part of this span needs to be lowered */
	if(TER_ENDPT(tmp) > s && TER_ENDPT(tmp) <= s + h)
	{
	    tmp->height -= TER_ENDPT(tmp) - s;
	    tmp = tmp->nexthigher;
	    continue;
	}
	/* case 4: this span needs to be split */
	if(TER_STARTPT(tmp) < s && TER_ENDPT(tmp) > (s + h))
	{
	    nxt = (TerrainSpans_ter *) malloc(sizeof(TerrainSpans_ter));
	    nxt->start = s + h;
	    nxt->height = (tmp->start + tmp->height) - (s + h);
	    nxt->vy = 0;
	    nxt->nexthigher = tmp->nexthigher;
	    nxt->nextlower = tmp;
	    if(nxt->nexthigher)
		nxt->nexthigher->nextlower = nxt;
	    tmp->height = s - tmp->start;
	    tmp->nexthigher = nxt;
	    tmp = nxt;
	    continue;
	}
	tmp = tmp->nexthigher;
    }
}

void terLine(int x1, int y1, int x2, int y2, TerrainSpans_ter * landscape)
{
    int y_unit, x_unit;
    int x = x1, y = y1;
    int ydiff = y2 - y1;
    int xdiff = x2 - x1;
    int error_term = 0;
    int length;
    register int i;

    if(ydiff < 0)
    {
	ydiff = -ydiff;
	y_unit = -1;
    }
    else
	y_unit = 1;

    if(xdiff < 0)
    {
	xdiff = -xdiff;
	x_unit = -1;
    }
    else
	x_unit = 1;

    if(xdiff > ydiff)
    {
	length = xdiff + 1;
	for(i = 0; i < length; i++)
	{
	    if(y > ter_sizey)
	    {
		landscape[x].start = 0;
		landscape[x].height = ter_sizey;
		landscape[x].nextlower = NULL;
		landscape[x].nexthigher = NULL;
	    }
	    else
	    {
		if(y > 0)
		{
		    landscape[x].start = 0;
		    landscape[x].height = y;
		    landscape[x].nextlower = NULL;
		    landscape[x].nexthigher = NULL;
		}
		else
		{
		    landscape[x].start = 0;
		    landscape[x].height = 0;
		    landscape[x].nextlower = NULL;
		    landscape[x].nexthigher = NULL;
		}
	    }
	    x += x_unit;
	    error_term += ydiff;
	    if(error_term > xdiff)
	    {
		error_term -= xdiff;
		y += y_unit;
	    }
	}
    }
    else
    {
	length = ydiff + 1;
	for(i = 0; i < length; i++)
	{
	    if(y > ter_sizey)
	    {
		landscape[x].start = 0;
		landscape[x].height = ter_sizey;
		landscape[x].nextlower = NULL;
		landscape[x].nexthigher = NULL;
	    }
	    else
	    {
		if(y > 0)
		{
		    landscape[x].start = 0;
		    landscape[x].height = y;
		    landscape[x].nextlower = NULL;
		    landscape[x].nexthigher = NULL;
		}
		else
		{
		    landscape[x].start = 0;
		    landscape[x].height = 0;
		    landscape[x].nextlower = NULL;
		    landscape[x].nexthigher = NULL;
		}
	    }
	    y += y_unit;
	    error_term += xdiff;
	    if(error_term > 0)
	    {
		error_term -= ydiff;
		x += x_unit;
	    }
	}
    }
}

/* fractal tessalation baby!  yea, dig it! */
void
terGenerate(int x1, int y1, int x2, int y2, int depth, int *terraintable,
	    TerrainSpans_ter * output)
{
    int midy, variation;

/*	midy=(y1+y2)/2+(random()%(depth*35))*(random()%2 ? 1 : -1); */

    if(depth > 0)
    {
	variation = (random() % terraintable[depth]);
	midy = (y1 + y2) / 2 + variation * (random() % 2 ? 1 : -1);
	terGenerate(x1,
		    y1,
		    x1 + (x2 - x1) / 2, midy, depth - 1, terraintable, output);
	terGenerate(x1 + (x2 - x1) / 2,
		    midy, x2, y2, depth - 1, terraintable, output);
    }
    else
    {
	terLine(x1, y1, x2, y2, output);
    }
}