Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #7164 > unrolled thread

Visibility algorithm

Back to article view | Back to comp.programming

Contents

  Visibility algorithm malcolm.mclean5@btinternet.com - 2016-12-15 16:12 -0800
    Re: Visibility algorithm fir <profesor.fir@gmail.com> - 2016-12-16 11:00 -0800
      Re: Visibility algorithm malcolm.mclean5@btinternet.com - 2016-12-16 11:06 -0800
        Re: Visibility algorithm fir <profesor.fir@gmail.com> - 2016-12-16 11:22 -0800
          Re: Visibility algorithm fir <profesor.fir@gmail.com> - 2016-12-16 11:46 -0800
            Re: Visibility algorithm fir <profesor.fir@gmail.com> - 2016-12-16 11:56 -0800
              Re: Visibility algorithm fir <profesor.fir@gmail.com> - 2016-12-16 12:01 -0800
                Re: Visibility algorithm fir <profesor.fir@gmail.com> - 2016-12-16 12:07 -0800
                  Re: Visibility algorithm Chad <cdalten@gmail.com> - 2016-12-16 15:05 -0800
                    Re: Visibility algorithm fir <profesor.fir@gmail.com> - 2016-12-17 05:39 -0800

#7164 — Visibility algorithm

We have a map which (for now at least) consists entirely of floor
squares and filled or wall squares. The observer can be considered 
to be at the centre of one cell.

Now we can test each square for visibility by going round in
increasing squares and building an "occluded list". So the occluded 
list starts off empty. We then take the eight neighbouring cells, 
going round anticlockwise. If the cell is floor, it is marked as 
visible. If it is filled, it is also marked as visible, but we
calculate the angle it subtends, and add to the occluded list.
Note that the occluded list will tend to have overlapping entries,
which we must merge.

On pass two, we do the same thing, except a cell is not marked
as visible if the angle it subtends is wholly contained in the
occluded list.

We terminate when the occluded list is the entire 360 degrees
occluded.

The question is how to code this efficiently and elegantly. 
The angles can be pre-calculated and are symmetrical, for example,
and one large regions are occluded, the algorithm can quickly
skip them over.

  

[toc] | [next] | [standalone]

#7166

W dniu piątek, 16 grudnia 2016 01:12:55 UTC+1 użytkownik malcolm...@btinternet.com napisał:
> We have a map which (for now at least) consists entirely of floor
> squares and filled or wall squares. The observer can be considered 
> to be at the centre of one cell.
> 
> Now we can test each square for visibility by going round in
> increasing squares and building an "occluded list". So the occluded 
> list starts off empty. We then take the eight neighbouring cells, 
> going round anticlockwise. If the cell is floor, it is marked as 
> visible. If it is filled, it is also marked as visible, but we
> calculate the angle it subtends, and add to the occluded list.
> Note that the occluded list will tend to have overlapping entries,
> which we must merge.
> 
> On pass two, we do the same thing, except a cell is not marked
> as visible if the angle it subtends is wholly contained in the
> occluded list.
> 
> We terminate when the occluded list is the entire 360 degrees
> occluded.
> 
> The question is how to code this efficiently and elegantly. 
> The angles can be pre-calculated and are symmetrical, for example,
> and one large regions are occluded, the algorithm can quickly
> skip them over.

are you sure it is worth doing? maybe it is worth but 
im not sure, You probably has some range in vision in 
tiles (how many it is?) when i was writing something like that for rogualike vision was short (dont remember but r<15 tiles  or so, and i could do it more simple, sorta like bressenham based - i dont remember - no any angle calculations needed) - esp where in game you wanted czeck vuision not between all bots and all vicinity tiles but in
pairs bots-bots or bots-items (dont remember the details)

besides that you can really do it it shouldnt be hard,
indeed angles for  small rings can be precalculated/arrays stored, worse thing for bigger rings as you will drown in
hundreds of angles so maybe maximum vision radius should be assumed  - go for rings store angles in rings - how update list and merge? - should  be easy strightforward  but you will need a lot of reallocking to keep it sorted, or you may go not sorted but will be need more costly lookup 
- or do a mix sort after whole ring only or what

all in all it does not seem to be best efficient method for me 

[toc] | [prev] | [next] | [standalone]

#7167

On Friday, December 16, 2016 at 7:00:31 PM UTC, fir wrote:
>
> are you sure it is worth doing? maybe it is worth but 
> im not sure,
>
The alternative is just to declare every visited "room" visible.
>
> You probably has some range in vision in tiles (how many it is?) 
> when i was writing something like that for rogualike vision was 
> short (dont remember but r<15 tiles  or so, and i could do it 
> more simple, sorta like bressenham based - i dont remember - 
> no any angle calculations needed) - esp where in game you wanted 
> czeck vuision not between all bots and all vicinity tiles but in
> pairs bots-bots or bots-items (dont remember the details)
> 
The visible portion of the map isn't very large. But you want to
be able to scale up for AI bots.

