/* $Id: map.c,v 1.236 2022/09/29 18:40:04 kili Exp $ */
/*
 * Copyright (c) 2016,2017 Matthias Kilian <kili@outback.escape.de>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <assert.h>
#include <errno.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "alloc.h"
#include "map.h"
#include "moves.h"
#include "steps.h"

static void
freemvl(struct move_list *mvl)
{
	struct move_list *mvlp;

	while (mvl) {
		mvlp = mvl;
		mvl = mvl->next;
		free(mvlp);
	}
}

void
freemap(struct map *m)
{
	if (!m)
		return;
	free(m->fields);
	free(m->dnfs);
	freemvl(m->stafirst);
	freemvl(m->finfirst);
	freemovesl(m->w, m->h, m->moves);
	free(m);
}

/* Check wether c is a valid map character.
 * Returns 0 if it's valid, else -1.
 */
static int
check_field(char c)
{
    switch (c) {
	case 'X':	/* Lawn */
	case 'Y':	/* Sand */
	case 'Z':	/* Mud */
	case 'G':	/* Gold */
	case 'L':	/* Lava */
	case 'N':	/* Snow */
	case 'V':	/* Mountain */
	case 'T':	/* Tar */
	case 'W':	/* Water */
	case 'O':	/* Road */
	case 'S':	/* Start */
	case 'F':	/* Finish */
	case 'P':	/* Parc femme */
	/* The next four are the same as the above four, just in my
	 * 'readable' map format.
	 */
	case ' ':	/* Road */
	case '@':	/* Start */
	case '#':	/* Finish */
	case '=':	/* Parc femme */
	case '1':	/* CP 1 */
	case '2':	/* CP 2 */
	case '3':	/* CP 3 */
	case '4':	/* CP 4 */
	case '5':	/* CP 5 */
	case '6':	/* CP 6 */
	case '7':	/* CP 7 */
	case '8':	/* CP 8 */
	case '9':	/* CP 9 */
		return 0;
	default:
		return -1;
	}
}

static int
finish_row(struct map *m, char *buf, char *fname, int x, int y)
{
	if (y > 0 && x != m->w) {
		fprintf(stderr,
			"%s, row %d: length %d differs "
			"from previous row length %d\n",
			fname, y, x, m->w
		);
		return -1;
	} else
		m->w = x;
	y++;
	m->fields = resizearray(m->fields, x * y, sizeof(*(m->fields)));
	if (m->fields == NULL) {
		fprintf(stderr,
			"row %d: %s\n",
			y, strerror(errno));
		return -1;
	}
	memcpy(m->fields + x * (y - 1), buf, x * sizeof(*(m->fields)));
	m->h = y;
	return 0;
}

static int calc_dnfs(struct map * m);

struct map *
readmap(FILE *in, char *fname, struct map_stat *st)
{
	int c;
	int x = 0, y = 0;
	struct map *m = NULL;
	static char buf[MAP_MAX];

	if (!(m = calloc(1, sizeof(*m))))
		goto fail;

	m->fname = fname;

	while ((c = fgetc(in)) != EOF) {
		if (c == '\r')
			continue;

		if (c == '\n') {
			if (finish_row(m, buf, fname, x, y))
				goto fail;
			y++;
			x = 0;
			continue;
		}

		if (y == 0 && x >= sizeof(buf) - 1) {
			fprintf(stderr, "row size (%zd) exceeded.\n", sizeof(buf));
			goto fail;
		}

		/* XXX */
		if (y >= MAP_MAX) {
			fprintf(stderr, "row count exceeded.\n");
			goto fail;
		}

		if (check_field(c) < 0) {
			fprintf(stderr,
				"(%d, %d): illegal character `%c'\n",
				x, y, c
			);
			goto fail;
		}
		buf[x++] = c;
		if (c >= '1' && c <= '9')
			m->cps |= 1 << (c - '1');
	}

	/* Inclomplete last line (no \n), so call finish_row(). */
	if (x && finish_row(m, buf, fname, x, y))
		goto fail;

	if(!(m->moves = allocmovesl(m->w, m->h)))
		goto fail;

	if (!(m->dnfs = calloc(m->w * m->h, sizeof(*(m->dnfs)))))
		goto fail;

	if(calc_dnfs(m) < 0)
		goto fail;

	m->st = st;
	if (st)
		memset(st, 0, sizeof(*st));

	return m;

fail:
	freemap(m);
	return NULL;
}

