距離上次釋出已經有了很長一段時間,期間由于各種原因沒有更新這方面的技術分享,在這裡深表遺憾。在MMO或其他的遊戲中,會有針對各種形狀的計算,通常在攻擊區域裡不會很複雜,常見的為矩形、圓形、扇形。今天分享的是判斷一個目标點是否在扇形内的計算,用到的是比較簡單的運算,高效率的算法我很盡快更新。
數學知識
在這裡需要大家回顧一下國中以及高中的代數和平面幾何的知識,想必大部分的朋友在這方面和我一樣幾乎忘記了或是對這些數學知識感覺有些頭痛。不過大家沒有必要擔心,在實際運用中,我們都不會涉及太複雜的計算,因為我們不需要追求的十分精确。
但是在以下内容中,大家需要知道一些基本的定理和公式:勾股定理、餘弦定理。
需要了解弧度和角度的一些轉換:角度 = 弧度 * 180.0 / ∏
一些數學函數:atan2、acos等。
中心線:以中心線順、逆時針展開半角,形成一個完整的目标扇形區域。
極坐标概念:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5SM0ITOxITO1QTMtMjM4cDM3MjNxQjMyEjNxAjMtATN0gzMz8CXyEjNxAjMvwFM1QDOzMzLcd2bsJ2Lc12bj5ycn9Gbi52YuUTMwIzcldWYtl2Lc9CX6MHc0RHaiojIsJye.png)
如上圖坐标點A的平面坐标為(7.96, 5.43),對應的極坐标為(ρ, θ)
相對坐标的概念:
在扇形的計算中,我們的X軸與Y軸的方向與原點的的X軸和Y軸平行,在上圖中,如果以A點作為中心點,那麼B的相對坐标為(xb - xa, yb - ya)。
扇形與點的關系
示例圖1:
必要的資料: 原點A(攻擊者坐标)、方向點B(direction)、目标點C(point)、扇形角度(β)、扇形的半徑(r)。
扇形的有效區域:
如上圖中的扇形的角度為180°,其有效面積為:以X軸為中心分布的可攻擊區域1(area1紫色區域)和可攻擊區域2(area2綠色區域)。
如果目标點的極坐标為(ρ,Θ),那麼上述的目标點判斷為:目标點到原點A的距離小于扇形的半徑(ρ <= r)、在區域1(0 <= Θ <= α + β / 2)或區域2((a - β / 2) + 360 <= Θ <= 360)。
因為我們的極坐标的範圍為(0-360),是以如果算出來的扇形最小的角度為負,需要轉換為正來比較。
從上述的判斷中,并沒有将所有的情況考慮到,如果需要的扇形角度超過180或者方向點落在不同的象限内,計算的方式是不同的,接下來再看一張示意圖。
示例圖2:
如上圖所示,這樣的面積計算就不能使用第一種方式,方向的極坐标的角度為315°,而扇形的角度的不過270°,那麼α、β、γ到底變成了怎樣的關系,我們求出了方向的極坐标是否能把這樣兩個面積的角度分别計算出來?
區域1(0 <= Θ <= α + β / 2),如果是上圖的資料則為0 <= Θ <= 315 + 270 / 2,範圍就是[0,450],如果用詞判斷則象限2中的空白部分的本不符合的點就符合條件了,其實我們可以看出區域1的實際範圍為[0,90],同理區域2的範圍為[180,360]。而超過了360°的角度隻要減去360,這裡的450轉換為正常角度則為90剛剛是我們的正确角度。而第一種方式中的區域二的區域為[a - β / 2,360],在上圖中剛剛為[180,360]是符合的。
如何判斷一個扇形是否跨域了X軸正方向?
因為我們的扇形是以中心線分成兩個部分,那麼隻需要判斷這兩個部分是否超過了就可以,目前如果中心線在X軸正方向時絕對是跨域了兩個方向。
三種跨域的方式:示例圖1中(a - β / 2)的值小于零、示例圖2中的(α + β / 2)大于360、方向點在X軸正方向上(極坐标的角度Θ為0或絕對坐标X大于0和Y等于0)。
同時兩個扇形的角度需要轉換:小于0的角度需要轉換為正(示例圖1中a - β / 2,加上360)、大于360的角度需要轉換為360以内的角度(示例圖中的α + β / 2,減去360)。
那麼兩個區域就為[0, a + β / 2]、[a - β / 2, 360],需要注意這裡的角度都需要進行上述的轉換。
示例圖3:
如果扇形的範圍沒有跨域X軸正方向,那麼角度的範圍是[a - β / 2, a + β / 2]。
代碼實作
我們知道了點和面的關系後,就能夠對目标點進行判定了,編碼實作才有了依據。(上面三種情況是否會有遺漏,暫時沒有考慮過,歡迎大家指正)
基礎結構定義:
struct point_struct {
double x;
double y;
point_struct() : x{.0}, y{.0} {}
};
using point_t = point_struct;
相對坐标轉換(沒有方向):
/**
* 沒有方向的相對坐标轉換,x、y軸的方向與原點相同
* @param origin 坐标系原點
* @param point 需要轉換的點
*/
/**
* Y
* |
* | CY
* | |
* | | .point
* | |
* | |
* | origin----------------- CX
* |
* |
* O--------------------------------------------------- X
*
*/
point_t absolute_to_relative(const point_t &origin, const point_t &point) {
point_t result;
result.x = point.x - origin.x;
result.y = point.y - origin.y;
return result;
}
極坐标轉換:
/**
* 簡單極坐标轉換(轉換後的x為斜邊,y為角度),
* 減少數學函數調用(可以忽略,因為通常情況下這幾種情況命中機率極低)
* @param point 需要轉換的點
*/
point_t to_spolar_coordinate(const point_t &point) {
point_t result;
result.x = 0;
result.y = -1;
if (0 == point.x == point.y) {
result.y = 0;
return result;
}
if (0 == point.y) {
result.x = abs(point.x);
result.y = point.x > 0 ? 0 : 180;
return result;
}
if (0 == point.x) {
result.x = abs(point.y);
result.y = point.y > 0 ? 90 : 270;
return result;
}
if (abs(point.x) == abs(point.y)) {
result.x = 1.41421 * abs(point.x);
if (point.x > 0 && point.y > 0) {
result.y = 45;
} else if (point.x < 0 && point.y > 0) {
result.y = 135;
} else if (point.x < 0 && point.y < 0) {
result.y = 225;
} else if (point.x > 0 && point.y < 0) {
result.y = 315;
}
}
return result;
}
/**
* 轉換為極坐标(轉換後的x為斜邊,y為角度)
* @param point 需要轉換的點
*/
inline point_t to_polar_coordinate(const point_t &point) {
point_t result;
result.x = sqrt(point.x * point.x + point.y * point.y);
result.y = (180.0 / PI) * atan2(point.y , point.x); //弧度轉角度
result.y = result.y < .0 ? result.y + 360.0 : result.y;
return result;
}
判斷是否在扇形内:
/**
* 判斷一個點是否在扇形内(相對中心點)
* @param center 扇形的中心點
* @param direction 中心線的方向坐标
* @param r 半徑
* @param angle 角度(0 < angle < 360)
* @param point 需要檢查的點
*/
bool in_circular_sector(const point_t ¢er,
const point_t &direction,
double r,
int angle,
const point_t &point) {
//實際使用中,我們會把方向點的極坐标放到外部進行計算
point_t d_rpoint = absolute_to_relative(center, direction); //方向相對坐标
point_t d_pc_point = to_spolar_coordinate(d_rpoint); //方向極坐标
if (-1 == d_pc_point.y) { //簡單的如果轉換不出,則需要調用角度函數計算
d_pc_point = to_polar_coordinate(d_rpoint);
}
point_t rpoint = absolute_to_relative(center, point); //目标相對坐标
point_t pc_point = to_polar_coordinate(rpoint); //目标極坐标
if (pc_point.x > r) return false;
bool result = false;
auto half_angle = angle / 2;
auto angle_counter = d_pc_point.y - half_angle; //中心線順時針方向的範圍
auto angle_clockwise = d_pc_point.y + half_angle; //中心線逆時針方向的範圍
/*
std::cout << "angle_counter: " << angle_counter << " angle_clockwise: "
<< angle_clockwise << " d_pc_point.y" << d_pc_point.y << std::endl;
*/
if (0 == d_pc_point.y || angle_counter < 0 || angle_clockwise > 360) {
angle_counter = angle_counter < 0 ? angle_counter + 360 : angle_counter;
angle_clockwise = angle_clockwise > 360 ? angle_counter - 360 : angle_counter;
if (pc_point.y >= 0 && pc_point.y <= angle_counter) {
result = true;
} else if (pc_point.y >= angle_clockwise && pc_point.y <= 360) {
result = true;
}
} else {
result = angle_counter <= pc_point.y && angle_clockwise >= pc_point.y;
}
return result;
}
實際使用的優化:
可以先求出圓範圍内的所有玩家對象,這樣可以減少atan2調用,其次方向點的極坐标放到循環之外,減少循環次數。
PF人員招募
開篇語
我們沒有大神,隻有解決問題的人。
我們沒有強悍的技術,隻有一顆向往簡單的心。
我們沒有驚人的理論,隻有一堆不可思議的妄想。
我們不需要複雜,隻需要夠簡潔。
我們不需要固定的思維,隻需要你能想得到。
PF托管位址
https://github.com/viticm/plainframework1
PF安裝教程
http://www.cnblogs.com/lianyue/p/3974342.html
PF交流QQ群
348477824(同時歡迎技術人員加入進行交流)
作者:viticm
出處: http://www.cnblogs.com/lianyue/
本文版權歸作者和部落格園共有,歡迎轉載,但未經作者同意必須保留此段聲明,且在文章頁面明顯位置給出原文連接配接,否則保留追究法律責任的權利。如果覺得還有幫助的話,可以點一下右下角的【推薦】,希望能夠持續的為大家帶來好的技術文章!想跟我一起進步麼?那就【關注】我吧。