[toc] | [prev] | [next] | [standalone]

#7168

W dniu piątek, 16 grudnia 2016 20:06:34 UTC+1 użytkownik malcolm...@btinternet.com napisał:
> On Friday, December 16, 2016 at 7:00:31 PM UTC, fir wrote:
> >
> > are you sure it is worth doing? maybe it is worth but 
> > im not sure,
> >
> The alternative is just to declare every visited "room" visible.
> >
> > You probably has some range in vision in tiles (how many it is?) 
> > when i was writing something like that for rogualike vision was 
> > short (dont remember but r<15 tiles  or so, and i could do it 
> > more simple, sorta like bressenham based - i dont remember - 
> > no any angle calculations needed) - esp where in game you wanted 
> > czeck vuision not between all bots and all vicinity tiles but in
> > pairs bots-bots or bots-items (dont remember the details)
> > 
> The visible portion of the map isn't very large. But you want to
> be able to scale up for AI bots.

so what you wanna do coz i dont understand ?

if you want me to thinking of answer tell maybe how you plan to do it , i probably would do it at first draft as

for each ring form 1 to n
{
  for each cell in ring
  { 
    if(cell in angles) continue;
    if(cell==wall) add_angle(angle[cell][ring]);
  }
  sort and merge angles //strightforward i think
}
 
the details (of lookup, inserting and sort/merge)  should not be so hard - i would do it on normal arrays if i would chose such method at all

[toc] | [prev] | [next] | [standalone]

#7169

W dniu piątek, 16 grudnia 2016 20:22:17 UTC+1 użytkownik fir napisał:
> W dniu piątek, 16 grudnia 2016 20:06:34 UTC+1 użytkownik malcolm...@btinternet.com napisał:
> > On Friday, December 16, 2016 at 7:00:31 PM UTC, fir wrote:
> > >
> > > are you sure it is worth doing? maybe it is worth but 
> > > im not sure,
> > >
> > The alternative is just to declare every visited "room" visible.
> > >
> > > You probably has some range in vision in tiles (how many it is?) 
> > > when i was writing something like that for rogualike vision was 
> > > short (dont remember but r<15 tiles  or so, and i could do it 
> > > more simple, sorta like bressenham based - i dont remember - 
> > > no any angle calculations needed) - esp where in game you wanted 
> > > czeck vuision not between all bots and all vicinity tiles but in
> > > pairs bots-bots or bots-items (dont remember the details)
> > > 
> > The visible portion of the map isn't very large. But you want to
> > be able to scale up for AI bots.
> 
> so what you wanna do coz i dont understand ?
> 
> if you want me to thinking of answer tell maybe how you plan to do it , i probably would do it at first draft as
> 
> for each ring form 1 to n
> {
>   for each cell in ring
>   { 
>     if(cell in angles) continue;
>     if(cell==wall) add_angle(angle[cell][ring]);
>   }
>   sort and merge angles //strightforward i think
> }
>  
> the details (of lookup, inserting and sort/merge)  should not be so hard - i would do it on normal arrays if i would chose such method at all

i think probably there is a way to do it better:
those precalculated angle[cell][ring] is just a array of angle[x][y] on the other side, you could just use this
or better skiop this at all - if given cell is visible 
it depends on some vicinity cells betwean this cell and vicinity cells on a way of radius, (so very little need to be checked) - those cells may be denoted as visible, non visible or nontested, some only need a way of wandering on all this and just set the satatus based on the neighbours
- it should be faster and it resembles midpoint algorithm in some way (midopint test for distance (if x*x+y*y >R*R) here one will need some test for "radiality" - dont know the detaild i would need pen and paper maybe)

[toc] | [prev] | [next] | [standalone]

#7170