static int
in_map(struct map *m, int x, int y) {
	return x >= 0 && x < m->w && y >= 0 && y < m->h;
}

static int
is_road(struct map *m, int x, int y)
{
	char c;

	assert(in_map(m, x, y));
	c = m->fields[m->w * y + x];
	return c == ' ' || c == '@' || c == '#' ||
	       c == 'O' || c == 'S' || c == 'F' ||
		(c >= '1' && c <= '9');
}

static int
is_start(struct map *m, int x, int y)
{
	char c;

	assert(in_map(m, x, y));
	c =  m->fields[m->w * y + x];
	return c == '@' || c == 'S';
}

static int
is_finish(struct map *m, int x, int y)
{
	char c;

	assert(in_map(m, x, y));
	c =  m->fields[m->w * y + x];
	return c == '#' || c == 'F';
}

/* Returns the number of the checkpoint or 0 if it isn't a checkpoint.
 */
static int
is_checkpoint(struct map *m, int x, int y)
{
	char c;

	assert(in_map(m, x, y));
	c = m->fields[m->w * y + x];
	if (c < '1' || c > '9')
		return 0;
	else
		return c - '0';
}

static int calc_dnfs
(struct map *m)
{
	int d, p, x, y;
	size_t n, nfs1 = 0, nfs2 = 0;
	struct {
		int x;
		int y;
	} *fs1 = NULL, *fs2 = NULL;

	/* Collect finish fields.
	 * Could be done better while reading the map, but maps aren't
	 * *that* large.
	 */
	for (y = 0; y < m->h; y++)
		for (x = 0; x < m->w; x++) {
			if (!is_finish(m, x, y))
				continue;
			if (!(fs1 = resizearray(fs1, sizeof(*fs1), ++nfs1)))
				return -1;
			fs1[nfs1 - 1].x = x;
			fs1[nfs1 - 1].y = y;
		}

	/* Assign all neigbour fields that are road, start, finish
	 * or checkpoint, and that don't already have a smaller distance
	 * assigned, the current fields distance + 1 and collect the
	 * newly assigned fields in fs2. Then, iterate over with the new
	 * fields in fs1 until no fields are left.
	 */
	while (nfs1 > 0) {
		for (n = 0; n < nfs1; n++)
			for (p = 0; p < 9; p++) {
				if (p == 4)
					/* Skip current field */
					continue;
				/* Current fields x, y and dnf: */
				x = fs1[n].x;
				y = fs1[n].y;
				d = m->dnfs[y * m->w + x];
				/* New x and y: */
				x += p % 3 - 1;
				y += p / 3 - 1;
				if (x < 0 || x >= m->w ||
				    y < 0 || y >= m->h)
					continue;
				/* Add 2 for diagonal neighbours, 1 for
				 * the others.
				 */
				d += 2 - p % 2;
				if (m->dnfs[y * m->w + x] &&
				    m->dnfs[y * m->w + x] <= d ||
				    is_finish(m, x, y) ||
				    !is_road(m, x, y))
					continue;
				m->dnfs[y * m->w + x] = d;
				if (!(fs2 = resizearray(fs2,
				      sizeof(*fs2), ++nfs2))) {
					free(fs1);
					return -1;
				}
				fs2[nfs2 - 1].x = x;
				fs2[nfs2 - 1].y = y;
			}
		free(fs1);
		fs1 = fs2;
		fs2 = NULL;
		nfs1 = nfs2;
		nfs2 = 0;
	}

	free(fs1);
	return 0;
}

/* Return the dnf delta of the next and the current fields of a move.
 * So, if this return a value > 0, the move is "away from finish",
 * if it's < 0, it's "towards finish".
 */
static int
dnfd(struct map *m, struct move *mv) {
	int dnf = m->dnfs[mv->y * m->w + mv->x];
	int dnf1 = m->dnfs[(mv->y + mv->dy) * m->w + (mv->x + mv->dx)];
	return dnf1 - dnf;
}

/* Calculates the sum of 1 + 2 + ... + i or, for negative numbers,
 * -1 - 2 - ... - i.
 */
static int
sum_to(int i)
{
	int a = i < 0 ? -1 : 1;
	return a * i * (i + a) / 2;
}

/* The reverse. For a given boundary b, calculates the largest value of
 * n with sum_to(n) <= b.
 */
static int
unsum_from(int b)
{
	return floor(sqrt((2 * b + 0.25)) - 0.5);
}

