scene

build.c

#include "scene.h"
#include <assert.h>

struct build_context {
	int shift;
	int x;
	int y;
	int id;
	slot_t *grid;
};

static void
build_init(struct build_context *C, struct scene *S, int layer) {
	C->shift = S->shift_x;
	C->x = 1 << S->shift_x;
	C->y = S->y;
	C->id = -1;
	assert(layer >=0 && layer < S->layer_n);
	C->grid = S->layer[layer];
}

static int
available_id(struct build_context *C) {
	if (C->id >= 0) {
		return C->id++;
	}
	int m = 0;
	slot_t * grid = C->grid;
	int sz = C->y << C->shift;
	int i;
	for (i=0; i<sz; i++) {
		if (grid[i] > m)
			m = grid[i];
	}
	C->id = m + 1;
	return C->id++;
}

static int
neighbor_east(struct build_context *C, struct scene_coord c, struct scene_coord *output, slot_t *grid) {
	if (c.x >= C->x -1)
		return -1;
	output->x = c.x + 1;		
	output->y = c.y;
	return *(grid + 1);
}

static int
neighbor_west(struct build_context *C, struct scene_coord c, struct scene_coord *output, slot_t *grid) {
	if (c.x <= 0)
		return -1;
	output->x = c.x - 1;		
	output->y = c.y;
	return *(grid - 1);
}

static int
neighbor_south(struct build_context *C, struct scene_coord c, struct scene_coord *output, slot_t *grid) {
	if (c.y >= C->y -1)
		return -1;
	output->x = c.x;		
	output->y = c.y + 1;
	return *(grid + (1 << C->shift));
}

static int
neighbor_north(struct build_context *C, struct scene_coord c, struct scene_coord *output, slot_t *grid) {
	if (c.y <= 0)
		return -1;
	output->x = c.x;		
	output->y = c.y - 1;
	return *(grid - (1 << C->shift));
}

typedef int (*neighbor_func)(struct build_context *C, struct scene_coord c, struct scene_coord *output, slot_t *grid);

static const neighbor_func funcs[] = {
	neighbor_east,
	neighbor_west,
	neighbor_south,
	neighbor_north,
};
	
static inline slot_t *
get_coord(struct build_context *C, struct scene_coord p) {
	return C->grid + (p.y << C->shift) + p.x;
}

static void
convert(struct build_context *C, int oid, int id) {
	int sz = C->y << C->shift;
	int i;
	slot_t * s = C->grid;
	for (i=0;i<sz;i++) {
		if (s[i] == oid)
			s[i] = id;
	}
}

static void
render_(struct build_context *C, struct scene_coord p, int from, int to) {
	slot_t * s = get_coord(C, p);
	if (*s != from)
		return;
	*s = to;
	// east
	struct scene_coord tmp;
	if (p.x < C->x - 1) {
		tmp.x = p.x + 1;
		tmp.y = p.y;
		render_(C, tmp, from, to);
	}
	// west
	if (p.x > 0) {
		tmp.x = p.x - 1;
		tmp.y = p.y;
		render_(C, tmp, from, to);
	}
	// south
	if (p.y < C->y - 1) {
		tmp.x = p.x;
		tmp.y = p.y + 1;
		render_(C, tmp, from, to);
	}
	// north
	if (p.y > 0) {
		tmp.x = p.x;
		tmp.y = p.y - 1;
		render_(C, tmp, from, to);
	}
}

static void
render(struct build_context *C, struct scene_coord p, int id) {
	slot_t * s = get_coord(C, p);
	int oid = *s;
	if (oid == id)
		return;
	render_(C, p, oid, id);
}

