# 2D visibility clipping C++

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

## Recommended Posts

So, I am trying to generate a visibility map from a given point taking into account wall segments along the way.  I have run into a problem though and I haven't figured out how to fix it and was hoping someone here could point me to what is wrong with this code:

Since it would be impossible for you to look at this and some data points I made a small youtube video of what the code is doing that makes it glitchy.  This video can be found at:

In this video we should never see the white area as we are surrounded by a box.

I do have a demo, but it is larger than the 2mb limit here it is posted on allegro's forums:  https://www.allegro.cc/forums/thread/613568

This should let you play around and see what kind of issues I have to better inform you to help with a solution.  Thanks for your time.

#include "Visibility.h"

#include <allegro.h>
#include <iostream>
#include <winalleg.h>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <math.h>

#include "Line_Segment_2D.h"
#include "Point_2D.h"

bool sortByAngle(const Point_2D &lhs,const Point_2D &rhs){return lhs.Last_Angle < rhs.Last_Angle;}
bool sortByDistance(const Line_Segment_2D *lhs, const Line_Segment_2D *rhs){return lhs->dist < rhs->dist;}

bool PointIsVisible(Point_2D ori, Point_2D p, std::vector <Line_Segment_2D *> &w)
{
Line_Segment_2D t(ori,p);
Point_2D intersect;
for(unsigned int i = 0;i < w.size();i++)
{
if(p != w[i]->A && p != w[i]->B && ori != w[i]->A && ori != w[i]->B )  //if we don't belong to this line; basicly line should not interfere with itself or other walls that end at the same point.
{
if(t.Segments_Intersect(w[i],intersect))return false;
}
}
return true;
}
Point_2D Find_Projection_Intersection(Point_2D Ori, Point_2D ver, std::vector <Line_Segment_2D *> W)
{
Point_2D intersect(0,0);

Line_Segment_2D *Line_Of_Sight;
Line_Of_Sight = new Line_Segment_2D(ver,Ori);
Line_Of_Sight->Resize(3072);        //need a big number here to extend to at least the outer bounding box.
for(unsigned int i = 0;i < W.size();i++)
{
if(Line_Of_Sight->Segments_Intersect(W[i],intersect))
{   //ok wall intersects with LOS!  Lets make sure it isn't our origonal wall now or one that ends at the same spot.
intersect.isProjection = true;
intersect.Last_Angle = ver.Last_Angle;
if(intersect != ver)
{
return intersect;
}
}
}
}
Visibility::Visibility(int x, int y)
{
TESTING = false;
size_x = x;
size_y = y;
VIS_MAP = create_bitmap(x,y);
}

BITMAP* Visibility::Get_Visibility(int max, int x,int y, std::vector <Line_Segment_2D *> &Walls)
{

Point_2D Ori(x,y);
std::vector <Point_2D> Endpoints;
rectfill(VIS_MAP,0,0,size_x,size_y,makecol(0,0,0));     //put fog of war up over everything!
for(unsigned int i = 0;i < Walls.size();i++)        //populate Endpoints from the walls in the nearby area.
{
Walls[i]->DistanceToPoint(Ori);
Endpoints.push_back(Walls[i]->A);
Ori.Angle_In_Degrees(Endpoints[i*2]);
Endpoints.push_back(Walls[i]->B);
Ori.Angle_In_Degrees(Endpoints[(i*2)+1]);
}

std::sort(Endpoints.begin(),Endpoints.end(),sortByAngle);   //sort vertices by angle
std::sort(Walls.begin(),Walls.end(),sortByDistance);        //sort walls by distance
std::vector <Point_2D> Final_Points;                        //container for vertices
for(unsigned int i = 0; i < Endpoints.size();i++)
{
while(i+1 < Endpoints.size() && Endpoints[i] == Endpoints[i+1])Endpoints.erase(Endpoints.begin()+i);   //only one of each vertex
bool has_start = false;
bool has_end = false;
//if(i==0 || i == Endpoints.size()-1){has_end = true;has_start = true;}       //making an assumption here it causes issues with projections.  First/last points should never give projections if this line is in.
for(unsigned int j = 0; j < Walls.size();j++)
{
if(Walls[j]->A == Endpoints[i] || Walls[j]->B == Endpoints[i])
{
if(Walls[j]->Active == true)
{
Walls[j]->Active = false;
has_end = true;
}else
{
Walls[j]->Active = true;
has_start = true;
}
}
}
if(PointIsVisible(Ori,Endpoints[i],Walls))
{
if(has_end && has_start)      //if a wall starts and ends here
{
Final_Points.push_back(Endpoints[i]);
}else
{
if(has_end) //end has projection second
{
Final_Points.push_back(Endpoints[i]);
Final_Points.push_back(Find_Projection_Intersection(Ori,Endpoints[i],Walls));
}
else //start has projection first
{
Final_Points.push_back(Find_Projection_Intersection(Ori,Endpoints[i],Walls));
Final_Points.push_back(Endpoints[i]);
}
}
}
}
for(unsigned int i = 0;i + 1 < Final_Points.size();i++)
{
triangle(VIS_MAP,Final_Points[i].x,Final_Points[i].y,Final_Points[i+1].x,Final_Points[i+1].y,Ori.x,Ori.y,makecol(255,0,255));
line(VIS_MAP,Final_Points[i+1].x,Final_Points[i+1].y,Final_Points[i].x,Final_Points[i].y,makecol(255,0,0));
circlefill(VIS_MAP,Final_Points[i].x,Final_Points[i].y,5,makecol(255,255,0));
}
triangle(VIS_MAP,Final_Points[Final_Points.size() -1].x,Final_Points[Final_Points.size()-1].y,Final_Points[0].x,Final_Points[0].y,Ori.x,Ori.y,makecol(255,0,255));
circlefill(VIS_MAP,Final_Points[Final_Points.size() -1].x,Final_Points[Final_Points.size() -1].y,5,makecol(255,255,0));
return VIS_MAP;
}

Visibility::~Visibility()
{
destroy_bitmap(VIS_MAP);
}



• ### 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!

• 11
• 15
• 21
• 26
• 11