/****************************************************************************

EDITSS: A shipshape editor for XPilot shipshapes     V2.1
Copyright (C) 1994 Ronald In 't Velt


    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., 675 Mass Ave, Cambridge, MA 02139, USA.

Right now, it is impossible to reach me via E-Mail.  When I will have
an account again somewhere, I will post a notice in alt.games.xpilot (or
rec.games.xpilot in case this newgroup is accepted into rec.).

****************************************************************************/


/* EDITSS V2.1 Module pship.c 
 *
 * THIS MODULE IS AN ADAPTED VERSION OF THE MATH.C PART OF XPILOT
 *
 * XPilot, a multiplayer gravity war game.  Copyright (C) 1991-94 by
 *
 *      Bjørn Stabell        (bjoerns@staff.cs.uit.no)
 *      Ken Ronny Schouten   (kenrsc@stud.cs.uit.no)
 *      Bert Gÿsbers         (bert@mc.bio.uva.nl)
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#include <X11/Intrinsic.h>	/* nessesary for some functions */

#include "const.h"		/* provide access to other editss stuff */
#include "types.h"
#include "vars.h"
#include "xstuff.h"
#include "pship.h"

#define MSG_LEN MAXSHIPLEN	/* redefine max message length */

static int	debugShapeParsing = 0;
static int	verboseShapeParsing;
static int	shapeLimits;

static int	Get_shape_keyword(char *keyw);


int mod(int x, int y)		/* modulo */
{
    if (x >= y || x < 0)
	x = x - y*(x/y);

    if (x < 0)
	x += y;

    return x;
}



static int minimum(int a, int b)		/* return smallest */
{
	if (a>b) return b; else return a;
}



static int shape2wire(char *ship_shape_str, ship *w)
{
/*
 * Macros to simplify limit-checking for ship points.
 * Until XPilot goes C++.
 */
#define GRID_PT(x,y)	grid.pt[(x)+15][(y)+15]
#define GRID_ADD(x,y)	(GRID_PT(x, y) = 2, \
			 grid.chk[grid.todo][0] = (x), \
			 grid.chk[grid.todo][1] = (y), \
			 grid.todo++)
#define GRID_GET(x,y)	((x) = grid.chk[grid.done][0], \
			 (y) = grid.chk[grid.done][1], \
			 grid.done++)
