マップパースと検証
形式言語理論の基礎
Noam Chomskyと言語の階層
1956年、言語学者Noam Chomsky（ノーム・チョムスキー）は、形式言語を4つの階層に分類するChomsky階層を提唱しました。この理論は、コンピュータサイエンスにおける構文解析の基盤となっています。
Chomsky階層（1956年）
Type 0: 無制限文法（Unrestricted Grammar）
- チューリングマシンで認識可能
- 停止問題は決定不能
Type 1: 文脈依存文法（Context-Sensitive Grammar）
- 線形有界オートマトンで認識可能
- 自然言語の一部の特性をモデル化
Type 2: 文脈自由文法（Context-Free Grammar）
- プッシュダウンオートマトンで認識可能
- プログラミング言語の構文を定義
Type 3: 正規文法（Regular Grammar）
- 有限オートマトンで認識可能
- 正規表現で記述可能
包含関係:
┌─────────────────────────────────────────────┐
│ Type 0 │
│ ┌─────────────────────────────────────┐ │
│ │ Type 1 │ │
│ │ ┌─────────────────────────────┐ │ │
│ │ │ Type 2 │ │ │
│ │ │ ┌─────────────────────┐ │ │ │
│ │ │ │ Type 3 │ │ │ │
│ │ │ │ 正規言語 │ │ │ │
│ │ │ └─────────────────────┘ │ │ │
│ │ │ 文脈自由言語 │ │ │
│ │ └─────────────────────────────┘ │ │
│ │ 文脈依存言語 │ │
│ └─────────────────────────────────────┘ │
│ 帰納的可算言語 │
└─────────────────────────────────────────────┘
.berファイルの形式言語としての分析
So_longのマップファイル（.ber形式）は、正規言語（Type 3）として形式化できます：
.ber ファイルの形式文法
非終端記号: MAP, LINE, TILE
終端記号: '0', '1', 'C', 'E', 'P', '\n'
生成規則:
MAP → LINE+
LINE → TILE+ '\n'
TILE → '0' | '1' | 'C' | 'E' | 'P'
正規表現での表現:
map = ([01CEP]+\n)+
制約（文法外で定義）:
- すべてのLINEは同じ長さ
- 最初と最後のLINEは'1'のみ
- 各LINEの最初と最後の文字は'1'
- 'P'はちょうど1つ
- 'E'はちょうど1つ
- 'C'は1つ以上
字句解析と構文解析
コンパイラ設計の歴史
1950年代後半、Grace Hopperの先駆的な仕事に続き、John BackusはFORTRANコンパイラの開発を主導しました。この過程で、プログラム言語の処理を字句解析（Lexical Analysis）と構文解析（Syntax Analysis）に分離するアプローチが確立されました。
コンパイラのフロントエンド構造
┌───────────┐ ┌───────────┐ ┌───────────┐
│ Source │ │ Token │ │ AST │
│ Code │───▶│ Stream │───▶│ (Parse │
│ ソースコード│ │トークン列 │ │ Tree) │
└───────────┘ └───────────┘ └───────────┘
│ │ │
▼ ▼ ▼
┌───────────┐ ┌───────────┐ ┌───────────┐
│ Lexer │ │ Parser │ │ Semantic │
│ 字句解析器 │ │ 構文解析器 │ │ Analyzer │
│ │ │ │ │ 意味解析器 │
└───────────┘ └───────────┘ └───────────┘
.berファイルのパーシング
マップファイルの読み込みは、この2段階プロセスに従います：
// 字句解析: ファイルを行（トークン）に分割
char **lexer_phase(char *filename, int *line_count)
{
int fd;
char *line;
t_list *lines;
char **result;
fd = open(filename, O_RDONLY);
if (fd < 0)
return (NULL);
lines = NULL;
*line_count = 0;
while ((line = get_next_line(fd)) != NULL)
{
// 改行文字の正規化
normalize_line_ending(line);
ft_lstadd_back(&lines, ft_lstnew(line));
(*line_count)++;
}
close(fd);
result = list_to_array(lines, *line_count);
ft_lstclear(&lines, NULL); // ノードのみ解放、contentは保持
return (result);
}
// 構文解析: トークン列の構造検証
int parser_phase(char **lines, int line_count, t_map *map)
{
// 空ファイルチェック
if (line_count == 0)
return (parse_error("Empty file"));
// 長方形チェック（すべての行が同じ長さ）
if (!validate_rectangular(lines, line_count))
return (0);
// 有効な文字のみを含むかチェック
if (!validate_characters(lines, line_count))
return (0);
// マップ構造体の構築
map->grid = lines;
map->height = line_count;
map->width = ft_strlen(lines[0]);
return (1);
}
グラフ理論の基礎
Leonhard Eulerと「ケーニヒスベルクの7つの橋」問題
1736年、スイスの数学者Leonhard Euler（レオンハルト・オイラー）は、ケーニヒスベルク（現ロシア・カリーニングラード）の7つの橋を一度ずつ渡って出発点に戻れるかという問題を解きました。この研究はグラフ理論の誕生とされています。
ケーニヒスベルクの橋問題（1736年）
A
/|\
/ | \
b c d
/ | \
B----e----C
\ /
f g
\ /
D
Eulerの定理:
一筆書きが可能 ⟺ 奇数次数の頂点が0個または2個
ケーニヒスベルク: 全頂点が奇数次数 → 不可能
グラフの形式的定義
グラフ G = (V, E)
V: 頂点の集合（Vertices）
E: 辺の集合（Edges）⊆ V × V
無向グラフ: E は順序なしペア {u, v}
有向グラフ: E は順序付きペア (u, v)
マップをグラフとして表現:
- 頂点: 移動可能な各タイル
- 辺: 隣接する移動可能タイル間の接続
例:
11111
1P0C1
10001
1E001
11111
頂点: {(1,1), (2,1), (3,1), (1,2), (2,2), (3,2), (1,3), (2,3), (3,3)}
辺: {(1,1)-(2,1), (2,1)-(3,1), (1,1)-(1,2), ...}
連結性（Connectivity）
グラフ理論において、連結性は重要な概念です。So_longでは、プレイヤーからすべての収集物と出口への到達可能性を検証する必要があります。
連結性の定義
無向グラフ G = (V, E) において:
- uからvへの経路: 頂点の列 u = v₀, v₁, ..., vₖ = v
ただし ∀i: (vᵢ, vᵢ₊₁) ∈ E
- 連結: ∀u, v ∈ V について u から v への経路が存在
到達可能性:
reachable(u, v) = ∃ 経路 from u to v
So_longの検証条件:
∀c ∈ Collectibles: reachable(Player, c)
∧ reachable(Player, Exit)
グラフ探索アルゴリズム
深さ優先探索（DFS）
深さ優先探索（Depth-First Search, DFS）は、グラフを探索する基本的なアルゴリズムです。可能な限り深く進み、行き止まりに達したらバックトラックします。
DFSアルゴリズム
DFS(G, s):
Input: グラフ G = (V, E)、開始頂点 s
Output: s から到達可能なすべての頂点
visited ← ∅
DFS-Visit(s, visited)
return visited
DFS-Visit(v, visited):
visited ← visited ∪ {v}
for each u ∈ Adj(v):
if u ∉ visited:
DFS-Visit(u, visited)
時間計算量: O(|V| + |E|)
空間計算量: O(|V|) （再帰スタック）
探索順序の例:
1
/ \
2 3
/ \ \
4 5 6
DFS順: 1 → 2 → 4 → 5 → 3 → 6
幅優先探索（BFS）
幅優先探索（Breadth-First Search, BFS）は、開始点から等距離の頂点を層ごとに探索します。
BFSアルゴリズム
BFS(G, s):
Input: グラフ G = (V, E)、開始頂点 s
Output: s から各頂点への最短距離
visited ← {s}
queue ← [s]
distance[s] ← 0
while queue ≠ ∅:
v ← queue.dequeue()
for each u ∈ Adj(v):
if u ∉ visited:
visited ← visited ∪ {u}
distance[u] ← distance[v] + 1
queue.enqueue(u)
return distance
時間計算量: O(|V| + |E|)
空間計算量: O(|V|)
探索順序の例:
1
/ \
2 3
/ \ \
4 5 6
BFS順: 1 → 2 → 3 → 4 → 5 → 6
Flood Fillアルゴリズム
起源：コンピュータグラフィックス
Flood Fill（洪水充填）アルゴリズムは、1970年代にXerox PARCで開発されたペイントプログラムに起源を持ちます。Alvy Ray Smithらが、連続した領域を一括で塗りつぶすために考案しました。
Flood Fillの応用
1. ペイントプログラム
- バケツツール（塗りつぶし）
- 選択領域の特定
2. 画像処理
- 連結成分のラベリング
- 境界検出
3. ゲーム開発
- 迷路の到達可能性判定
- 地形の連結性チェック
4. 地理情報システム（GIS）
- 流域分析
- 浸水シミュレーション
アルゴリズムの形式化
Flood Fill（4連結版）
FloodFill(image, x, y, targetColor, fillColor):
if x < 0 or x ≥ width or y < 0 or y ≥ height:
return
if image[y][x] ≠ targetColor:
return
if image[y][x] = fillColor: // 無限ループ防止
return
image[y][x] ← fillColor
FloodFill(image, x + 1, y, targetColor, fillColor) // 右
FloodFill(image, x - 1, y, targetColor, fillColor) // 左
FloodFill(image, x, y + 1, targetColor, fillColor) // 下
FloodFill(image, x, y - 1, targetColor, fillColor) // 上
連結性:
- 4連結: 上下左右の4方向のみ（So_longで使用）
- 8連結: 斜め方向も含む8方向
┌───┬───┬───┐ ┌───┬───┬───┐
│ │ ↑ │ │ │ ↖ │ ↑ │ ↗ │
├───┼───┼───┤ ├───┼───┼───┤
│ ← │ ● │ → │ │ ← │ ● │ → │
├───┼───┼───┤ ├───┼───┼───┤
│ │ ↓ │ │ │ ↙ │ ↓ │ ↘ │
└───┴───┴───┘ └───┴───┴───┘
4連結 8連結
.berファイル形式の実装
マップ記号の定義
// map_symbols.h
#ifndef MAP_SYMBOLS_H
# define MAP_SYMBOLS_H
// マップタイル定義
# define FLOOR '0'
# define WALL '1'
# define COLLECTIBLE 'C'
# define EXIT 'E'
# define PLAYER 'P'
// Flood Fill用マーカー
# define VISITED 'V'
// 有効な文字かどうかを判定
static inline int is_valid_tile(char c)
{
return (c == FLOOR || c == WALL || c == COLLECTIBLE
|| c == EXIT || c == PLAYER);
}
#endif
マップ読み込み実装
// ファイル拡張子の検証
int validate_extension(const char *filename, const char *ext)
{
size_t filename_len;
size_t ext_len;
if (!filename || !ext)
return (0);
filename_len = ft_strlen(filename);
ext_len = ft_strlen(ext);
if (filename_len <= ext_len)
return (0);
return (ft_strncmp(filename + filename_len - ext_len,
ext, ext_len) == 0);
}
// 行末文字の正規化
void normalize_line_ending(char *line)
{
size_t len;
if (!line)
return;
len = ft_strlen(line);
while (len > 0 && (line[len - 1] == '\n' || line[len - 1] == '\r'))
{
line[len - 1] = '\0';
len--;
}
}
// マップファイルの読み込み
char **read_map_file(const char *filename, int *height)
{
int fd;
char *line;
t_list *lines;
t_list *node;
char **result;
int i;
fd = open(filename, O_RDONLY);
if (fd < 0)
return (NULL);
lines = NULL;
*height = 0;
while ((line = get_next_line(fd)) != NULL)
{
normalize_line_ending(line);
if (ft_strlen(line) == 0)
{
free(line);
continue; // 空行をスキップ
}
ft_lstadd_back(&lines, ft_lstnew(line));
(*height)++;
}
close(fd);
if (*height == 0)
{
ft_lstclear(&lines, free);
return (NULL);
}
// リストを配列に変換
result = malloc(sizeof(char *) * (*height + 1));
if (!result)
{
ft_lstclear(&lines, free);
return (NULL);
}
i = 0;
node = lines;
while (node)
{
result[i++] = node->content;
node = node->next;
}
result[i] = NULL;
// リストノードのみ解放（contentは保持）
ft_lstclear(&lines, NULL);
return (result);
}
マップ検証の実装
形状検証（長方形チェック）
int validate_rectangular(t_map *map)
{
int i;
size_t expected_width;
if (!map->grid || map->height == 0)
return (0);
expected_width = ft_strlen(map->grid[0]);
if (expected_width == 0)
{
return (error_msg("Map width is zero"));
}
i = 1;
while (i < map->height)
{
if (ft_strlen(map->grid[i]) != expected_width)
{
return (error_msg("Map is not rectangular"));
}
i++;
}
map->width = expected_width;
return (1);
}
境界検証（壁チェック）
int validate_walls(t_map *map)
{
int i;
// 上辺と下辺のチェック
i = 0;
while (i < map->width)
{
if (map->grid[0][i] != WALL)
return (error_msg("Top wall is incomplete"));
if (map->grid[map->height - 1][i] != WALL)
return (error_msg("Bottom wall is incomplete"));
i++;
}
// 左辺と右辺のチェック
i = 0;
while (i < map->height)
{
if (map->grid[i][0] != WALL)
return (error_msg("Left wall is incomplete"));
if (map->grid[i][map->width - 1] != WALL)
return (error_msg("Right wall is incomplete"));
i++;
}
return (1);
}
要素カウントと検証
typedef struct s_element_count
{
int player;
int exit;
int collectible;
} t_element_count;
int validate_elements(t_map *map)
{
t_element_count count;
int x;
int y;
char tile;
ft_bzero(&count, sizeof(t_element_count));
y = 0;
while (y < map->height)
{
x = 0;
while (x < map->width)
{
tile = map->grid[y][x];
if (!is_valid_tile(tile))
return (error_msg("Invalid character in map"));
if (tile == PLAYER)
{
count.player++;
map->player.x = x;
map->player.y = y;
}
else if (tile == EXIT)
{
count.exit++;
map->exit.x = x;
map->exit.y = y;
}
else if (tile == COLLECTIBLE)
count.collectible++;
x++;
}
y++;
}
// 制約の検証
if (count.player != 1)
return (error_msg("Map must have exactly one player"));
if (count.exit != 1)
return (error_msg("Map must have exactly one exit"));
if (count.collectible < 1)
return (error_msg("Map must have at least one collectible"));
map->collectibles = count.collectible;
return (1);
}
Flood Fill実装
再帰版（DFS）
typedef struct s_flood_result
{
int collectibles_found;
int exit_found;
} t_flood_result;
void flood_fill_recursive(char **grid, int x, int y,
t_flood_result *result, t_map *map)
{
char tile;
// 境界チェック
if (x < 0 || x >= map->width || y < 0 || y >= map->height)
return;
tile = grid[y][x];
// 壁または訪問済みはスキップ
if (tile == WALL || tile == VISITED)
return;
// 収集物と出口を記録
if (tile == COLLECTIBLE)
result->collectibles_found++;
if (tile == EXIT)
result->exit_found = 1;
// 訪問済みとしてマーク
grid[y][x] = VISITED;
// 4方向に再帰（DFS順）
flood_fill_recursive(grid, x + 1, y, result, map); // 右
flood_fill_recursive(grid, x - 1, y, result, map); // 左
flood_fill_recursive(grid, x, y + 1, result, map); // 下
flood_fill_recursive(grid, x, y - 1, result, map); // 上
}
反復版（BFS）- スタックオーバーフロー対策
大きなマップでは再帰が深くなりすぎる可能性があります。キューを使用したBFSによる反復版が安全です：
typedef struct s_point
{
int x;
int y;
} t_point;
typedef struct s_queue
{
t_point *data;
int front;
int rear;
int capacity;
} t_queue;
t_queue *queue_create(int capacity)
{
t_queue *q;
q = malloc(sizeof(t_queue));
if (!q)
return (NULL);
q->data = malloc(sizeof(t_point) * capacity);
if (!q->data)
{
free(q);
return (NULL);
}
q->front = 0;
q->rear = 0;
q->capacity = capacity;
return (q);
}
void queue_enqueue(t_queue *q, int x, int y)
{
q->data[q->rear].x = x;
q->data[q->rear].y = y;
q->rear++;
}
t_point queue_dequeue(t_queue *q)
{
return (q->data[q->front++]);
}
int queue_is_empty(t_queue *q)
{
return (q->front >= q->rear);
}
void queue_destroy(t_queue *q)
{
if (q)
{
free(q->data);
free(q);
}
}
// BFSによるFlood Fill
int flood_fill_bfs(char **grid, t_map *map)
{
t_queue *queue;
t_point current;
t_flood_result result;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int i;
int nx, ny;
// キューの初期化（最大でマップ全体のタイル数）
queue = queue_create(map->width * map->height);
if (!queue)
return (0);
ft_bzero(&result, sizeof(t_flood_result));
// 開始点をキューに追加
queue_enqueue(queue, map->player.x, map->player.y);
grid[map->player.y][map->player.x] = VISITED;
while (!queue_is_empty(queue))
{
current = queue_dequeue(queue);
// 4方向を探索
i = 0;
while (i < 4)
{
nx = current.x + dx[i];
ny = current.y + dy[i];
// 境界チェック
if (nx >= 0 && nx < map->width &&
ny >= 0 && ny < map->height)
{
if (grid[ny][nx] != WALL && grid[ny][nx] != VISITED)
{
// 収集物と出口をカウント
if (grid[ny][nx] == COLLECTIBLE)
result.collectibles_found++;
if (grid[ny][nx] == EXIT)
result.exit_found = 1;
// 訪問済みとしてマーク
grid[ny][nx] = VISITED;
queue_enqueue(queue, nx, ny);
}
}
i++;
}
}
queue_destroy(queue);
// 結果の検証
if (result.collectibles_found != map->collectibles)
return (error_msg("Not all collectibles are reachable"));
if (!result.exit_found)
return (error_msg("Exit is not reachable"));
return (1);
}
マップのコピーと解放
char **copy_map_grid(t_map *map)
{
char **copy;
int i;
copy = malloc(sizeof(char *) * (map->height + 1));
if (!copy)
return (NULL);
i = 0;
while (i < map->height)
{
copy[i] = ft_strdup(map->grid[i]);
if (!copy[i])
{
while (--i >= 0)
free(copy[i]);
free(copy);
return (NULL);
}
i++;
}
copy[i] = NULL;
return (copy);
}
void free_grid(char **grid, int height)
{
int i;
if (!grid)
return;
i = 0;
while (i < height)
{
free(grid[i]);
i++;
}
free(grid);
}
// 経路検証のラッパー関数
int validate_path(t_map *map)
{
char **grid_copy;
int result;
grid_copy = copy_map_grid(map);
if (!grid_copy)
return (error_msg("Memory allocation failed"));
result = flood_fill_bfs(grid_copy, map);
free_grid(grid_copy, map->height);
return (result);
}
統合マップパーサー
完全な検証パイプライン
int parse_and_validate_map(t_map *map, const char *filename)
{
// 1. ファイル拡張子の検証
if (!validate_extension(filename, ".ber"))
return (error_msg("Invalid file extension (expected .ber)"));
// 2. ファイルの読み込み（字句解析）
map->grid = read_map_file(filename, &map->height);
if (!map->grid)
return (error_msg("Failed to read map file"));
// 3. 長方形チェック（構文解析）
if (!validate_rectangular(map))
{
free_map(map);
return (0);
}
// 4. 壁チェック（意味解析）
if (!validate_walls(map))
{
free_map(map);
return (0);
}
// 5. 要素検証（意味解析）
if (!validate_elements(map))
{
free_map(map);
return (0);
}
// 6. 経路検証（Flood Fill）
if (!validate_path(map))
{
free_map(map);
return (0);
}
// 初期状態の設定
map->collected = 0;
return (1);
}
エラーハンドリング
// 一貫したエラー出力
int error_msg(const char *message)
{
write(STDERR_FILENO, "Error\n", 6);
write(STDERR_FILENO, message, ft_strlen(message));
write(STDERR_FILENO, "\n", 1);
return (0);
}
// マップの解放
void free_map(t_map *map)
{
if (!map)
return;
if (map->grid)
free_grid(map->grid, map->height);
ft_bzero(map, sizeof(t_map));
}
テストとデバッグ
デバッグ用マップ表示
#ifdef DEBUG
void debug_print_map(t_map *map, const char *label)
{
int y;
printf("\n=== %s ===\n", label);
printf("Size: %d x %d\n", map->width, map->height);
printf("Player: (%d, %d)\n", map->player.x, map->player.y);
printf("Exit: (%d, %d)\n", map->exit.x, map->exit.y);
printf("Collectibles: %d\n", map->collectibles);
printf("\n");
y = 0;
while (y < map->height)
{
printf("%s\n", map->grid[y]);
y++;
}
printf("\n");
}
#endif
テストケース
有効なマップ例:
simple.ber:
1111111111111
10010000000C1
1000011111001
1P0011E000001
1111111111111
無効なマップ例:
no_wall.ber (壁が不完全):
1111111111111
00010000000C1
1P0011E000001
1111111111111
no_path.ber (経路なし):
1111111111111
1P0111111111
1111111111111
100000000EC1
1111111111111
multiple_players.ber (複数プレイヤー):
1111111
1P0CP1
1E0001
1111111
計算量の分析
マップサイズ: W × H（幅 × 高さ）
読み込み: O(W × H)
- ファイルを1回走査
長方形チェック: O(H)
- 各行の長さを比較
壁チェック: O(W + H)
- 境界のみを走査
要素カウント: O(W × H)
- 全タイルを1回走査
経路検証 (Flood Fill): O(W × H)
- 各タイルを最大1回訪問
合計: O(W × H)
空間計算量:
- マップ格納: O(W × H)
- Flood Fill用コピー: O(W × H)
- BFSキュー: O(W × H) 最悪ケース
まとめ
この章では、マップの解析と検証について体系的に学びました：
- 形式言語理論: Chomsky階層と.berファイルの形式文法
- 字句解析・構文解析: コンパイラ設計のフロントエンド
- グラフ理論: Eulerの研究と連結性の概念
- 探索アルゴリズム: DFSとBFSの形式的定義
- Flood Fill: コンピュータグラフィックスからの応用
- 実装技術: 再帰版とBFS版の比較
これらの概念は、ゲーム開発に限らず、画像処理、ネットワーク分析、経路探索など、多くの分野で応用できる普遍的な知識です。
次の章では、スプライトと画像処理について学びます。XPMファイル形式、画像読み込み、効率的なレンダリング技術を探求します。