Re: Fast LOS algorithm

Kenneth 'Bessarion' Boyd wrote:

Spiral-path fov is a specific way of guaranteeing that squares with Manhattan
distance i.e. Lesbesgue-1 distance i.e. L1 distance n [sum of absolute value of
coordinates] are all dequed (with light passed through to squares at L1 distance
n+1, squares with no prior light enqued, etc.) before any squares with L1
distance n+1 are dequed.

It actually gets a lot less finicky to code in 2-d (eg, not caring
if the order is actually a spiral) if you use two queues (one for
each "active" manhattan distance), and just don't go to the next
until all the ones at the current distance are done, doesn't it?
I mean, it "wastes" space, but it's easier to get correct.

I kept getting tangled when I wanted to move it to 3-d because I
couldn't visualize a traversal order that would satisfy the invariant
the way a spiral does for 2-d. But you're right, here: you actually
don't need to do that. Just maintain separate queues for the "current"
and "next" manhattan distance, and that constraint goes away.


For the N-d case:
* There are 2n squares with L1 distance 1, indexed by the basis vectors and
their additive inverses.
* Light bounds are represented by n-1 dimensional polygons (projections of the
square faces) whose points have angle coordinates.

Okay, I can see that, sort of.... light passes into a cube above and
northeast of the origin, through its bottom, south, and west faces,
so you get a sort of squashed hexagon as your unimpeded light passage,
degenerating to squares if the cubes are along an axis.

But your impeded light passage (ie, where the cube didn't get all the
light it could have gotten) has a more complex shape because it can be
cut by the shadow of another cube. You have to do some more complex
geometry than just keeping track of minimum and maximum lit angles to
find the shape that's the union of the light that got passed in,
before you can pass it out. Not "hard" geometry; just more complex.

Bear




.

Relevant Pages

  • Re: Fast LOS algorithm
    ... coordinates] are all dequed (with light passed through to squares at L1 distance ... distance n+1 are dequed. ... I don't see a material space wastage from two queues instead of one, ... excuse to store the manhattan distance with the square. ...
    (rec.games.roguelike.development)
  • Re: Fast simulated monster FOV
    ... If you have 100 monsters in a level, ... interesting before checking its distance, ... a finely grained zoning system may be the sort of idea you are ... If a monster can see 10 squares, ...
    (rec.games.roguelike.development)
  • Re: distance
    ... depends on the distance to the locations in dataset two. ... maxdis to each location in 1. ... avoid the terrible figure of 50000 times 50000 or more pairings of points. ... and then compare only pairs of points that lie in squares ...
    (comp.soft-sys.matlab)
  • Re: distance between points from 2d normal distribution
    ... > The distance variable I desire is the square root of the appropriate ... > how I could use this pdf to restore a function expressing frequency ... The sqrt of the sum of squares will be chi ... preferably the same, cat. ...
    (comp.soft-sys.matlab)
  • Re: Radius of largest n+1 balls in n-dimensional unit cube?
    ... sqrtis maximal distance between two corners of the cube, ... Then the distance from the center of the ball in that corner to the ... If I want to put N+1 balls (all with ... the same radius R), within the unit hypercube such that: ...
    (sci.math)