Arduboyで狙い撃つぜ！（atan2テーブルの作り方） その５

今回もM-KAI氏のものを参考にした。
http://web.archive.org/web/20021220053234/http://www02.geocities.co.jp:80/SiliconValley-Bay/8572/algobib/lv029.htm
atanテーブルの検索ではなく、インデックスを求め、テーブルから一発で値を取得できる。

今までは、
x,yの比をテーブル化しておき、
1. x,yの比を求める
2. テーブルから求めた比に近い値を検索する
3. そのインデックスを返す

今回は、
インデックスをテーブル化しておき、
1. x,yの比を求める
2. 求めた比をインデックスにテーブルの値を返す

という流れになる。

---

atanテーブルを作成するのは、今まで通り。

import math

for angle in range(16):
    r = (angle + 0.5) / 64 * 2 * math.pi
    x = math.cos(r)
    y = math.sin(r)
    print(str(y / x) + ',')

今までは、このatanテーブルをArduboyで使用していたが、
Arduboyで作成した関数と同等なものをPythonで作成する。

そして、xを64に固定して、（１周を６４分割するため）
0〜64までyを変化させ、get_atan2からそれぞれの比のインデックスをテーブルとして出力する。
このインデックス値は0〜45度を表す、0〜8の値になる。

今までは、atanテーブルから近い値を探し、そのインデックスを返していたが、
予めインデックスのテーブルを作成しておき、x,yの比を添字にしてテーブルを参照するだけで、
sinテーブルを参照できるインデックスが手に入る、というものになる。

import math
import sys

atan_tbl = [
    0.049126849769467254,
    0.14833598753834742,
    0.25048696019130545,
    0.3578057213145241,
    0.4729647758913199,
    0.5993769336819237,
    0.7416505462720353,
    0.9063471690191469,
    1.1033299757334754,
    1.3483439134867197,
    1.668399205583507,
    2.11432235754864,
    2.7948127724904768,
    3.9922237837700827,
    6.7414524054149885,
    20.35546762498714,
]

def get_atan2(y, x):
    if x == 0:
        ratio = sys.float_info.max
    else:
        ratio = abs(y / x)

    idx = 0
    for i in range(16):
        idx = i
        if ratio < atan_tbl[idx]:
            break

    if x < 0:
        idx = 32 - idx
    if y < 0:
        idx = 64 - idx

    return idx

for y in range(64 + 1):
    print(str(get_atan2(y, 64)) + ', ', end='')

    if y % 16 == 15:
        print('')

x,yの絶対値で場合分けし、x,yの比が0〜1に収まるようにしておき、
それを64倍して今回作成したatanテーブルを参照する。
比が1になることがあるので、テーブルは65個必要ということ。

#include <Arduboy2.h>

Arduboy2 arduboy;

#define BOSS_SHOT   10

typedef struct CharaData {
  float x, y;
  float vx, vy;
  int8_t life;
};

CharaData player;

CharaData boss;
CharaData bossShot[BOSS_SHOT];

uint16_t counter;

const float sinTbl[] PROGMEM = {
  0.0,
  0.0980171403295606,
  0.19509032201612825,
  0.29028467725446233,
  0.3826834323650898,
  0.47139673682599764,
  0.5555702330196022,
  0.6343932841636455,
  0.7071067811865475,
  0.7730104533627369,
  0.8314696123025451,
  0.8819212643483549,
  0.9238795325112867,
  0.9569403357322089,
  0.9807852804032304,
  0.9951847266721968,
};

float getSin(int16_t angle)
{
  float result = 1.f;
  uint8_t idx = angle & 0x1f;

  if (idx < 16) {
    result = pgm_read_float(sinTbl + idx);
  } else if (idx > 16) {
    result = pgm_read_float(sinTbl + 32 - idx);
  }

  return (angle & 0x3f) > 32 ? -result : result;
}

float getCos(int16_t angle)
{
  return getSin(16 + angle);
}

const uint8_t atanTbl[] PROGMEM = {
  0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 
  2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 
  5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 
  8, 
};

uint8_t getAtan2(float y, float x)
{
  int8_t idx = 0; // 0度
  if (x == 0.f && y == 0.f) return idx; // 同じ位置の時は0度とみなす

  float ax = abs(x);
  float ay = abs(y);

  if (ax > ay) {
    uint8_t ratio = ay / ax * 64;
    idx = pgm_read_byte(atanTbl + ratio);
  } else {
    uint8_t ratio = ax / ay * 64;
    idx = 16 - pgm_read_byte(atanTbl + ratio);
  }

  // idxは第１象限の値なので、実際の象限の値に調整する
  if (x < 0) idx = 32 - idx;
  if (y < 0) idx = 64 - idx;

  return idx;
}

void setup()
{
  arduboy.begin();

  player.x = 20;
  player.y = 64 / 2;

  boss.x = 128 / 2;
  boss.y = 64 / 2;
}

void loop()
{
  if (!arduboy.nextFrame()) return;
  arduboy.clear();

  if (arduboy.pressed(LEFT_BUTTON)) {
    player.x -= 1.f;
  } else if (arduboy.pressed(RIGHT_BUTTON)) {
    player.x += 1.f;
  }
  if (arduboy.pressed(UP_BUTTON)) {
    player.y -= 1.f;
  } else if (arduboy.pressed(DOWN_BUTTON)) {
    player.y += 1.f;
  }
  arduboy.fillRect(player.x - 8.f, player.y - 4.f, 16, 8);

  arduboy.drawTriangle(boss.x, boss.y - 8.f, boss.x - 8.f, boss.y + 8.f, boss.x + 8.f, boss.y + 8.f);

  if (++counter % 10 == 0) {
    for (int8_t i = 0; i < BOSS_SHOT; ++i) {
      CharaData *p = &bossShot[i];
      if (p->life == 0) {
        p->life = 1;
        p->x = boss.x;
        p->y = boss.y + 2.f;

        // プレイヤの方向を求める
        uint8_t r = getAtan2(player.y - p->y, player.x - p->x);

        // 弾の移動方向を求める
        p->vx = getCos(r);
        p->vy = getSin(r);

        break;
      }
    }
  }

  for (int8_t i = 0; i < BOSS_SHOT; ++i) {
    CharaData *p = &bossShot[i];
    if (p->life > 0) {
      p->x += p->vx;
      p->y += p->vy;

      if (p->x < 0.f || 128.f < p->x || p->y < 0.f || 64.f < p->y) {
        p->life = 0;
      }

      arduboy.fillCircle(p->x, p->y, 2);
    }
  }

  arduboy.display();
}

今回の方法で、テーブルから一発で値を取得できるようになり、
テーブルを検索していた頃に比べると、高速化ができた。

しかし、一つ気になる箇所がある。

  if (ax > ay) {
    uint8_t ratio = ay / ax * 64;
    ...
  } else {
    uint8_t ratio = ax / ay * 64;
    ...
  }

x,yの比を求めるために割り算している点だ。
割り算は重いので、十分な高速化ができていないように思われる。