static int
check_crash(void *d, int x, int y)
{
	return !is_road((struct map *) d, x, y);
}

static int
calc(struct map *m, int x0, int y0, int x1, int y1)
{
	int dx, dy, dx_stop, dy_stop, v, wkfailed;

	dx = x1 - x0;
	dy = y1 - y0;

	/* 0/0 moves aren't possible. */
	if (!(dx || dy))
		return -1;

	/* Check wether the current move is reachable from a point
	 * within the map by calculating the stop point backwards from
	 * the end point (x1, y1).
	 */
	dx_stop = sum_to(dx);
	dy_stop = sum_to(dy);
	if (dx > 0 && x1 - dx_stop < 0 ||
	    dy > 0 && y1 - dy_stop < 0 ||
	    dx < 0 && x1 - dx_stop >= m->w ||
	    dy < 0 && y1 - dy_stop >= m->h)
		return -1;

	wkfailed = walk_steps(check_crash, m, x0, y0, dx, dy);
	if (!m->st)
		/* Returning wkfailed here, because it's not necessarily an
		 * error if we don't collect statistics.
		 */
		return wkfailed;

	m->st->tcount++;

	if (wkfailed)
		return wkfailed;

	v = dx * dx + dy * dy;
	if (v > m->st->max1r_vv) {
		m->st->max1r_x = x0;
		m->st->max1r_y = y0;
		m->st->max1r_dx = dx;
		m->st->max1r_dy = dy;
		m->st->max1r_vv = v;
	}
	m->st->rcount++;
	return 0;
}

/* Returns -1 on allocation errors. */
static int
calc_moves_from(struct map *m, int x0, int y0)
{
	int x1, y1;
	struct move_arr **mvsp;

	if (!is_road(m, x0, y0))
		return 0;

	mvsp = &(m->moves[m->w * y0 + x0]);

	for (y1 = 0; y1 < m->h; y1++)
		for (x1 = 0; x1 < m->w; x1++) {
			if (calc(m, x0, y0, x1, y1))
				continue;
			if (addmove(mvsp, x0, y0, x1 - x0, y1 - y0) == -1)
				return -1;
		}

	if (!m->st || !(*mvsp) || (*mvsp)->count < m->st->max_mc)
		return 0;

	m->st->max_mc = (*mvsp)->count;
	m->st->max_mc_x = x0;
	m->st->max_mc_y = y0;

	return 0;
}

struct map_delta {
	struct map	*m;
	struct move	*mv;
};

static int
set_special(void *d, int x, int y)
{
	enum MV_SPECIAL spec;
	int cp;
	struct map_delta *md;

	md = (struct map_delta *) d;
	if (is_start(md->m, x, y))
		spec = MV_SPEC_START;
	else if (is_finish(md->m, x, y)) {
		spec = MV_SPEC_FIN;
		if (md->mv->lastspecial == MV_SPEC_START)
			md->mv->startfin = 1;
	} else if((cp = is_checkpoint(md->m, x, y)))
		spec = cp - 1 + MV_SPEC_CP1;
	else
		return 0;

	md->mv->lastspecial = spec;

	return 0;
}

/* Returns -1 on allocation errors. */
static int
find_specials(struct map *m, int x0, int y0)
{
	int spec;
	unsigned long n;
	struct map_delta md;
	struct move_list *mvl;
	struct move_arr *mvs;

	md.m = m;
	mvs = m->moves[y0 * m->w + x0];
	if (mvs == NULL)
		return 0;
	md.mv = mvs->mv;
	for (n = 0; n < mvs->count; n++, md.mv++) {
		if (!md.mv->valid)
			continue;
		set_special(&md, x0, y0);
		walk_steps(set_special, &md, x0, y0, md.mv->dx, md.mv->dy);
		if (!(spec = md.mv->lastspecial))
			continue;
		/* Build linked lists of finish and start moves, but
		 * only consider real start moves instead of all moves
		 * touching a start field.
		 */
		if (spec == MV_SPEC_FIN) {
			if (!(mvl = calloc(1, sizeof(*mvl))))
				return -1;
			mvl->mv = md.mv;
			mvl->next = md.m->finfirst;
			md.m->finfirst = mvl;
		} else if (abs(md.mv->dx) <= 1 && abs(md.mv->dy) <= 1
		    && is_start(m, x0, y0)) {
			md.mv->realstart = 1;
			if (!(mvl = calloc(1, sizeof(*mvl))))
				return -1;
			mvl->mv = md.mv;
			mvl->next = md.m->stafirst;
			md.m->stafirst = mvl;
		}
	}
	return 0;
}