#define GRID_CHK(x,y)	(GRID_PT(x, y) == 2)
#define GRID_READY()	(grid.done >= grid.todo)
#define GRID_RESET()	(memset(grid.pt, 0, sizeof grid.pt), \
			 grid.done = 0, \
			 grid.todo = 0)

    struct grid_t {
	int		todo, done;
	char		pt[32][32];
	signed char		chk[32*32][2];
    } grid;

    int 		i, j, x, y, dx, dy,
    			inx, iny, max,
    			ofNum, ofLeft, ofRight;		/* old format */
    int			shape_version = 0;
    point 		pt[MAXPOINTS],
			engine,
			m_gun,
			l_light[MAXLIGHTS],
			r_light[MAXLIGHTS],
			l_gun[MAXGUNS],
			r_gun[MAXGUNS],
			m_rack[MAXRACK];
    bool		mainGunSet = FALSE,
			engineSet = FALSE;
    char		*str,
    			*teststr,
				*endstr;
    char 		keyw[20],
    			buf[MSG_LEN];

    w->n = 0;
    w->nlg = 0;
    w->nrg = 0;
    w->nll = 0;
    w->nrl = 0;
    w->nmr = 0;
	 *w->name='\0';
	 *w->author='\0';
	shape_version=0;

    if (debugShapeParsing) {
	printf("parsing shape: %s\n", ship_shape_str);
    }

    for (str = ship_shape_str; (str = strchr(str, '(' )) != NULL; ) {

        str++;

        if (shape_version == 0) {
	    if (isdigit(*str)) {
		shape_version = 0x3100;
		w->version=shape_version;
		if (verboseShapeParsing) {
		    printf("ship shape is in old format\n");
		}
		break;
	    }
	    else {
		shape_version = 0x3200;
		w->version=shape_version;
	    }
	}

        for (i = 0; (keyw[i] = str[i]) != '\0'; i++) {
	    if (i == sizeof(keyw) - 1) {
		keyw[i] = '\0';
		break;
	    }
	    if (keyw[i] == ':') {
		keyw[i + 1] = '\0';
		break;
	    }
	}
	if (str[i] != ':') {
	    if (verboseShapeParsing) {
		printf("Missing colon in ship shape: %s\n", keyw);
	    }
	    continue;
	}
        for (teststr = &buf[++i]; (buf[i] = str[i]) != '\0'; i++) {
	    if (buf[i] == ')' ) {
		buf[++i] = '\0';
		break;
	    }
        }
        str += i;

	switch (Get_shape_keyword(keyw)) {

	case 0:		/* Keyword is 'shape' */
	    while (teststr) {
		while (*teststr == ' ') teststr++;
		if (sscanf(teststr, "%d,%d", &inx, &iny) != 2) {
		    if (verboseShapeParsing) {
			printf("Missing ship shape coordinate in: \"%s\"\n",
			       teststr);
		    }
		    break;
		}
		if (w->n >= MAXPOINTS) {
		    if (verboseShapeParsing) {
			printf("Too many ship shape coordinates\n");
		    }
		}
		else {
		    pt[w->n].x = inx;
		    pt[w->n].y = iny;
		    w->n++;
		    if (debugShapeParsing) {
			printf("ship point at %d,%d\n", inx, iny);
		    }
		}
		teststr = strchr(teststr, ' ');
	    }
	    break;

	case 1:		/* Keyword is 'mainGun' */
	    if (mainGunSet) {
		if (verboseShapeParsing) {
		    printf("Ship shape keyword \"%s\" multiple defined\n",
			   keyw);
		}
		break;
	    }
	    while (*teststr == ' ') teststr++;
	    if (sscanf(teststr, "%d,%d", &inx, &iny) != 2) {
		if (verboseShapeParsing) {
		    printf("Missing main gun coordinate in: \"%s\"\n",
			   teststr);
		}
	    }
	    else {
		m_gun.x = inx;
		m_gun.y = iny;
		mainGunSet = TRUE;
		if (debugShapeParsing) {
		    printf("main gun at %d,%d\n", inx, iny);
		}
	    }
	    break;

	case 2:		/* Keyword is 'leftGun' */
	    while (teststr) {
		while (*teststr == ' ') teststr++;
		if (sscanf(teststr, "%d,%d", &inx, &iny) != 2) {
		    if (verboseShapeParsing) {
			printf("Missing left gun coordinate in: \"%s\"\n",
			       teststr);
		    }
		    break;
		}
		if (w->nlg >= MAXGUNS) {
		    if (verboseShapeParsing) {
			printf("Too many left gun coordinates\n");
		    }
		}
		else {
		    l_gun[w->nlg].x = inx;
		    l_gun[w->nlg].y = iny;
		    w->nlg++;
		    if (debugShapeParsing) {
			printf("left gun at %d,%d\n", inx, iny);
		    }
		}
		teststr = strchr(teststr, ' ');
	    }
	    break;

	case 3:		/* Keyword is 'rightGun' */
	    while (teststr) {
		while (*teststr == ' ') teststr++;
		if (sscanf(teststr, "%d,%d" ,&inx, &iny) != 2) {
		    if (verboseShapeParsing) {
			printf("Missing right gun coordinate in: \"%s\"\n",
			       teststr);
		    }
		    break;
		}
		if (w->nrg >= MAXGUNS) {
		    if (verboseShapeParsing) {
			printf("Too many right gun coordinates\n");
		    }
		}
		else {
		    r_gun[w->nrg].x = inx;
		    r_gun[w->nrg].y = iny;
		    w->nrg++;
		    if (debugShapeParsing) {
			printf("right gun at %d,%d\n", inx, iny);
		    }
		}
		teststr = strchr(teststr, ' ');
	    }
	    break;

	case 4:		/* Keyword is 'leftLight' */
	    while (teststr) {
		while (*teststr == ' ') teststr++;
		if (sscanf(teststr, "%d,%d", &inx, &iny) != 2) {
		    if (verboseShapeParsing) {
			printf("Missing left light coordinate in: \"%s\"\n",
			       teststr);
		    }
		    break;
		}
		if (w->nll >= MAXLIGHTS) {
		    if (verboseShapeParsing) {
			printf("Too many left light coordinates\n");
		    }
		}
		else {
		    l_light[w->nll].x = inx;
		    l_light[w->nll].y = iny;
		    w->nll++;
		    if (debugShapeParsing) {
			printf("left light at %d,%d\n", inx, iny);
		    }
		}
		teststr = strchr(teststr, ' ');
	    }
	    break;

	case 5:		/* Keyword is 'rightLight' */
	    while (teststr) {
		while (*teststr == ' ') teststr++;
		if (sscanf(teststr, "%d,%d", &inx, &iny) != 2) {
		    if (verboseShapeParsing) {
			printf("Missing right light coordinate in: \"%s\"\n",
			       teststr);
		    }
		    break;
		}
		if (w->nrl >= MAXLIGHTS) {
		    if (verboseShapeParsing) {
			printf("Too many right light coordinates\n");
		    }
		}
		else {
		    r_light[w->nrl].x = inx;
		    r_light[w->nrl].y = iny;
		    w->nrl++;
		    if (debugShapeParsing) {
			printf("right light at %d,%d\n", inx, iny);
		    }
		}
		teststr = strchr(teststr, ' ');
	    }
	    break;

	case 6:		/* Keyword is 'engine' */
	    if (engineSet) {
		if (verboseShapeParsing) {
		    printf("Ship shape keyword \"%s\" multiple defined\n",
			   keyw);
		}
		break;
	    }
	    while (*teststr == ' ') teststr++;
	    if (sscanf(teststr, "%d,%d", &inx, &iny) != 2) {
		if (verboseShapeParsing) {
		    printf("Missing engin coordinate in: \"%s\"\n",
			   teststr);
		}
	    }
	    else {
		engine.x = inx;
		engine.y = iny;
		engineSet = TRUE;
		if (debugShapeParsing) {
		    printf("engine at %d,%d\n", inx, iny);
		}
	    }
	    break;

	case 7:		/* Keyword is 'missileRack' */
	    while (teststr) {
		while (*teststr == ' ') teststr++;
		if (sscanf(teststr, "%d,%d", &inx, &iny) != 2) {
		    if (verboseShapeParsing) {
			printf("Missing missile rack coordinate in: \"%s\"\n",
			       teststr);
		    }
		    break;
		}
		if (w->nmr >= MAXRACK) {
		    if (verboseShapeParsing) {
			printf("Too many missile rack coordinates\n");
		    }
		}
		else {
		    m_rack[w->nmr].x = inx;
		    m_rack[w->nmr].y = iny;
		    w->nmr++;
		    if (debugShapeParsing) {
			printf("missile rack at %d,%d\n", inx, iny);
		    }
		}
		teststr = strchr(teststr, ' ');
	    }
	    break;

	case 8:	/* keyword is 'name' */
		while (*teststr == ' ') teststr++;
		endstr = strchr(teststr,')');
		if (endstr==NULL) {
			if (verboseShapeParsing) printf("Error in name field\n");
		} else {
			strncpy(w->name, teststr, strcspn(teststr,")")+1);
			endstr = strchr(w->name,')');
			*endstr='\0';			
			if (debugShapeParsing) printf("name: %s\n",w->name);
		}
		break;

	case 9:	/* keyword is 'author' */
		while (*teststr == ' ') teststr++;
		endstr = strchr(teststr,')');
		if (endstr==NULL) {
			if (verboseShapeParsing) printf("Error in author field\n");
		} else {
			strncpy(w->author, teststr, strcspn(teststr,")")+1);
			endstr = strchr(w->author,')');
			*endstr='\0';			
			if (debugShapeParsing) printf("author: %s\n",w->author);
		}
		break;

	default:
	    if (verboseShapeParsing) {
		printf("Invalid ship shape keyword: \"%s\"\n", keyw);
	    }
	    /* the good thing about this format is that we can just ignore
	     * this.  it is likely to be a new extension we don't know
	     * about yet. */
	    break;
	}
    }

    if (shape_version == 0x3100) {
	str = ship_shape_str;

	if (sscanf(str, "(%d,%d,%d)", &ofNum, &ofLeft, &ofRight) != 3
	    || ofNum < MINPOINTS
	    || ofNum > MAXPOINTS
	    || ofLeft < 0
	    || ofLeft >= ofNum
	    || ofRight < 0
	    || ofRight >= ofNum
	    ) {
	    if (verboseShapeParsing) {
		printf("Invalid ship shape header: \"%s\"\n", str);
	    }
	    return -1;
	}

	for (i = 0; i < ofNum; i++) {
	    str = strchr(str + 1, '(');
	    if (!str) {
		if (verboseShapeParsing) {
		    printf("Bad ship shape: "
			   "only %d points defined, %d expected\n",
			   i, ofNum);
		}
		return -1;
	    }
	    if (sscanf(str, "(%d,%d)", &inx, &iny) != 2) {
		if (verboseShapeParsing) {
		    printf("Bad ship shape: format error in point %d\n",
			   i);
		}
		return -1;
	    }
	    pt[i].x = inx;
	    pt[i].y = iny;
	}

	w->n = ofNum;

	m_gun = pt[0];
	mainGunSet = TRUE;

	l_light[0] = pt[ofLeft];
	w->nll = 1;

	r_light[0] = pt[ofRight];
	w->nrl = 1;

	engine.x = (pt[ofLeft].x + pt[ofRight].x) / 2;
	engine.y = (pt[ofLeft].y + pt[ofRight].y) / 2;
	engineSet = TRUE;
    }

    /* Check for some things being set, and give them defaults if not */

    if (w->n < 3) {
	if (verboseShapeParsing) {
	    printf("not enough ship points defined\n");
	}
	return -1;
    }
    if (!mainGunSet) {		/* No main gun set, put at foremost point */
    	max = 0;
    	for (i = 1; i < w->n; i++) {
    	    if (pt[i].x > pt[max].x
		|| (pt[i].x == pt[max].x
		    && abs(pt[i].y) < abs(pt[max].y))) {
    	        max = i;
            }
        }
	m_gun = pt[max];
	mainGunSet = TRUE;
    }
    if (!w->nll) {	/* No left light set, put at leftmost point */
	max = 0;
    	for (i = 1; i < w->n; i++) {
    	    if (pt[i].y > pt[max].y
		|| (pt[i].y == pt[max].y
		    && pt[i].x <= pt[max].x)) {
    	        max = i;
            }
        }
	l_light[0] = pt[max];
        w->nll = 1;
    }
    if (!w->nrl) {	/* No right light set, put at rightmost point */
	max = 0;
    	for (i = 1; i < w->n; i++) {
    	    if (pt[i].y < pt[max].y
		|| (pt[i].y == pt[max].y
		    && pt[i].x <= pt[max].x)) {
    	        max = i;
            }
        }
	r_light[0] = pt[max];
        w->nrl = 1;
    }
    if (!engineSet) {		/* No engine position, put at rear of ship */
    	max = 0;
    	for (i = 1; i < w->n; i++) {
    	    if (pt[i].x < pt[max].x) {
    	        max = i;
            }
        }
	engine.x = pt[max].x;
	engine.y = 0;		/* this may lay outside of ship. */
	engineSet = TRUE;
    }
    if (!w->nmr) {	/* No missile racks, put at main gun position*/
        m_rack[0] = m_gun;
        w->nmr = 1;
    }

    if (shapeLimits) {
	const int	isLow = -8, isHi = 8, isLeft = 8, isRight = -8,
			minLow = 1, minHi = 1, minLeft = 1, minRight = 1,
			horMax = 15, verMax = 15, horMin = -15, verMin = -15,
			minCount = 3, minSize = 22 + 16;
	int		low = 0, hi = 0, left = 0, right = 0,
			count = 0, change, max = 0,
			lowest = 0, highest = 0, leftmost = 0, rightmost = 0;
	bool		invalid = 0;

	for (i = 0; i < w->n; i++) {
	    x = pt[i].x;
	    y = pt[i].y;
	    change = 0;
	    if (y >= isLeft) {
		change++, left++;
		if (y > leftmost) leftmost = y;
	    }
	    if (y <= isRight) {
		change++, right++;
		if (y < rightmost) rightmost = y;
	    }
	    if (x <= isLow) {
		change++, low++;
		if (x < lowest) lowest = x;
	    }
	    if (x >= isHi) {
		change++, hi++;
		if (x > highest) highest = x;
	    }
	    if (change) count++;
	    if (y > horMax || y < horMin) max++;
	    if (x > verMax || x < verMin) max++;
	}
	if (low < minLow
	    || hi < minHi
	    || left < minLeft
	    || right < minRight
	    || count < minCount) {
	    if (verboseShapeParsing) {
		printf("Ship shape does not meet size requirements (%d,%d,%d,%d,%d)\n",
		       low, hi, left, right, count);
	    }
	    return 1;
	}
	if (max != 0) {
	    if (verboseShapeParsing) {
		printf("Ship shape exceeds size maxima.\n");
	    }
	    return -1;
	}
	if (leftmost - rightmost + highest - lowest < minSize) {
	    if (verboseShapeParsing) {
		printf("Warning: ship is not big enough, "
		       "future versions may not allow this.\n"
		       "The ship's width and height added together should "
		       "be at least %d.\n", minSize);
	    }
	}

	/*
	 * Check that none of the special points are outside the
	 * shape defined by the normal points.
	 * First the shape is drawn on a grid.  Then all grid points
	 * on the outside of the shape are marked.  Thusly for each
	 * special point can be determined if it is outside the shape.
	 */
	GRID_RESET();

	/* Draw the ship outline first. */
 	for (i = 0; i < w->n; i++) {
	    j = i + 1;
	    if (j == w->n) j = 0;

	    GRID_PT(pt[i].x, pt[i].y) = 1;

	    dx = pt[j].x - pt[i].x;
	    dy = pt[j].y - pt[i].y;
	    if (abs(dx) >= abs(dy)) {
		if (dx > 0) {
		    for (x = pt[i].x + 1; x < pt[j].x; x++) {
			y = pt[i].y + (dy * (x - pt[i].x)) / dx;
			GRID_PT(x, y) = 1;
		    }
		}
		else {
		    for (x = pt[j].x + 1; x < pt[i].x; x++) {
			y = pt[j].y + (dy * (x - pt[j].x)) / dx;
			GRID_PT(x, y) = 1;
		    }
		}
	    }
	    else {
		if (dy > 0) {
		    for (y = pt[i].y + 1; y < pt[j].y; y++) {
			x = pt[i].x + (dx * (y - pt[i].y)) / dy;
			GRID_PT(x, y) = 1;
		    }
		}
		else {
		    for (y = pt[j].y + 1; y < pt[i].y; y++) {
			x = pt[j].x + (dx * (y - pt[j].y)) / dy;
			GRID_PT(x, y) = 1;
		    }
		}
	    }
	}

	/* Check the borders of the grid for blank points. */
	for (y = -15; y <= 15; y++) {
	    for (x = -15; x <= 15; x += (y == -15 || y == 15) ? 1 : 2*15) {
		if (GRID_PT(x, y) == 0) {
		    GRID_ADD(x, y);
		}
	    }
	}

	/* Check from the borders of the grid to the centre. */
	while (!GRID_READY()) {
	    GRID_GET(x, y);
	    if (x <  15 && GRID_PT(x + 1, y) == 0) GRID_ADD(x + 1, y);
	    if (x > -15 && GRID_PT(x - 1, y) == 0) GRID_ADD(x - 1, y);
	    if (y <  15 && GRID_PT(x, y + 1) == 0) GRID_ADD(x, y + 1);
	    if (y > -15 && GRID_PT(x, y - 1) == 0) GRID_ADD(x, y - 1);
	}

	/*
	 * Note that for the engine, old format shapes may well have the
	 * engine position outside the ship, so this check not used for those.
	 */

	if (GRID_CHK(m_gun.x, m_gun.y)) {
	    if (verboseShapeParsing) {
		printf("Main gun outside ship\n");
	    }
	    invalid++;
	}
 	for (i = 0; i < w->nlg; i++) {
 	    if (GRID_CHK(l_gun[i].x, l_gun[i].y)) {
		if (verboseShapeParsing) {
		    printf("Left gun %d outside ship\n", i);
		}
		invalid++;
	    }
	}
 	for (i = 0; i < w->nrg; i++) {
 	    if (GRID_CHK(r_gun[i].x, r_gun[i].y)) {
		if (verboseShapeParsing) {
		    printf("Right gun %d outside ship\n", i);
		}
		invalid++;
	    }
	}
 	for (i = 0; i < w->nmr; i++) {
 	    if (GRID_CHK(m_rack[i].x, m_rack[i].y)) {
		if (verboseShapeParsing) {
		    printf("Missile rack %d outside ship\n", i);
		}
		invalid++;
	    }
	}
 	for (i = 0; i < w->nll; i++) {
 	    if (GRID_CHK(l_light[i].x, l_light[i].y)) {
		if (verboseShapeParsing) {
		    printf("Left light %d outside ship\n", i);
		}
		invalid++;
	    }
	}
 	for (i = 0; i < w->nrl; i++) {
 	    if (GRID_CHK(r_light[i].x, r_light[i].y)) {
		if (verboseShapeParsing) {
		    printf("Right light %d outside ship\n", i);
		}
		invalid++;
	    }
	}
 	if (GRID_CHK(engine.x, engine.y)) {
	    if (verboseShapeParsing) {
		printf("Engine outside of ship\n");
	    }
	    invalid++;
	    /* this could happen in case of an old format ship shape. */
	    if (shape_version == 0x3100 && invalid == 1) {
		/* move engine until it is legal. */
		for (x = -15, y = 0; x <= 15; x++) {
		    if (!GRID_CHK(x, y)) {
			engine.x = x;
			engine.y = y;
			invalid--;
			break;
		    }
		}
	    }
	}

	if (debugShapeParsing) {
	    for (i = -15; i <= 15; i++) {
		for (j = -15; j <= 15; j++) {
		    switch (GRID_PT(j, i)) {
		    case 0: putchar(' '); break;
		    case 1: putchar('*'); break;
		    case 2: putchar('.'); break;
		    default: putchar('?'); break;
		    }
		}
		putchar('\n');
	    }
	}

	if (invalid != 0) {
	    return 1;
	}
    }


    for (i = 0; i < w->n; i++) {
	w->p[i].x = pt[i].x;
	w->p[i].y = pt[i].y;
    }
    if (engineSet) {
	w->en.x = engine.x;
	w->en.y = engine.y;
    }
    if (mainGunSet) {
	w->mg.x = m_gun.x;
	w->mg.y = m_gun.y;
    }
    for (i = 0; i < w->nlg; i++) {
	w->lg[i].x = l_gun[i].x;
	w->lg[i].y = l_gun[i].y;
    }
    for (i = 0; i < w->nrg; i++) {
	w->rg[i].x = r_gun[i].x;
	w->rg[i].y = r_gun[i].y;
    }
    for (i = 0; i < w->nll; i++) {
	w->ll[i].x = l_light[i].x;
	w->ll[i].y = l_light[i].y;
    }
    for (i = 0; i < w->nrl; i++) {
	w->rl[i].x = r_light[i].x;
	w->rl[i].y = r_light[i].y;
    }
    for (i = 0; i < w->nmr; i++) {
	w->mr[i].x = m_rack[i].x;
	w->mr[i].y = m_rack[i].y;
    }

    return 0;
}

