# 2.5D Raycasting Engine

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

## 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 on other sites
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.
 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.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 11
• 24
• 43
• 75