Advertisement Jump to content
Sign in to follow this  
~kyo~

2D visibility clipping C++

This topic is 1879 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 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);
}

Share this post


Link to post
Share on other sites
Advertisement
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!