static ship *do_parse_shape(char *str)
{
    ship		*w;

    if (!str || !*str) {
	if (debugShapeParsing) {
	    printf("shape str not set\n");
	}
	return NULL;
    }
    if (!(w = (ship *)malloc(sizeof(*w)))) {
	return NULL;
    }
    if (shape2wire(str, w) < 0) {
	free(w);
	if (debugShapeParsing) {
	    printf("shape2wire failed\n");
	}
	return NULL;
    }
    if (debugShapeParsing) {
	printf("shape2wire succeeded\n");
    }

    return(w);
}

void Free_ship_shape(ship *w)
{
    if (w != NULL) {
	free(w);
    }
}

ship *Parse_shape_str(char *str)
{
    verboseShapeParsing = debugShapeParsing;
    shapeLimits = 1;
    return do_parse_shape(str);
}

ship *Convert_shape_str(char *str)
{
    verboseShapeParsing = debugShapeParsing;
    shapeLimits = debugShapeParsing;
    return do_parse_shape(str);
}

int Validate_shape_str(char *str)
{
    ship		*w;

    verboseShapeParsing = 1;
    shapeLimits = 1;
    w = do_parse_shape(str);
    Free_ship_shape(w);
    return (w!=NULL);
}


void Convert_ship_2_string(ship *w, char *buf, unsigned shape_version)
{
    int			i,
			len,
			ll,
			rl;

    if (shape_version == 0x3200) {
	strcpy(buf, "(SH:");
	len = strlen(&buf[0]);
	for (i = 0; i < w->n; i++) {
	    sprintf(&buf[len], " %d,%d",
		    (int)w->p[i].x, (int)w->p[i].y);
	    len += strlen(&buf[len]);
	}
	sprintf(&buf[len], ")(EN: %d,%d)(MG: %d,%d",
		(int)w->en.x, (int)w->en.y,
		(int)w->mg.x, (int)w->mg.y);
	len += strlen(&buf[len]);
	if (w->nlg > 0) {
	    strcpy(&buf[len], ")(LG:");
	    len += strlen(&buf[len]);
	    for (i = 0; i < w->nlg; i++) {
		sprintf(&buf[len], " %d,%d",
			(int)w->lg[i].x, (int)w->lg[i].y);
		len += strlen(&buf[len]);
	    }
	}
	if (w->nrg > 0) {
	    strcpy(&buf[len], ")(RG:");
	    len += strlen(&buf[len]);
	    for (i = 0; i < w->nrg; i++) {
		sprintf(&buf[len], " %d,%d",
			(int)w->rg[i].x, (int)w->rg[i].y);
		len += strlen(&buf[len]);
	    }
	}
	if (w->nll > 0) {
	    strcpy(&buf[len], ")(LL:");
	    len += strlen(&buf[len]);
	    for (i = 0; i < w->nll; i++) {
		sprintf(&buf[len], " %d,%d",
			(int)w->ll[i].x, (int)w->ll[i].y);
		len += strlen(&buf[len]);
	    }
	}
	if (w->nrl > 0) {
	    strcpy(&buf[len], ")(RL:");
	    len += strlen(&buf[len]);
	    for (i = 0; i < w->nrl; i++) {
		sprintf(&buf[len], " %d,%d",
			(int)w->rl[i].x, (int)w->rl[i].y);
		len += strlen(&buf[len]);
	    }
	}
	if (w->nmr > 0) {
	    strcpy(&buf[len], ")(MR:");
	    len += strlen(&buf[len]);
	    for (i = 0; i < w->nmr; i++) {
		sprintf(&buf[len], " %d,%d",
			(int)w->mr[i].x, (int)w->mr[i].y);
		len += strlen(&buf[len]);
	    }
	}
	if (strlen(w->name)>0) {
		strcpy(&buf[len], ")(NM:");
		len += strlen(&buf[len]);
		strcpy(&buf[len], w->name);
		len += strlen(&buf[len]);
	}
	if (strlen(w->author)>0) {
		strcpy(&buf[len], ")(AU:");
		len += strlen(&buf[len]);
		strcpy(&buf[len], w->author);
		len += strlen(&buf[len]);
	}
	strcpy(&buf[len], ")");

    }
    else {
        /* 3.1 version had 16 points maximum.  just ignore the excess. */
	int num_points = minimum(w->n, 16);

	if (shape_version != 0x3100) {
	    printf("Unknown ship shape version: %x", shape_version);
	}

    	for (i = 1, ll = rl = 0; i < num_points; i++) {
    	    if (w->p[i].y > w->p[ll].y
		|| (w->p[i].y == w->p[ll].y
		    && w->p[i].x < w->p[ll].x)) {
    	        ll = i;
            }
    	    if (w->p[i].y < w->p[rl].y
		|| (w->p[i].y == w->p[rl].y
		    && w->p[i].x < w->p[rl].x)) {
    	        rl = i;
            }
        }
        sprintf(buf, "(%d,%d,%d)", num_points, ll, rl);
        len = strlen(buf);
    	for (i = 0; i < num_points; i++) {
	    sprintf(&buf[len], "(%d,%d)",
		    (int)w->p[i].x, (int)w->p[i].y);
	    len += strlen(&buf[len]);
    	}
    }
    if (len >= MSG_LEN - 1) {
	printf("bug ship 2 str: buffer overflow");
    }
    if (debugShapeParsing) {
	printf("ship 2 str: %s\n", buf);
    }
}

