Bresenham's Line Algorithm in PHP

Question

私は、テキストベース（コンソール）のWW2戦略ゲームに取り組んでいます。マップ上のあるタイルから別のタイルへ視線を計算するメソッドが必要です。私はこれは私が書いたものです、私のコードをオフベースにthis Javaの例を使用しました：

public function plotLine($x0, $y0, $x1, $y1, $size) 
{ 
    $arr = $this->getEmptyMap($size); 
    $xDist = abs($x1 - $x0); 
    $yDist = -abs($y1 - $y0); 
    if($x0 < $x1) { 
     $xStep = 1; 
    } else { 
     $xStep = -1; 
    } 

    if($y0 < $y1) { 
     $yStep = 1; 
    } else { 
     $yStep = -1; 
    } 

    $plotError = $xDist + $yDist; 

    $arr[$x0][$y0] = 1; 

    while($x0 != $x1 || $y0 != $y1) { 
     // if(2 * $plotError > $yDist) { 
     // // Horizontal step 
     // $plotError += $yDist; 
     // $x0 += $xStep; 
     // } 

     // if(2 * $plotError < $xDist) { 
     // // Vertical step 
     // $plotError += $xDist; 
     // $y0 += $yStep; 
     // } 

     if(2 * $plotError - $yDist > $xDist - 2 * $plotError) { 
      // Horizontal step 
      $plotError += $yDist; 
      $x0 += $xStep; 
     } else { 
      // Vertical step 
      $plotError += $xDist; 
      $y0 += $yStep; 
     }   


     $arr[$x0][$y0] = 1; 
    } 

    $this->line = $arr; 
} 

注：getEmptyMapは、ちょうど0の持つ多次元配列を埋めます。

1100 
0110 
0011 
0001 

Iラインをマッピングする方法を試みた：一つはフランツD.は、（現在使用される通常の実装である入力（4、0、0、4、4）を用い

Testresult上記の私の例でコメントアウトされています）、もう1つはFranz D.が示した変更された実装です。どちらも私には私が探している結果を与えていません。 「アンチエイリアシング」の一種。はんだが2,2で0,0から見え、1,2と2,1に建物がある場合、2,2にあるものはすべて視界からブロックする必要があります。コメントアウトされた実装は建物を完全に無視しますが、変更は2,1には当てられますが1,2ではありません。行の下と行の上の両方に「ヒット」するようにコードを調整するにはどうすればよいでしょうか？

Answer 1

あなたが直面している「問題」は、正確な対角線を見ると特殊なエッジケースのために起こります。

1）対角線で水平と垂直のタイルを同時に増やします。あなたのゲームでは、これは、たとえ枢機卿の指示がブロックされたとしても、ユニットが対角線を見ることができることを意味します。

2）水平タイルまたは垂直タイルの優先順位を選択し、そのうちの1つだけ増分するかを選択します。これはFranz Dのアルゴリズムであり、あなたが書いてあなたの投稿に載せることになりました。

1100 
0110 
0011 
0001 

あなたは業種が優先したい場合は、あなたがそれを変更することができます：という

... 
     if(2 * $plotError - $yDist < $xDist - 2 * $plotError) { 
      // Vertical step 
      $plotError += $xDist; 
      $y0 += $yStep; 
     } else { 
      // Horizontal step 
      $plotError += $yDist; 
      $x0 += $xStep; 
     } 

... 

注ここでは、if -statementは、結果がされることを意味し、対角線のために真でありますif/elseの両方のボディが入れ替えられ、>が<に変更されました。

さて、その結果は以下のようになります。

1000 
1100 
0110 
0011 

あなただけのユニットが隣接する枢機卿のいずれかを遮断するものがない場合は対角線に目を向けることができるようしたい場合は、最も簡単な解決策を使用することですアルゴリズムの上記の変形の両方を実行し、その結果を1つのタイルの単一の配列に結合する。

1つの最終的な注記：座標にのみ関心があり、その値ではない場合（あなたが記述したユースケースの場合のように）、単純な配列の(x, y)の座標を抽出して、完成したマップの2次元配列の代わりに後でループして、結果が1の(x, y)座標をすべて抽出します。

ゲームで幸運を祈る！