--- a/librpg/rpg/map.c	Wed Nov 11 17:10:40 2020 +0100
+++ b/librpg/rpg/map.c	Sat Nov 14 16:59:11 2020 +0100
@@ -24,6 +24,7 @@
 #include <core/error.h>
 #include <core/event.h>
 #include <core/image.h>
+#include <core/maths.h>
 #include <core/painter.h>
 #include <core/sprite.h>
 #include <core/state.h>
@@ -41,7 +42,7 @@
  * SPEED represents the number of pixels it must move per SEC.
  * SEC simply represends the number of milliseconds in one second.
  */
-#define SPEED 200
+#define SPEED 220
 #define SEC   1000
 
 /*
@@ -115,8 +116,8 @@
 	map->view_h = window.h;
 
 	/* Adjust margin. */
-	map->margin_w = map->view_w - (MARGIN_WIDTH * 2);
-	map->margin_h = map->view_h - (MARGIN_HEIGHT * 2);
+	map->margin_w = map->view_w - (MARGIN_WIDTH * 2) - map->player_sprite->cellw;
+	map->margin_h = map->view_h - (MARGIN_HEIGHT * 2) - map->player_sprite->cellh;
 
 	/* Center the view by default. */
 	center(map);
@@ -152,6 +153,10 @@
 handle_keyup(struct map *map, const union event *event)
 {
 	switch (event->key.key) {
+	case KEY_TAB:
+		map->flags ^= MAP_FLAGS_SHOW_GRID | MAP_FLAGS_SHOW_COLLIDE;
+		map_repaint(map);
+		break;
 	case KEY_UP:
 		map->player_movement &= ~(MOVING_UP);
 		break;
@@ -169,68 +174,229 @@
 	}
 }
 