static int Get_shape_keyword(char *keyw)
{
#define NUM_SHAPE_KEYS	10

    static char		shape_keys[NUM_SHAPE_KEYS][16] = {
			    "shape:",
			    "mainGun:",
			    "leftGun:",
			    "rightGun:",
			    "leftLight:",
			    "rightLight:",
			    "engine:",
			    "missileRack:",
				 "name:",
				 "author:"
			};
    static char		abbrev_keys[NUM_SHAPE_KEYS][4] = {
			    "SH:",
			    "MG:",
			    "LG:",
			    "RG:",
			    "LL:",
			    "RL:",
			    "EN:",
			    "MR:",
				 "NM:",
				 "AU:"
			};
    int			i;

    /* non-abbreviated keywords start with an upper case letter. */
    if (islower(*keyw)) {
	for (i = 0; strcmp(keyw, shape_keys[i]) && i < NUM_SHAPE_KEYS; i++);
    }
    /* abbreviated keywords start with an upper case letter. */
    else if (isupper(*keyw)) {
        for (i = 0; strcmp(keyw, abbrev_keys[i]) && i < NUM_SHAPE_KEYS; i++);
    }
    /* dunno what this is. */
    else {
	i = -1;
    }
    return(i);
}


void cleanship(ship *w)
{
	w->n=0;
	w->nll=0; w->nrl=0;
	w->nlg=0; w->nrg=0;
	w->nmr=0;
	w->mg.x=NOPOINT;
	w->mg.y=NOPOINT;
	w->en.x=NOPOINT;
	w->en.y=NOPOINT;
	w->version=0x3200;
}


