Evil Science A whole load of stuff

24Dec/135

Field of Vision using recursive shadow casting: C# .Net 3.5 implementation

A working field-of-view ?(FOV) algorithm is one of the essential parts in any roguelike, it is used to calculate which mapcells, within a given radius, that can be seen by seen by the player. This article describes a C# implementation of such an algorithm, known as recursive shadow casting which is described in more detail in the article ?FOV using recursive shadowcasting - improved.

Shadow Casting

Shadowcasting divides the FOV calculations into eight octants and visits the ?mapcells of each ?row by row or column by column, starting with the nearest row or column and working it's way outward.

  ------>  6 row 6 last
   ----->  5 .
    ---->  4 .
     --->  3 .
      -->  2 row 2 second
       ->  1 row 1 is scanned first
        @  @ this is the starting point

When a scan comes across a cell that blocks the players line of sight it calculates which other cells in rows/columns farther away that isn't visible because of the blocker. Those cells are "in shadow", hence the term shadowcasting.

  -...---  - = visible cells
   -..---  # = blocking cell
    -#---  . = cells in blocker's shadow
     ----
      ---
       --
        @

The above text is taken from this article, from the website RogueBasin. I have shamelessly lifted this text, as I feel it is a very clear description of how shadowcasting works, and I can't improve upon it.

The Application

Below are several pictures of the application which demonstrate that algorithm.?The lighter squares represent the cells visible to the player, and the darker ones are those which the player cannot see.?The maze displayed in the map has been generated using another algorithm (which I'll post soon) and is loaded when the application starts up.

fov2 fov3

The keys q,w,e,a,d,z,x and c control the player move the player. W is up, S down, d right, A left right etc

Source Code

The source code can be downloaded?here.?And to run it, you'll need Microsoft Visual Studio which you can find here.

Github: the code for the class FOVRecurse.

What's Going On?

The class FOVRecurse.cs?contains the FOV algorithm, and the?methods are GetVisibleCells and ScanOctant are where the magic happens.

When the player moves, the method GetVisibleCells?is called which in turn calls the method ScanOctant for each of the?8 areas surrounding the player and?all the cells that the player can see are stored in a generic list. Upon completion of this scan the the event?playerMoved is fired, which causes the map to be redrawn in the form event?pictureBox1_Paint.

There really isn't that much to say about it as the code speaks for itself, but if you're stuck with anything please add a comment and I'll get back to you.

Acknowledgements

This post takes text from the RogueBasin articles:

  1. FOV using recursive shadowcasting - improved.
  2. FOV using recursive shadowcasting

I have used the take from the above as I feel these are the best explanations of how the shadow casting technique works, and I can't really improve upon them.

Filed under: C#, Roguelike Leave a comment
Comments (5) Trackbacks (0)
  1. Hey!
    Very nice article and good implementation. I tested it a little and found out that it still need some improvement. For example in one room I created an ‘L’ shape and everything behind that wall (on playerhight) was visible. Any idea on how to fix that?

    Best regards,

    Max

  2. Hi Max

    You have just discovered an “artifact” of the algorithm, a side effect of it how calculates visible cells. I’ve been tinkering with the algorithm, to see if I can eliminate it, but with no success, however, I’m not the originator of this algorithm and am not familiar with it’s finer details. Perhaps another step after FOV is calculated, to refine the information produced might solve this, but I’m not sure.

    You might be in interested in this article:

    http://www.robotacid.com/flash/red_rogue/shadow_casting/fov.pdf

    which discusses the pros and cons of different implementations of field of vision algorithms. it might give you some ideas.

    Cheers

  3. Hi Max

    It looks like you’ve found a bug – thanks for spotting it! I’ve fixed it and added a few more things to the code for efficiency. I’ve updated the github source and VS download to reflect these changes, please take a look and let me know what you think.

    Cheers

    The Evil Scientist

  4. Thank you very much, after a bit of fiddling around (changing Points and Sizes to Vector 2’s) i have the algorithm running nicely inside unity. Thank you very much for pointing me in the right direction!

  5. Thanks for your interest!


Leave a comment

No trackbacks yet.