static void
build_one(struct build_context *C, struct scene_coord p) {
	slot_t * grid = get_coord(C, p);
	int current = *grid;
	struct scene_coord neighbor;
	int i;
	int nid;
	struct scene_coord connect[4];
	int connect_n = 0;
	struct scene_coord split[4];
	int split_n = 0;
	int del[4];
	int del_n = 0;
	
	for (i=0;i<4;i++) {
		if ((nid = funcs[i](C, p, &neighbor, grid)) >= 0) {
			if (nid != current) {
				connect[connect_n++] = neighbor;
			} else {
				split[split_n++] = neighbor;
			}
		}
	}
	if (connect_n > 0) {
		slot_t * neighbor = get_coord(C, connect[0]);
		int id = *neighbor; 
		*grid = id;
		for (i = 1; i < connect_n; i++) {
			neighbor = get_coord(C, connect[i]);
			int oid = *neighbor;
			if (oid != id) {
				convert(C, oid, id);
				del[del_n++] = oid;
			}
		}
	} else {
		*grid = available_id(C);
	}
	for (i = 1;i < split_n; i++) {
		slot_t * neighbor = get_coord(C, split[i]);
		if (*neighbor == current) {
			int id;
			if (del_n > 0) {
				id = del[--del_n];
			} else {
				id = available_id(C);
			}
			render(C, split[i], id);
		}
	}
	if (split_n > 1) {
		slot_t * neighbor = get_coord(C, split[0]);
		if (*neighbor != current) {
			del[del_n++] = current;
		}
	}
	if (del_n > 0) {
		int id = available_id(C);
		int i = 0;
		while (i < del_n) {
			if (del[i] >= id) {
				del[i] = del[--del_n];
			} else {
				++i;
			}
		}
		C->id -= del_n + 1;
		id -= del_n;
		for (i=0;i<del_n;i++) {
			convert(C, id+i, del[i]);
		}
	}
}

void
scene_build(struct scene *S, int layer, int n, struct scene_coord p[]) {
	struct build_context C;
	build_init(&C, S, layer);
	int i;
	for (i=0;i<n;i++) {
		build_one(&C, p[i]);
	}
}

pathmap.c

#include "scene.h"
#include <assert.h>
#include <string.h>

static inline void
check_layer(struct scene *S, int layer) {
	assert(layer >= 0 && layer < S->layer_n);	
}

struct pathmap_context {
	int x;
	int y;
	int shift;
	int id;
	slot_t * block;
	slot_t * target;
};

static inline slot_t *
get_coord(struct pathmap_context *C, slot_t *layer, struct scene_coord p) {
	if (p.x < 0 || p.y < 0 || p.x >= C->x || p.y >= C->y)
		return NULL;
	return layer + (p.y << C->shift) + p.x;
}

static void
pathmap_init(struct pathmap_context *C, struct scene *S, int layer, int target_layer, struct scene_coord pos) {
	C->x = 1 << S->shift_x;
	C->y = S->y;
	C->shift = S->shift_x;
	check_layer(S, layer);
	check_layer(S, target_layer);
	C->block = S->layer[layer];
	C->target = S->layer[target_layer];
	slot_t * s = get_coord(C, C->block, pos);
	assert(s != NULL);
	C->id = *s;
}

static const int neighbor[8*3] = {
	-1, -1, 7,	// NW
	 0, -1, 5,	// N
	 1, -1, 7,	// NE
	-1,  0, 5,	// W
	 1,  0,	5,	// E
	-1,  1, 7,	// SW
	 0,  1,	5,	// S
	 1,  1,	7,	// SE
};

static void
render(struct pathmap_context *C, struct scene_coord pos, int dist) {
	slot_t * s = get_coord(C, C->block, pos);
	if (s == NULL || *s != C->id)
		return;
	slot_t * t = s + (C->target - C->block);
	if (*t != 0 && *t <= dist)
		return;
	*t = dist;
	int i;
	for (i=0;i<8*3;i+=3) {
		struct scene_coord t = pos;
		t.x += neighbor[i+0];
		t.y += neighbor[i+1];
		render(C, t, dist + neighbor[i+2]);		
	}
}

void
scene_pathmap(struct scene *S, int layer, struct scene_coord pos, int target_layer) {
	struct pathmap_context C;
	pathmap_init(&C, S, layer, target_layer, pos);
	memset(C.target, 0, C.x * C.y * sizeof(slot_t));
	render(&C, pos, 1);
}

scene.h

#ifndef SCENE_H
#define SCENE_H

typedef int slot_t;

struct scene {
	int shift_x;
	int y;
	int layer_n;
	slot_t *layer[1];
};

struct scene_coord {
	unsigned short x;
	unsigned short y;
};

void scene_build(struct scene *S, int layer, int n, struct scene_coord p[]);
void scene_pathmap(struct scene *S, int layer, struct scene_coord pos, int target_layer);

#endif