void cpyship(ship *wt, ship *ws)
{
	int i;
	wt->n = ws->n;
	wt->nll = ws->nll;
	wt->nrl = ws->nrl;
	wt->nlg = ws->nlg;
	wt->nrg = ws->nrg;
	wt->nmr = ws->nmr;
	for (i=0; i<wt->nll; i++) {
		wt->ll[i].x = ws->ll[i].x;
		wt->ll[i].y = ws->ll[i].y;
	}
	for (i=0; i<wt->nrl; i++) {
		wt->rl[i].x = ws->rl[i].x;
		wt->rl[i].y = ws->rl[i].y;
	}
	for (i=0; i<wt->nlg; i++) {
		wt->lg[i].x = ws->lg[i].x;
		wt->lg[i].y = ws->lg[i].y;
	}
	for (i=0; i<wt->nrg; i++) {
		wt->rg[i].x = ws->rg[i].x;
		wt->rg[i].y = ws->rg[i].y;
	}
	for (i=0; i<wt->nmr; i++) {
		wt->mr[i].x = ws->mr[i].x;
		wt->mr[i].y = ws->mr[i].y;
	}
	for (i=0; i<wt->n; i++) {
		wt->p[i].x = ws->p[i].x;
		wt->p[i].y = ws->p[i].y;
	}
	wt->mg.x = ws->mg.x;
	wt->mg.y = ws->mg.y;
	wt->en.x = ws->en.x;
	wt->en.y = ws->en.y;
	wt->version=ws->version;
	strcpy(wt->name, ws->name);
	strcpy(wt->author, ws->author);
}


