visibility.cpp

#include <SFML/Graphics.hpp>
#include <stdio.h>
#include <set>
#include <vector>
#include <math.h>
#include <assert.h>

const sf::Vector2u window_size{1280, 720};

sf::CircleShape player{20.f};

struct Corner
{
	Corner(sf::Vector2f position_) 
		: position{position_}
	{
	}

	sf::Vector2f delta() const { return player.getPosition() - position; }
	float angle() const { return std::atan(delta().y / delta().x) + (delta().x < 0 ? 3.1415f : 0.f); }
	sf::Vector2f position;

	bool operator<(Corner const& other_) const
	{
		return angle() < other_.angle();
	}
};

std::vector<sf::RectangleShape>	obstacles;
std::set<Corner> 				corners;
std::vector<sf::ConvexShape>	visible_areas;

struct Ray
{
	Ray(sf::Vector2f delta_)
		: step{delta_ / std::hypot(delta_.x, delta_.y)}
		, position{player.getPosition()} 
	{
	}
	
	sf::Vector2f step;
	sf::Vector2f position;

	bool outOfBounds()
	{
		return (position.x < 0 || position.y < 0 || position.x > window_size.x || position.y > window_size.y);
	}

	void cast()
	{
		while (!outOfBounds())
		{
			position -= step;
				
			for (const auto& obstacle : obstacles)
			{
				auto rect{obstacle.getGlobalBounds()};
				++rect.top;
				++rect.left;
				--rect.height;
				--rect.width;
				if (rect.contains(position))
					return;
			}
		}
	}
};

void makeObstacle(sf::Vector2f position_, sf::Vector2f size_)
{
	sf::RectangleShape obstacle{size_};
	obstacle.setPosition(position_);
	obstacle.setFillColor(sf::Color::Black);
	obstacles.push_back(obstacle);

	for (sf::Vector2f corner_position : {position_, position_ + size_, position_ + sf::Vector2f{size_.x, 0}, position_ + sf::Vector2f{0, size_.y}})
		corners.emplace(corner_position);

}

int main()
{
	bool lmb_pressed{false};

	sf::RenderWindow window{{window_size.x, window_size.y}, "Ray Casting Visibillity Algorithm"};
	player.setFillColor(sf::Color::Red);
	player.setOrigin(20.f, 20.f);
	player.setPosition(640, 360);

	makeObstacle({50, 100}, {200, 100});
	makeObstacle({700, 300}, {500, 50});
	makeObstacle({200, 600}, {150, 150});

	corners.insert(sf::Vector2f{0, 0});
	corners.insert(sf::Vector2f{window_size});
	corners.insert(sf::Vector2f(window_size.x, 0));
	corners.insert(sf::Vector2f(0, window_size.y));

	while (true)
	{
		sf::Event event;
		while(window.pollEvent(event))
		{
			if (event.type == sf::Event::Closed || (event.type == sf::Event::KeyPressed && event.key.code == sf::Keyboard::Escape))
				return 0;

			if (event.type == sf::Event::MouseButtonPressed && event.mouseButton.button == sf::Mouse::Left)
				lmb_pressed = true;

			if (event.type == sf::Event::MouseButtonReleased && event.mouseButton.button == sf::Mouse::Left)
				lmb_pressed = false;
		}

		if (lmb_pressed)
		{
			player.setPosition(static_cast<sf::Vector2f>(sf::Mouse::getPosition(window)));

			obstacles.clear();
			corners.clear();

			makeObstacle({50, 100}, {200, 100});
			makeObstacle({700, 300}, {500, 50});
			makeObstacle({200, 600}, {150, 150});

			corners.insert(sf::Vector2f{0, 0});
			corners.insert(sf::Vector2f{window_size});
			corners.insert(sf::Vector2f{window_size.x, 0});
			corners.insert(sf::Vector2f{0, window_size.y});
		}

		visible_areas.clear();

		Ray previous_ray{(corners.rbegin())->delta()};
		Corner previous_corner{corners.rbegin()->position};
		for (auto& corner : corners)
		{
			Ray ray{corner.delta()};

			previous_ray.cast();
			ray.cast();

			visible_areas.emplace_back(3);
			auto& visible_area{visible_areas.back()};

			visible_area.setFillColor(sf::Color::Yellow);

			if (!previous_ray.outOfBounds() || (previous_ray.outOfBounds() && ray.outOfBounds()))
				visible_area.setPoint(0, previous_ray.position);
			else
				visible_area.setPoint(0, previous_corner.position);

			if (!ray.outOfBounds() || (previous_ray.outOfBounds() && ray.outOfBounds()))
				visible_area.setPoint(1, ray.position);
			else
				visible_area.setPoint(1, corner.position);
			
			visible_area.setPoint(2, player.getPosition());

			previous_ray = std::move(ray);
			previous_corner = std::move(corner);
		}

		window.clear(sf::Color::White);

		for (const auto& visible_area : visible_areas)
			window.draw(visible_area);

		for (const auto& obstacle : obstacles)
			window.draw(obstacle);
		
		window.draw(player);

		window.display();
	}
}