第1章: コンピュータグラフィックスの歴史とMiniLibX
1.1 コンピュータグラフィックスの誕生
1.1.1 Ivan SutherlandとSketchpad（1963年）
コンピュータグラフィックスの歴史は、1963年にMITのIvan Sutherlandが開発したSketchpadに始まる。Sutherlandの博士論文「Sketchpad: A man-machine graphical communication system」は、インタラクティブコンピュータグラフィックスの基礎を確立した。
Sketchpadの革新的な概念
> "Sketchpad pioneered the concepts of object-oriented programming, graphical user interfaces, and computer-aided design." > > — ACM A.M. Turing Award citation for Ivan Sutherland, 1988
Sketchpadが導入した概念：
| 概念 | 説明 | 現代での影響 | |------|------|-------------| | ライトペン | 直接画面操作 | タッチスクリーン、スタイラス | | オブジェクト指向 | グラフィカル要素の階層 | OOP、シーングラフ | | 制約充足 | 幾何学的関係の維持 | CAD、レイアウトエンジン | | インスタンス化 | マスターからの複製 | コンポーネント、プレハブ |
Sketchpadの基本構造（概念図）：
┌─────────────────────────────────────┐
│ Display File │
│ ┌─────────────────────────────┐ │
│ │ オブジェクトリスト │ │
│ │ ├── 線分1 (x1,y1)→(x2,y2) │ │
│ │ ├── 円1 (cx,cy,r) │ │
│ │ └── 制約 (線分1 ⊥ 線分2) │ │
│ └─────────────────────────────┘ │
└─────────────────────────────────────┘
↓ 変換
┌─────────────────────────────────────┐
│ CRTディスプレイ │
│ (ベクタースキャン) │
└─────────────────────────────────────┘
1.1.2 ベクターグラフィックスからラスターグラフィックスへ
ベクターディスプレイの時代（1960年代）
初期のコンピュータディスプレイは、電子ビームを直接制御して図形を描画するベクタースキャン方式を採用していた。
ベクタースキャンの動作：
電子ビームが直接図形を描画：
開始点 → 終点へビームを移動
利点：
- 高解像度の線描画
- メモリ効率が良い（座標のみ保存）
- スケーリングが容易
欠点：
- 複雑な画像でちらつき
- 塗りつぶしが困難
- 画像表示に不適
ラスターディスプレイの登場（1970年代）
1970年代、フレームバッファの概念が登場し、ラスタースキャン方式のディスプレイが実用化された。
ラスタースキャンの動作：
画面をピクセルのグリッドとして走査：
←←←←←←←←←←←←←←←←
→→→→→→→→→→→→→→→→
←←←←←←←←←←←←←←←←
→→→→→→→→→→→→→→→→
...
フレームバッファ：
┌───┬───┬───┬───┬───┬───┐
│RGB│RGB│RGB│RGB│RGB│RGB│ 行0
├───┼───┼───┼───┼───┼───┤
│RGB│RGB│RGB│RGB│RGB│RGB│ 行1
├───┼───┼───┼───┼───┼───┤
│RGB│RGB│RGB│RGB│RGB│RGB│ 行2
└───┴───┴───┴───┴───┴───┘
フレームバッファの数学
定義（フレームバッファ）
フレームバッファ F は2次元配列：
F : [0, W) × [0, H) → C
where:
W : 画面の幅（ピクセル）
H : 画面の高さ（ピクセル）
C : カラースペース（例：RGB24 = [0,255]³）
メモリ使用量：
M = W × H × bpp / 8 bytes
where:
bpp : bits per pixel
例：1920×1080、24bit色
M = 1920 × 1080 × 24 / 8 = 6,220,800 bytes ≈ 6MB
1.1.3 カラー表現の理論
三原色理論（Young-Helmholtz, 1802/1850年代）
Thomas YoungとHermann von Helmholtzは、人間の色知覚が3種類の錐体細胞（赤、緑、青に対応）に基づくことを発見した。
RGBカラーモデル
RGB色空間：
G（緑）
↑
│ ・ 白 (255,255,255)
│ /│
│ / │
│ / │
│/ │
├────┼────→ R（赤）
/│ │
/ │ │
/ │ │
↙ │ │
B（青）・ 黒 (0,0,0)
色の表現：
赤 = (255, 0, 0)
緑 = (0, 255, 0)
青 = (0, 0, 255)
黄 = (255, 255, 0) // 赤 + 緑
シアン = (0, 255, 255) // 緑 + 青
マゼンタ = (255, 0, 255) // 赤 + 青
白 = (255, 255, 255) // 赤 + 緑 + 青
黒 = (0, 0, 0) // なし
ピクセルフォーマット
// 24ビットRGB（真色）
typedef struct {
unsigned char r; // 0-255
unsigned char g; // 0-255
unsigned char b; // 0-255
} t_rgb24;
// 32ビットRGBA（アルファチャンネル付き）
typedef struct {
unsigned char r;
unsigned char g;
unsigned char b;
unsigned char a; // 0=透明, 255=不透明
} t_rgba32;
// パックされた32ビット整数として
// 0xAARRGGBB or 0xRRGGBBAA（エンディアン依存）
unsigned int color = 0xFF00FF00; // 不透明な緑
1.2 ウィンドウシステムの発展
1.2.1 Xerox Altoと最初のGUI（1973年）
1973年、Xerox PARCでAltoコンピュータが開発された。Altoは最初のビットマップディスプレイを持つパーソナルコンピュータであり、WIMP（Windows, Icons, Menus, Pointer）インターフェースの原型を確立した。
Alan Kayの貢献
> "The best way to predict the future is to invent it." > > — Alan Kay, Xerox PARC, 1971
Alan KayはDynabook構想を提唱し、Smalltalkプログラミング言語とともに、現代のGUIの基礎を築いた。
1.2.2 X Window System（1984年）
MITプロジェクトAthena
1984年、MITのProject AthenaでX Window Systemが開発された。XはUnixワークステーション向けの標準的なウィンドウシステムとなった。
Xのアーキテクチャ
X Window Systemの構造：
┌─────────────────────────────────────────────┐
│ クライアント │
│ ┌─────────────┐ ┌─────────────┐ │
│ │ アプリケーション1│ │ アプリケーション2│ │
│ └──────┬──────┘ └──────┬──────┘ │
│ │ │ │
│ └──────┬───────┘ │
│ ↓ │
│ ┌─────────────────┐ │
│ │ Xlib / XCB │ Xプロトコル │
│ └────────┬────────┘ │
└──────────────────┼──────────────────────────┘
│ ネットワーク（TCP/IP または Unix Socket）
↓
┌──────────────────┴──────────────────────────┐
│ Xサーバー │
│ ┌─────────────────────────────────┐ │
│ │ ウィンドウマネージャ │ │
│ │ ├── ウィンドウ配置 │ │
│ │ ├── 装飾（タイトルバー等） │ │
│ │ └── フォーカス管理 │ │
│ └─────────────────────────────────┘ │
│ ↓ │
│ ┌─────────────────────────────────┐ │
│ │ グラフィックスハードウェア │ │
│ └─────────────────────────────────┘ │
└─────────────────────────────────────────────┘
Xプロトコルの特徴
- ネットワーク透過性：クライアントとサーバーは別のマシンで実行可能
- 非同期通信：リクエストとレスポンスが独立
- 拡張性：拡張機能をプロトコルに追加可能
1.2.3 ダブルバッファリング
ティアリングとちらつき問題
シングルバッファの問題：
時刻t1: フレームバッファに描画開始
┌──────────────┐
│ 古いフレーム │← 画面表示中
│ + │
│ 新しい描画 │← 描画中
└──────────────┘
時刻t2: 垂直同期信号（VSync）
画面更新 → ティアリング発生！
┌──────────────┐
│ 新しい部分 │
├──────────────┤
│ 古い部分 │← 描画が間に合わなかった
└──────────────┘
ダブルバッファリングの解決策
ダブルバッファリング：
バックバッファ フロントバッファ
（描画先） （表示中）
┌──────────────┐ ┌──────────────┐
│ │ │ │
│ 新しい描画 │ │ 現在の表示 │
│ │ │ │
└──────────────┘ └──────────────┘
↓ 描画完了後、VSync時にスワップ
┌──────────────┐ ┌──────────────┐
│ │ │ │
│ 現在の表示 │ │ 新しい描画 │
│ (次のフレーム用) │ │
└──────────────┘ └──────────────┘
1.3 イベント駆動プログラミング
1.3.1 ハリウッドの原則
イベント駆動の起源
1980年代、GUIアプリケーションの普及とともに、イベント駆動プログラミングが標準となった。
> "Don't call us, we'll call you." > > — Hollywood Principle（ハリウッドの原則）
従来の逐次プログラミングとの比較：
逐次プログラミング：
┌───────────────────────────────┐
│ main() { │
│ input = get_input(); │ ← プログラムが入力を要求
│ process(input); │
│ output(result); │
│ } │
└───────────────────────────────┘
イベント駆動プログラミング：
┌───────────────────────────────┐
│ main() { │
│ register_handler(KEY, f); │ ← ハンドラを登録
│ register_handler(MOUSE, g);
│ event_loop(); │ ← システムがイベントを通知
│ } │
│ │
│ void f(Event e) { │ ← システムから呼び出される
│ // キー処理 │
│ } │
└───────────────────────────────┘
1.3.2 コールバックパターン
コールバック関数の理論
定義（コールバック）
コールバックは、他のコードに引数として渡される
実行可能なコード（関数）であり、適切な時点で
呼び出し元によって実行される。
形式的には：
register : Event × (Event → Action) → void
dispatch : Event → Action
コールバックの呼び出し：
∀ e ∈ Event: dispatch(e) = f(e)
where f = registered_handler(event_type(e))
Xのイベントモデル
// Xイベントの構造
typedef union _XEvent {
int type; // イベントタイプ
XKeyEvent xkey; // キーイベント
XButtonEvent xbutton; // マウスボタン
XMotionEvent xmotion; // マウス移動
XExposeEvent xexpose; // 再描画要求
XConfigureEvent xconfigure; // ウィンドウ設定変更
// ...
} XEvent;
// イベントループの基本パターン
void event_loop(Display *dpy) {
XEvent event;
while (1) {
XNextEvent(dpy, &event); // イベントを待機
switch (event.type) {
case KeyPress:
handle_key(&event.xkey);
break;
case ButtonPress:
handle_button(&event.xbutton);
break;
case Expose:
handle_expose(&event.xexpose);
break;
// ...
}
}
}
1.3.3 MiniLibXのイベントシステム
MiniLibXのフック関数
MiniLibXは、Xイベントを簡略化したインターフェースを提供する：
// MiniLibXのフック登録
int mlx_key_hook(void *win, int (*f)(), void *param);
int mlx_mouse_hook(void *win, int (*f)(), void *param);
int mlx_expose_hook(void *win, int (*f)(), void *param);
int mlx_loop_hook(void *mlx, int (*f)(), void *param);
int mlx_hook(void *win, int event, int mask, int (*f)(), void *param);
// 関係性
┌──────────────────────────────────────────────┐
│ mlx_hook (汎用) │
│ ┌────────────────┐ ┌────────────────┐ │
│ │ mlx_key_hook │ │ mlx_mouse_hook │ ... │
│ │ (event=2,3) │ │ (event=4,5) │ │
│ └────────────────┘ └────────────────┘ │
└──────────────────────────────────────────────┘
↓
┌──────────────────────────────────────────────┐
│ X Window Events │
│ KeyPress, KeyRelease, ButtonPress, ... │
└──────────────────────────────────────────────┘
Xイベントコード
// X11のイベントタイプ
#define KeyPress 2
#define KeyRelease 3
#define ButtonPress 4
#define ButtonRelease 5
#define MotionNotify 6
#define EnterNotify 7
#define LeaveNotify 8
#define FocusIn 9
#define FocusOut 10
#define Expose 12
#define DestroyNotify 17
// MiniLibXでの使用例
mlx_hook(win, 2, 1L<<0, key_press, &game); // KeyPress
mlx_hook(win, 17, 0, close_window, &game); // DestroyNotify
1.4 ゲームループの理論
1.4.1 ゲームループの歴史
初期のゲームループ（1970年代）
最初のビデオゲーム（Pong, 1972年）から、ゲームはループ構造を採用してきた。
基本的なゲームループ：
while (game_running) {
process_input(); // 入力処理
update_game_state(); // ゲーム状態更新
render(); // 描画
}
1.4.2 固定タイムステップ vs 可変タイムステップ
固定タイムステップ
固定タイムステップ（例：60 FPS）：
while (running) {
start_time = get_time();
process_input();
update(FIXED_DT); // DT = 1/60秒
render();
elapsed = get_time() - start_time;
if (elapsed < FRAME_TIME) {
sleep(FRAME_TIME - elapsed);
}
}
利点：
- 物理シミュレーションが安定
- 再現可能な動作
- デバッグが容易
欠点：
- 処理が間に合わないとスローダウン
- ハードウェア依存
可変タイムステップ
可変タイムステップ：
last_time = get_time();
while (running) {
current_time = get_time();
dt = current_time - last_time;
last_time = current_time;
process_input();
update(dt); // 経過時間に基づく更新
render();
}
利点：
- スムーズな動作
- ハードウェア適応
欠点：
- 物理シミュレーションが不安定になりうる
- 浮動小数点誤差の蓄積
1.4.3 So_longでのゲームループ
// MiniLibXでのゲームループ
// mlx_loop()が内部的にイベントループを実行
// ループフックで毎フレーム処理
int game_loop(t_game *game)
{
// ゲーム状態の更新（必要に応じて）
// So_longはイベント駆動なので通常は不要
// 描画は入力時に行うか、ここで行う
if (game->needs_redraw)
{
render_game(game);
game->needs_redraw = 0;
}
return (0);
}
// mlx_loop_hook(mlx, game_loop, &game);
// mlx_loop(mlx);
1.5 タイルベースグラフィックス
1.5.1 タイルマップの歴史
ファミコン/NES時代（1983年）
メモリとハードウェアの制約から、タイルベースのグラフィックスが発展した。
タイルマップの概念：
画面サイズ: 256×240 ピクセル
タイルサイズ: 8×8 ピクセル
タイルマップ: 32×30 = 960 タイル
メモリ効率：
- 直接ビットマップ: 256 × 240 × 2 = 122,880 bytes
- タイルマップ: 960 タイル番号 + 256 タイル × 64 = 16,384 bytes
→ 約87%のメモリ節約
タイルマップの形式的定義
定義（タイルマップ）
タイルマップ M は：
M = (T, G, W, H) where:
T : タイルセット（パターンの集合）
G : [0, W) × [0, H) → T（グリッド関数）
W : マップの幅（タイル単位）
H : マップの高さ（タイル単位）
描画関数：
render(M, x, y) = T[G[x÷tile_size, y÷tile_size]]
where:
tile_size : タイルのピクセルサイズ
1.5.2 So_longのマップ形式
So_longマップ (.ber ファイル)：
記号の意味：
'1' : 壁（通行不可）
'0' : 床（通行可能）
'P' : プレイヤー開始位置
'C' : 収集物（コレクタブル）
'E' : 出口
例：
1111111111111
10010000000C1
1000011111001
1P0011E000001
1111111111111
これは次のタイルマップに変換される：
G(x, y) = map[y][x]
where:
G(0, 0) = '1' (壁)
G(1, 3) = 'P' (プレイヤー)
G(11, 1) = 'C' (収集物)
G(6, 3) = 'E' (出口)
1.6 MiniLibXライブラリ
1.6.1 MiniLibXの設計思想
MiniLibXは42 Schoolが教育目的で開発した軽量グラフィックスライブラリである。
設計原則
- シンプルさ：最小限のAPIで基本的なグラフィックス操作
- クロスプラットフォーム：X11（Linux）、AppKit（macOS）
- 教育目的：低レベルの概念を学習可能
- C言語互換：純粋なC言語で使用可能
1.6.2 MiniLibXの基本関数
初期化とウィンドウ管理
// MLXインスタンスの初期化
void *mlx_init(void);
// 戻り値：MLX接続ハンドル（失敗時はNULL）
// 内部的にX11/Cocoaに接続
// ウィンドウの作成
void *mlx_new_window(void *mlx, int width, int height, char *title);
// パラメータ：
// mlx : MLXインスタンス
// width : 幅（ピクセル）
// height : 高さ（ピクセル）
// title : ウィンドウタイトル
// 戻り値：ウィンドウハンドル
// ウィンドウの破棄
int mlx_destroy_window(void *mlx, void *win);
画像処理
// 新しい画像の作成
void *mlx_new_image(void *mlx, int width, int height);
// XPMファイルから画像を読み込み
void *mlx_xpm_file_to_image(void *mlx, char *filename, int *w, int *h);
// 画像データへのアクセス
char *mlx_get_data_addr(void *img, int *bpp, int *line_len, int *endian);
// パラメータ：
// img : 画像ポインタ
// bpp : bits per pixel（出力）
// line_len : 1行のバイト数（出力）
// endian : バイトオーダー（出力）
// ウィンドウへの画像描画
int mlx_put_image_to_window(void *mlx, void *win, void *img, int x, int y);
// 画像の破棄
int mlx_destroy_image(void *mlx, void *img);
イベント処理
// キーフック
int mlx_key_hook(void *win, int (*f)(), void *param);
// 汎用フック
int mlx_hook(void *win, int event, int mask, int (*f)(), void *param);
// ループフック（毎フレーム呼び出し）
int mlx_loop_hook(void *mlx, int (*f)(), void *param);
// イベントループの開始
int mlx_loop(void *mlx);
1.6.3 最初のMiniLibXプログラム
#include <mlx.h>
#include <stdlib.h>
// プラットフォーム別キーコード
#ifdef __APPLE__
#define KEY_ESC 53
#else
#define KEY_ESC 65307
#endif
typedef struct s_app
{
void *mlx;
void *win;
} t_app;
// ウィンドウクローズハンドラ
int close_handler(t_app *app)
{
mlx_destroy_window(app->mlx, app->win);
exit(0);
return (0);
}
// キー押下ハンドラ
int key_handler(int keycode, t_app *app)
{
if (keycode == KEY_ESC)
close_handler(app);
return (0);
}
int main(void)
{
t_app app;
// MLX初期化
app.mlx = mlx_init();
if (!app.mlx)
return (1);
// ウィンドウ作成
app.win = mlx_new_window(app.mlx, 800, 600, "Hello MiniLibX");
if (!app.win)
return (1);
// イベントフック登録
mlx_key_hook(app.win, key_handler, &app);
mlx_hook(app.win, 17, 0, close_handler, &app); // DestroyNotify
// イベントループ開始
mlx_loop(app.mlx);
return (0);
}
1.7 So_longプロジェクトの概要
1.7.1 プロジェクト要件
必須機能
.ber拡張子のテキストファイル
- 長方形で壁（1）に囲まれている
- プレイヤー（P）、収集物（C）、出口（E）を含む- プレイヤー移動
- ゲームロジック
- ウィンドウ管理
1.7.2 データ構造設計
/* 位置を表す構造体 */
typedef struct s_pos
{
int x;
int y;
} t_pos;
/* マップデータ */
typedef struct s_map
{
char **grid; // 2次元配列
int width; // 幅（タイル数）
int height; // 高さ（タイル数）
int collectibles; // 収集物の総数
int collected; // 収集済み数
t_pos player; // プレイヤー位置
t_pos exit; // 出口位置
} t_map;
/* テクスチャ */
typedef struct s_textures
{
void *wall;
void *floor;
void *player;
void *collectible;
void *exit_closed;
void *exit_open;
int size; // タイルサイズ
} t_textures;
/* ゲーム状態 */
typedef struct s_game
{
void *mlx;
void *win;
t_map map;
t_textures tex;
int moves;
int game_over;
} t_game;
1.7.3 プロジェクト構成
so_long/
├── Makefile
├── includes/
│ └── so_long.h
├── srcs/
│ ├── main.c // エントリポイント
│ ├── init.c // 初期化
│ ├── map_parser.c // マップ読み込み
│ ├── map_validator.c // マップ検証
│ ├── path_checker.c // パス到達性検証（BFS/DFS）
│ ├── render.c // 描画
│ ├── events.c // イベント処理
│ ├── movement.c // 移動処理
│ ├── utils.c // ユーティリティ
│ └── cleanup.c // リソース解放
├── textures/
│ ├── wall.xpm
│ ├── floor.xpm
│ ├── player.xpm
│ ├── collectible.xpm
│ ├── exit_closed.xpm
│ └── exit_open.xpm
└── maps/
├── valid.ber
└── test.ber
1.8 XPMファイル形式
1.8.1 XPMの歴史
XPM（X PixMap）は、1989年にDaniel Dardaillerが開発したテキストベースの画像フォーマットである。Cソースコードとして直接組み込める点が特徴。
1.8.2 XPMの構造
/* XPM */
static char *image_name[] = {
/* 幅 高さ 色数 文字/ピクセル */
"32 32 4 1",
/* カラーテーブル */
". c None", /* 透明 */
"# c #000000", /* 黒 */
"@ c #FF0000", /* 赤 */
" c #FFFFFF", /* 白（スペース）*/
/* ピクセルデータ */
"................................",
"..............##................",
".............####...............",
/* ... 32行 ... */
};
1.8.3 So_long用テクスチャ例
/* wall.xpm - 32x32ピクセルの壁テクスチャ */
static char *wall_xpm[] = {
"32 32 3 1",
". c #2C2C2C",
"# c #1A1A1A",
"@ c #3F3F3F",
"@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@",
"@##############################@",
"@#............................#@",
"@#............................#@",
/* ... */
};
1.9 参考文献
- Sutherland, I. E. (1963). "Sketchpad: A man-machine graphical communication system". MIT PhD Thesis
- Foley, J. D. et al. (1990). "Computer Graphics: Principles and Practice". Addison-Wesley
- Kay, A. (1993). "The Early History of Smalltalk". ACM SIGPLAN Notices, 28(3)
- Scheifler, R. W. & Gettys, J. (1986). "The X Window System". ACM Transactions on Graphics, 5(2)
- Gamma, E. et al. (1994). "Design Patterns: Elements of Reusable Object-Oriented Software". Addison-Wesley (Observer Pattern)
- Gregory, J. (2018). "Game Engine Architecture, Third Edition". CRC Press
- Nystrom, R. (2014). "Game Programming Patterns". Genever Benning
- コンピュータグラフィックスの歴史：Sutherland、ベクター/ラスター、フレームバッファ
- 色彩理論：RGB、ピクセルフォーマット、アルファチャンネル
- ウィンドウシステム：X Window、ダブルバッファリング
- イベント駆動プログラミング：コールバック、フック、イベントループ
- ゲームループ：固定/可変タイムステップ
- タイルベースグラフィックス：タイルマップ、メモリ効率
- MiniLibX：API、初期化、イベント処理
1.10 まとめ
この章では、So_longプロジェクトの理論的基盤を学んだ：
次の章では、ウィンドウ管理とイベント処理について詳しく学び、キーボード入力とプレイヤー移動を実装する。