W dniu piątek, 16 grudnia 2016 20:46:20 UTC+1 użytkownik fir napisał:
> W dniu piątek, 16 grudnia 2016 20:22:17 UTC+1 użytkownik fir napisał:
> > W dniu piątek, 16 grudnia 2016 20:06:34 UTC+1 użytkownik malcolm...@btinternet.com napisał:
> > > On Friday, December 16, 2016 at 7:00:31 PM UTC, fir wrote:
> > > >
> > > > are you sure it is worth doing? maybe it is worth but 
> > > > im not sure,
> > > >
> > > The alternative is just to declare every visited "room" visible.
> > > >
> > > > You probably has some range in vision in tiles (how many it is?) 
> > > > when i was writing something like that for rogualike vision was 
> > > > short (dont remember but r<15 tiles  or so, and i could do it 
> > > > more simple, sorta like bressenham based - i dont remember - 
> > > > no any angle calculations needed) - esp where in game you wanted 
> > > > czeck vuision not between all bots and all vicinity tiles but in
> > > > pairs bots-bots or bots-items (dont remember the details)
> > > > 
> > > The visible portion of the map isn't very large. But you want to
> > > be able to scale up for AI bots.
> > 
> > so what you wanna do coz i dont understand ?
> > 
> > if you want me to thinking of answer tell maybe how you plan to do it , i probably would do it at first draft as
> > 
> > for each ring form 1 to n
> > {
> >   for each cell in ring
> >   { 
> >     if(cell in angles) continue;
> >     if(cell==wall) add_angle(angle[cell][ring]);
> >   }
> >   sort and merge angles //strightforward i think
> > }
> >  
> > the details (of lookup, inserting and sort/merge)  should not be so hard - i would do it on normal arrays if i would chose such method at all
> 
> i think probably there is a way to do it better:
> those precalculated angle[cell][ring] is just a array of angle[x][y] on the other side, you could just use this
> or better skiop this at all - if given cell is visible 
> it depends on some vicinity cells betwean this cell and vicinity cells on a way of radius, (so very little need to be checked) - those cells may be denoted as visible, non visible or nontested, some only need a way of wandering on all this and just set the satatus based on the neighbours
> - it should be faster and it resembles midpoint algorithm in some way (midopint test for distance (if x*x+y*y >R*R) here one will need some test for "radiality" - dont know the detaild i would need pen and paper maybe)

this should be a candidate on recursive method, 

start from central visible point 
 recurse on all potentially visible (it is not wall) neighbours - point is visible if at least one of his 
radial neighbours is visible [what are exactly this radial neighbours im not sure now, but maybe simple chose of 3 
neighbours would work ok] - repeat until recursion ends

[toc] | [prev] | [next] | [standalone]

#7171

W dniu piątek, 16 grudnia 2016 20:56:04 UTC+1 użytkownik fir napisał:
> W dniu piątek, 16 grudnia 2016 20:46:20 UTC+1 użytkownik fir napisał:
> > W dniu piątek, 16 grudnia 2016 20:22:17 UTC+1 użytkownik fir napisał:
> > > W dniu piątek, 16 grudnia 2016 20:06:34 UTC+1 użytkownik malcolm...@btinternet.com napisał:
> > > > On Friday, December 16, 2016 at 7:00:31 PM UTC, fir wrote:
> > > > >
> > > > > are you sure it is worth doing? maybe it is worth but 
> > > > > im not sure,
> > > > >
> > > > The alternative is just to declare every visited "room" visible.
> > > > >
> > > > > You probably has some range in vision in tiles (how many it is?) 
> > > > > when i was writing something like that for rogualike vision was 
> > > > > short (dont remember but r<15 tiles  or so, and i could do it 
> > > > > more simple, sorta like bressenham based - i dont remember - 
> > > > > no any angle calculations needed) - esp where in game you wanted 
> > > > > czeck vuision not between all bots and all vicinity tiles but in
> > > > > pairs bots-bots or bots-items (dont remember the details)
> > > > > 
> > > > The visible portion of the map isn't very large. But you want to
> > > > be able to scale up for AI bots.
> > > 
> > > so what you wanna do coz i dont understand ?
> > > 
> > > if you want me to thinking of answer tell maybe how you plan to do it , i probably would do it at first draft as
> > > 
> > > for each ring form 1 to n
> > > {
> > >   for each cell in ring
> > >   { 
> > >     if(cell in angles) continue;
> > >     if(cell==wall) add_angle(angle[cell][ring]);
> > >   }
> > >   sort and merge angles //strightforward i think
> > > }
> > >  
> > > the details (of lookup, inserting and sort/merge)  should not be so hard - i would do it on normal arrays if i would chose such method at all
> > 
> > i think probably there is a way to do it better:
> > those precalculated angle[cell][ring] is just a array of angle[x][y] on the other side, you could just use this
> > or better skiop this at all - if given cell is visible 
> > it depends on some vicinity cells betwean this cell and vicinity cells on a way of radius, (so very little need to be checked) - those cells may be denoted as visible, non visible or nontested, some only need a way of wandering on all this and just set the satatus based on the neighbours
> > - it should be faster and it resembles midpoint algorithm in some way (midopint test for distance (if x*x+y*y >R*R) here one will need some test for "radiality" - dont know the detaild i would need pen and paper maybe)
> 
> this should be a candidate on recursive method, 
> 
> start from central visible point 
>  recurse on all potentially visible (it is not wall) neighbours - point is visible if at least one of his 
> radial neighbours is visible [what are exactly this radial neighbours im not sure now, but maybe simple chose of 3 
> neighbours would work ok]

