↑のように（例えば16×16ピクセルの）格子で区切られた座標空間を
座標A(x1,y1)からB(x2,y2)へ直線移動したときに、通過する全ての区画と
通過した順番を知るにはどのような方法が良いのか考えています。
直線と格子の交点を１つ１つ求めていけばいけそうではありますが、
処理が複雑になりそうです。また、交点の座標を求める必要はないので、
もっと簡単な方法があるのではないかと考えています。
もし、なにかアイディアがありましたらよろしくお願いします。

私にはよく分かりませんが、
二点間に直線を引くのを画面的に1ピクセルが16pxになるくらいにズームしたと考えて、
ブレゼンハムアルゴリズムってのが、ヒントになりませんか？？
自分にはなんの事やら、さっぱり？？

分かったら教えてください。

まだ（端点の処理に）バグがあるようですが、
1ピクセルを16ピクセルにズームしたと考えたブレゼンハムです。

実は僕も始めにブレセンハムを考えたんですが、
「通過する全ての区画」にはならないようです。
直線と格子の交点を求めていく方向で考える必要があるかもしれません。

お?スゴイじゃないですかぁ
どんな仕組みですか？

ブレゼンハムのアルゴリズムについては

No007-07 直線描画

を参考にしました。
検索するとアルゴリズムの説明をしているサイトが沢山あります。
しかし実装方法が微妙に違っていたりして、考察中です。

FLAファイルはこちらですが、
かなりわかりずらいと思います...。参考まで。

あまり具体的な答えではないのですが
その昔ラインの描画方法には二通りある様な事を
何かで見た気がします。

　　　　■■
　　■■
■■

と言うのと

　　　■■■
　■■■
■■

参考になるか分かりませんが、頑張って下さい。

----------------
「アカウント編集」で環境を書いておくとレスがつきやすいです。

閃光の魔術師（見習い）みっく
Blogはじめました

ankoです。
自分も作ってみました。
全部の点を拾って行くタイプです。
http://www.city-walker.net/test.html

確かにsmoke123さんの言われたように、直線と格子の交点を出す方が速いのでしょうね。

理屈的にはｙ軸と交差したポイントの左右両側のブロック、
ｘ軸と交差したポイントの上下のブロックは
必ず通過していますからね。

＞anko さん
いいですねー。
端点の処理もばっちりのようですね。
（もしよろしければ計算部分のソースコードを公開して頂けないでしょうか...？）
直線と格子の交点を求める方法は確実ですね。

＞みっく さん
　　　■■■
　■■■
■■
となる、無駄なく高速な線分描画アルゴリズムが理想的だと思います。
直線と格子の交点を求めずに通過する区画を調べる方法も
引き続き考えていきたいと思います。

ankoです。
当方FLASH5ですし、難しいscriptは書けませんが。参考までに

最初にステージに16×16サイズの、色が変る仕込をしたMCを600個複製します。
横30×縦20個、d0?d599の名前を付けておきます。左上起点（0,0）

for (var i = 0; i<600; i++) {
damblock.duplicateMovieClip("d"+i, i);
xx = (i%30);
yy = Math.floor(i/30);
this["d"+i]._x = xx*16;
this["d"+i]._y = yy*16;
}
-----------
次のは球のMC「A」に書いたscript

onClipEvent (enterFrame) {
mx = _root.B._x-_x;//A?B間のX距離
my = _root.B._y-_y;//A?B間のy距離

xL= Math.pow ( myx, 2 );//2乗
yL = Math.pow ( myy, 2 )
zL = Math.floor(Math.sqrt( xL+yL));//三平方の定理でA?B間の直線距離を出す

wx = mx/zL;//x増分
wy = my/zL;//y増分

for (var i = 0; i< zL ;i++ ) {
//ここを「i+=2」（一つおき）とか「i+=3」に変えると精度が低下=速くなる

ix = _x+(i*wx);
iy = _y+(i*wy);//forループ1回毎の座標を求める

BrokX = Math.floor(ix/16)%30;//ブロックのX列
BrokY = Math.floor(iy/16);//ブロックのY行

BrockNum = BrokY*30+BrokX;//当該ブロックの数字

_root["d"+BrockNum ].irokaete();

}
}

以上ですが、色々問題がありますよね?
●forループで遅い。
●1ループ間に、同じブロックに何度も同じ命令を出している。
等。

はじめまして。
はじめて投稿するのですが、不備があったらごめんなさい。

ブレゼンハムのアルゴリズムを利用して、
格子点用に読み替えてみました。

http://www.geocities.jp/animecomic_pen_7380/note/gridline.html

ただし、肝心のFlash側が分からないので、
JavaScriptで代用してます。