char *validateship (ship *w)
{
/*
 * Macros to simplify limit-checking for ship points.
 * Until XPilot goes C++.
 */
#define GRID_PT(x,y)	grid.pt[(x)+15][(y)+15]
#define GRID_ADD(x,y)	(GRID_PT(x, y) = 2, \
			 grid.chk[grid.todo][0] = (x), \
			 grid.chk[grid.todo][1] = (y), \
			 grid.todo++)
#define GRID_GET(x,y)	((x) = grid.chk[grid.done][0], \
			 (y) = grid.chk[grid.done][1], \
			 grid.done++)
#define GRID_CHK(x,y)	(GRID_PT(x, y) == 2)
#define GRID_READY()	(grid.done >= grid.todo)
#define GRID_RESET()	(memset(grid.pt, 0, sizeof grid.pt), \
			 grid.done = 0, \
			 grid.todo = 0)

	int		low = 0, hi = 0, left = 0, right = 0,
			count = 0, change, max = 0,
			lowest = 0, highest = 0, leftmost = 0, rightmost = 0;
	bool		invalid = 0;

	const int	isLow = -8, isHi = 8, isLeft = 8, isRight = -8,
			minLow = 1, minHi = 1, minLeft = 1, minRight = 1,
			horMax = 15, verMax = 15, horMin = -15, verMin = -15,
			minCount = 3, minSize = 22 + 16;



    struct grid_t {
	int		todo, done;
	char		pt[32][32];
	signed char		chk[32*32][2];
    } grid;

    int 		i, j, x, y, dx, dy,
    			inx, iny;

    static char		buf[MSG_LEN];

	buf[0]='\0';

	if (w->n > MAXPOINTS) {
		sprintf(buf,"Too many points");
	}

	if ((w->mg.x==NOPOINT)||(w->mg.y==NOPOINT)) {
		sprintf(buf,"Missing main gun");
	}

	if ((w->en.x==NOPOINT)||(w->en.y==NOPOINT)) {
		sprintf(buf,"Missing engine");
	}

	if (w->nlg > MAXGUNS) {
		sprintf(buf, "Too many left guns");
	}

	if (w->nrg > MAXGUNS) {
		sprintf(buf, "Too many right guns");
	}

	if (w->nll > MAXLIGHTS) {
		sprintf(buf, "Too many left lights");
	}

	if (w->nrl > MAXLIGHTS) {
		sprintf(buf, "Too many right lights");
	}

	if (w->nmr > MAXRACK) {
		sprintf(buf, "Too many missile racks");
	}

	if (w->n < MINPOINTS) {
	       	sprintf(buf,"not enough points");
	}

	for (i = 0; i < w->n; i++) {
	    x = w->p[i].x;
	    y = w->p[i].y;
	    change = 0;
	    if (y >= isLeft) {
		change++, left++;
		if (y > leftmost) leftmost = y;
	    }
	    if (y <= isRight) {
		change++, right++;
		if (y < rightmost) rightmost = y;
	    }
	    if (x <= isLow) {
		change++, low++;
		if (x < lowest) lowest = x;
	    }
	    if (x >= isHi) {
		change++, hi++;
		if (x > highest) highest = x;
	    }
	    if (change) count++;
	    if (y > horMax || y < horMin) max++;
	    if (x > verMax || x < verMin) max++;
	}
	if (low < minLow
	    || hi < minHi
	    || left < minLeft
	    || right < minRight
	    || count < minCount) {
		sprintf(buf,"Check: size requirements");
	}
	if (max != 0) {
		sprintf(buf,"Ship exceeds size maxima");
	}

	/*
	 * Check that none of the special points are outside the
	 * shape defined by the normal points.
	 * First the shape is drawn on a grid.  Then all grid points
	 * on the outside of the shape are marked.  Thusly for each
	 * special point can be determined if it is outside the shape.
	 */
	GRID_RESET();

	/* Draw the ship outline first. */
 	for (i = 0; i < w->n; i++) {
	    j = i + 1;
	    if (j == w->n) j = 0;

	    GRID_PT(w->p[i].x, w->p[i].y) = 1;

	    dx = w->p[j].x - w->p[i].x;
	    dy = w->p[j].y - w->p[i].y;
	    if (abs(dx) >= abs(dy)) {
		if (dx > 0) {
		    for (x = w->p[i].x + 1; x < w->p[j].x; x++) {
			y = w->p[i].y + (dy * (x - w->p[i].x)) / dx;
			GRID_PT(x, y) = 1;
		    }
		}
		else {
		    for (x = w->p[j].x + 1; x < w->p[i].x; x++) {
			y = w->p[j].y + (dy * (x - w->p[j].x)) / dx;
			GRID_PT(x, y) = 1;
		    }
		}
	    }
	    else {
		if (dy > 0) {
		    for (y = w->p[i].y + 1; y < w->p[j].y; y++) {
			x = w->p[i].x + (dx * (y - w->p[i].y)) / dy;
			GRID_PT(x, y) = 1;
		    }
		}
		else {
		    for (y = w->p[j].y + 1; y < w->p[i].y; y++) {
			x = w->p[j].x + (dx * (y - w->p[j].y)) / dy;
			GRID_PT(x, y) = 1;
		    }
		}
	    }
	}

	/* Check the borders of the grid for blank points. */
	for (y = -15; y <= 15; y++) {
	    for (x = -15; x <= 15; x += (y == -15 || y == 15) ? 1 : 2*15) {
		if (GRID_PT(x, y) == 0) {
		    GRID_ADD(x, y);
		}
	    }
	}

	/* Check from the borders of the grid to the centre. */
	while (!GRID_READY()) {
	    GRID_GET(x, y);
	    if (x <  15 && GRID_PT(x + 1, y) == 0) GRID_ADD(x + 1, y);
	    if (x > -15 && GRID_PT(x - 1, y) == 0) GRID_ADD(x - 1, y);
	    if (y <  15 && GRID_PT(x, y + 1) == 0) GRID_ADD(x, y + 1);
	    if (y > -15 && GRID_PT(x, y - 1) == 0) GRID_ADD(x, y - 1);
	}

	/*
	 * Note that for the engine, old format shapes may well have the
	 * engine position outside the ship, so this check not used for those.
	 */

	if (w->mg.x!=NOPOINT) {
		if (GRID_CHK(w->mg.x, w->mg.y)) {
			sprintf(buf,"Main gun outside ship");
			invalid++;
		}
	} else sprintf(buf, "Main gun not set");

 	for (i = 0; i < w->nlg; i++) {
 	    if (GRID_CHK(w->lg[i].x, w->lg[i].y)) {
		sprintf(buf,"Left gun %d outside ship", i);
		invalid++;
	    }
	}
 	for (i = 0; i < w->nrg; i++) {
 	    if (GRID_CHK(w->rg[i].x, w->rg[i].y)) {
		sprintf(buf,"Right gun %d outside ship", i);
		invalid++;
	    }
	}
 	for (i = 0; i < w->nmr; i++) {
 	    if (GRID_CHK(w->mr[i].x, w->mr[i].y)) {
		sprintf(buf,"Missile rack %d outside ship", i);
		invalid++;
	    }
	}
 	for (i = 0; i < w->nll; i++) {
 	    if (GRID_CHK(w->ll[i].x, w->ll[i].y)) {
		sprintf(buf,"Left light %d outside ship", i);
		invalid++;
	    }
	}
 	for (i = 0; i < w->nrl; i++) {
 	    if (GRID_CHK(w->rl[i].x, w->rl[i].y)) {
		sprintf(buf,"Right light %d outside ship", i);
		invalid++;
	    }
	}
	if (w->en.x!=NOPOINT) {
	 	if (GRID_CHK(w->en.x, w->en.y)) {
		    sprintf(buf, "Engine outside of ship");
		    invalid++;
		}
	} else sprintf(buf, "Engine point not set");

	if (strlen(buf)==0) {
		if (leftmost - rightmost + highest - lowest < minSize) {
			sprintf(buf, "Warn: ship not big enough");
		}
	}

	return buf;
}