ye this could work as each given pixel shows two walls and one corner to the radius/origin point (except those pixels that touch axes, thiose only show one wall) - this meand which 3 neighbours need to check for each (if im not wrong), so put it recursively and it should fast fill all visibles /woah) 

> - repeat until recursion ends

[toc] | [prev] | [next] | [standalone]

#7172

W dniu piątek, 16 grudnia 2016 21:01:23 UTC+1 użytkownik fir napisał:
> W dniu piątek, 16 grudnia 2016 20:56:04 UTC+1 użytkownik fir napisał:
> > W dniu piątek, 16 grudnia 2016 20:46:20 UTC+1 użytkownik fir napisał:
> > > W dniu piątek, 16 grudnia 2016 20:22:17 UTC+1 użytkownik fir napisał:
> > > > W dniu piątek, 16 grudnia 2016 20:06:34 UTC+1 użytkownik malcolm...@btinternet.com napisał:
> > > > > On Friday, December 16, 2016 at 7:00:31 PM UTC, fir wrote:
> > > > > >
> > > > > > are you sure it is worth doing? maybe it is worth but 
> > > > > > im not sure,
> > > > > >
> > > > > The alternative is just to declare every visited "room" visible.
> > > > > >
> > > > > > You probably has some range in vision in tiles (how many it is?) 
> > > > > > when i was writing something like that for rogualike vision was 
> > > > > > short (dont remember but r<15 tiles  or so, and i could do it 
> > > > > > more simple, sorta like bressenham based - i dont remember - 
> > > > > > no any angle calculations needed) - esp where in game you wanted 
> > > > > > czeck vuision not between all bots and all vicinity tiles but in
> > > > > > pairs bots-bots or bots-items (dont remember the details)
> > > > > > 
> > > > > The visible portion of the map isn't very large. But you want to
> > > > > be able to scale up for AI bots.
> > > > 
> > > > so what you wanna do coz i dont understand ?
> > > > 
> > > > if you want me to thinking of answer tell maybe how you plan to do it , i probably would do it at first draft as
> > > > 
> > > > for each ring form 1 to n
> > > > {
> > > >   for each cell in ring
> > > >   { 
> > > >     if(cell in angles) continue;
> > > >     if(cell==wall) add_angle(angle[cell][ring]);
> > > >   }
> > > >   sort and merge angles //strightforward i think
> > > > }
> > > >  
> > > > the details (of lookup, inserting and sort/merge)  should not be so hard - i would do it on normal arrays if i would chose such method at all
> > > 
> > > i think probably there is a way to do it better:
> > > those precalculated angle[cell][ring] is just a array of angle[x][y] on the other side, you could just use this
> > > or better skiop this at all - if given cell is visible 
> > > it depends on some vicinity cells betwean this cell and vicinity cells on a way of radius, (so very little need to be checked) - those cells may be denoted as visible, non visible or nontested, some only need a way of wandering on all this and just set the satatus based on the neighbours
> > > - it should be faster and it resembles midpoint algorithm in some way (midopint test for distance (if x*x+y*y >R*R) here one will need some test for "radiality" - dont know the detaild i would need pen and paper maybe)
> > 
> > this should be a candidate on recursive method, 
> > 
> > start from central visible point 
> >  recurse on all potentially visible (it is not wall) neighbours - point is visible if at least one of his 
> > radial neighbours is visible [what are exactly this radial neighbours im not sure now, but maybe simple chose of 3 
> > neighbours would work ok]
> 
> ye this could work as each given pixel shows two walls and one corner to the radius/origin point (except those pixels that touch axes, thiose only show one wall) - this meand which 3 neighbours need to check for each (if im not wrong), so put it recursively and it should fast fill all visibles /woah) 
> 
> > - repeat until recursion ends

well, no - i may be wrong- as radial neighbours visible may not mean the more far one is visible (as neighbour is not fully visible) - so it should be repaired maybe

afair i was not needed exact accuracy so maybe this will fit to cases where not total accureacy is needed, it could be hard to say without realy coding and prototyping it

[toc] | [prev] | [next] | [standalone]

#7173

fir, the person who doesn't have what it takes to work as a programmer for a living. Go back to your general labor job and labor some more.

[toc] | [prev] | [next] | [standalone]

#7178

W dniu sobota, 17 grudnia 2016 00:05:56 UTC+1 użytkownik Chad napisał:
> fir, the person who doesn't have what it takes to work as a programmer for a living. Go back to your general labor job and labor some more.

i not take advices from those with "iq below 70"

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web