masterchief

hey, I've got this huge problem with one of my little test-programs!
I don't want to ask you for some code, but some Idea how to solve my problem! It istn' C++ specific at all, just because I started to write the programm in c++...

anyway:
I've got a big polygon with a few smaller polygon-blocks inside them. The Polygons represent a house or someting and the smaller ones are visibility-blocking stuff like walls or something else. And I've got a little man or whatever (the blue block).
Everything I've got are the x and y coordinates of these polygons.
Now I would like to somehow draw a surface that represents the area, that my little blue man could see from his position.



The following Image is drawn in Paint, but that is almost exactly what I want(the red area)
I already painted these black lines from the blue man to the corners, I think thats how I have to programm it but I'm not very shure about that and it would be very nice if you could either point me to some tutorial or take the time to explain it to me, again I don't need some code but an Idea how to do this!

thanks in advance

andro

This is off the top of my head, so this may be a slow approach, espescially for larger areas.

For every point inside the large shape, draw a red line to the (x,y) of wherever your "man" is standing. If no point on that red line interesects any of the outside shape lines or inside shape lines, you know it's a visible point. If it does interesect, do not draw the line.

teencoder

Are you masking the background if not it appears as if boxes were covering the other stuff.

__________________
Geeks may not be cool now but in the long run they prosper.

masterchief

@andro, already tried something similar to your idea, but I did it graphically (using a TImage Component of the Borland C++ Builder) and only checked every black Pixel
if a pixel was black, I drew a red line from my man in direction of the black pixel until I reach a black pixel...that worked more or less, but I need a more accurate and (hopefully) faster way...I had to round a lot with the graphical stuff...I somehow need a mathematicall algorithm that works without the image!

@teencoder what do you mean with masking the background? that image is just painted in MS Paint, in my Programm I've only got the coordinates, so I can only draw the polygons as black lines and can't fill anything!

teencoder

Sorry I misinterpreted your post I thought you were using a bitmap.

__________________
Geeks may not be cool now but in the long run they prosper.

theproject

Hi there. Andro's approach is simple yet it is very slow, it would be much faster if you draw the lines From the guy to the map instead of backwards. That way u would eliminate lots of lines being projected , especially if u have a huge map with lots of walls.. u could draw a line starting from the center (where your guy is) , determine the closest point of intersection with your walls and then rotate that line ( around your guy) a little bit. your algorythm would be complete when the rotation would be >= 360º ... To determine the point of intersection in a very fast manner i would suggest a BSP approach... In this method you divide your space into N subspaces and create a tree with your subspaces and the subspaces inside some subspace etc... For instance, imagine you first divide your map into 4 smaller squares, if you generate a random line u know your line will intersect a wall that is contained in some of the squares, typically it will intersect a line that is contained in one of the smaller squrares, so, as you test the other 3 squares, the test for intersection will be false and you will determine the subspace in wich there is an intersection... this single 4 tests allowed you to discard 3/4 of the map and now u only have to test the objects wich are inside the subspace u know there is an intersection. Of course u can go even further and divide your original space M times in wich u divide the original space for example in 4 subspace , then u divide each of the subspace 4 more times etc... the thing to know is this:
Your tree only has to be created once.
The more times u subdivide each space , the more faster will your algorythm be ( untill some point) , because what you're really doing is to make the tree deeper...
The Number of subspace in wich u subvide a single space (or subspace) is the branching factor of the tree, if u divide in 4 quadrants u know that every node in the tree will have four childs' ...

hope it helped... cya []