Skip to content

Instantly share code, notes, and snippets.

@naoppy
Created March 19, 2023 16:48
Show Gist options
  • Save naoppy/0aeba4369c5db200136fa2258a418c89 to your computer and use it in GitHub Desktop.
Save naoppy/0aeba4369c5db200136fa2258a418c89 to your computer and use it in GitHub Desktop.
#include "QTree.h"
#include <random>
#include <climits>
int BitSeparate16(int n)
{
n = (n | (n << 8)) & 0x00ff00ff;
n = (n | (n << 4)) & 0x0f0f0f0f;
n = (n | (n << 2)) & 0x33333333;
n = (n | (n << 1)) & 0x55555555;
return n;
}
Shot::Shot(float cx, float cy, float speed)
: cx(cx), cy(cy), speed(speed)
{
}
std::random_device rd;
std::mt19937 mt(rd());
void Shot::MoveRandom()
{
this->cx += speed * mt() / INT32_MAX;
}
void QTree::PushShot(std::weak_ptr<Shot> shot)
{
}
#pragma once
#include <list>
#include <forward_list>
#include <memory>
class Shot
{
public:
Shot(float cx, float cy, float speed);
float cx, cy;
float r = 3;
bool active = true;
float speed;
void MoveRandom();
};
class QTree
{
public:
std::forward_list<std::weak_ptr<Shot>> cells[85];
void PushShot(std::weak_ptr<Shot> shot);
};
// 16bitの入力を、bitを一つ飛ばしにして出力する。
// 例:
// n= 0b 0100 1110
// out= 0b 00 01 00 00 01 01 01 00
int BitSeparate16(int x);
// 16bitの入力x, yからモートン番号を得る
// x, yは最小分割単位のセルの上で左上から右にx, 下にy移動の意味
inline int Get2DMortonNumber(int x, int y) {
return (BitSeparate16(x) | (BitSeparate16(y) << 1));
}
inline int GetCellID(int L, int idx)
{
static int offset[] = { 0, 1, 5, 21, 85 }; // (4^n - 1) / 3
return offset[L] + idx;
}
inline int GetCellIDFromPair(std::pair<int, int> p)
{
return GetCellID(p.first, p.second);
}
#define CELL_SPRIT_L 4 // 各辺2^4の分割をしている
/*
* 最も細かいセルでの左上と右下の座標(左上からセルを何個移動するか)を入力すると
* どの階層かと、その階層での座標のセル番号を求める
*/
std::pair<int, int> GetLAndIdx(int lux, int luy, int rbx, int rby)
{
// printf("lux=%d, luy=%d, rbx=%d, rby=%d\n", lux, luy, rbx, rby);
int cx = lux xor rbx;
int cy = luy xor rby;
int z = cx | cy;
// printf("x = %d, y = %d, z = %d\n", x, y, z);
// 1になっている一番上の桁を求める(16bit ver)
// intの上位16bitは0クリアされている仮定
z = z & 0xFF00 ? z & 0xFF00 : z;
z = z & 0xF0F0 ? z & 0xF0F0 : z;
z = z & 0xCCCC ? z & 0xCCCC : z;
z = z & 0xAAAA ? z & 0xAAAA : z;
// printf("MLB z: %d\n", z);
int L = CELL_SPRIT_L - 1;
if (z == 0) {
return std::make_pair(L, Get2DMortonNumber(lux, luy));
}
L -= 1;
int ret = Get2DMortonNumber(lux, luy) >> 2;
int i = 0;
while ((z >> i) != 1)
{
ret >>= 2;
i++;
L--;
}
// printf("ans: %d\n", ret);
return std::make_pair(L, ret);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment