Spaghetti-Code LOS Graph Technique

I've worked out an algorithm for generating an optimized graph for line-of-sight (LOS) computation. The goals I set for myself are as follows:

  • Each visible map cell should be examined exactly once.
  • No unseeable map cell should ever be visited.
  • The code must be strictly graph-based (a state machine); the only runtime calculations permitted are coordinate translations to the viewer's position.
  • The graph should be nonredundant; that is, it should contain the least number of nodes possible to correctly compute the field of view for every possible arrangement of blocking and non-blocking cells within a specified maximum radius.

    The only item which I think I have not yet accomplished is the nonredundancy condition. I believe I can eliminate a few more redundant paths, given certain carefully chosen optimization decisions during generation.

    I've made available code for both radius 6 LOS, and a much shorter version for radius 3 LOS, just to get the idea. (The radius 3 code has approximately 200 graph nodes, while the radius 6 code has approximately 4000.)

    Some questions and answers:

    How did you make this code?
    The spaghetti code was generated by a program I wrote in Smalltalk. I will write up an explanation of the algorithm later. Then I heaped the steaming, writhing spaghetti into a minimal, hand-crafted bowl to exhibit its loathsome glory.

    What should I look for?
    The demo code should display a reasonably sane field of view for a random distribution of blocking cells. The '~' characters represent the unseen, while a '+' indicates a visible cell which has been visited twice. (You should never see a '+'!)

    Your LOS looks like crap. Shouldn't diagonally adjacent blockers obscure your vision more?
    For this demo, I decided to use every line which passes from the center of the viewer's cell, through each possible corner, and do not consider them blocked by either of the tangent cells at that point. The algorithm, once these lines are generated, makes relatively few assumptions about them, so it could be applied to a number of other possible line sets. But it was quite enough work ironing out the problems in the algorithm without the extra complexity of a more aesthetically pleasing set of sight lines. (And I'm not entirely sure it would be possible to ensure "visible corners" worked, but further sight along those lines was blocked, without a substantial reworking of the algorithm itself.)

    What do the labels mean?
    A label of the form L12P_3x3B-4x3L11F5 refers to a node looking at the point (-3,3) on scan line 12, for which the last relevant blocking cell was the point (-4,3) on scan line 11, with the first blocking cell on scanline 1 having been (5,0).

    Why are the nodes all out of order?
    This is caused by the hashing order of the dictionary of known nodes used during generation. It would be a simple matter to put them in an ordered sequence, but I decided I like how the arbitrary order accentuates the spaghetti qualities of the code.

    Isn't 'goto' evil?
    While 'goto' should be used at most sparingly by humans, as you can see, computers can profitably employ 'goto's by the thousands (over 8000 in LOSSpaghetti6.c). But woe be on the mere human eye that gazes for too long into that swirling space of formless chaos.