|
-
July 7th, 2005, 03:24 AM
#1
Looking for ideas for "field of view" (line of sight) algorithm
i do not know if i'm using the correct expression: "field of view" (FOW)
i'll try to explain
by FOW i mean an area that someone can see from one point.
since i dont know how to implement bitmaps from my comp in thread
ill draw with ascii chars:)
lets say we have 9x9 map and a person (:)) is standing in the middle
Code:
A B C D E F G H I
______ ______ ______ ______ ______ ______ ______ ______ ______
| | | | | | | | | |
1 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
2 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
3 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
4 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
5 | | | | | :) | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
6 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
7 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
8 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
9 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
now if the person would have FOW of just 1 square the map would look like this:
Code:
A B C D E F G H I
______ ______ ______ ______ ______ ______ ______ ______ ______
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
1 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
2 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
3 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████| | | |██████|██████|██████|
4 |██████|██████|██████| | | |██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████| | | |██████|██████|██████|
5 |██████|██████|██████| | :) | |██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████| | | |██████|██████|██████|
6 |██████|██████|██████| | | |██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
7 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
8 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
9 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
balcked squares are the ones a person cant see
if the person would have FOW of 2 squares the map would look like this:
Code:
A B C D E F G H I
______ ______ ______ ______ ______ ______ ______ ______ ______
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
1 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
2 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████| | | |██████|██████|██████|
3 |██████|██████|██████| | | |██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████| | | | | |██████|██████|
4 |██████|██████| | | | | |██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████| | | | | |██████|██████|
5 |██████|██████| | | :) | | |██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████| | | | | |██████|██████|
6 |██████|██████| | | | | |██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████| | | |██████|██████|██████|
7 |██████|██████|██████| | | |██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
8 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
9 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
since distance between center of (E,5) and, lets say, (C,3) is 2*sqrt(2)*a, where a is the length of square's side, and rounded up that equals 3*a, that square is blacked out
now lets add an obstacle and FOW 3
Code:
A B C D E F G H I
______ ______ ______ ______ ______ ______ ______ ______ ______
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
1 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|▒▒ | | |██████|██████|██████|
2 |██████|██████|██████|▒▒▒ | | |██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▒▒▒___|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|▒▒▒▒▒▒|▒▒▒▒ | | | |██████|██████|
3 |██████|██████|▒▒▒▒▒▒|▒▒▒▒▒ | | | |██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▒▒▒▒▒▒|▒▒▒▒▒▒|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|▒▒▒▒▒▒|▒▒▒▒▒▒|XXXXXX| | | | |██████|
4 |██████| ▒|▒▒▒▒▒▒|XXXXXX| | | | |██████|
|▀▀▀▀▀▀|______|_____▒|XXXXXX|______|______|______|______|▀▀▀▀▀▀|
|██████| | | | | | | |██████|
5 |██████| | | | :) | | | |██████|
|▀▀▀▀▀▀|______|______|______|______|______|______|______|▀▀▀▀▀▀|
|██████| | | | | | | |██████|
6 |██████| | | | | | | |██████|
|▀▀▀▀▀▀|______|______|______|______|______|______|______|▀▀▀▀▀▀|
|██████|██████| | | | | |██████|██████|
7 |██████|██████| | | | | |██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████| | | |██████|██████|██████|
8 |██████|██████|██████| | | |██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
9 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
grayed out sections inside squares are the one that person cant se becouse of the obstacle in square (D,4)
since squres (B,4) and (D,2) are more than 50% visible and (C,4) and (D,3) more than 50% visible the map looks like this:
Last edited by l00p1n6; July 7th, 2005 at 03:28 AM.
Reason: corrected typing errors
-
July 7th, 2005, 03:24 AM
#2
Re: Looking for ideas for "field of view" (line of sight) algorithm
Code:
A B C D E F G H I
______ ______ ______ ______ ______ ______ ______ ______ ______
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
1 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████| | | |██████|██████|██████|
2 |██████|██████|██████| | | |██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████| | | |██████|██████|
3 |██████|██████|██████|██████| | | |██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████| |██████|XXXXXX| | | | |██████|
4 |██████| |██████|XXXXXX| | | | |██████|
|▀▀▀▀▀▀|______|▀▀▀▀▀▀|XXXXXX|______|______|______|______|▀▀▀▀▀▀|
|██████| | | | | | | |██████|
5 |██████| | | | :) | | | |██████|
|▀▀▀▀▀▀|______|______|______|______|______|______|______|▀▀▀▀▀▀|
|██████| | | | | | | |██████|
6 |██████| | | | | | | |██████|
|▀▀▀▀▀▀|______|______|______|______|______|______|______|▀▀▀▀▀▀|
|██████|██████| | | | | |██████|██████|
7 |██████|██████| | | | | |██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████| | | |██████|██████|██████|
8 |██████|██████|██████| | | |██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|______|______|______|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
|██████|██████|██████|██████|██████|██████|██████|██████|██████|
9 |██████|██████|██████|██████|██████|██████|██████|██████|██████|
|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|▀▀▀▀▀▀|
now i think you understand the way my algorithm should work for various FOWs and any number of obstacles
the question is how to implement this "algorithm"
i had in mind some "spiral-walk" starting from center then sperading rountd the clock one "square-ring", then the second "square_ring" and so on
by "square-ring" i mean all squares with the same distance from point of view - from persons perspective
any comments/criticis would be welcome
if someone didnt understend my algorithm i will explain a bit further
-
July 7th, 2005, 07:40 AM
#3
Re: Looking for ideas for "field of view" (line of sight) algorithm
Hi!
I don't know if this will be right (or fast), but try doing something like this:
- retrieve all obstacles' points, choosing only the ones which are inside the circle, and put then in an array of some kind (try using STL containters)
Here you see an image of what is going on right now. As you see some of the dots have the same, let's say, angle. But their distance to the main dot is different. The idea with the spiral walk is great, but first sort the list of obstacles so that the nearest points go first. The STL containters sort the lists themselves so there should be no problem.
I wrote about point, but I know you want to operate on squares. I'm just mentioning points, because thanks to that technique your game will look more realistic. Try also using floating point while doing any calculations. Anyway, the next step:
After you sorted the list you will have something like this:
You see that points 1 and 3 may be before points 4 and 7. Now the main part. I think it's not so hard.
Get the first point (that point can be the rectangle's center point) and if you're using some shapes like squares for objects, put the two nearest to the main point and most further from the other in the pair to something like array of covers. I know this is a bit confusing and my english doesn't help here at all  But look at the next picture and maybe you will understand. The cover is marked here as the violet line.
For a rectangle the two points that make the cover will be much easier to extract so don't worry. The last step involves checking if the next point in the list is somewhere between the two "angles" of the points of the cover.
The more covers you have, the more checking you have to make. Insted of points or something like that you may use the cover's two points and immediately calculate the angles. This would enchance the performance.
I hope you understood what I was trying to explain. Is you have any more questions feel free to ask: lican@wp.pl . I'm writing a game of my own and maybe some day I will have a problem, who knows... 
P.S. Is there any way to paste images here :P?
-
July 7th, 2005, 07:42 AM
#4
Re: Looking for ideas for "field of view" (line of sight) algorithm
I'm sure there are plenty of predefined solutions to this issue, but I'll chime in with my idea.
Rather than considering the point of view of the observer, consider instead the ability of each taget cell to "see" the observer.
Examine each cell that is within range of the observer and inspect each cell in towards the observer. If you make it all the way to the observer without running into an obstacle, then that cell is visible.
Some shortcuts would be to limit the cells you examine to those in an NxN grid (where N=sight limit), and the first check you make for each cell is its actual distance from the observer. Also, as you examine the inner cells along the outer cell's sightlines, you can mark these inner cells as visible and avoid checking them again later.
Check the outer cells first, then work your way inwards until all cells are marked one way or the other.
Hope this helps.
--
Scott
-
July 7th, 2005, 07:54 AM
#5
Re: Looking for ideas for "field of view" (line of sight) algorithm
And one more thing. While using the list of covers or something like that you can update it every time the main point or any of the obstacles move. Here a heap might come in handy. If an obstacle moves it should update it's cover in the heap. That way fewer calculations have to be done.
-
July 7th, 2005, 09:24 AM
#6
Re: Looking for ideas for "field of view" (line of sight) algorithm
first of all: ofcourse i have to use NxN "array" only (N = FOW range), sorry for not pointing that out:)
i'm sorry but i didnt quite understand the second part of Lican's suggestion (after second immage)
wsmmi6674 , why should i start from the outside?
i could use center points of rectangles as wanted points,
but if i use point tehnique (wich is good)
i ran into another problem:
i might run into false "visible point"
example:
Code:
A B C D E F G H I
______ ______ ______ ______ ______ ______ ______ ______ ______
| | | | | | | | | |
1 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
2 | | | | | | | | :( | |
|______|______|______|______|______|______|______|______|______|
| | | | | |██████| | | |
3 | | | | | |██████| | | |
|______|______|______|______|______|▀▀▀▀▀▀|______|______|______|
| | | | | | |██████| | |
4 | | | | | | |██████| | |
|______|______|______|______|______|______|▀▀▀▀▀▀|______|______|
| | | | | | | | | |
5 | | | | | :) | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
6 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
7 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
8 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
9 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
the happy face":)" should not see the sad face ":(" but it does, since it has a straight line
maybe i should check a straight line with 3 point thickness?
like this:
Code:
A B C D E F G H I
______ ______ ______ ______ ______ ______ ______ ______ ______
| | | | | | | | /| /|
1 | | | | | | | | // | // |
|______|______|______|______|______|______|______|/_____|/_____|
| | | | | | | /| /| /|
2 | | | | | | | // | :( | // |
|______|______|______|______|______|______|/_____|/_____|/_____|
| | | | | |█████/| /| /| |
3 | | | | | |██//██| // | // | |
|______|______|______|______|______|/▀▀▀▀▀|/_____|/_____|______|
| | | | | /| /|█████/| | |
4 | | | | | // | // |██//██| | |
|______|______|______|______|/_____|/_____|/▀▀▀▀▀|______|______|
| | | | | /| /| | | |
5 | | | | | :) | // | | | |
|______|______|______|______|/_____|/_____|______|______|______|
| | | | | | | | | |
6 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
7 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
8 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
| | | | | | | | | |
9 | | | | | | | | | |
|______|______|______|______|______|______|______|______|______|
this way i'm positive that if at least 2 lines are blocked that means that desired point in middle line's path behind blocked points is 100% not visible
-
July 7th, 2005, 11:25 AM
#7
Re: Looking for ideas for "field of view" (line of sight) algorithm
You should start from the outside as this will naturally lead to marking many of the interior cells as the visibility of the outside cells are determined.
The touching diagonal obstacle problem is a bit trickier. The easiest solution I can see is to prevent it from happening in the first place. In your obstacle drawing algorithm, make sure diagonal gaps are filled on one side or another.
Failing that, I'm not sure what a good solution would be. Your suggestions would result in false blind spots:
Code:
---------------------
| | |XXX| | |
| | |XXX| 1 | |
| | |XXX| | |
---------------------
| | | | | |
| | | | | |
| | | | | |
---------------------
| | |XXX| | |
| | 2 |XXX| | |
| | |XXX| | |
---------------------
Should [1] be able to see [2]? I can draw a line from somewhere in box one to somewhere in box two. Is this good enough? If the answer is yes, the problem is that a cell in this case is not the smallest defined division of space. There should be no concept of "area within a cell". If one cell's center can see another's then a liine of sight exists.
I'd stick with my first suggestion, if at all possible - don't allow diagonal gaps in the playfield.
--
Scott
-
July 7th, 2005, 03:59 PM
#8
Re: Looking for ideas for "field of view" (line of sight) algorithm
Ok. I know the third part it was a bit hard to understand. I'll try to make it as clear as possible. Look at the picture:
Blue circle: Main character
Red circle: Obstacles
Light blue: "Invisibility shade"
Orange dot: Extreme points
Violet line: Shading line segment (Cover)
As you see object 3 is partialy visible - you get to choose if it will be fully visible or hidden. While scanning through the list of objects (from closest to furthest) do something like this:
Code:
1- create some kind of angles list
2- get next object's rectangle (square)
3- choose the two points that will create the cover
4- calculate the angle between them
5a- if this is not the first calculated angle check if the angle is outside
other angles and if is then add to some angles list
5b- if it's the first add it to the list
6- goto 2
That algorithm should be quite fast. Some steps can be optimized, but first let me know if you understood this part
-
July 8th, 2005, 12:35 PM
#9
Re: Looking for ideas for "field of view" (line of sight) algorithm
i got it now, thx lycan
about diagonal gaps:
i think that lican's suggestion covers it. it just has to be adjusted. i had this in mind:
you should check the minimum angle available at that radius and ignore all gaps that have that angle from that radius. this is only the case when you dont use rectangle tiles (cells) but use points instead of them. i.e for radius 1 (in my example) that angle would be 45 degrees:
Code:
(x,y) (x+1,y)
o--------------o
| /
| /
| /
| /
| ß /
| /
|/
o
(x,y+1)
for radius 2 it would be 30 deg:
Code:
(x,y) (x+1,y)
o--------------o
| /
| /
| /
| /
| /
| /
| /
(x,y+1)o /
| /
| /
| /
| ß /
| /
| /
|/
o
(x,y+2)
and so on
it might get tricky with small tiles and large radius, but hey, even the human eye has to take some time to focus something at long distance and it too cant see indefinetley:)
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|
Reply With Quote