/* engine.c
* This software is released under the revised BSD license.  
* See license.txt for details
* Copyright 2006 Dale Wick, John-Paul Gignac.
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include "engine.h"

#define range(x,min,max) ((x)<(min)?(min):((x)>(max)?(max):(x)))
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define mod(a,b) ((a)>=0?(a)%(b):(b)-1-(-1-(a))%(b))

#define can_hillwalk(a) ((a)->type == T_PLAYER)
#define x_ref(a) ((a)->x+(a)->x_tweak-((a)->landed_on?(a)->landed_on->x:0))

struct Game game;
static int dir_x[4]={-1,0,1,0},dir_y[4]={0,-1,0,1};
int editMode=0;

#define SECTORWIDTH (TILEWIDTH*8)
#define SECTORHEIGHT (TILEHEIGHT*8)
#define ACTIVE_MARGIN (TILEWIDTH*5)

#define TP_ANIMATED 1
#define TP_MIRROR_BELOW 2
#define TP_MIRROR_BESIDE 4
#define TP_FALLS 8
#define TP_BRIDGE 16
#define TP_SUBSTRATE 32	// You can stand on it, can't walk through it
#define TP_SLOPELEFT 64
#define TP_SLOPERIGHT 128
#define TP_SLIPPERY 256
#define TP_BADDY 512
#define TP_ETHEREAL 1024
#define TP_FRAMES_BELOW 2048

struct TileProp tileProp[]={
	{'!',T_PLAYER,M_PONY,7,5,6,TP_MIRROR_BESIDE|TP_FRAMES_BELOW|TP_BADDY|TP_FALLS,16,16,80,64,40,150},
	{'+',T_FRUIT,M_FRUIT1,1,1,4,TP_FRAMES_BELOW|TP_ETHEREAL,-12,0,40,16,0,0},
	{'#',T_GROUND,M_SOLIDGROUND,1,1,1,TP_SUBSTRATE,0,0,16,16,1000,2000},
	{'?',T_EXIT,M_EXIT,9,10,1,TP_ETHEREAL,59,82,1,78,0,0},
	{'2',T_GROUND,M_BRIDGE,1,1,1,TP_SUBSTRATE|TP_BRIDGE,0,0,16,16,1000,2000},
	{'F',T_CRATE,M_CRATE,2,2,1,TP_SUBSTRATE|TP_FALLS,0,0,32,32,30,2000},
	{'d',T_CRATE,M_HAYBALE,2,2,1,TP_SUBSTRATE|TP_FALLS,0,0,32,32,30,2000},
	{'I',T_ELEVATOR,M_ELEVATOR,8,1,1,TP_SUBSTRATE,0,0,96,16,100,2000},
	{'K',0,M_GRASS,1,1,1,TP_ETHEREAL,0,0,16,16,0,0},
	{'U',T_KITTEN,M_KITTEN,2,2,9,TP_FRAMES_BELOW|TP_FALLS,8,11,16,16,10,2000},
	{'V',T_KITTEN,M_KITTEN+2,2,2,9,TP_FRAMES_BELOW|TP_FALLS,8,11,16,16,10,2000},
	{'W',T_KITTEN,M_KITTEN+4,2,2,9,TP_FRAMES_BELOW|TP_FALLS,8,11,16,16,10,2000},
	{'%',T_SPECIALEFX,M_SPARKLE,2,2,2,TP_ETHEREAL,0,0,32,32,10,40},
	{'^',T_SPECIALEFX,M_KISSING,4,2,8,TP_FRAMES_BELOW|TP_ETHEREAL,0,0,64,32,10,40},
};

#define MAXCHAR 256
#define MAXTILE 2048
int mapCharToTile[MAXCHAR];
struct TileProp *mapTileToProp[MAXTILE];

#define JUMPINITIAL 1000
#define ROCKETINITIAL 2000
#define PATROLDIST (4*TILEWIDTH)
#define TERMINALVELOCITY 1000
#define HIGHGRAVITY 28
#define LOWGRAVITY 12
#define HORIZ_ACCEL 5
#define HORIZ_DECEL 7
#define HORIZ_SKID 23   // Deceleration when pointing the joystick
                        // opposite to the direction of motion.
#define MAX_SPEED 400

void set_tile(int x,int y,int tile)
{
	x+=game.l/TILEHEIGHT;
	y+=game.t/TILEWIDTH;
	if(x<0 || x>=game.w || y<0 || y>=game.h) return;
	game.map[x+y*game.w]=tile;
}

struct TileProp *tile_to_prop(int tile)
{
	if(tile<0 || tile>=MAXTILE) return NULL;
    return mapTileToProp[tile];
}

int ch_to_tile(int ch)
{
	if(ch<0 || ch>=MAXCHAR) return -1;
	
	return mapCharToTile[ch];
}

void set_tiles(int x,int y,int tile)
{
	struct TileProp *prop;
	int i,j;

	if(tile<0 || tile>=MAXTILE) {
		set_tile(x,y,-1);
		return;
	}
	
	prop=mapTileToProp[tile];
	if(prop==NULL) {
		set_tile(x,y,-1);
		return;
	}

	// Otherwise draw whole object.
	for(j=0;j<prop->gfxh;j++) {
		for(i=0;i<prop->gfxw;i++) {
			set_tile(x+i,y+j,prop->id+i+TILESACROSS*j);
		}
	}
	
}

int scaledcore = 0;

void new_game()
{
	int i;
	int mapped=0;

	game.level=1;
	game.lives=5;
	game.score=0;
	game.invalidate=0;
	game.map=0;
	// Initialize maps:

	for(i=0;i<MAXCHAR;i++) mapCharToTile[i]=-1;
	for(i=0;i<MAXTILE;i++) mapTileToProp[i]=NULL;
	// Now mark all of the ones in the list
	for(i=0;i<sizeof(tileProp)/sizeof(struct TileProp);i++) {
		int x,y;

        if( !scaledcore) {
            // Scale the core offset into high-precision coordinates
            tileProp[i].offsetx *= PRECISION;
            tileProp[i].offsety *= PRECISION;
            tileProp[i].w *= PRECISION;
            tileProp[i].h *= PRECISION;
        }

		mapCharToTile[tileProp[i].ch]=tileProp[i].id;
		for(y=0;y<tileProp[i].gfxh*(tileProp[i].flags&TP_MIRROR_BELOW?2:1)*(tileProp[i].flags&TP_FRAMES_BELOW?tileProp[i].frames:1);y++) {
			for(x=0;x<tileProp[i].gfxw*(tileProp[i].flags&TP_FRAMES_BELOW?1:tileProp[i].frames)*(tileProp[i].flags&TP_MIRROR_BESIDE?2:1);x++) {
//				ASSERT((mapTileToProp[tileProp[i].id+x+y*TILESACROSS]-tileProp))==-1);
				mapTileToProp[tileProp[i].id+x+y*TILESACROSS]=tileProp+i;
				mapped++;
			}
		}
	}
    scaledcore = 1;
#ifdef _DEBUG
	printf("char to tile table:\n");
	for(i=0;i<MAXCHAR;i++) {
		if(mapCharToTile[i]<0) continue;
		if(i>32 && i<127) printf("%c=",i);
		printf("%d\n",mapCharToTile[i]);
	}
	printf("tile to prop table:\n");
	for(i=0;i<MAXTILE;i++) {
		printf("%02x ",(mapTileToProp[i]-tileProp)&255);
		if((i%16)==15) printf("\n");
	}
#endif
//	ASSERT(mapped==MAXTILE);
    game.player.prop = mapTileToProp[M_PONY];
}

void init_char_iterator( struct CharIterator *iter,
        int x, int y, int w, int h)
{
    iter->minx = range((x-TILEWIDTH*5/2)/SECTORWIDTH,0,game.gridw-1);
    iter->miny = range((y-TILEHEIGHT*4/2)/SECTORHEIGHT,0,game.gridh-1);
    iter->maxx = range((x+w+TILEWIDTH*5/2-1)/SECTORWIDTH,0,game.gridw-1);
    iter->maxy = range((y+h+TILEHEIGHT*4/2-1)/SECTORHEIGHT,0,game.gridh-1);
    iter->x = iter->minx;
    iter->y = iter->miny-1;
    iter->last = NULL;
}

struct Character *next_char( struct CharIterator *iter)
{
    if( iter->last != NULL) iter->last = iter->last->next;
    while( iter->last == NULL) {
        iter->y ++;
        if( iter->y > iter->maxy) {
            iter->y = iter->miny;
            iter->x ++;
            if( iter->x > iter->maxx) return NULL;
        }
        iter->last = game.grid[iter->x + game.gridw * iter->y];
    }
    return iter->last;
}

int test_npc(int x,int y)
{
    struct CharIterator iter;
    struct Character *c;
    init_char_iterator( &iter, x, y, TILEWIDTH, TILEHEIGHT);
    while( (c = next_char(&iter)) != NULL) {
		// Overlapping
		if( x >= c->x - c->prop->offsetx &&
            x < c->x - c->prop->offsetx + TILEWIDTH * c->prop->gfxw &&
            y >= c->y - c->prop->offsety &&
            y < c->y - c->prop->offsety + TILEHEIGHT * c->prop->gfxh) return 0;
	}
	return -1;
}

// If the direction is horizontal, the "extra" parameter is used
// to imagine that all objects are that many units taller, thus
// increasing the chances of collisions.  It is only used in
// making a list of potential participants in horizontal pushes.
// If extra is not zero, then for simplicity, slopes are treated
// as their boundboxes.
int distance_to_collision(struct Character *moving,
    struct Character *waiting, int distance, int dir, int extra)
{
    int dist;

    // Collisions between identical non-substrate types are completely ignored.
    if( !(moving->prop->flags & TP_SUBSTRATE) &&
        moving->type == waiting->type && moving->type != T_KITTEN) return -1;

    // Use relativity to get rid of the UP and LEFT directions
    if( dir == D_LEFT || dir == D_UP) {
        struct Character *tmp = moving;
        moving = waiting;
        waiting = tmp;
        dir = (dir + 2) & 3;
    }

    dist = 0;
    if( dir == D_DOWN) {
        if( moving->x >= waiting->x + waiting->prop->w ||
            moving->x + moving->prop->w <= waiting->x) return -1;
        dist += waiting->y - moving->y - moving->prop->h;
    } else {
        if( moving->y - extra >= waiting->y + waiting->prop->h ||
            moving->y + moving->prop->h <= waiting->y - extra) return -1;
        dist += waiting->x - (moving->x + moving->prop->w);
    }

    if( dist < 0 || dist > distance) return -1;

    // Allow certain pairs of objects to pass through each other.  A -2 return
    // code indicates that there is a collision, but not one that interrupts
    // the motion.

    // Substrate can never pass through other substrate
    if( (waiting->prop->flags & TP_SUBSTRATE) &&
        (moving->prop->flags & TP_SUBSTRATE)) return dist;

    // If neither object is substrate, then they can always pass through
    if( !((waiting->prop->flags|moving->prop->flags) & TP_SUBSTRATE)) return -2;

    // Flying fruit can't pass through substrate
    if( (waiting->type == T_FRUIT && waiting->delay) ||
        (moving->type == T_FRUIT && moving->delay)) return dist;

    // Ethereal objects can pass through anything
    if( (waiting->prop->flags|moving->prop->flags) & TP_ETHEREAL) return -2;

    // The player can pass upwards through bridge substrate
    if( moving == &game.player &&
        (waiting->prop->flags & TP_BRIDGE) && dir != D_DOWN) return -2;
    if( waiting == &game.player &&
        (moving->prop->flags & TP_BRIDGE) && dir != D_UP) return -2;

    return dist;
}

struct Character **grid_square( int x, int y)
{
    x /= SECTORWIDTH;
    if( x < 0) x = 0;
    if( x >= game.gridw) x = game.gridw-1;

    y /= SECTORHEIGHT;
    if( y < 0) y = 0;
    if( y >= game.gridh) y = game.gridh-1;

    return &game.grid[x + game.gridw * y];
}

void setpos( struct Character *c, int x, int y)
{
    struct Character **sq = grid_square( x+c->prop->w/2, y+c->prop->h/2);
    c->x = x;
    c->y = y;
    c->prev = NULL;
    c->next = *sq;
    if(c->next) c->next->prev = c;
    *sq = c;
}

void unsetpos( struct Character *c)
{
    if( c->prev) c->prev->next = c->next;
    else *grid_square(c->x+c->prop->w/2,c->y+c->prop->h/2) = c->next;
    if( c->next) c->next->prev = c->prev;
}

void resetpos( struct Character *c, int x, int y)
{
    unsetpos( c);
    setpos( c, x, y);
}

void note_collision( struct Character *a, struct Character *b, int dir)
{
    if( game.collisionCount == MAXCOLLISIONS) return;
    game.collision[game.collisionCount].a = a;
    game.collision[game.collisionCount].b = b;
    game.collision[game.collisionCount].dir = dir;
    game.collisionCount ++;
}

void lift_off(struct Character *c)
{
    if( !c->landed_on) return;
    c->x_tweak -= c->landed_on->x;
	if( c->next_landed) c->next_landed->prev_landed = c->prev_landed;
	if( c->prev_landed) c->prev_landed->next_landed = c->next_landed;
	else c->landed_on->first_landed = c->next_landed;
    c->landed_on = NULL;
}

void land(struct Character *c, struct Character *on)
{
	if( c->prop->inertia > on->prop->inertia * 2) return;
	if( c->landed_on) lift_off(c);
	c->next_landed = on->first_landed;
	c->prev_landed = NULL;
	if( on->first_landed) on->first_landed = c;
	on->first_landed = c;
    c->landed_on = on;
    c->x_tweak += on->x;
}

// This function will push the character in the given direction with the
// given maxpressure.  The caller is responsible for calling motion_limit()
// first in order to ensure that the character will indeed be able to proceed
// the entire requested distance.  This function returns -1 if the character is
// crushed.  As a side effect, other characters may be pushed, pulled or
// crushed.
int push_character(struct Character *c, int distance, int dir, int maxpressure)
{
    int dist;
    struct Character *otherguy;

    // The character isn't being pushed hard enough to move it.
    if( c->prop->inertia > maxpressure) return 0;

    otherguy = game.first_marked;
    while( 1) {
        if( otherguy == NULL) {
            dist = distance;
            if( dir == D_LEFT && c->x - c->prop->offsetx - dist < 0)
                dist = c->x - c->prop->offsetx;
            else if( dir == D_RIGHT &&
                c->x - c->prop->offsetx + c->prop->gfxw * TILEWIDTH + dist >
                    game.w * TILEWIDTH)
                dist = (game.w - c->prop->gfxw)*TILEWIDTH -
                    (c->x - c->prop->offsetx);
            if( dist > distance) dist = distance;
        } else {
            dist = distance_to_collision( c, otherguy, distance, dir, 0);
            if( dist != -1) note_collision( c, otherguy, dir);
        }
        if( dist >= 0 && dist <= distance) {
            if( otherguy) {
                if( dir == D_DOWN) land(c,otherguy);
                else if( dir == D_UP) land(otherguy,c);
            }

            // Try to push the other character out of our way
            if( otherguy)
                dist += push_character( otherguy, distance-dist, dir,
                    min(maxpressure,c->prop->rigidity));

            if( dist < distance) {
                // We couldn't push the object out of our way.
                if( c->prop->rigidity >= maxpressure) {
                    // The character is rigid enough to withstand the pressure,
                    // so it will simply not move any further.  Something else
                    // up the chain will get crushed instead.
                    distance = dist;
                } else {
                    // The character is not rigid enough.  It is crushed.
                    c->type = -1;
                    return distance;
                }
            }
        }
        if( otherguy == NULL) break;
        otherguy = otherguy->next_marked;
    }

    // Now set this object's position.
    resetpos( c, c->x + distance * dir_x[dir], c->y + distance * dir_y[dir]);

    return distance;
}

// This function determines how far a character can be pushed in a certain
// cardinal direction when pushing with a certain amount of pressure.
// If the limit is greater than distance, or if the object would be crushed,
// this function returns distance.  Otherwise, it returns the distance that
// it could be pushed prior to jamming.
int motion_limit( struct Character *c, int distance, int dir,
        int maxpressure, int nocrush, struct Character **blocker)
{
    struct TileProp *p = c->prop;
    int dist;
    struct CharIterator iter;
    struct Character *d;

    // Just an optimization
    if( distance == 0) return 0;

    // If the character is being propelled with a higher maxpressure than its
    // skeleton can withstand, then there is no motion limit, because in the
    // worst case, the character would simply be crushed.
    if( !nocrush && maxpressure > c->prop->rigidity) return distance;

    // If the character's inertia is greater than the maxpressure, then it
    // won't budge.
    if( c->prop->inertia > maxpressure) return 0;

    // Do bounds checking against the left and right edges of the map
    if( dir == D_LEFT && c->x - p->offsetx - distance < 0)
        distance = c->x - p->offsetx;
    if( dir == D_RIGHT &&
        c->x-p->offsetx+p->gfxw*TILEWIDTH+distance>game.w*TILEWIDTH)
        distance = (game.w-p->gfxw)*TILEWIDTH - (c->x-p->offsetx);

    // Watch out for other characters that might block our path
    init_char_iterator( &iter,
        c->x + (dir==D_LEFT?-distance:(dir==D_RIGHT?c->prop->w:0)), 
        c->y + (dir==D_UP?-distance:(dir==D_DOWN?c->prop->h:0)), 
        (dir==D_LEFT || dir==D_RIGHT) ? distance : c->prop->w,
        (dir==D_UP || dir==D_DOWN) ? distance : c->prop->h);
    while( (d = next_char(&iter)) != NULL) {
        // Slight optimization
        if( distance == 0) break;

        dist = distance_to_collision( c, d, distance, dir, 0);
        if( dist >= 0 && dist < distance) {
            dist += motion_limit( d, distance-dist, dir,
                    min(maxpressure,c->prop->rigidity), nocrush, NULL);
            if( dist < distance) {
                distance = dist;
                if( blocker) *blocker = d;
            }
        }
    }

    return distance;
}

void accelerate( struct Character *c, int joystick_dir)
{
    struct TileProp *t;
    int dir = joystick_dir, accel, slipping;
    int vel = c->x_velocity;

    t = c->landed_on ? c->landed_on->prop : NULL;
    slipping = (t && (t->flags & TP_SLIPPERY));

    if( t) vel -= c->landed_on->x_velocity;

    if( vel < 0) dir = D_LEFT;
    if( vel > 0) dir = D_RIGHT;

    // Ignore up and down directions
    if( joystick_dir != D_LEFT && joystick_dir != D_RIGHT) joystick_dir=D_NONE;

    if( joystick_dir != D_NONE) {
        accel = dir_x[joystick_dir] * (slipping ? HORIZ_ACCEL / 2 :
            (dir==joystick_dir ? (t?HORIZ_ACCEL:HORIZ_ACCEL*3/4):HORIZ_SKID));
    } else if(t && dir != D_NONE) {
        accel = -dir_x[dir] * (slipping ? HORIZ_ACCEL / 4 : HORIZ_DECEL);
    } else {
        accel = 0;
    }

    vel += accel;

    if( vel < -MAX_SPEED && accel < 0) vel = min(vel-accel,-MAX_SPEED);
    if( vel > MAX_SPEED && accel > 0) vel = max(vel-accel,MAX_SPEED);

    // Disallow instantaneous change of direction
    if( (vel < 0 && dir == D_RIGHT) || (vel > 0 && dir == D_LEFT)) vel = 0;

    c->x_velocity = vel + (t ? c->landed_on->x_velocity : 0);
}

// This function marks all characters that might be involved
// in a particular push operation.
void mark_participants( struct Character *c, int distance,
        int dir, int maxpressure)
{
    struct CharIterator iter;
    struct Character *d;

    if( c->marked == 0) {
        c->next_marked = game.first_marked;
        game.first_marked = c;
    }
    c->marked = 2;

    if( c->prop->inertia > maxpressure) return;

    init_char_iterator( &iter,
        c->x-(dir==D_LEFT?distance:0),
        c->y-2*PRECISION-(dir==D_UP?distance:0),
        c->prop->w+((dir==D_LEFT||dir==D_RIGHT)?distance:0),
        c->prop->h+2*PRECISION+((dir==D_UP||dir==D_DOWN)?distance:0));
    while( (d = next_char(&iter)) != NULL) {
        int dist;
        if( d->marked == 2) continue;
        dist = distance_to_collision( c, d, distance, dir, 2*PRECISION);
        if( dist >= 0) mark_participants( d, distance, dir, maxpressure);
        else if( dist == -2 && d->marked == 0) {
            d->next_marked = game.first_marked;
            game.first_marked = d;
            d->marked = 1;
        }
    }
}

void handle_x_momentum( struct Character *c)
{
    int vel, dir, proposed_dist, dist;
    struct Character *blocker;

    // If we've already been pushed backwards this frame,
    // don't bother trying to move forwards.
    if( c->x_velocity * (c->x - c->oldx) < 0) return;

    vel = c->x_velocity - (c->x - c->oldx);
    if( vel == 0) return;

    dir = (vel < 0 ? D_LEFT : D_RIGHT);
    proposed_dist = (dir == D_LEFT ? -vel : vel);
    mark_participants( c, proposed_dist, dir, c->prop->inertia);

    dist = motion_limit(c, proposed_dist, dir, c->prop->inertia, 0, &blocker);
    dist = push_character( c, dist, dir, c->prop->inertia);
    if( dist < proposed_dist) {
        // We bumped into something
        c->x_velocity = 0;
    }

    while( game.first_marked) {
        game.first_marked->marked = 0;
        game.first_marked = game.first_marked->next_marked;
    }
}

void handle_y_momentum( struct Character *c)
{
    int vel, dir, proposed_dist, dist;
    struct Character *blocker;

    // If we've already been pushed backwards this frame,
    // don't bother trying to move forwards.
    if( c->y_velocity * (c->y - c->oldy) < 0) return;

    vel = c->y_velocity - (c->y - c->oldy);
    if( vel == 0) return;

    dir = (vel < 0 ? D_UP : D_DOWN);
    proposed_dist = (dir == D_UP ? -vel : vel);
    mark_participants( c, proposed_dist, dir, c->prop->inertia);

    dist = motion_limit(c, proposed_dist, dir, c->prop->inertia, 0, &blocker);
    dist = push_character( c, dist, dir, c->prop->inertia);
    if( dist < proposed_dist) {
        // We bumped into something
        c->y_velocity = 0;
    }

    while( game.first_marked) {
        game.first_marked->marked = 0;
        game.first_marked = game.first_marked->next_marked;
    }
}

struct Character *add_npc(int type,int x,int y,int dir,int id)
{
    struct Character *npc;

    npc = game.first_unused_npc;
    if( npc == NULL) return NULL;
    game.first_unused_npc = npc->next;

	npc->type=type;
	npc->homex=x;
	npc->homey=y;
	npc->facing=dir;
	npc->x_velocity=0;
	npc->y_velocity=0;
    npc->gravity=0;

	npc->frame=0;
	npc->health=100;
	npc->prop=mapTileToProp[id];
	npc->delay=0;
    npc->marked=0;
    npc->landed_on=NULL;
    npc->x_tweak=0;
	if(type==T_KITTEN) npc->frame=(x/TILEWIDTH)%npc->prop->frames;

    setpos( npc, x, y);

	return npc;
}

void new_level(int level)
{
	char buf[256];
	sprintf(buf,"map/level%03d.txt",level);
	load_level(buf);
	game.level=level;
	play_sound(S_LEVELSONG);
	play_sound(S_LEVELSTART);
	game.mode=MODE_GETREADY;
}

void construct_level(int w,int h) {
	int i;
	if(game.map) free(game.map);
	if(w<SCREENWIDTH) w=SCREENWIDTH;
	if(h<SCREENHEIGHT) h=SCREENHEIGHT;
	//printf("Decided on %dx%d map\n",w,h);
	game.map=(short *)malloc(w*h*sizeof(short));
	game.w=w;
	game.h=h;
	game.t=0;
	game.l=0;
	game.level=1;
	game.checkpointX=0;
	game.checkpointY=0;
	game.collected=0;
	game.available=0;	// Number of pieces of fruit to collect.
	game.bonus[0]=0;
	game.bonus[1]=0;
	game.bonus[2]=0;
	game.kittenCount=0;
	game.activeTeleport=-1;
    game.first_marked=NULL;
	for(i=0;i<4;i++) {
		game.key[i]=0;
	}

    for( i=0; i<MAXNPC-1; i++) game.npc[i].next = &game.npc[i+1];
    game.npc[i].next = NULL;
    game.first_unused_npc = &game.npc[0];

	for(i=0;i<w*h;i++) game.map[i]=-1;

    if( game.grid) free( game.grid);
    game.gridw = (w * TILEWIDTH + SECTORWIDTH-1) / SECTORWIDTH;
    game.gridh = (h * TILEHEIGHT + SECTORHEIGHT-1) / SECTORHEIGHT;
    game.grid = calloc( game.gridw * game.gridh, sizeof(*game.grid));
}

void load_level(const char *fname)
{
	FILE *file;
	int len=0;
	unsigned char *data=0;
	int i,j,k;
	int x,y;
	int w=0,h=0;
	int bol=0;
	int attr=0;
	enum ParseMode { PM_BOL,PM_COMMENT,PM_LINE,PM_ATTRIBUTE } pm=PM_BOL;
	const char *buf=fname;

	file=fopen(buf,"rb");
	if(file) {
		fseek(file,0,SEEK_END);
		len=ftell(file);
		fseek(file,0,SEEK_SET);
		if(len>0) {
			data=(unsigned char *)malloc(len+1);
			data[len]=0;
			fread(data,len,1,file);
			fclose(file);		// Slurped it in.  
		} else {
			fprintf(stderr,"Could not load empty file %s\n",buf);
			fclose(file);
		}
	} else {
		fprintf(stderr,"Could not find needed file %s\n",buf);
	}
	if(data==0) return load_level( "map/level001.txt");

	// Now figure out what it says:
	// Pass 1 through file:
	for(i=0;i<len;i++) {
		if(data[i]=='"') {
			pm=PM_COMMENT;
		} else if(data[i]=='\r' || data[i]=='\n') {
			if(pm==PM_LINE) {
				if(w<i-bol) w=i-bol;
				h++;
			}
			pm=PM_BOL;
			bol=i+1;
		} else if(pm==PM_COMMENT) {
			// Skip comment
		} else if(data[i]=='=') {
			attr=i+1;
			pm=PM_ATTRIBUTE;
		} else if(pm!=PM_ATTRIBUTE) {
			pm=PM_LINE;
		}
	}
	if(pm==PM_LINE) {
		if(w<i-bol) w=i-bol;
		h++;
	}
	// Now we should have the map size.
	//printf("Loading a %dx%d map...\n",w,h);
	construct_level(w,h);
	// Now create the path sections
	x=0;
	y=0;
	pm=PM_BOL;
	bol=0;
	for(i=0;i<len;i++) {
		if(data[i]=='"') {
			pm=PM_COMMENT;
		} else if(data[i]=='\r' || data[i]=='\n') {
			if(pm==PM_ATTRIBUTE) {
				// Should add it to the attributes list.
			} else if(pm==PM_LINE) {
				y++;
				x=0;
			}
			pm=PM_BOL;
			bol=i+1;
		} else if(pm==PM_COMMENT) {
			// Skip comment
		} else if(pm==PM_ATTRIBUTE) {
			// Collect attribute at the end
		} else if(data[i]=='=') {
			attr=i+1;
			pm=PM_ATTRIBUTE;
			x=0;
		} else if(pm!=PM_ATTRIBUTE) {
			int id=mapCharToTile[data[i]];
			struct TileProp *prop=NULL;
			if(id>=0) prop=mapTileToProp[id];

			if(!prop && data[i]!=' ') printf("Error loading cell %d,%d: %c\n",x,y,data[i]);

			pm=PM_LINE;
			if(prop && game.map[x+w*y]==-1) {
				if(prop == tileProp && editMode==0) {
					// We've found the start point for the level.
					if(game.checkpointX==0 && game.checkpointY==0) {
						game.checkpointX=(x+mapTileToProp[M_PONY]->gfxw/2)*TILEWIDTH;
						game.checkpointY=(y+mapTileToProp[M_PONY]->gfxh)*TILEHEIGHT;
					}
				} else if(editMode==0) {
					if(test_npc(x*TILEWIDTH,y*TILEHEIGHT)==-1) {
						struct Character *c = add_npc(prop->type,x*TILEWIDTH+mapTileToProp[id]->offsetx,
                            y*TILEHEIGHT+mapTileToProp[id]->offsety,D_LEFT,id);
                        if( c) {
                            if( prop->type == T_FRUIT) c->frame = (x+y)%4;
                            // Quick kitten-kitten collision system
                            if( prop->type == T_KITTEN && game.kittenCount<MAXKITTEN) {
								game.kitten[game.kittenCount++]=c;
								printf("Found kitten %d\n",game.kittenCount);
							}
                            if( prop->flags & TP_FALLS)
                                c->gravity=(HIGHGRAVITY+LOWGRAVITY)/2;
                        }
					}
				} else {	// Fill in the tiles for the whole object.
					for(j=0;j<prop->gfxh;j++) {
						for(k=0;k<prop->gfxw;k++) {
							game.map[x+k+(y+j)*w]=id+k+TILESACROSS*j;
						}
					}
				}
				if(prop->id==M_FRUIT1) game.available++;
			}
			x++;
		}
	}
	game.player.health=100;
	game.player.invincible=0;
	game.player.x_velocity=0;
	game.player.y_velocity=0;
	game.player.gravity=HIGHGRAVITY;
	game.player.facing=D_RIGHT;
	game.invalidate=2;
    game.player.marked=0;
    game.player.landed_on = NULL;
    game.player.x_tweak=0;

    if( game.checkpointX == 0 && game.checkpointY == 0) {
        game.checkpointX = mapTileToProp[M_PONY]->gfxw*TILEWIDTH/2;
        game.checkpointY = mapTileToProp[M_PONY]->gfxh*TILEHEIGHT;
    }

    setpos( &game.player,
        game.checkpointX - game.player.prop->w/2,
        game.checkpointY - game.player.prop->h);
}

void save_level(const char *fname) 
{
	int x,y;
	FILE *file;
	int blank=0;

	file=fopen(fname,"w");

	for(y=0;y<game.h;y++) {
		for(x=0;x<game.w;x++) {
			if(game.map[x+y*game.w]==-1) {
				fprintf(file," ");
				blank++;
			} else {
				int tile=game.map[x+y*game.w];
				//fprintf(file,"t=%d;p=%d;",tile,prop);
				fprintf(file,"%c",mapTileToProp[tile]->ch);
			}
		}
		fprintf(file,"\n");
	}
	fclose(file);
	printf("%d of %d tiles are sky.\n",blank,game.w*game.h);
}

void draw_map()
{
	int i;
    struct CharIterator iter;
    struct Character *c;

	if(game.invalidate>0) game.invalidate--;

	// Now draw all the npcs:
    for( i=0; i<3; i++) {
        init_char_iterator( &iter, game.l, game.t,
            SCREENWIDTH * TILEWIDTH, SCREENHEIGHT * TILEHEIGHT);
        while( (c = next_char(&iter)) != NULL) {
            struct TileProp *p = c->prop;
            int id = p->id + c->frame * (p->flags&TP_FRAMES_BELOW?p->gfxh*TILESACROSS:p->gfxw);
            if( i == 2 && c != &game.player) continue;
            if(c->facing == D_LEFT && (p->flags & TP_MIRROR_BELOW))
                id += p->gfxh*TILESACROSS;
            if(c->facing == D_LEFT && (p->flags & TP_MIRROR_BESIDE))
                id += p->gfxw*(p->flags&TP_FRAMES_BELOW?1:p->frames);
            if((c->invincible % 20) < 10) {
                draw_tile_rect( id, (c->x-p->offsetx-game.l) / PRECISION,
                        (c->y-p->offsety-game.t) / PRECISION,
                        p->gfxw, p->gfxh);
            }
            if( c->invincible > 0) c->invincible --;
        }
    }
}

void set_player_direction(int direction)
{
	if(game.activeTeleport==-1) 
		game.joystick=direction;
	else {
		game.joystick=-1;
		game.player.x_velocity=0;
		game.player.y_velocity=0;
	}
}

void do_jump()		// Handle CROSS
{
	if(game.lives==0) {
		new_game();
		new_level(game.level);
		return;
	}
	if(game.activeTeleport>=0) return;
	if(game.player.landed_on) {
        game.player.y_velocity=-JUMPINITIAL;
        play_sound(S_JUMP);
    }
    game.player.gravity = LOWGRAVITY;
}

void release_jump()
{
    game.player.gravity = HIGHGRAVITY;
}

int overlap(struct Character *a, struct Character *b)
{
    if( a->x > b->x + b->prop->w) return 0;
    if( b->x > a->x + a->prop->w) return 0;
    if( a->y > b->y + b->prop->h) return 0;
    if( b->y > a->y + a->prop->h) return 0;
    return 1;
}

void do_attack()		// Handle SQUARE
{
}

void do_special()		// Handle CIRCLE (shoot)
{
}

void do_bomb()		// Handle TRIANGLE (bomb)
{
}

int npc_damage(struct Character *npc,int percent)
{
	if( game.player.invincible > 0 && percent>0) return 0;
    if(percent>0) play_sound(S_DIE);
    game.player.health-=percent;
    if(percent>0) game.player.invincible = 200;
    return 1;
}

void clear_substrate( struct Character *brick, int dir)
{
    struct CharIterator iter;
    struct Character *c;

    init_char_iterator( &iter,
        brick->x + dir_x[dir]*TILEWIDTH,
        brick->y + dir_y[dir]*TILEHEIGHT,
        TILEWIDTH, TILEHEIGHT);
    while( (c = next_char(&iter)) != NULL) {
        if( c->prop->id == brick->prop->id &&
            c->x == brick->x + dir_x[dir]*TILEWIDTH &&
            c->y == brick->y + dir_y[dir]*TILEHEIGHT) {
            clear_substrate( c, dir);
            break;
        }
    }
    brick->type = -1;
}

void matched_kittens(struct Character *a,struct Character *b) {
	game.score+=1000;
	play_sound(S_MATCH);
	// Make em disappear.
	a->type=-1;
	b->type=-1;
	game.bonus[game.bonus[0]==0?0:(game.bonus[1]==0?1:2)]=1;
    struct Character *t = add_npc(T_SPECIALEFX,a->x,a->y,D_LEFT,M_SPARKLE);
    if(t) t->delay = PATROLDIST/PRECISION*3;
}

void handle_collision( struct Collision *c) {
    if( c->a->type == -1 || c->b->type == -1) return;

    if( c->a == &game.player || c->b == &game.player) {
        struct Character *npc = (c->a==&game.player?c->b:c->a);
        switch( npc->type) {
        case T_KITTEN:
			if(npc->landed_on != &game.player) {
				if(npc->y>=game.player.y)
					play_sound(S_KITTEN);
			    resetpos( npc,
				game.player.x+game.player.prop->w/2-npc->prop->w/2,
				game.player.y-npc->prop->h);
			}
            break;
        case T_FRUIT:
            if( npc->x_velocity == 0) {
                npc->type=-1;
                game.score+=10;
                game.collected++;
                //play_sound(S_FRUIT);
            }
            break;
        case T_ELEVATOR:
            if( npc->prop->id == M_ELEVATOR) {
				play_sound(S_ELEVATOR);
			}

            break;
        case T_EXIT:
            if(game.collected>=5*game.available/10) {
                new_level(game.level+1);
                game.mode=MODE_LEVELOVER;
            }
            break;
        }
    }
}

void update_npc(struct Character *npc)
{
	int maxspeed,accel,targetvel;
	
	switch(npc->type) {
	case T_FRUIT:
        if( npc->x_velocity) {
            if(npc->landed_on) {
                npc->x_velocity=0;
                npc->gravity = 0;
                npc->delay = 0;  // Changes the behaviour of the fruit
            } else npc->gravity = HIGHGRAVITY;
        }
        break;
    case T_SPECIALEFX:	// Sparkle
    	game.player.x_velocity=0;
    	game.player.y_velocity=0;
		if(npc->delay>0) {
			npc->delay--;
			npc->frame=(npc->delay/15)%npc->prop->frames;
		} else {
			npc->type=-1;	// Effect done
			game.activeTeleport=-1;
		}
        break;
    case T_ELEVATOR:
		// Patrol vacinity of checkpoint. with Gravity/Flight
        maxspeed = PRECISION/2;
        accel = maxspeed*maxspeed/PATROLDIST*3/2;

        if( npc->facing != D_UP && npc->facing != D_DOWN) npc->facing = D_UP;

        if( npc->y_velocity == 0) npc->facing = D_UP+D_DOWN-npc->facing;

        targetvel = maxspeed * dir_y[npc->facing];

        if( npc->facing == D_UP &&
            motion_limit(npc,TILEHEIGHT*7,D_UP,npc->prop->inertia,0,NULL) < 
                TILEHEIGHT*7) targetvel = maxspeed;

        if( npc->y_velocity > targetvel)
            npc->y_velocity = max(targetvel,npc->y_velocity-accel);
        else
            npc->y_velocity = min(targetvel,npc->y_velocity+accel);

        npc->facing = (npc->y_velocity < 0 ? D_UP : D_DOWN);

        break;
    case T_PONY:
        if( npc->x_velocity == 0) npc->facing = D_LEFT+D_RIGHT-npc->facing;

        npc->frame = mod(x_ref(npc)/(PRECISION*5),npc->prop->frames);
        if( npc->facing == D_RIGHT) npc->frame=npc->prop->frames-1-npc->frame;

        npc->x_velocity = (npc->facing==D_LEFT?-PRECISION/4:PRECISION/4);

        break;
    case T_KITTEN:
		if(npc->y>game.h*TILEHEIGHT) {	// Fell off the screen, teleport to safety.
	        resetpos( npc,
	            game.checkpointX-game.player.prop->w/2,
	            game.checkpointY-game.player.prop->h);
		}
        npc->delay --;
        if( npc->delay <= 0) {
            npc->delay = 50;
            npc->frame ++;
            if( npc->frame == npc->prop->frames) npc->frame = 0;
        }
        break;
	}
}

void next_frame_tick();

void next_frame(int elapsed)
{
	while(elapsed>5) {
		next_frame_tick();
		elapsed-=5;
	}
//	next_frame_tick();
//	SDL_Delay(20);
}

void next_frame_tick()
{
	int i;
	int x,y;
    struct CharIterator iter;
    struct Character *c;

	if( game.player.health <= 0) {
		game.player.health = 100;
		game.player.x_velocity=0;
		game.player.y_velocity=0;
        game.player.gravity=HIGHGRAVITY;
		game.player.facing=D_RIGHT;
        resetpos( &game.player,
            game.checkpointX-game.player.prop->w/2,
            game.checkpointY-game.player.prop->h);
		game.lives --;
		if(game.lives>0) {
			play_sound(S_LEVELSTART);
			game.mode=MODE_GETREADY;
		} else {
			game.mode=MODE_GAMEOVER;
			play_sound(S_LEVELEND);
		}

        init_char_iterator(&iter,0,0,game.w*TILEWIDTH,game.h*TILEHEIGHT);
        while( (c = next_char(&iter)) != NULL) {
            if( c->type == T_GROUND) c->frame = 0;
        }
	}
	if(game.lives<1) return;
	if(game.player.y - game.player.prop->offsety > game.h*TILEHEIGHT)
        game.player.health=0;

	// See if moving in direction is currently valid.
	if(game.joystick==D_LEFT || game.joystick==D_RIGHT) {
//        game.player.prop=mapTileToProp[M_PONY];
		game.player.facing=game.joystick;
	}

    // Make a list of all of the active characters
    game.first_active = NULL;
    init_char_iterator( &iter,
        game.l - ACTIVE_MARGIN, game.t - ACTIVE_MARGIN,
        SCREENWIDTH * TILEWIDTH + ACTIVE_MARGIN*2,
        SCREENHEIGHT * TILEHEIGHT + ACTIVE_MARGIN*2);
    while( (c = next_char(&iter)) != NULL) {
        c->next_active = game.first_active;
        game.first_active = c;
    }

	// Also needs to check npcs.
    c = game.first_active;
    while( c) {
        update_npc(c);
        c = c->next_active;
    }

    c = game.first_active;
    while( c) {
        accelerate( c, c==&game.player ? game.joystick : D_NONE);
        c->y_velocity = min(c->y_velocity + c->gravity, TERMINALVELOCITY);
        c->oldx = c->x;
        c->oldy = c->y;
        lift_off(c);
        c = c->next_active;
    }

    // Reset the list of collisions
    game.collisionCount = 0;

    c = game.first_active;
    while( c) {
        handle_y_momentum( c);
        handle_x_momentum( c);
        c = c->next_active;
    }

    // Set the velocities for next frame according to how far the characters
    // actually moved this frame.
    c = game.first_active;
    while( c) {
        c->x_velocity = c->x - c->oldx;
        c->y_velocity = c->y - c->oldy;
        c = c->next_active;
    }

    // Handle collisions
    for(i=0; i<game.collisionCount; i++) {
        handle_collision( &game.collision[i]);
    }

    // Handle kitten collisions
    for(i=0; i<game.kittenCount; i++) {
		struct Collision col,*c=&col;
		int j;
		c->a=game.kitten[i];
		for(j=i+1; j<game.kittenCount; j++) {
			c->b=game.kitten[j];
			c->dir=D_RIGHT;
			if(c->a->type==T_KITTEN && c->b->type==T_KITTEN) {
		        // Check for overlapping rectangles
		        if(c->a->x > c->b->x+c->b->prop->w ||
		        c->a->x+c->a->prop->w < c->b->x ||
		        c->a->y > c->b->y+c->b->prop->h ||
		        c->a->y+c->a->prop->h < c->b->y) {
					// Out of range
				} else {
					// We overlap!
					if(c->a->prop==c->b->prop)
						matched_kittens(c->a,c->b);
				}
			}
		}
    }

	// Now reap the dead characters
    struct Character *dead = NULL;
    init_char_iterator(&iter,0,0,game.w*TILEWIDTH,game.h*TILEHEIGHT);
    while( (c = next_char(&iter)) != NULL) {
        if( c->type == -1) {
            c->next_marked = dead;
            dead = c;
        }
    }
    while( dead) {
        unsetpos( dead);
        dead->next = game.first_unused_npc;
        game.first_unused_npc = dead;
        dead = dead->next_marked;
	}

	// Attempt to centre the player on screen.
    x = game.player.x + game.player.prop->w / 2;
    y = game.player.y + game.player.prop->h / 2;
    if( x - game.l < SCREENWIDTH * TILEWIDTH / 3)
        game.l = x - SCREENWIDTH * TILEWIDTH / 3;
    else if( x - game.l > SCREENWIDTH * TILEWIDTH * 2 / 3)
        game.l = x - SCREENWIDTH * TILEWIDTH * 2 / 3;
    if( y - game.t < SCREENHEIGHT * TILEHEIGHT / 3)
        game.t = y - SCREENHEIGHT * TILEHEIGHT / 3;
    else if( y - game.t > SCREENHEIGHT * TILEHEIGHT * 2 / 3)
        game.t = y - SCREENHEIGHT * TILEHEIGHT * 2 / 3;
	if(game.t<0) game.t=0;
	if(game.t+TILEHEIGHT*SCREENHEIGHT>game.h*TILEHEIGHT) game.t=(game.h-SCREENHEIGHT)*TILEHEIGHT;
	if(game.l<0) game.l=0;
	if(game.l+TILEWIDTH*SCREENWIDTH>game.w*TILEWIDTH) game.l=(game.w-SCREENWIDTH)*TILEWIDTH;

    game.player.frame=mod(x_ref(&game.player)/(PRECISION*5),game.player.prop->frames);
    if( game.player.facing == D_RIGHT) game.player.frame=game.player.prop->frames-1-game.player.frame;
}