/* Weird stuff moved to the end of this file. */
static unsigned long validate_moves_from(struct map *m, int x, int y);

/* For every move of every field of the map which is not yet marked
 * as valid, check wether it's a single step move or wether any of
 * the (up to 9) previous moves is valid. If so, mark the current
 * move as valid, too.
 * Returns the number of validated moves (0 means you can stop
 * iterating).
 */
static unsigned long
validate_moves(struct map *m)
{
	int x, y;
	unsigned long vcount = 0;

	for (y = 0; y < m->h; y++)
		for (x = 0; x < m->w; x++)
			vcount += validate_moves_from(m, x, y);
	return vcount;
}

int
has_moves(struct map *m, short x, short y)
{
	return m->moves[m->w * y + x] && m->moves[m->w * y + x]->count > 0;
}

struct move *
adj_mv(struct map *m, struct move *mv, int fwd, short dd)
{
	int dxa, dya, xa, ya;
	struct move_arr *mvs;

	/* You are not supposed to understand this. */
	dxa = mv->dx + (fwd ? 1 : -1) * (dd % 3 - 1);
	dya = mv->dy + (fwd ? 1 : -1) * (dd / 3 - 1);
	xa = mv->x + fwd * mv->dx + (fwd - 1) * dxa;
	ya = mv->y + fwd * mv->dy + (fwd - 1) * dya;
	if (xa < 0 || xa >= m->w || ya < 0 || ya >= m->h)
		return NULL;
	mvs = m->moves[ya * m->w + xa];
	return find_move(mvs, dxa, dya);
}

struct q_node {
	size_t s;
	struct {
		struct mv_cost	 mvc;
		struct move	*mvp;
	} d[];
};

/* Add a move and a move cost to the queue.
 */
static struct q_node *
enqueue(struct q_node *bh, struct move *mvp, struct mv_cost mvc)
{
	size_t s = bh != NULL ? bh->s : 0;

	if (!(bh = resizeflarray(bh, sizeof(*bh), ++s, sizeof(bh->d[0]))))
		return NULL;

	bh->d[s - 1].mvp = mvp;
	bh->d[s - 1].mvc = mvc;
	bh->s = s;

	return bh;
}

/* Retrieve the move and move cost from the queue and store them in
 * the given pointers.
 * Returns 0 when the queue was empty, otherwise 1.
 */
static int
dequeue(struct q_node *bh, struct move **mvpp, struct mv_cost *mvcp)
{
	size_t s = bh != NULL ? bh->s : 0;
	if(s == 0)
		return 0;
	*mvpp = bh->d[s - 1].mvp;
	*mvcp = bh->d[s - 1].mvc;
	bh->s--;
	return 1;
}

/* Problems with classic direction (probably incomplete):
 * 013
 * 024
 * 035
 * 043
 * 049
 * 050
 * 082
 * 094
 * 152 (no checkpoints)
 * 156
 * 178 (no checkpoints)
 */

