Jump to content
  • Advertisement
Sign in to follow this  
Sepiantum

2.5D Raycasting Engine

This topic is 2509 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I recently wrote code to handle 2D ray casts, but I'm not sure if it is the most efficient method. Can anyone look through my algorithm and find areas that can be improved?

Many thanks,
Sepiantum

Code:
//find_distance - calculates perpendicular distance from player to wall in his direction + relative angle
float QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayCast::find_distance(QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayPlayer* pPlayer,
QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayMap* pMap,
float ray_angle,
float max_dist){
float angle = fmod(pPlayer->GetDirection() + ray_angle, static_cast<float>(2.0f * D3DX_PI)); //Calculate ray absolute angle based off of player direction and ray angle offset
if(angle == 0.0f || angle == D3DX_PI){
//Angles of 0 and pi are perfectly horizontal, so we can only check vertical
return this->vertical_distance(pPlayer, pMap, ray_angle, max_dist) * cos(ray_angle);
}
else if(angle == 0.5f * D3DX_PI || angle == 1.5f * D3DX_PI){
//Angles of pi/4 and 7pi/4 are perfectly vertical, so we can only check horizontal
return this->horizontal_distance(pPlayer, pMap, ray_angle, max_dist) * cos(ray_angle);
}
else {
//Not in the 4 cardinal directions, so we take the minimum distance
float d1 = this->horizontal_distance(pPlayer, pMap, ray_angle, max_dist);
float d2 = this->vertical_distance(pPlayer, pMap, ray_angle, max_dist);
if(d1 < 0.0f){
return d2 * cos(ray_angle);
}
else if(d2 < 0.0f){
return d1 * cos(ray_angle);
}
else {
return min(d1, d2) * cos(ray_angle);
}
}
}
//horizontal_distance - calculates perpendicular distance from player to wall in his direction + relative angle using horizontal lattice lines
float QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayCast::horizontal_distance(QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayPlayer* pPlayer,
QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayMap* pMap,
float ray_angle,
float max_dist){
float angle = fmod(pPlayer->GetDirection() + ray_angle, static_cast<float>(2.0f * D3DX_PI)); //Calculate ray absolute angle based off of player direction and ray angle offset

//Block size variable
float block = static_cast<float>(BLOCK_SIZE);
//Variables for lattice line points
float x = 0.0f;
float y = 0.0f;
const float px = pPlayer->GetX();
const float py = pPlayer->GetY();
float dx = block / tan(angle);
float dy = block;
float dist = 0.0f;
if(angle > 0.0f && angle < D3DX_PI){
//Upwards facing ray
dy = -dy; //Negate dy
//Calculate first intersection
y = static_cast<float>((static_cast<int>(px) / BLOCK_SIZE) * BLOCK_SIZE) - 1.0f;
x = px + (py - y) / tan(angle);
dist = sqrt((x - px) * (x - px) + (y - py) * (y - py));
if(this->wall_exists(pMap, static_cast<int>(x / block), static_cast<int>(y / block))){
//Return distance if there is a wall here
return dist;
}
//Otherwise continue
do {
x += dx; //Increment x
y += dy; //Increment y
dist = sqrt((x - px) * (x - px) + (y - py) * (y - py)); //Calculate distance
if(dist > max_dist){
//Exceed maximum ray distance
return -1.0f / cos(ray_angle); //-1 for failure
}
} while(!this->wall_exists(pMap, static_cast<int>(x / block), static_cast<int>(y / block)));
//Found wall
return dist;
} else {
//Downwards facing ray
//Calculate first intersection
y = static_cast<float>((static_cast<int>(py) / BLOCK_SIZE) * BLOCK_SIZE) + block;
x = px + (py - y) / tan(angle);
dist = sqrt((x - px) * (x - px) + (y - py) * (y - py));
if(this->wall_exists(pMap, static_cast<int>(x / block), static_cast<int>(y / block))){
//Return distance if there is a wall here
return dist;
}
//Otherwise continue
do {
x += dx; //Increment x
y += dy; //Increment y
dist = sqrt((x - px) * (x - px) + (y - py) * (y - py)); //Calculate distance
if(dist > max_dist){
//Exceed maximum ray distance
return -1.0f / cos(ray_angle); //-1 for failure
}
} while(!this->wall_exists(pMap, static_cast<int>(x / block), static_cast<int>(y / block)));
//Found wall
return dist;
}
return -1.0f / cos(ray_angle); //Could not find wall - return -1 to signify failure
}
//vertical_distance - calculates perpendicular distance from player to wall in his direction + relative angle using vertical lattice lines
float QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayCast::vertical_distance(QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayPlayer* pPlayer,
QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayMap* pMap,
float ray_angle,
float max_dist){
float angle = fmod(pPlayer->GetDirection() + ray_angle, static_cast<float>(2.0f * D3DX_PI)); //Calculate ray absolute angle based off of player direction and ray angle offset

//Block size variable
float block = static_cast<float>(BLOCK_SIZE);
//Variables for lattice line points
float x = 0.0f;
float y = 0.0f;
const float px = pPlayer->GetX();
const float py = pPlayer->GetY();
float dy = block * tan(angle);
float dx = block;
float dist = 0.0f;
if(angle > 0.5f * D3DX_PI && angle < 1.5f * D3DX_PI){
//Left facing ray
dx = -dx; //Negate dx
//Calculate first intersection
x = static_cast<float>((static_cast<int>(px) / BLOCK_SIZE) * BLOCK_SIZE) - 1.0f;
y = py + (px - x) * tan(angle);
dist = sqrt((x - px) * (x - px) + (y - py) * (y - py));
if(this->wall_exists(pMap, static_cast<int>(x / block), static_cast<int>(y / block))){
//Return distance if there is a wall here
return dist;
}
//Otherwise continue
do {
x += dx; //Increment x
y += dy; //Increment y
dist = sqrt((x - px) * (x - px) + (y - py) * (y - py)); //Calculate distance
if(dist > max_dist){
//Exceed maximum ray distance
return -1.0f / cos(ray_angle); //-1 for failure
}
} while(!this->wall_exists(pMap, static_cast<int>(x / block), static_cast<int>(y / block)));
//Found wall
return dist;
} else {
//Right facing ray
//Calculate first intersection
x = static_cast<float>((static_cast<int>(px) / BLOCK_SIZE) * BLOCK_SIZE) + block;
y = py + (px - x) * tan(angle);
dist = sqrt((x - px) * (x - px) + (y - py) * (y - py));
if(this->wall_exists(pMap, static_cast<int>(x / block), static_cast<int>(y / block))){
//Return distance if there is a wall here
return dist;
}
//Otherwise continue
do {
x += dx; //Increment x
y += dy; //Increment y
dist = sqrt((x - px) * (x - px) + (y - py) * (y - py)); //Calculate distance
if(dist > max_dist){
//Exceed maximum ray distance
return -1.0f / cos(ray_angle); //-1 for failure
}
} while(!this->wall_exists(pMap, static_cast<int>(x / block), static_cast<int>(y / block)));
//Found wall
return dist;
}
return -1.0f / cos(ray_angle); //Could not find wall - return -1 to signify failure
}
//wall_exists - tests if there is a wall at a grid point
bool QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayCast::wall_exists(QuantumGameEngine::QuantumGraphics::QuantumRaycast::CRayMap* pMap, int x, int y){
if(x >= pMap->map_width || y >= pMap->map_height){
//Out of bounds - we should not get this?
return false;
} else {
return !(pMap->map[x + pMap->map_width * y] == 0);
}
}

Share this post


Link to post
Share on other sites
Advertisement
It seems quite slow because you have a square root within your innermost loop and some trigonometric functions per ray.
You really don't need the sqrt because you can simply compare the squares of the distances.
Instead of

dist = sqrt((x - px) * (x - px) + (y - py) * (y - py)); //Calculate distance
if(dist > max_dist){ // ...

do it like this

dist = (x - px) * (x - px) + (y - py) * (y - py); //Calculate square of the distance
if(dist > max_dist*max_dist){ // ...


Also you don't need to separate the vertical and the horizontal function.
But I don't think you really need to optimize much because drawing the walls will take much more time.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!