Created
March 19, 2023 16:48
-
-
Save naoppy/0aeba4369c5db200136fa2258a418c89 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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) | |
{ | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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