int
calc_costs(struct map *m)
{
	int i, p;
	size_t n_start;
	struct mv_cost mvc;
	struct move_list *mvl;
	struct move *mv, *pmv;
	struct q_node *bh1 = NULL, *bh2 = NULL;

	for (n_start = 0, mvl = m->stafirst; mvl; mvl = mvl->next)
		n_start++;

	/* Build an initial queue of pointers to moves, missing
         * checkpoint mask and cost distance to assign to the move.
	 * The set of missing checkpoints is obviously 0, because we
	 * start with finish moves, and the initial distance is 1.
	 */
	mvc.dist = 1;
	mvc.mcps = 0;
	for (mvl = m->finfirst; mvl; mvl = mvl->next)
		if (mvl->mv->valid && !(bh1 = enqueue(bh1, mvl->mv, mvc)))
			return -1;

	/* Process the current working queue, assigning costs to
         * the set of yet unprocessed moves in the queue, and enqueue
         * the next sets of previous moves (with checkpoint map and
         * distance) for later iterations until no moves are left.
	 * (That's basically Dijkstra's shortest path algorithm)
	 */
	while (1) {
		if (!(dequeue(bh1, &mv, &mvc))) {
			free(bh1);
			bh1 = bh2;
			bh2 = NULL;
			if (!dequeue(bh1, &mv, &mvc))
				break;
		}
		if (!m->cps && mv->startfin)
			/* No CPs or CPs disabled: moves touching a
			 * finish after a start are forbidden.
			 */
			continue;
		mvc.mcps |= (m->cps ? mv_cpm(mv) : 0);
		if (findcost(mv, mvc.mcps) >= 0)
			continue;
		if (mvc.mcps == m->cps && mv->realstart)
			n_start--;
		if ((i = addcost(mv, mvc.mcps, mvc.dist)) < 0) {
			free(bh1);
			free(bh2);
			return -1;
		}
		if (m->st)
			m->st->ccount++;

		if (!n_start)
			/* All start moves reached, no reason to enqueue
			 * new moves or process additional queued ones.
			 */
			break;

		mvc.dist++;
		for (p = 0; p < 9; p++)
			if((pmv = adj_mv(m, mv, 0, p))
			    && pmv->valid
			    && !(bh2 = enqueue(bh2, pmv, mvc))) {
				free(bh1);
				return -1;
			}
	}
	if (m->st)
		m->st->ucount = n_start;
	free(bh1);
	free(bh2);

	return 0;
}

long
calc_moves(struct map *m)
{
	int x0, y0;
	long vcount;
	long vcount_total = 0;

	for (y0 = 0; y0 < m->h; y0++)
		for (x0 = 0; x0 < m->w; x0++)
			if (calc_moves_from(m, x0, y0) == -1)
				return -1;

	/* This is potentially inefficient, because it's iterating
	 * over all moves of all fields until there are no changes
	 * left.
	 */
	while (vcount = validate_moves(m))
		vcount_total += vcount;

	for (y0 = 0; y0 < m->h; y0++)
		for (x0 = 0; x0 < m->w; x0++)
			if (find_specials(m, x0, y0) == -1)
				return -1;

	if (!m->st)
		return vcount_total;

	m->st->dx_max = unsum_from(m->w - 1);
	m->st->dy_max = unsum_from(m->h - 1);
	m->st->max1r_v = sqrt(m->st->max1r_vv);
	m->st->max1v_v = sqrt(m->st->max1v_vv);

	return vcount_total;
}

static int
is_prev_valid(struct map *m, struct move *mv)
{
	int p;
	struct move *pmv;

	for (p = 0; p < 9; p++)
		if ((pmv = adj_mv(m, mv, 0, p)) != NULL && pmv->valid)
			return 1;
	return 0;
}

static unsigned long
validate_moves_from(struct map *m, int x, int y)
{
	int dx, dy, vv;
	struct move_arr *mvs;
	unsigned long mi, vcount;

	if (!is_road(m, x, y))
		return 0;

	mvs = m->moves[m->w * y + x];
	for (mi = 0, vcount = 0; mvs && mi < mvs->count; mi++) {
		if (mvs->mv[mi].valid)
			continue;
		dx = mvs->mv[mi].dx;
		dy = mvs->mv[mi].dy;
		/* The current list of moves only contains moves *not*
		 * touching lawn, so all single step moves are valid.
		 * Other moves are valid if any of their predecessors 
		 * is valid.
		 */
		if (abs(dx) <= 1 && abs(dy) <= 1 ||
		    is_prev_valid(m, mvs->mv + mi)) {
			mvs->mv[mi].valid = 1;
			vcount++;
			if (!m->st)
				continue;

			vv = dx * dx + dy * dy;
			if (vv > m->st->max1v_vv) {
				m->st->max1v_x = x;
				m->st->max1v_y = y;
				m->st->max1v_dx = dx;
				m->st->max1v_dy = dy;
				m->st->max1v_vv = vv;
			}
		}
	}

	return vcount;
}

static void
dump_move(struct map *m, struct move *mv)
{
	int i, n;
	struct move *pmv;
	struct mv_cost *mvc;

	if (!mv->valid)
		return;

	printf("%10p:\t%d/%d %d/%d (%d)\n",
	       mv, mv->x, mv->y, mv->dx, mv->dy, mv->lastspecial);
	for (i = 0; i < 9; i++)
		if ((pmv = adj_mv(m, mv, 0, i)) && pmv->valid)
			printf("\t\tprev %d: %p\n", i, pmv);
	for (n = 0; mv->costs && n < mv->costs->n; n++) {
		mvc = mv->costs->mvc + n;
		printf("\t\tcost mcps %03x: %d\n", mvc->mcps, (int) mvc->dist);
	}
}

static void
dump_moves_from(struct map *m, int x, int y)
{
	unsigned long i;
	struct move_arr *mvs;

	mvs = m->moves[m->w * y + x];
	if (mvs == NULL)
		return;
	for (i = 0; i < mvs->count; i++)
		dump_move(m, mvs->mv + i);
}

static void
dump_fin_moves(struct map *m)
{
	struct move_list *mvl;

	if (!(mvl = m->finfirst))
		return;
	printf("\t\t");
	while (mvl) {
		if (!mvl->mv->valid)
			continue;
		printf(" %p", mvl->mv);
		mvl = mvl->next;
	}
	printf("\n");
}

void
dump_moves(struct map *m)
{
	int x, y;

	for (y = 0; y < m->h; y++)
		for (x = 0; x < m->w; x++)
			dump_moves_from(m, x, y);
	printf("\n");
	dump_fin_moves(m);
}

static int
cmp_mvci_yxc(const void *a, const void *b)
{
	int d;
	const struct mv_cost_info *mvci1 = (const struct mv_cost_info *) a;
	const struct mv_cost_info *mvci2 = (const struct mv_cost_info *) b;

	if ((d = mvci1->mv->y - mvci2->mv->y))
		return d;
	if ((d = mvci1->mv->x - mvci2->mv->x))
		return d;
	return MVCI_C(mvci1)->dist - MVCI_C(mvci2)->dist;
}

static int
cmp_mvci_cyxdydx(const void *a, const void *b)
{
	int d;
	const struct mv_cost_info *mvci1 = (const struct mv_cost_info *) a;
	const struct mv_cost_info *mvci2 = (const struct mv_cost_info *) b;

	if ((d = MVCI_C(mvci1)->dist - MVCI_C(mvci2)->dist))
		return d;
	if ((d = mvci1->mv->y - mvci2->mv->y))
		return d;
	if ((d = mvci1->mv->x - mvci2->mv->x))
		return d;
	if ((d = mvci1->mv->dy - mvci2->mv->dy))
		return d;
	return mvci1->mv->dx - mvci2->mv->dx;
}

struct mv_cost_info *
find_best_start_mvcs(struct map *m, size_t *mcountp)
{
	struct move_list *mvl;
	struct move *mv;
	struct mv_cost_info *mvcis;
	size_t mcount, f, t;
	int ci;

	mvcis = NULL;
	*mcountp = mcount = 0;
	for (mvl = m->stafirst; mvl; mvl = mvl->next) {
		mv = mvl->mv;
		if (!mv->realstart || (ci = findcost(mv, m->cps)) < 0)
			continue;
		mvcis = resizearray(mvcis, ++mcount, sizeof(*mvcis));
		if (mvcis == NULL)
			return NULL;
		mvcis[mcount - 1].i = ci;
		mvcis[mcount - 1].mv = mv;
	}

	if (!mcount)
		/* Nothing found (probably map 117).
		 * Early return so we don't have to deal with underflows
		 * of mcount, f or t below.
		 */
		return NULL;

	qsort(mvcis, mcount, sizeof(*mvcis), cmp_mvci_yxc);

	/* Find the first mvci whose move has the same coordinates but
	 * different (higher) costs than the previous mvcis move.
	 */
	for (t = 1; t < mcount; t++)
		if (mvcis[t].mv->x ==  mvcis[t - 1].mv->x
		    && mvcis[t].mv->y == mvcis[t - 1].mv->y
		    && MVCI_C(&mvcis[t])->dist != MVCI_C(&mvcis[t - 1])->dist)
			break;

	/* Copy remaining mvcis down (from f to t), skipping mvcis with
	 * the same condition as above.
	 */
	for (f = t; f < mcount; f++)
		if (mvcis[f].mv->x != mvcis[t - 1].mv->x
		    || mvcis[f].mv->y != mvcis[t - 1].mv->y
		    || MVCI_C(&mvcis[f])->dist == MVCI_C(&mvcis[t - 1])->dist)
			mvcis[t++] = mvcis[f];
	*mcountp = mcount = t;
	assert(mvcis = resizearray(mvcis, mcount, sizeof(*mvcis)));

	qsort(mvcis, mcount, sizeof(*mvcis), cmp_mvci_cyxdydx);

	return mvcis;
}