-static void
-move_up(struct map *map, int delta)
+static int
+cmp_tile(const struct map_tile *t1, const struct map_tile *t2)
+{
+	if (t1->id < t2->id)
+		return -1;
+	if (t1->id > t2->id)
+		return 1;
+
+	return 0;
+}
+
+static struct map_tile *
+find_tile_by_id(const struct map *map, unsigned short id)
 {
-	map->player_y -= delta;
+	typedef int (*cmp)(const void *, const void *);
+
+	const struct map_tile key = {
+		.id = id
+	};
+
+	return bsearch(&key, map->tiles, map->tilesz, sizeof (struct map_tile), (cmp)cmp_tile);
+}
+
+static struct map_tile *
+find_tile_in_layer(const struct map *map, const struct map_layer *layer, int pr, int pc)
+{
+	unsigned short id;
 
-	if (map->player_y < map->margin_y) {
-		map->view_y = map->player_y - MARGIN_HEIGHT;
+	if ((id = layer->tiles[pc + pr * map->w]) == 0)
+		return NULL;
+
+	return find_tile_by_id(map, id - 1);
+}
 
-		if (map->view_y < 0)
-			map->view_y = 0;
+static bool
+can_be_used(const struct map *map, const struct map_tile *block, int drow, int dcol)
+{
+	if (drow) {
+		/* Object outside of left-right bounds. */
+		if (block->x + (int)block->w <= map->player_x ||
+		    block->x                 >= map->player_x + (int)map->player_sprite->cellw)
+			return false;
+
+		if ((drow < 0 && block->y            >= map->player_y + (int)map->player_sprite->cellh) ||
+		    (drow > 0 && block->y + block->h <= map->player_y + (int)map->player_sprite->cellh))
+			return false;
+	} else if (dcol) {
+		/* Object outside of up-down bounds. */
+		if (block->y + (int)block->h <= map->player_y ||
+		    block->y                 >= map->player_y + (int)map->player_sprite->cellh)
+			return false;
+
+		if ((dcol < 0 && block->x            >= map->player_x + (int)map->player_sprite->cellw) ||
+		    (dcol > 0 && block->x + block->w <= map->player_x + (int)map->player_sprite->cellw))
+			return false;
 	}
 
-	if (map->player_y < 0)
-		map->player_y = 0;
+	return true;
+}
+
+static bool
+find_tile_absolute(const struct map *map, struct map_tile *block, int row, int col, int drow, int dcol)
+{
+	struct map_tile *tile, tmp;
+
+	if (row < 0 || (unsigned int)row >= map->h || col < 0 || (unsigned int) col >= map->w)
+		return false;
+
+	if (!(tile = find_tile_in_layer(map, &map->layers[1], row, col)))
+		tile = find_tile_in_layer(map, &map->layers[0], row, col);
+
+	if (!tile)
+		return false;
+
+	/* Convert to absolute values. */
+	tmp.id = tile->id;
+	tmp.x = tile->x + col * map->tileset->cellw;
+	tmp.y = tile->y + row * map->tileset->cellh;
+	tmp.w = tile->w;
+	tmp.h = tile->h;
+
+	/* This tile is not usable */
+	if (!tile || !can_be_used(map, &tmp, drow, dcol))
+		return false;
+
+	memcpy(block, &tmp, sizeof (tmp));
+
+	return true;
 }
 
 static void
-move_right(struct map *map, int delta)
+find_block_y(const struct map *map, struct map_tile *block, int pr, int pc, int drow)
 {
-	if (map->player_x + map->player_sprite->cellw + delta > map->real_w)
-		map->player_x = map->real_w - map->player_sprite->cellw;
-	else
-		map->player_x += delta;
+	int ncols = map->player_sprite->cellw / map->tileset->cellw;
+	int nrows = map->player_sprite->cellh / map->tileset->cellh;
+	int start, end;
 
-	if (map->player_x + map->player_sprite->cellw > map->margin_x + map->margin_w) {
-		map->view_x += delta;
+	if (drow < 0) {
+		start = 0;
+		end = pr;
+		block->x = block->y = block->h = 0;
+		block->w = map->real_w;
+	} else {
+		start = pr + nrows;
+		end = map->h;
+		block->x = block->h = 0;
+		block->y = map->real_h;
+		block->w = map->real_w;
+	}
 
-		if (map->view_x + map->view_w > map->real_w)
-			map->view_x = map->real_w - map->view_w;
+	for (int r = start; r <= end; ++r) {
+		for (int c = 0; c <= ncols; ++c) {
+			struct map_tile tmp;
+
+			if (!find_tile_absolute(map, &tmp, r, pc + c, drow, 0))
+				continue;
+			if ((drow < 0 && tmp.y + tmp.h > block->y + block->h) ||
+			    (drow > 0 && tmp.y < block->y))
+				memcpy(block, &tmp, sizeof (tmp));
+		}
 	}
 }
 
 static void
-move_down(struct map *map, int delta)
+find_block_x(const struct map *map, struct map_tile *block, int pr, int pc, int dcol)
 {
-	if (map->player_y + map->player_sprite->cellh + delta > map->real_h)
-		map->player_y = map->real_h - map->player_sprite->cellh;
-	else
-		map->player_y += delta;
+	int ncols = map->player_sprite->cellw / map->tileset->cellw;
+	int nrows = map->player_sprite->cellh / map->tileset->cellh;
+	int start, end;
 
-	if (map->player_y + map->player_sprite->cellh > map->margin_y + map->margin_h) {
-		map->view_y += delta;
+	if (dcol < 0) {
+		start = 0;
+		end = pc;
+		block->x = block->y = block->w = 0;
+		block->h = map->real_h;
+	} else {
+		start = pc + ncols;
+		end = map->w;
+		block->x = map->real_w;
+		block->y = block->w = 0;
+		block->h = block->h;
+	}
 
-		if (map->view_y + map->view_h > map->real_h)
-			map->view_y = map->real_h - map->view_h;
+	for (int c = start; c <= end; ++c) {
+		for (int r = 0; r <= nrows; ++r) {
+			struct map_tile tmp;
+
+			if (!find_tile_absolute(map, &tmp, pr + r, c, 0, dcol))
+				continue;
+			if ((dcol < 0 && tmp.x + tmp.w > block->x + block->w) ||
+			    (dcol > 0 && tmp.x < block->x))
+				memcpy(block, &tmp, sizeof (tmp));
+		}
 	}
 }
 
+/*
+ * Fill dimensions of the adjacent tile from the current player position. The
+ * arguments drow/dcolumn indicate the desired movement (e.g. -1, +1) but only
+ * one at a time must be set.
+ *
+ * The argument block will be set to a rectangle that will collide with the
+ * player according to its position and destination. It is never null because
+ * if no tile definition is found it is set to the screen edges.
+ */
 static void
-move_left(struct map *map, int delta)
+find_tile_collision(const struct map *map, struct map_tile *block, int drow, int dcol)
+{
+	assert((drow != 0 && dcol == 0) || (drow == 0 && dcol != 0));
+
+	const int pcol = map->player_x / map->tileset->cellw;
+	const int prow = map->player_y / map->tileset->cellh;
+
+	if (drow)
+		find_block_y(map, block, prow, pcol, drow);
+	else if (dcol)
+		find_block_x(map, block, prow, pcol, dcol);
+}
+
+static void
+move_x(struct map *map, int delta)
 {
-	if (map->player_x < delta)
-		map->player_x = 0;
-	else
-		map->player_x -= delta;
+	struct map_tile block;
+
+	find_tile_collision(map, &block, 0, delta < 0 ? -1 : +1);
+
+	if (delta < 0 && map->player_x + delta < (int)(block.x + block.w))
+		delta = map->player_x - block.x - block.w;
+	else if (delta > 0 && (int)(map->player_x + map->player_sprite->cellw + delta) >= block.x)
+		delta = block.x - map->player_x - (int)(map->player_sprite->cellw);
+
+	map->player_x += delta;
+
+	if (map->player_x < map->margin_x || map->player_x >= (int)(map->margin_x + map->margin_w))
+		map->view_x += delta;
+
+	if (map->view_x < 0)
+		map->view_x = 0;
+	else if (map->view_x >= (int)(map->real_w - map->view_w))
+		map->view_x = map->real_w - map->view_w;
+}
 
-	if (map->player_x < map->margin_x) {
-		if (map->view_x < delta)
-			map->view_x = 0;
-		else
-			map->view_x -= delta;
-	}
+static void
+move_y(struct map *map, int delta)
+{
+	struct map_tile block;
+
+	find_tile_collision(map, &block, delta < 0 ? -1 : +1, 0);
+
+	if (delta < 0 && map->player_y + delta < (int)(block.y + block.h))
+		delta = map->player_y - block.y - block.h;
+	else if (delta > 0 && (int)(map->player_y + map->player_sprite->cellh + delta) >= block.y)
+		delta = block.y - map->player_y - (int)(map->player_sprite->cellh);
+
+	map->player_y += delta;
+
+	if (map->player_y < map->margin_y || map->player_y >= (int)(map->margin_y + map->margin_h))
+		map->view_y += delta;
+
+	if (map->view_y < 0)
+		map->view_y = 0;
+	else if (map->view_y >= (int)(map->real_h - map->view_h))
+		map->view_y = map->real_h - map->view_h;
 }
 
 static void
@@ -259,15 +425,10 @@
 		dx = 1;
 
 	/* Move the player and adjust view if needed. */
-	if (dx > 0)
-		move_right(map, delta);
-	else if (dx < 0)
-		move_left(map, delta);
-
-	if (dy > 0)
-		move_down(map, delta);
-	else if (dy < 0)
-		move_up(map, delta);
+	if (dx)
+		move_x(map, dx * delta);
+	if (dy)
+		move_y(map, dy * delta);
 
 	walksprite_update(&map->player_ws, ticks);
 }
@@ -278,23 +439,53 @@
 	assert(map);
 	assert(layer);
 
-	int x = 0, y = 0;
+	struct texture colbox = {0};
+	const size_t ntiles = map->w * map->h;
 
-	for (unsigned int r = 0; r < map->w; ++r) {
-		for (unsigned int c = 0; c < map->h; ++c) {
-			unsigned int si = r * map->w + c;
-			unsigned int sr = (layer->tiles[si] - 1) / map->tileset->ncols;
-			unsigned int sc = (layer->tiles[si] - 1) % map->tileset->nrows;
+	/* Show collision box if requested. */
+	if (map->flags & MAP_FLAGS_SHOW_COLLIDE && texture_new(&colbox, 16, 16)) {
+		texture_set_blend_mode(&colbox, TEXTURE_BLEND_BLEND);
+		texture_set_alpha_mod(&colbox, 100);
+		PAINTER_BEGIN(&colbox);
+		painter_set_color(0xa53030ff);
+		painter_clear();
+		PAINTER_END();
+	}
+
+	for (size_t i = 0; i < ntiles; ++i) {
+		const struct map_tile *tile;
+		int mx, my, mr, mc, sr, sc, id;
+
+		if (layer->tiles[i] == 0)
+			continue;
+
+		id = layer->tiles[i] - 1;
 
-			if (layer->tiles[si] != 0)
-				sprite_draw(map->tileset, sr, sc, x, y);
+		/* Map row/column. */
+		mc = i % map->w;
+		mr = i / map->w;
+
+		/* Map row/column real positions. */
+		mx = mc * map->tileset->cellw;
+		my = mr * map->tileset->cellh;
 
-			x += map->tile_w;
+		/* Sprite row/column. */
+		sc = (id) % map->tileset->ncols;
+		sr = (id) / map->tileset->ncols;
+
+		sprite_draw(map->tileset, sr, sc, mx, my);
+
+		if ((tile = find_tile_by_id(map, id)) && texture_ok(&colbox))
+			texture_scale(&colbox, 0, 0, 5, 5, mx + tile->x, my + tile->y, tile->w, tile->h, 0);
+
+		if (map->flags & MAP_FLAGS_SHOW_GRID) {
+			painter_set_color(0x202e37ff);
+			painter_draw_line(mx, my, mx + map->tileset->cellw, my);
+			painter_draw_line(mx + map->tileset->cellw - 1, my, mx + map->tileset->cellw - 1, my + map->tileset->cellh);
 		}
+	}
 
-		x = 0;
-		y += map->tile_h;
-	}
+	texture_finish(&colbox);
 }
 
 static void
@@ -312,7 +503,7 @@
 static void
 draw(struct state *state)
 {
-	return map_draw(state->data);
+	map_draw(state->data);
 }
 
 bool
@@ -359,7 +550,7 @@
 {
 	assert(map);
 
-	struct debug_report report = {0};
+	struct texture box = {0};
 
 	/* Draw the texture about background/foreground. */
 	texture_scale(&map->picture, map->view_x, map->view_y, window.w, window.h,
@@ -371,10 +562,18 @@
 		map->player_x - map->view_x,
 		map->player_y - map->view_y);
 
-	debugf(&report, "position: %d, %d", map->player_x,
-	    map->player_y);
-	debugf(&report, "view: %d, %d", map->view_x,
-	    map->view_y);
+	/* Draw collide box around player if requested. */
+	if (map->flags & MAP_FLAGS_SHOW_COLLIDE &&
+	    texture_new(&box, map->player_sprite->cellw, map->player_sprite->cellh)) {
+		texture_set_alpha_mod(&box, 100);
+		texture_set_blend_mode(&box, TEXTURE_BLEND_BLEND);
+		PAINTER_BEGIN(&box);
+		painter_set_color(0x4f8fbaff);
+		painter_clear();
+		PAINTER_END();
+		texture_draw(&box, map->player_x - map->view_x, map->player_y - map->view_y);
+		texture_finish(&box);
+	}
 }
 
 void
@@ -410,4 +609,3 @@
 
 	memset(map, 0, sizeof (*map));
 }
-