http://roguebasin.roguelikedevelopment.org/api.php?action=feedcontributions&user=Rico&feedformat=atomRogueBasin - User contributions [en]2019-10-19T04:09:20ZUser contributionsMediaWiki 1.19.9http://roguebasin.roguelikedevelopment.org/index.php?title=RubyRuby2008-08-29T23:02:35Z<p>Rico: </p>
<hr />
<div>=Ruby=<br />
<br />
Ruby is still coming of age in the roguelike field -- there are no roguelike libraries and only a few finished games in the language. That said, Ruby is very powerful, combining an elegant syntax with an incredibly dynamic object system. It's also incredibly fun to code with. But beware! Many dangers lurk within beneath its alluring facade!<br />
<br />
==Reasons not to use Ruby==<br />
<br />
* <b>Speed:</b> Ruby 1.8 measures far below Python in terms of performance. This is mostly due to Python having a bytecode compiler. On the other hand, the upcoming Ruby 1.9 has JIT compilation and <i>out-performs</i> Python, but it's not out yet.<br />
<br />
* <b>Documentation:</b> The language is not well documented in relation to other languages, but this is getting better all the time. There are quite a few gotchas (like using <tt>setter=</tt> methods inside of classes).<br />
<br />
* <b>Libraries:</b> Ruby has no roguelike library, nor are there many (if any) roguelike sources to borrow from. Built-in curses support has no colors under Windows and is generally a mess.<br />
<br />
==But!==<br />
<br />
The first two of these issues will be fixed by the time your roguelike is finished :) <br />
<br />
As people begin to use Ruby for RL development, code will surface. There are already a few algorithms implemented and put up at RogueBasin.<br />
<br />
Cross-platform, true curses support can be achieved using <b>ncurses</b> (see below)<br />
<br />
==Okay, I'm going to use Ruby. What now?==<br />
<br />
You'll need to install a copy of Ruby 1.8 from http://www.ruby-lang.org/ (I recommend the one-click installer) or your package manager (<tt>apt-get install ruby</tt>). Then acquaint yourself with the Ruby tools: <tt>irb</tt>, <tt>ri</tt> and <tt>rdoc</tt>. A good version of the standard library API can be found at http://www.noobkit.com/<br />
<br />
===ncurses-ruby===<br />
<br />
It is possible to use the built-in curses on linux and other platforms, and interface with the Win32 console via the Win32 API for Windows support. However, this is a relative pain. Instead, install the non-standard ncurses-ruby package!<br />
<br />
<b>On Windows:</b><br />
* Download <tt>ncurses-ruby1.8-0.9.1-i386-mswin32.zip</tt> from http://ncurses-ruby.berlios.de/<br />
* Copy <tt>lib/ncurses.rb</tt> and <tt>ncurses.so</tt> into your code directory (don't copy the <tt>lib</tt> directory itself!)<br />
* In your script, <tt>require 'ncurses'</tt><br />
<br />
That's it! You can now use ncurses (see the examples or the C API, which is very similar). At some point an example roguelike using ncurses will be uploaded.<br />
<br />
===Field of View===<br />
<br />
A few [[Field of Vision|field of view]] algorithms have been implemented in Ruby<br />
<br />
* [[Ruby shadowcasting implementation]]<br />
* [[Ruby precise permissive FOV implementation]]<br />
<br />
===Bitfields===<br />
<br />
For certain intensive operations it may be prudent to use a [[Ruby bitfield|Bitfield]]. One example is storing which map tiles have been visited by your player (and will be drawn).<br />
<br />
Using this library, it is easy to add methods to your Map class for FOV calculation:<br />
<br />
<pre><br />
def initialize(map)<br />
....<br />
@visited = BitField.new(@width * @height) # visited by player (drawn in grey)<br />
@lit = BitField.new(@width * @height) # seen by player this round (drawn in white)<br />
end<br />
<br />
# Return true if the square is lit (seen by player)<br />
def lit?(x, y)<br />
@lit[y * @width + x] == 1<br />
end<br />
<br />
# Returns true if square has been visited by player<br />
def visited?(x, y)<br />
@visited[y * @width + x] == 1<br />
end<br />
<br />
# Set lit status for square. Also visits the square<br />
def light(x, y)<br />
idx = y * @width + x<br />
@lit[idx] = @visited[idx] = 1<br />
end<br />
<br />
# Unlight everything (call after doing FOV calc + map draw)<br />
def reset_light<br />
@lit.clear<br />
end<br />
</pre></div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=Ruby_bitfieldRuby bitfield2008-08-29T23:01:48Z<p>Rico: </p>
<hr />
<div>This code describes a Ruby bitfield, implemented using arrays (a large string might be faster, try it and see). The code is also available at http://snippets.dzone.com/posts/show/4234 but you have to remove the line numbers (a snippet site that doesn't actually let you copy the code, who would have thought?) This version adds a <tt>clear</tt> method.<br />
<br />
<pre><br />
# NAME: BitField<br />
# AUTHOR: Peter Cooper<br />
# LICENSE: MIT ( http://www.opensource.org/licenses/mit-license.php )<br />
# COPYRIGHT: (c) 2007 Peter Cooper (http://www.petercooper.co.uk/)<br />
# VERSION: v4<br />
# HISTORY: v4 (fixed bug where setting 0 bits to 0 caused a set to 1)<br />
# v3 (supports dynamic bitwidths for array elements.. now doing 32 bit widths default)<br />
# v2 (now uses 1 << y, rather than 2 ** y .. it's 21.8 times faster!)<br />
# v1 (first release)<br />
#<br />
# DESCRIPTION: Basic, pure Ruby bit field. Pretty fast (for what it is) and memory efficient.<br />
# I've written a pretty intensive test suite for it and it passes great. <br />
# Works well for Bloom filters (the reason I wrote it).<br />
#<br />
# Create a bit field 1000 bits wide<br />
# bf = Bitfield.new(1000)<br />
#<br />
# Setting and reading bits<br />
# bf[100] = 1<br />
# bf[100] .. => 1<br />
# bf[100] = 0<br />
#<br />
# More<br />
# bf.to_s = "10101000101010101" (example)<br />
# bf.total_set .. => 10 (example - 10 bits are set to "1")<br />
<br />
class BitField<br />
attr_reader :size, :field<br />
include Enumerable<br />
<br />
ELEMENT_WIDTH = 32<br />
<br />
def initialize(size)<br />
@size = size<br />
@field = Array.new(((size - 1) / ELEMENT_WIDTH) + 1, 0)<br />
end<br />
<br />
# Set a bit (1/0)<br />
def []=(position, value)<br />
if value == 1<br />
@field[position / ELEMENT_WIDTH] |= 1 << (position % ELEMENT_WIDTH)<br />
elsif (@field[position / ELEMENT_WIDTH]) & (1 << (position % ELEMENT_WIDTH)) != 0<br />
@field[position / ELEMENT_WIDTH] ^= 1 << (position % ELEMENT_WIDTH)<br />
end<br />
end<br />
<br />
# Read a bit (1/0)<br />
def [](position)<br />
@field[position / ELEMENT_WIDTH] & 1 << (position % ELEMENT_WIDTH) > 0 ? 1 : 0<br />
end<br />
<br />
# Iterate over each bit<br />
def each(&block)<br />
@size.times { |position| yield self[position] }<br />
end<br />
<br />
# Returns the field as a string like "0101010100111100," etc.<br />
def to_s<br />
inject("") { |a, b| a + b.to_s }<br />
end<br />
<br />
# Clears the bitfield. More efficient than using Bitfield#each<br />
def clear<br />
@field.each_index { |i| @field[i] = 0 }<br />
end<br />
<br />
# Returns the total number of bits that are set<br />
# (The technique used here is about 6 times faster than using each or inject direct on the bitfield)<br />
def total_set<br />
@field.inject(0) { |a, byte| a += byte & 1 and byte >>= 1 until byte == 0; a }<br />
end<br />
end<br />
</pre></div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=RubyRuby2008-08-29T23:00:14Z<p>Rico: </p>
<hr />
<div>=Ruby=<br />
<br />
Ruby is still coming of age in the roguelike field -- there are no roguelike libraries and only a few finished games in the language. That said, Ruby is very powerful, combining an elegant syntax with an incredibly dynamic object system. It's also incredibly fun to code with. But beware! Many dangers lurk within beneath its alluring facade!<br />
<br />
==Reasons not to use Ruby==<br />
<br />
* <b>Speed:</b> Ruby 1.8 measures far below Python in terms of performance. This is mostly due to Python having a bytecode compiler. On the other hand, the upcoming Ruby 1.9 has JIT compilation and <i>out-performs</i> Python, but it's not out yet.<br />
<br />
* <b>Documentation:</b> The language is not well documented in relation to other languages, but this is getting better all the time. There are quite a few gotchas (like using <tt>setter=</tt> methods inside of classes).<br />
<br />
* <b>Libraries:</b> Ruby has no roguelike library, nor are there many (if any) roguelike sources to borrow from. Built-in curses support has no colors under Windows and is generally a mess.<br />
<br />
==But!==<br />
<br />
The first two of these issues will be fixed by the time your roguelike is finished :) <br />
<br />
As people begin to use Ruby for RL development, code will surface. There are already a few algorithms implemented and put up at RogueBasin.<br />
<br />
Cross-platform, true curses support can be achieved using <b>ncurses</b> (see below)<br />
<br />
==Okay, I'm going to use Ruby. What now?==<br />
<br />
You'll need to install a copy of Ruby 1.8 from http://www.ruby-lang.org/ (I recommend the one-click installer) or your package manager (<tt>apt-get install ruby</tt>). Then acquaint yourself with the Ruby tools: <tt>irb</tt>, <tt>ri</tt> and <tt>rdoc</tt>. A good version of the standard library API can be found at http://www.noobkit.com/<br />
<br />
===ncurses-ruby===<br />
<br />
It is possible to use the built-in curses on linux and other platforms, and interface with the Win32 console via the Win32 API for Windows support. However, this is a relative pain. Instead, install the non-standard ncurses-ruby package!<br />
<br />
<b>On Windows:</b><br />
* Download <tt>ncurses-ruby1.8-0.9.1-i386-mswin32.zip</tt> from http://ncurses-ruby.berlios.de/<br />
* Copy <tt>lib/ncurses.rb</tt> and <tt>ncurses.so</tt> into your code directory (don't copy the <tt>lib</tt> directory itself!)<br />
* In your script, <tt>require 'ncurses'</tt><br />
<br />
That's it! You can now use ncurses (see the examples or the C API, which is very similar). At some point an example roguelike using ncurses will be uploaded.<br />
<br />
===Field of View===<br />
<br />
A few [[Field of Vision|field of view]] algorithms have been implemented in Ruby<br />
<br />
* [[Ruby shadowcasting implementation]]<br />
* [[Ruby precise permissive FOV implementation]]<br />
<br />
===Bitfields===<br />
<br />
For certain intensive operations it may be prudent to use a [[Ruby bitfield|Bitfield]]. One example is storing which map tiles have been visited by your player (and will be drawn).<br />
<br />
Using this library, it is easy to add methods to your Map class for FOV calculation:<br />
<br />
<pre><br />
def initialize(map)<br />
....<br />
@visited = Bitfield.new(@width * @height) # visited by player (drawn in grey)<br />
@lit = Bitfield.new(@width * @height) # seen by player this round (drawn in white)<br />
end<br />
<br />
# Return true if the square is lit (seen by player)<br />
def lit?(x, y)<br />
@lit[y * @width + x] == 1<br />
end<br />
<br />
# Returns true if square has been visited by player<br />
def visited?(x, y)<br />
@visited[y * @width + x] == 1<br />
end<br />
<br />
# Set lit status for square. Also visits the square<br />
def light(x, y)<br />
idx = y * @width + x<br />
@lit[idx] = @visited[idx] = 1<br />
end<br />
<br />
# Unlight everything (call after doing FOV calc + map draw)<br />
def reset_light<br />
@lit.clear<br />
end<br />
</pre></div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=ArticlesArticles2008-08-29T22:28:27Z<p>Rico: /* Programming languages */</p>
<hr />
<div>This is a listing of articles, arranged by subject.<br />
<br />
Articles under "design" will help the developer make decisions about gameplay. Articles under "implementation" will help with algorithm design, and offer various methods of implementing features. Headings are arranged in a general chronological order of development. Large lists of ideas (items, spells, themes, etc.) are in bold.<br />
<br />
==Development==<br />
* [[Roguelike Dev FAQ]]<br />
* [[How to Write a Roguelike in 15 Steps]]<br />
* [[7DRL]]<br />
* [[Motivation]]<br />
* [[Open Source]]<br />
<br />
=== Fundamentals ===<br />
* [[What a roguelike is]]<br />
* [[Dungeon]]<br />
* [[Items]]<br />
* [[Monster]]<br />
* [[Character]]<br />
* [[Race]]<br />
* [[Class]]<br />
* [[Skill]]<br />
* [[Permadeath]]<br />
* [[Shops]]<br />
* [[Random generation]]<br />
<br />
===Project management===<br />
Roguelike developments are complicated projects to handle; if you have weak goals, the project will slip out of your control and its success may be compromised.<br />
* [[Rewrite]]<br />
* [[Bug Report]]<br />
* [[RFE]]<br />
<br />
===Game modification===<br />
* [[Translation]]<br />
<br />
=== Communities ===<br />
* [[rgrd]]<br />
* The [http://wiki.gamedev.net/ Game Programming Wiki]<br />
<br />
==Design==<br />
* [[Aspects of playing]]<br />
* [[Fun Factor]]<br />
* [[Power Curve]]<br />
* [[The Role of Hunger]]<br />
* [[Alternatives to Permadeath]]<br />
* [[Third dimension in an ASCII-based roguelike]]<br />
* [[Time Systems]]<br />
* [[What a RL should be]]<br />
* [[Roguelike Alphabet]]<br />
* [[Spatial Consistency]]<br />
<br />
===Setting, story, and mood===<br />
* '''[[Theme]]'''<br />
* [[Roguelike Themes]]<br />
* [[Creating a Story]]<br />
* [[Horror in Roguelike Games]]<br />
* [[Horror1|Horror in Roguelike Games, Part I : Gore]]<br />
* [[Roguelike Mood]]<br />
* [[Big List of RPG Plots]]<br />
<br />
===Roleplaying===<br />
* [[Quests in Roguelikes]]<br />
<br />
===Dungeon features, terrain===<br />
* [[Dungeon persistence]]<br />
* [[RL Terrain]]<br />
* [http://roguelikedeveloper.blogspot.com/2007/11/unangband-dungeon-generation-part-one.html Unangband Dungeon Generation]<br />
<br />
===Combat===<br />
* '''[[Monster attacks]]'''<br />
* [[Implicit Facing]]<br />
<br />
===Magic===<br />
* [[Magic]]<br />
* [[Magic systems]]<br />
* [[Spell]]<br />
* [[The Gramarye A Magic System for FUDGE]]<br />
* [http://roguelikedeveloper.blogspot.com/2008/05/unangband-magic-system-part-one.html Designing a Magic System]<br />
<br />
===Religion===<br />
* [[Religious Constraints (Rules)]]<br />
<br />
===Interface===<br />
* '''[[PreferredKeyControls]]'''<br />
* '''[[User interface features]]'''<br />
* [[Icons in Roguelikes]]<br />
* [[Roguelike Interface]]<br />
<br />
===Game ideas===<br />
Ideas for roguelikes are posted regularly on [[rgrd]], but over time are forgotten. In an attempt to preserve the more interesting ideas these pages were created:<br />
* [[Magic Tower]]<br />
* [[Modern Dungeon Exploration]]<br />
* [[Roguelike DM]] by [[Timothy Pruett]]<br />
* [[Magical Dungeon]] by Patashu<br />
* [[GalaxyRL]] by tongHoAnh<br />
* [[Time-gate roguelike]] by anchor0057<br />
* [[Murder Mystery RL]] by Shedletsky<br />
* [[World of Rogue]] by [[Gamer_2k4]]<br />
* [[Shopkeeper RL]] by Antonie<br />
* [[Fire Brigade RL]] by Antonie<br />
* [[TraderRL]] by alsagoz<br />
* [[OrcRL]] by DrGong<br />
<br />
==Implementation==<br />
* [[Language in Roguelikes]]<br />
* [[Things which are hard to code]]<br />
* [[Portability Issues]]<br />
* [[Code design basics]]<br />
<br />
=== Programming languages ===<br />
The best language for your roguelike is the one you know well (or want to learn).<br />
* [[C]]<br />
* [[C_Sharp|C#]]<br />
* [[Cpp|C++]]<br />
* [[Bcx Basic]] <br />
* [[FreePascal]]<br />
* [[Java]]<br />
* [[Python]]<br />
* [[Ruby]]<br />
<br />
=== Portability ===<br />
* [[Portability Issues]]<br />
* [[Unix]]<br />
* [[Windows]]<br />
* [[Linux]]<br />
* [[Mac]]<br />
* [[Unicode]]<br />
<br />
=== Extensibility ===<br />
* [[Roguelike engines]]<br />
* [[Info Files]]<br />
* [[Info File Variant - Compile-to-Code]]<br />
<br />
=== Map ===<br />
* [[Cellular Automata Method for Generating Random Cave-Like Levels]]<br />
* [[CreatingAForest|Creating A Forest]]<br />
* [[Dungeon builder written in Python]]<br />
* [[Data structures for the map]]<br />
* [[Simple maze]]<br />
* [[Dungeon-Building Algorithm]]<br />
* [[Irregular Shaped Rooms]]<br />
* [http://roguelikedeveloper.blogspot.com/2007/07/wilderness-generation-using-voronoi.html Wilderness generation using Vornoi diagrams]<br />
* [http://www.evilscience.co.uk/?p=53 Island and labyrinth map generating algorithm]<br />
* See also: [[:Category:WorldGeneration]]<br />
<br />
===Combat===<br />
* [[Simple Combat in the Dungeon]]<br />
* [[Thoughts on Combat Models]]<br />
<br />
===AI===<br />
* [http://www.oangband.com/dl_misc/4GAI.txt 4GAI - The "4th Generation AI" used in many Angband variants]<br />
* [[A Better Monster AI]]<br />
* [[Complex NPC Interaction]]<br />
* [http://roguelikedeveloper.blogspot.com/2007/10/unangband-monster-ai-part-one-history.html Emergent Behaviour in Unangband Monster AI]<br />
* [[Implementing interesting townsfolk AI]]<br />
* [[Need driven AI]]<br />
* [[Pathfinding]]<br />
* [[Plug-In Monster AI]]<br />
* [[Quick Pathfinding in a Dungeon]]<br />
* [[Ratio AI]]<br />
* [[Roguelike AI - Doing it the generic way]]<br />
* [[Roguelike Integlligence - Evolving State Machine AIs]]<br />
* [[Roguelike Intelligence - Displaced Actions]]<br />
* [[Roguelike Intelligence - Genetic Algorithms and Evolving State Machine AIs]]<br />
* [[Roguelike Intelligence - Intrinsic Information and State Machine AIs]]<br />
* [[Roguelike Intelligence - Stateless AIs]]<br />
* [[Tracking by Scent and Sound]]<br />
* [http://www.gameai.com/ The game AI page]<br />
<br />
===Line of sight, field of vision===<br />
* [[Line of Sight]] is used to determine when a specific destination square is visible from a source square. This can be used to determine whether a player is visible to a monster, the path an arrow takes to a particular enemy, and as a building block for a field of vision algorithm.<br />
* [[Field of Vision]] determines all squares visible from a particular source. This is useful when determining which squares to show a player, what squares are lit up by a light source, etc.<br />
<br />
===Magic===<br />
* [http://roguelikedeveloper.blogspot.com/2008/05/unangband-magic-system-part-one.html Designing a Magic System]<br />
* [[Programming Roguelike Magic]]<br />
* [[Representing Magic Skills]]<br />
<br />
===Graphics===<br />
* [[Finding graphical tiles]]<br />
<br />
===Sound===<br />
* [[Sound and Music]]<br />
<br />
===Time management===<br />
* [[An elegant time-management system for roguelikes]]<br />
* [[A priority queue based turn scheduling system]]<br />
<br />
===Useful algorithms and code===<br />
* [[Compression]]<br />
* [[Bit manipulation]]<br />
* [[Fractals]]<br />
* [[Mersenne twister]]<br />
* [[Random name generation]]<br />
* [[Random number generation]]<br />
<br />
===Java Roguelike Development Guide===<br />
A list of articles specific to Java roguelike development<br />
* [[The Choice of Java]]<br />
* [[Java Curses Implementation]]<br />
* [[Items in Java]]<br />
<br />
==Game reviews==<br />
May give some idea of what people like and don't like in other games.<br />
* [[Rank RLs you have played a lot]]<br />
* [[Personalities of different roguelikes]]<br />
* See: [[:Category:Reviews]]<br />
<br />
<br />
== Other ==<br />
* [http://www.roguetemple.com/articles/increasing-challenge-in-roguelikes/ Increasing Challenge in Roguelikes]<br />
* [http://www.roguetemple.com/articles/stat-balancing-in-roguelikes/ Stat Balancing in Roguelikes]<br />
<br />
The original Dungeondweller articles are archived at [http://web.archive.org/web/20060114055601/http://roguelikedevelopment.org/]. Please do not move them to RogueBasin without permission from the original author.<br />
<br />
There are more articles at [http://arns.freeservers.com/workshop.html]. Most of these are duplicates of articles here.<br />
<br />
[[category:main]]</div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=Ruby_precise_permissive_FOV_implementationRuby precise permissive FOV implementation2008-08-29T22:27:44Z<p>Rico: use normal min/max funcs</p>
<hr />
<div>This is an implementation of [[Precise Permissive Field of View|Precise Permissive Field of View]] algorithm. It is based on the [[Permissive Field of View in Python|Python implementation]] by Aaron MacDonald.<br />
<br />
To use the algorithm, create a Map class or somesuch and provide two methods:<br />
<br />
<tt>blocked?(x, y)</tt> returns true if the tile at (x, y) blocks view of tiles beyond it (e.g. walls)<br /><br />
<tt>light(x, y)</tt> marks (x, y) as visible to the player (e.g. lit up on screen)<br />
<br />
Then <tt>include PermissiveFieldOfView</tt> within your Map class (or call <tt>extend(PermissiveFieldOfView)</tt> on your Map instance if you want to be dynamic) and call <tt>do_fov</tt>.<br />
<br />
Compared with [[Ruby shadowcasting implementation|shadowcasting]], permissive FOV runs ever so slightly slower but is reputedly artifact-free and symmetric (if you can see something, it can see you). Unfortunately this algorithm produces a <i>square</i> FOV shape around the player. Uncommenting the lines in <tt>visit_coord</tt> will change it to a diamond, but I don't understand enough to get a circle out of it :(<br />
<br />
My Ruby is fairly novice so if anyone sees anything amiss with the code, you are more than welcome to change it.<br />
<br />
<pre><br />
module PermissiveFieldOfView<br />
# Determines which co-ordinates on a 2D grid are visible<br />
# from a particular co-ordinate.<br />
# start_x, start_y: center of view<br />
# radius: how far field of view extends<br />
def do_fov(start_x, start_y, radius)<br />
@start_x, @start_y = start_x, start_y<br />
@radius_sq = radius * radius<br />
<br />
# We always see the center<br />
light @start_x, @start_y<br />
<br />
# Restrict scan dimensions to map borders and within the radius<br />
min_extent_x = [@start_x, radius].min<br />
max_extent_x = [@width - @start_x - 1, radius].min<br />
min_extent_y = [@start_y, radius].min<br />
max_extent_y = [@height - @start_y - 1, radius].min<br />
<br />
# Check quadrants: NE, SE, SW, NW<br />
check_quadrant 1, 1, max_extent_x, max_extent_y<br />
check_quadrant 1, -1, max_extent_x, min_extent_y<br />
check_quadrant -1, -1, min_extent_x, min_extent_y<br />
check_quadrant -1, 1, min_extent_x, max_extent_y<br />
end<br />
<br />
private<br />
# Represents a line (duh)<br />
class Line < Struct.new(:xi, :yi, :xf, :yf)<br />
# Macros to make slope comparisons clearer<br />
{:below => '>', :below_or_collinear => '>=', :above => '<',<br />
:above_or_collinear => '<=', :collinear => '=='}.each do |name, fn|<br />
eval "def #{name.to_s}?(x, y) relative_slope(x, y) #{fn} 0 end"<br />
end<br />
<br />
def dx; xf - xi end<br />
def dy; yf - yi end<br />
<br />
def line_collinear?(line)<br />
collinear?(line.xi, line.yi) and collinear?(line.xf, line.yf)<br />
end<br />
<br />
def relative_slope(x, y)<br />
(dy * (xf - x)) - (dx * (yf - y))<br />
end<br />
end<br />
<br />
class ViewBump < Struct.new(:x, :y, :parent)<br />
def deep_copy<br />
ViewBump.new(x, y, parent.nil? ? nil : parent.deep_copy)<br />
end<br />
end<br />
<br />
class View < Struct.new(:shallow_line, :steep_line)<br />
attr_accessor :shallow_bump, :steep_bump<br />
def deep_copy<br />
copy = View.new(shallow_line.dup, steep_line.dup)<br />
copy.shallow_bump = shallow_bump.nil? ? nil : shallow_bump.deep_copy<br />
copy.steep_bump = steep_bump.nil? ? nil : steep_bump.deep_copy<br />
return copy<br />
end<br />
end<br />
<br />
# Check a quadrant of the FOV field for visible tiles<br />
def check_quadrant(dx, dy, extent_x, extent_y)<br />
active_views = []<br />
shallow_line = Line.new(0, 1, extent_x, 0)<br />
steep_line = Line.new(1, 0, 0, extent_y)<br />
<br />
active_views << View.new(shallow_line, steep_line)<br />
view_index = 0<br />
<br />
# Visit the tiles diagonally and going outwards<br />
i, max_i = 1, extent_x + extent_y<br />
while i != max_i + 1 and active_views.size > 0<br />
start_j = [0, i - extent_x].max<br />
max_j = [i, extent_y].min<br />
j = start_j<br />
while j != max_j + 1 and view_index < active_views.size<br />
x, y = i - j, j<br />
visit_coord x, y, dx, dy, view_index, active_views<br />
j += 1<br />
end<br />
i += 1<br />
end<br />
end<br />
<br />
def visit_coord(x, y, dx, dy, view_index, active_views)<br />
# The top left and bottom right corners of the current coordinate<br />
top_left, bottom_right = [x, y + 1], [x + 1, y]<br />
<br />
while view_index < active_views.size and<br />
active_views[view_index].steep_line.below_or_collinear?(*bottom_right)<br />
# Co-ord is above the current view and can be ignored (steeper fields may need it though)<br />
view_index += 1<br />
end<br />
<br />
if view_index == active_views.size or<br />
active_views[view_index].shallow_line.above_or_collinear?(*top_left)<br />
# Either current co-ord is above all the fields, or it is below all the fields<br />
return<br />
end<br />
<br />
# Current co-ord must be between the steep and shallow lines of the current view<br />
# The real quadrant co-ordinates:<br />
real_x, real_y = x * dx, y * dy<br />
coord = [@start_x + real_x, @start_y + real_y]<br />
light *coord<br />
<br />
# Don't go beyond circular radius specified<br />
#if (real_x * real_x + real_y * real_y) > @radius_sq<br />
# active_views.delete_at(view_index)<br />
# return<br />
#end<br />
<br />
# If this co-ord does not block sight, it has no effect on the view<br />
return unless blocked?(*coord)<br />
<br />
view = active_views[view_index]<br />
if view.shallow_line.above?(*bottom_right) and view.steep_line.below?(*top_left)<br />
# Co-ord is intersected by both lines in current view, and is completely blocked<br />
active_views.delete(view)<br />
elsif view.shallow_line.above?(*bottom_right)<br />
# Co-ord is intersected by shallow line; raise the line<br />
add_shallow_bump top_left[0], top_left[1], view<br />
check_view active_views, view_index<br />
elsif view.steep_line.below?(*top_left)<br />
# Co-ord is intersected by steep line; lower the line<br />
add_steep_bump bottom_right[0], bottom_right[1], view<br />
check_view active_views, view_index<br />
else<br />
# Co-ord is completely between the two lines of the current view. Split the<br />
# current view into two views above and below the current co-ord.<br />
shallow_view_index, steep_view_index = view_index, view_index += 1<br />
active_views.insert(shallow_view_index, active_views[shallow_view_index].deep_copy)<br />
add_steep_bump bottom_right[0], bottom_right[1], active_views[shallow_view_index]<br />
<br />
unless check_view(active_views, shallow_view_index)<br />
view_index -= 1<br />
steep_view_index -= 1<br />
end<br />
<br />
add_shallow_bump top_left[0], top_left[1], active_views[steep_view_index]<br />
check_view active_views, steep_view_index<br />
end<br />
end<br />
<br />
def add_shallow_bump(x, y, view)<br />
view.shallow_line.xf = x<br />
view.shallow_line.yf = y<br />
view.shallow_bump = ViewBump.new(x, y, view.shallow_bump)<br />
<br />
cur_bump = view.steep_bump<br />
while not cur_bump.nil?<br />
if view.shallow_line.above?(cur_bump.x, cur_bump.y)<br />
view.shallow_line.xi = cur_bump.x<br />
view.shallow_line.yi = cur_bump.y<br />
end<br />
cur_bump = cur_bump.parent<br />
end<br />
end<br />
<br />
def add_steep_bump(x, y, view)<br />
view.steep_line.xf = x<br />
view.steep_line.yf = y<br />
view.steep_bump = ViewBump.new(x, y, view.steep_bump)<br />
<br />
cur_bump = view.shallow_bump<br />
while not cur_bump.nil?<br />
if view.steep_line.below?(cur_bump.x, cur_bump.y)<br />
view.steep_line.xi = cur_bump.x<br />
view.steep_line.yi = cur_bump.y<br />
end<br />
cur_bump = cur_bump.parent<br />
end<br />
end<br />
<br />
# Removes the view in active_views at index view_index if:<br />
# * The two lines are collinear<br />
# * The lines pass through either extremity<br />
def check_view(active_views, view_index)<br />
shallow_line = active_views[view_index].shallow_line<br />
steep_line = active_views[view_index].steep_line<br />
if shallow_line.line_collinear?(steep_line) and (shallow_line.collinear?(0, 1) or<br />
shallow_line.collinear?(1, 0))<br />
active_views.delete_at view_index<br />
return false<br />
end<br />
return true<br />
end<br />
end<br />
</pre></div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=Ruby_precise_permissive_FOV_implementationRuby precise permissive FOV implementation2008-08-29T22:25:54Z<p>Rico: </p>
<hr />
<div>This is an implementation of [[Precise Permissive Field of View|Precise Permissive Field of View]] algorithm. It is based on the [[Permissive Field of View in Python|Python implementation]] by Aaron MacDonald.<br />
<br />
To use the algorithm, create a Map class or somesuch and provide two methods:<br />
<br />
<tt>blocked?(x, y)</tt> returns true if the tile at (x, y) blocks view of tiles beyond it (e.g. walls)<br /><br />
<tt>light(x, y)</tt> marks (x, y) as visible to the player (e.g. lit up on screen)<br />
<br />
Then <tt>include PermissiveFieldOfView</tt> within your Map class (or call <tt>extend(PermissiveFieldOfView)</tt> on your Map instance if you want to be dynamic) and call <tt>do_fov</tt>.<br />
<br />
Compared with [[Ruby shadowcasting implementation|shadowcasting]], permissive FOV runs ever so slightly slower but is reputedly artifact-free and symmetric (if you can see something, it can see you). Unfortunately this algorithm produces a <i>square</i> FOV shape around the player. Uncommenting the lines in <tt>visit_coord</tt> will change it to a diamond, but I don't understand enough to get a circle out of it :(<br />
<br />
My Ruby is fairly novice so if anyone sees anything amiss with the code, you are more than welcome to change it.<br />
<br />
<pre><br />
module PermissiveFieldOfView<br />
# Determines which co-ordinates on a 2D grid are visible<br />
# from a particular co-ordinate.<br />
# start_x, start_y: center of view<br />
# radius: how far field of view extends<br />
def do_fov(start_x, start_y, radius)<br />
@start_x, @start_y = start_x, start_y<br />
@radius_sq = radius * radius<br />
<br />
# We always see the center<br />
light @start_x, @start_y<br />
<br />
# Restrict scan dimensions to map borders and within the radius<br />
min_extent_x = Math.min(@start_x, radius)<br />
max_extent_x = Math.min(@width - @start_x - 1, radius)<br />
min_extent_y = Math.min(@start_y, radius)<br />
max_extent_y = Math.min(@height - @start_y - 1, radius)<br />
<br />
# Check quadrants: NE, SE, SW, NW<br />
check_quadrant 1, 1, max_extent_x, max_extent_y<br />
check_quadrant 1, -1, max_extent_x, min_extent_y<br />
check_quadrant -1, -1, min_extent_x, min_extent_y<br />
check_quadrant -1, 1, min_extent_x, max_extent_y<br />
end<br />
<br />
private<br />
# Represents a line (duh)<br />
class Line < Struct.new(:xi, :yi, :xf, :yf)<br />
# Macros to make slope comparisons clearer<br />
{:below => '>', :below_or_collinear => '>=', :above => '<',<br />
:above_or_collinear => '<=', :collinear => '=='}.each do |name, fn|<br />
eval "def #{name.to_s}?(x, y) relative_slope(x, y) #{fn} 0 end"<br />
end<br />
<br />
def dx; xf - xi end<br />
def dy; yf - yi end<br />
<br />
def line_collinear?(line)<br />
collinear?(line.xi, line.yi) and collinear?(line.xf, line.yf)<br />
end<br />
<br />
def relative_slope(x, y)<br />
(dy * (xf - x)) - (dx * (yf - y))<br />
end<br />
end<br />
<br />
class ViewBump < Struct.new(:x, :y, :parent)<br />
def deep_copy<br />
ViewBump.new(x, y, parent.nil? ? nil : parent.deep_copy)<br />
end<br />
end<br />
<br />
class View < Struct.new(:shallow_line, :steep_line)<br />
attr_accessor :shallow_bump, :steep_bump<br />
def deep_copy<br />
copy = View.new(shallow_line.dup, steep_line.dup)<br />
copy.shallow_bump = shallow_bump.nil? ? nil : shallow_bump.deep_copy<br />
copy.steep_bump = steep_bump.nil? ? nil : steep_bump.deep_copy<br />
return copy<br />
end<br />
end<br />
<br />
# Check a quadrant of the FOV field for visible tiles<br />
def check_quadrant(dx, dy, extent_x, extent_y)<br />
active_views = []<br />
shallow_line = Line.new(0, 1, extent_x, 0)<br />
steep_line = Line.new(1, 0, 0, extent_y)<br />
<br />
active_views << View.new(shallow_line, steep_line)<br />
view_index = 0<br />
<br />
# Visit the tiles diagonally and going outwards<br />
i, max_i = 1, extent_x + extent_y<br />
while i != max_i + 1 and active_views.size > 0<br />
start_j = Math.max(0, i - extent_x)<br />
max_j = Math.min(i, extent_y)<br />
j = start_j<br />
while j != max_j + 1 and view_index < active_views.size<br />
x, y = i - j, j<br />
visit_coord x, y, dx, dy, view_index, active_views<br />
j += 1<br />
end<br />
i += 1<br />
end<br />
end<br />
<br />
def visit_coord(x, y, dx, dy, view_index, active_views)<br />
# The top left and bottom right corners of the current coordinate<br />
top_left, bottom_right = [x, y + 1], [x + 1, y]<br />
<br />
while view_index < active_views.size and<br />
active_views[view_index].steep_line.below_or_collinear?(*bottom_right)<br />
# Co-ord is above the current view and can be ignored (steeper fields may need it though)<br />
view_index += 1<br />
end<br />
<br />
if view_index == active_views.size or<br />
active_views[view_index].shallow_line.above_or_collinear?(*top_left)<br />
# Either current co-ord is above all the fields, or it is below all the fields<br />
return<br />
end<br />
<br />
# Current co-ord must be between the steep and shallow lines of the current view<br />
# The real quadrant co-ordinates:<br />
real_x, real_y = x * dx, y * dy<br />
coord = [@start_x + real_x, @start_y + real_y]<br />
light *coord<br />
<br />
# Don't go beyond circular radius specified<br />
#if (real_x * real_x + real_y * real_y) > @radius_sq<br />
# active_views.delete_at(view_index)<br />
# return<br />
#end<br />
<br />
# If this co-ord does not block sight, it has no effect on the view<br />
return unless blocked?(*coord)<br />
<br />
view = active_views[view_index]<br />
if view.shallow_line.above?(*bottom_right) and view.steep_line.below?(*top_left)<br />
# Co-ord is intersected by both lines in current view, and is completely blocked<br />
active_views.delete(view)<br />
elsif view.shallow_line.above?(*bottom_right)<br />
# Co-ord is intersected by shallow line; raise the line<br />
add_shallow_bump top_left[0], top_left[1], view<br />
check_view active_views, view_index<br />
elsif view.steep_line.below?(*top_left)<br />
# Co-ord is intersected by steep line; lower the line<br />
add_steep_bump bottom_right[0], bottom_right[1], view<br />
check_view active_views, view_index<br />
else<br />
# Co-ord is completely between the two lines of the current view. Split the<br />
# current view into two views above and below the current co-ord.<br />
shallow_view_index, steep_view_index = view_index, view_index += 1<br />
active_views.insert(shallow_view_index, active_views[shallow_view_index].deep_copy)<br />
add_steep_bump bottom_right[0], bottom_right[1], active_views[shallow_view_index]<br />
<br />
unless check_view(active_views, shallow_view_index)<br />
view_index -= 1<br />
steep_view_index -= 1<br />
end<br />
<br />
add_shallow_bump top_left[0], top_left[1], active_views[steep_view_index]<br />
check_view active_views, steep_view_index<br />
end<br />
end<br />
<br />
def add_shallow_bump(x, y, view)<br />
view.shallow_line.xf = x<br />
view.shallow_line.yf = y<br />
view.shallow_bump = ViewBump.new(x, y, view.shallow_bump)<br />
<br />
cur_bump = view.steep_bump<br />
while not cur_bump.nil?<br />
if view.shallow_line.above?(cur_bump.x, cur_bump.y)<br />
view.shallow_line.xi = cur_bump.x<br />
view.shallow_line.yi = cur_bump.y<br />
end<br />
cur_bump = cur_bump.parent<br />
end<br />
end<br />
<br />
def add_steep_bump(x, y, view)<br />
view.steep_line.xf = x<br />
view.steep_line.yf = y<br />
view.steep_bump = ViewBump.new(x, y, view.steep_bump)<br />
<br />
cur_bump = view.shallow_bump<br />
while not cur_bump.nil?<br />
if view.steep_line.below?(cur_bump.x, cur_bump.y)<br />
view.steep_line.xi = cur_bump.x<br />
view.steep_line.yi = cur_bump.y<br />
end<br />
cur_bump = cur_bump.parent<br />
end<br />
end<br />
<br />
# Removes the view in active_views at index view_index if:<br />
# * The two lines are collinear<br />
# * The lines pass through either extremity<br />
def check_view(active_views, view_index)<br />
shallow_line = active_views[view_index].shallow_line<br />
steep_line = active_views[view_index].steep_line<br />
if shallow_line.line_collinear?(steep_line) and (shallow_line.collinear?(0, 1) or<br />
shallow_line.collinear?(1, 0))<br />
active_views.delete_at view_index<br />
return false<br />
end<br />
return true<br />
end<br />
end<br />
</pre></div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_ViewPermissive Field of View2008-08-29T22:19:31Z<p>Rico: link to ruby impl.</p>
<hr />
<div>==What is Permissive Field of View?==<br />
<br />
Permissive field of view defines visibility more loosely than other [[Field of Vision]] methods. A destination square is visible from a source square if there is any unobstructed line from some point in the source square to some point in the destination square. This means that players and monsters will automatically 'peek' around corners, for example. It also means that field of view is symmetric. That is to say that if a destination square is visible from a source square, then that source square is also visible from the destination square. Some approximation algorithms might lose the property of guaranteed symmetry.<br />
<br />
One tricky corner case are literally the corners. There are two questions that must be answered. Are corners of squares valid points in the source and destination squares for determining visibility? And do corners of walls obstruct line of sight? Different algorithms may answer these questions in different ways.<br />
<br />
===Advantages===<br />
<br />
* Symmetry of field of view may make ranged combat more sensible.<br />
* Monsters cannot sneak up on the player as easily.<br />
* Reduced player exploitation of line of sight artifacts.<br />
* There is an existing library implementing it.<br />
* May make certain aspects of the game easier (realistic lighting).<br />
<br />
===Disadvantages===<br />
<br />
* The most complicated method to understand and implement (and therefore debug).<br />
* The player cannot sneak up on monsters more easily.<br />
* May ruin play balance of current games.<br />
* It is more difficult for the player to withdraw from ranged combat.<br />
<br />
==How do I implement it?==<br />
<br />
There are a number of articles describing different methods:<br />
* [[Isaac_s_fast_beamcasting_LOS]] -- An approximate algorithm using 'wide beams' sent out at fixed slopes. The larger the radius, the more beams must be sent out to avoid artifacts.<br />
* [[Mutual_Visibility_Field_Of_View]] -- Uses the corners of squares to determine visibility. In some cases, it does not precisely capture Permissive Field of View. However, the algorithm guarantees symmetry in the field of view.<br />
* A fast algorithm using pre-cached dependencies is described in the source code for [[Dungeon Crawl Stone Soup]]<br />
* [[Precise Permissive Field of View]] -- A fast and, in theory, artifact free variation.<br />
<br />
==What games use it?==<br />
<br />
* [[Dungeon Crawl Stone Soup]]<br />
<br />
==What libraries implement it?==<br />
<br />
{| class="wikitable" cellpadding="10" cellspacing="0" border="1"<br />
|-<br />
! Library<br />
! Language(s)<br />
! Algorithm(s)<br />
|-<br />
| [[Permissive Field of View in Python]]<br />
| Python<br />
|rowspan=4| [[Precise Permissive Field of View]]<br />
|-<br />
| [[permissive-fov]]<br />
| C/C++<br />
|-<br />
| [[Roguelike Library For Java]]<br />
| Java<br />
|-<br />
| [[Ruby precise permissive FOV implementation|Ruby implementation]]<br />
| Ruby<br />
|}</div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=Precise_Permissive_Field_of_ViewPrecise Permissive Field of View2008-08-29T22:17:12Z<p>Rico: link to implementations</p>
<hr />
<div>See [[Permissive Field of View]] for more information and existing implementations of the algorithm in C/C++, Java, Python and Ruby.<br />
<br />
A field of view is the set of destination squares which are visible from a source square. If the field of view is permissive, then a destination square is visible if and only if there is an unobstructed line from some point in the source square to some point in the destination square. I call it permissive because for a given source in a map, there are usually many more visible squares (including around corners) than in raytracing or shadowcasting algorithms.<br />
<br />
A precise field of view calculation uses no approximation. It must take account of every piece of every square. If approximations are used, there are artifacts, especially as distance increases. Artifacts are usually squares that are not visible even when there is an unobstructed line from the source. Artifacts are problems because they allow inconsistencies to creep in. These are intuitive inconsistencies (I shoot an arrow at an orc and accidentally hit a goblin I cannot see). But they cause imperfect symmetry because artifacts are rarely symmetric. This causes situations where a player can shoot a creature who cannot shoot back, for instance, which is a situation ripe for player exploitation. Usually approximation algorithms run slower the more accurate they become. To remove all artifacts usually costs a huge amount of performance.<br />
<br />
This algorithm was created by Jonathon Duerig. A [http://www.dismalpl.com/los-demo.zip demo] and source code for a reference implementation is available.<br />
<br />
There is a library which implements this algorithm with bindings for C and C++ described at [[permissive-fov]].<br />
<br />
==Those pesky corners==<br />
<br />
First of all, tracing paths between the corners of squares is insufficient. This fails in the counterexample shown in Figure 1, created by Isaac Kuo. From the source square s, d should always be visible. This is in spite of the fact that there exists no line between s and d that intersects any corner, middle-edge point, or the centers of either s or d. Further, any approximate solution will fail given a sufficiently long hallway.<br />
<br />
A Kuo Corridor (Figure 1):<br />
####<br />
###################..d<br />
##...................## <br />
s..################### <br />
####<br />
<br />
Second, the extreme corners of a square must be considered open even if the square has a wall. Since movement can be in any of the eight directions, it makes intuitive sense that s can see d in Figure 2. If the corners of walls were considered obstructing, then this would not be the case.<br />
<br />
Diagonal Wall (Figure 2):<br />
#d<br />
s#<br />
<br />
<br />
Third, corners are not considered valid points for creating an unobstructed line in the source and destination squares. If they were, then the previous rule would imply that s can see d in Figure 3, which is not desirable.<br />
<br />
Corner Pillar (Figure 3):<br />
..d<br />
.#.<br />
s..<br />
<br />
==Overall Algorithm==<br />
<br />
We use the point in the lower-left corner of a square to denote that square. The player is at position (0,0). We will discuss the top-left corner and bottom-right corners of squares. Given a square (x,y), the top-left corner is at point (x,y+1) and the bottom-right corner is at point (x+1,y). We will consider only the first quadrant because you can use the proper reflections to find the field of view in other quadrants easily.<br />
<br />
The algorithm works from near to far. The map squares are visited in the following order, with @ representing the player:<br />
<br />
.<br />
.<br />
.<br />
9<br />
5 8<br />
2 4 7<br />
@ 1 3 6...<br />
<br />
Similar to shadowcasting, we will incrementally update our visible area as we move outward. We have one or more views, each containing two lines which represent the extremities of that view. As we encounter walls, we add new views, modify existing views, or end them as appropriate.<br />
<br />
The intuition is that you are looking at a faraway object. You can move left and right between a left wall and a right wall. In between you and the object, there are a number of obstructions coming from the left and right walls. Now what happens when you are trying to see as much of the object as possible? If you want to see the right-most bit of the object, you go left as much as possible, until you get to the point where a left-side obstruction gets between you and the object or you get to the end of the line. It is the reverse if you want to see the leftmost part of the object.<br />
<br />
Now we'll apply that inutition to the square that the player is on. Draw a line across the diagonal of the of the source square (Figure 4). The 'left wall' here is the top-left corner of the origin square. Therefore the 'rightmost' glimpse at the map is going to be from that point. Similarly, the bottom-right corner is the 'right wall' and the 'leftmost' glimpse at the map is from that point.<br />
<br />
Figure 4: http://www.dismalpl.com/wide-view.png<br />
<br />
The slope of these two lines is an invariant. Therefore, we will refer to them as the steep line and the shallow line.<br />
<br />
The heart of the algorithm is how to incrementally update these two lines to deal with walls.<br />
<br />
==Initial Conditions==<br />
<br />
The shallow line starts out going from (0,1) -> (infinity,0).<br />
The steep line starts out going from (1,0) -> (0,infinity).<br />
Approximate infinity with any sufficiently large number.<br />
<br />
Note that it should be possible to tweak the initial conditions to calculate smaller fields of view than an entire quadrant, but there are subtleties here which I haven't worked out yet.<br />
<br />
==Incremental Update==<br />
<br />
There can be many views. Each view has a shallow line and a steep line. Each line is defined by two points, the near point and the far point.<br />
<br />
As the algorithm processes outwards, each view will contain a mutually exclusive section of map. A square can either contain a wall (obstructing visibility), or it can be empty. Given a particular view, there are five possible ways that a square can intrude upon it (Figure 5).<br />
<br />
Figure 5: http://www.dismalpl.com/five-cases.png<br />
<br />
(1) If a square is entirely below the shallow line or entirely above the steep line, then that square is not visible from this view, and does not change it. Note that because corners are not considered to obstruct, even if the top-left corner of a square is on the shallow line or the bottom-right corner of a square is on the steep line, that square is still ignored.<br />
<br />
(2) If an empty square is between the two lines or at least one line intersects with it, then that square should be marked as visible. Since it is not an obstruction, it does not affect the lines of visibility.<br />
<br />
(3) If both lines intersect with a wall, then that wall should be marked as visible, and the view is now completely blocked and should be destroyed.<br />
<br />
(4) If a wall intersects just one line, then it is called a shallow bump or a steep bump if it intersects with the shallow line or the steep line respectively. The wall means that we must narrow are view appropriately. If it is a steep bump, then we replace the far point on the steep line with the bottom-right corner or the square. Similarly, if it is a shallow bump, we replace the far point on the shallow line with the top-left corner of the wall. There is a crucial subtlety, which I will discuss at length below.<br />
<br />
(5) If a wall is between the lines, then we need to divide the current view into two smaller views. One view is created by using the shallow line from the original view and treating the bottom-right corner of the square as a steep bump. The other view is the oppposite, created by using the steep line from the original view and treating the top-left corner of the square as a shallow bump. If the top-left corner of the wall is on the steep line or the bottom-right corner of the wall is on the shallow line (or both), then it is still considered between, and an extremely narrow view is created.<br />
<br />
==A Bump in the Night==<br />
<br />
Suppose that you were following the above incremental argument and you came across the situation in Figure 6. The green squares are walls that have already been processed and the green pair of lines are the initial before processing the red square. The red square is a wall that is about to be processed. It is between the lines, so we create a new view using the top-left corner of the red wall as a shallow bump. This creates the view denoted by the red lines. And there lies the problem. The new shallow line passes through a wall that we have already processed.<br />
<br />
Figure 6: http://www.dismalpl.com/bump-conflict.png<br />
<br />
Lets relate this to the intuitive scenario above with the faraway object. We said that we need to move left until we get to a point where a left-side obstruction gets between you and the object. That is what this wall is. It is a 'left side obstruction'. We can no longer view the map from the whole square. From now on, we can only use part of the square.<br />
<br />
Figure 7 shows our new lines taking this into account. We replace the near point of the shallow line with the bottom-right corner of the wall. But how do we do this algorithmically? We have to maintain a list of previous shallow bumps and a list of previous steep bumps for every view. Then, when we move the shallow line because of a shallow bump, we can look through the list of steep bumps and ensure that the shallow line does not ignore any wall that was a steep bump previously. And vice versa.<br />
<br />
Figure 7: http://www.dismalpl.com/bump-resolve.png<br />
<br />
==Corners at the source==<br />
<br />
There is a final subtlety. Since the corners of the source square cannot themselves be used as sources, then whenever a bump moves a line or a new view is created, we need to check to see whether the two lines are actually the same line originating from one of the corners. In that case, we also need to consider the view blocked and destroy it.</div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=Ruby_shadowcasting_implementationRuby shadowcasting implementation2008-08-29T22:14:38Z<p>Rico: </p>
<hr />
<div>This is a Ruby implementation of Bjorn Bergstrom's [[FOV_using_recursive_shadowcasting|recursive shadowcasting FOV algorithm]]. It is basically a straight port of the [[Python shadowcasting implementation|Python version]], implemented as a module, and could probably do with some optimisation.<br />
<br />
To use the module, create a Map class or somesuch and provide two methods:<br />
<br />
<tt>blocked?(x, y)</tt> returns true if the tile at (x, y) blocks view of tiles beyond it (e.g. walls)<br /><br />
<tt>light(x, y)</tt> marks (x, y) as visible to the player (e.g. lit up on screen)<br />
<br />
Then <tt>include ShadowcastingFieldOfView</tt> within your Map class (or call <tt>extend(ShadowcastingFieldOfView)</tt> on your Map instance if you want to be dynamic)<br />
<br />
On both Ruby 1.8 and 1.9, shadowcasting runs slightly faster than [[Ruby precise permissive FOV implementation|Precise Permissive FOV]] and boasts a circular FOV shape, 8-directions of FOV casting, and is easier to understand. On the other hand, it has artifacts and is not symmetric ... but it is the more popular roguelike algorithm.<br />
<br />
<pre><br />
module ShadowcastingFieldOfView<br />
# Multipliers for transforming coordinates into other octants<br />
@@mult = [<br />
[1, 0, 0, -1, -1, 0, 0, 1],<br />
[0, 1, -1, 0, 0, -1, 1, 0],<br />
[0, 1, 1, 0, 0, -1, -1, 0],<br />
[1, 0, 0, 1, -1, 0, 0, -1],<br />
] <br />
<br />
# Determines which co-ordinates on a 2D grid are visible<br />
# from a particular co-ordinate.<br />
# start_x, start_y: center of view<br />
# radius: how far field of view extends<br />
def do_fov(start_x, start_y, radius)<br />
light start_x, start_y<br />
8.times do |oct|<br />
cast_light start_x, start_y, 1, 1.0, 0.0, radius,<br />
@@mult[0][oct],@@mult[1][oct],<br />
@@mult[2][oct], @@mult[3][oct], 0<br />
end<br />
end<br />
<br />
private<br />
# Recursive light-casting function<br />
def cast_light(cx, cy, row, light_start, light_end, radius, xx, xy, yx, yy, id)<br />
return if light_start < light_end<br />
radius_sq = radius * radius<br />
(row..radius).each do |j| # .. is inclusive<br />
dx, dy = -j - 1, -j<br />
blocked = false<br />
while dx <= 0<br />
dx += 1<br />
# Translate the dx, dy co-ordinates into map co-ordinates<br />
mx, my = cx + dx * xx + dy * xy, cy + dx * yx + dy * yy<br />
# l_slope and r_slope store the slopes of the left and right<br />
# extremities of the square we're considering:<br />
l_slope, r_slope = (dx-0.5)/(dy+0.5), (dx+0.5)/(dy-0.5)<br />
if light_start < r_slope<br />
next<br />
elsif light_end > l_slope<br />
break<br />
else<br />
# Our light beam is touching this square; light it<br />
light(mx, my) if (dx*dx + dy*dy) < radius_sq<br />
if blocked<br />
# We've scanning a row of blocked squares<br />
if blocked?(mx, my)<br />
new_start = r_slope<br />
next<br />
else<br />
blocked = false<br />
light_start = new_start<br />
end<br />
else<br />
if blocked?(mx, my) and j < radius<br />
# This is a blocking square, start a child scan<br />
blocked = true<br />
cast_light(cx, cy, j+1, light_start, l_slope,<br />
radius, xx, xy, yx, yy, id+1)<br />
new_start = r_slope<br />
end<br />
end<br />
end<br />
end # while dx <= 0<br />
break if blocked<br />
end # (row..radius+1).each<br />
end<br />
end<br />
</pre></div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=Ruby_shadowcasting_implementationRuby shadowcasting implementation2008-08-29T22:12:54Z<p>Rico: </p>
<hr />
<div>This is a Ruby implementation of Bjorn Bergstrom's [[FOV_using_recursive_shadowcasting|recursive shadowcasting FOV algorithm]]. It is basically a straight port of the [[Python shadowcasting implementation|Python version]], implemented as a module, and could probably do with some optimisation.<br />
<br />
To use the module, create a Map class or somesuch and provide two methods:<br />
<br />
<tt>blocked?(x, y)</tt> returns true if the tile at (x, y) blocks view of tiles beyond it (e.g. walls)<br /><br />
<tt>light(x, y)</tt> marks (x, y) as visible to the player (e.g. lit up on screen)<br />
<br />
On both Ruby 1.8 and 1.9, shadowcasting runs slightly faster than [[Ruby precise permissive FOV implementation|Precise Permissive FOV]] and boasts a circular FOV shape, 8-directions of FOV casting, and is easier to understand. On the other hand, it has artifacts and is not symmetric ... but it is the more popular roguelike algorithm.<br />
<br />
<pre><br />
module ShadowCastingFieldOfView<br />
# Multipliers for transforming coordinates into other octants<br />
@@mult = [<br />
[1, 0, 0, -1, -1, 0, 0, 1],<br />
[0, 1, -1, 0, 0, -1, 1, 0],<br />
[0, 1, 1, 0, 0, -1, -1, 0],<br />
[1, 0, 0, 1, -1, 0, 0, -1],<br />
] <br />
<br />
# Determines which co-ordinates on a 2D grid are visible<br />
# from a particular co-ordinate.<br />
# start_x, start_y: center of view<br />
# radius: how far field of view extends<br />
def do_fov(start_x, start_y, radius)<br />
light start_x, start_y<br />
8.times do |oct|<br />
cast_light start_x, start_y, 1, 1.0, 0.0, radius,<br />
@@mult[0][oct],@@mult[1][oct],<br />
@@mult[2][oct], @@mult[3][oct], 0<br />
end<br />
end<br />
<br />
private<br />
# Recursive light-casting function<br />
def cast_light(cx, cy, row, light_start, light_end, radius, xx, xy, yx, yy, id)<br />
return if light_start < light_end<br />
radius_sq = radius * radius<br />
(row..radius).each do |j| # .. is inclusive<br />
dx, dy = -j - 1, -j<br />
blocked = false<br />
while dx <= 0<br />
dx += 1<br />
# Translate the dx, dy co-ordinates into map co-ordinates<br />
mx, my = cx + dx * xx + dy * xy, cy + dx * yx + dy * yy<br />
# l_slope and r_slope store the slopes of the left and right<br />
# extremities of the square we're considering:<br />
l_slope, r_slope = (dx-0.5)/(dy+0.5), (dx+0.5)/(dy-0.5)<br />
if light_start < r_slope<br />
next<br />
elsif light_end > l_slope<br />
break<br />
else<br />
# Our light beam is touching this square; light it<br />
light(mx, my) if (dx*dx + dy*dy) < radius_sq<br />
if blocked<br />
# We've scanning a row of blocked squares<br />
if blocked?(mx, my)<br />
new_start = r_slope<br />
next<br />
else<br />
blocked = false<br />
light_start = new_start<br />
end<br />
else<br />
if blocked?(mx, my) and j < radius<br />
# This is a blocking square, start a child scan<br />
blocked = true<br />
cast_light(cx, cy, j+1, light_start, l_slope,<br />
radius, xx, xy, yx, yy, id+1)<br />
new_start = r_slope<br />
end<br />
end<br />
end<br />
end # while dx <= 0<br />
break if blocked<br />
end # (row..radius+1).each<br />
end<br />
end<br />
</pre></div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=Ruby_shadowcasting_implementationRuby shadowcasting implementation2008-08-29T22:12:42Z<p>Rico: </p>
<hr />
<div>This is a Ruby implementation of Bjorn Bergstrom's [[FOV_using_recursive_shadowcasting|recursive shadowcasting FOV algorithm]]. It is basically a straight port of the [[Python shadowcasting implementation|Python version]], implemented as a module, and could probably do with some optimisation.<br />
<br />
To use the module, create a Map class or somesuch and provide two methods:<br />
<br />
<tt>blocked?(x, y)</tt> returns true if the tile at (x, y) blocks view of tiles beyond it (e.g. walls)<br />
<tt>light(x, y)</tt> marks (x, y) as visible to the player (e.g. lit up on screen)<br />
<br />
On both Ruby 1.8 and 1.9, shadowcasting runs slightly faster than [[Ruby precise permissive FOV implementation|Precise Permissive FOV]] and boasts a circular FOV shape, 8-directions of FOV casting, and is easier to understand. On the other hand, it has artifacts and is not symmetric ... but it is the more popular roguelike algorithm.<br />
<br />
<pre><br />
module ShadowCastingFieldOfView<br />
# Multipliers for transforming coordinates into other octants<br />
@@mult = [<br />
[1, 0, 0, -1, -1, 0, 0, 1],<br />
[0, 1, -1, 0, 0, -1, 1, 0],<br />
[0, 1, 1, 0, 0, -1, -1, 0],<br />
[1, 0, 0, 1, -1, 0, 0, -1],<br />
] <br />
<br />
# Determines which co-ordinates on a 2D grid are visible<br />
# from a particular co-ordinate.<br />
# start_x, start_y: center of view<br />
# radius: how far field of view extends<br />
def do_fov(start_x, start_y, radius)<br />
light start_x, start_y<br />
8.times do |oct|<br />
cast_light start_x, start_y, 1, 1.0, 0.0, radius,<br />
@@mult[0][oct],@@mult[1][oct],<br />
@@mult[2][oct], @@mult[3][oct], 0<br />
end<br />
end<br />
<br />
private<br />
# Recursive light-casting function<br />
def cast_light(cx, cy, row, light_start, light_end, radius, xx, xy, yx, yy, id)<br />
return if light_start < light_end<br />
radius_sq = radius * radius<br />
(row..radius).each do |j| # .. is inclusive<br />
dx, dy = -j - 1, -j<br />
blocked = false<br />
while dx <= 0<br />
dx += 1<br />
# Translate the dx, dy co-ordinates into map co-ordinates<br />
mx, my = cx + dx * xx + dy * xy, cy + dx * yx + dy * yy<br />
# l_slope and r_slope store the slopes of the left and right<br />
# extremities of the square we're considering:<br />
l_slope, r_slope = (dx-0.5)/(dy+0.5), (dx+0.5)/(dy-0.5)<br />
if light_start < r_slope<br />
next<br />
elsif light_end > l_slope<br />
break<br />
else<br />
# Our light beam is touching this square; light it<br />
light(mx, my) if (dx*dx + dy*dy) < radius_sq<br />
if blocked<br />
# We've scanning a row of blocked squares<br />
if blocked?(mx, my)<br />
new_start = r_slope<br />
next<br />
else<br />
blocked = false<br />
light_start = new_start<br />
end<br />
else<br />
if blocked?(mx, my) and j < radius<br />
# This is a blocking square, start a child scan<br />
blocked = true<br />
cast_light(cx, cy, j+1, light_start, l_slope,<br />
radius, xx, xy, yx, yy, id+1)<br />
new_start = r_slope<br />
end<br />
end<br />
end<br />
end # while dx <= 0<br />
break if blocked<br />
end # (row..radius+1).each<br />
end<br />
end<br />
</pre></div>Ricohttp://roguebasin.roguelikedevelopment.org/index.php?title=FOV_using_recursive_shadowcastingFOV using recursive shadowcasting2008-08-29T22:07:12Z<p>Rico: add link to ruby impl.</p>
<hr />
<div>FOV using recursive shadowcasting - Bj&ouml;rn Bergstr&ouml;m [bjorn.bergstrom@roguelikedevelopment.org]<br />
<br />
==Introduction==<br />
A working field-of-view (or commonly known as line of sight) algorithm is one of<br />
the essential parts in any roguelike. A FOV algorithm is used to calculate which<br />
mapcells, within a given radius, that can be seen, or in the case of a<br />
lightsource, which mapcells that are lit.<br />
<br />
The simplest approach is to trace lines from the center out to all of the<br />
mapcells at the edge of the radius and stopping when a mapcell is blocking line<br />
of sight. The problem with this approach is that many mapcells are visited<br />
several times, most often near the starting point and more seldom at the edges.<br />
There are a few things that can improve the performance of this simple approach.<br />
The most obvious is improvement can be made when a blocking mapcell is hit.<br />
Using a simple calculation all rays that cross the blocking mapcell can be<br />
skipped, hence improving performance. All of this is covered in detail in other<br />
LOS articles. "Line of Sight" by Tobias Downer is a good starting point.<br />
<br />
Even if the "rayskipping" described above is implemented many mapcells will be<br />
visited more than once, thus wasting CPU time. To overcome this a totally<br />
different approach must be used. This approach is called shadowcasting.<br />
<br />
<br />
==Shadowcasting==<br />
Shadowcasting divides the FOV calculations into eight octants and visits the<br />
mapcells in a totally different way than normal raycasting, described above.<br />
Instead of tracing lines from the center out to the edges, shadowcasting visits<br />
mapcells row by row or column by column, starting with the nearest row or column<br />
and working it's way outward.<br />
<br />
<pre><br />
------> 6 row 6 last<br />
-----> 5 .<br />
----> 4 .<br />
---> 3 .<br />
--> 2 row 2 second<br />
-> 1 row 1 is scanned first<br />
@ @ this is the starting point <br />
<br />
Fig.2a Shadowcasting order of scanning<br />
</pre><br />
<br />
When a scan comes across a cell that blocks LOS it calculates which other cells<br />
in rows/columns farther away that isn't visible because of the blocker. Those<br />
cells are "in shadow", hence the term shadowcasting.<br />
<br />
<pre><br />
-...--- - = visible cells<br />
-..--- # = blocking cell<br />
-#--- . = cells in blocker's shadow<br />
----<br />
---<br />
--<br />
@<br />
<br />
Fig.2b Cells in shadow of blocker<br />
</pre><br />
<br />
Normal shadowcasting is described in detail in the article "Computing LOS for<br />
Large Areas" by Gordon Lipford. Gordon's algorithm uses a temporary array and<br />
is rather complex. Using recursion one can achieve a clean and pretty fast<br />
algorithm that only visits non blocking and blocking cells, leaving out the<br />
cells in shadow. The algorithm is especially fast in confined areas such as<br />
corridors and small rooms.<br />
<br />
==Definitions==<br />
In order to understand recursive shadowcasting one need to understand what the<br />
slope and inverse slope of a line means. The slope is calculated using this<br />
simple formula:<br />
<br />
slope = (x1 - x2) / (y1 - y2)<br />
<br />
If we draw a line between [6,6] and [5,3] the slope would be:<br />
<br />
slope = (6 - 5) / (6 - 3) = 1 / 3 = 0.33333<br />
<br />
If we were to walk along this line we would find that for each step that we<br />
decreased y, x would be decreased 0.3333.<br />
<br />
The inverse slope is simply 1 / slope.<br />
<br />
<br />
<br />
==Recursive Shadowcasting==<br />
<br />
Recursive shadowcasting divides the field of view into eight octants with shared<br />
edges. The field of view will look like this when the octants are marked:<br />
<br />
<pre><br />
Shared<br />
edge by<br />
Shared 1 & 2 Shared<br />
edge by\ | /edge by<br />
1 & 8 \ | / 2 & 3<br />
\1111|2222/<br />
8\111|222/3<br />
88\11|22/33<br />
888\1|2/333<br />
Shared 8888\|/3333 Shared<br />
edge by-------@-------edge by<br />
7 & 8 7777/|\4444 3 & 4<br />
777/6|5\444<br />
77/66|55\44<br />
7/666|555\4<br />
/6666|5555\<br />
Shared / | \ Shared<br />
edge by/ | \edge by<br />
6 & 7 Shared 4 & 5<br />
edge by <br />
5 & 6<br />
<br />
Fig.4a Area of coverage by each octant<br />
</pre><br />
<br />
As with normal shadowcasting, this recursive shadowcasting algorithm scans an<br />
octant row by row or column by column, depending on the octant. In each octant<br />
the rows/columns closest to the starting point are scanned first.<br />
<br />
<br />
In octant 1 and 6 the scans are performed row by row, going from the leftmost<br />
cell to the rightmost cell in each row.<br />
<br />
In octant 2 and 5 the scans are performed row by row, going from the rightmost<br />
cell to the leftmost cell in each row.<br />
<br />
In octant 3 and 8 the scans are performed column by column, going from the<br />
topmost cell to the bottom most cell in each column.<br />
<br />
In octant 4 and 7 the scans are performed column by column, going from the<br />
bottom most cell to the topmost cell in each column.<br />
<br />
<br />
When a blocking cell is found a new scan is recursivly started one row/column<br />
further away, covering the area up until the first cell in shadow of the<br />
blocker. The rest of the initial row/column is scanned and subsequent blocking<br />
cells directly adjacent to the initial blocker is skipped. If a new section of<br />
non-blocking cells, followed by a blocker, is found the procedure is repeated.<br />
<br />
I will try to illustrate the procedure described above using some simple ascii<br />
drawings. The area that we wish to calculate a field of view for looks like<br />
this:<br />
<br />
<pre><br />
................. 16 @ = starting cell<br />
......###....... 15 # = blocking cell<br />
.....###....... 14 . = non-blocking cell<br />
....###..#..## 13 <br />
...##........ 12<br />
............ 11<br />
........... 10<br />
.......... 9<br />
......... 8<br />
........ 7<br />
....... 6<br />
...... 5<br />
..... 4<br />
.... 3<br />
... 2<br />
.. 1<br />
@<br />
<br />
Fig.4b Field of view<br />
</pre><br />
<br />
Rows 1 through 11 are all scanned without any problems from left to right. When<br />
the rightmost cell is reached a new scan is started one row further away, just<br />
as described before.<br />
<br />
If we were to draw a line from the center of the starting cell to the center of<br />
the leftmost cell in any of these rows we would find that the slope is 1. We<br />
call this the scan's start slope. If we would do the same for the rightmost cell<br />
the slope would be 0. This slope is ofcourse called the end slope.<br />
<br />
When we reach the 12th row things are becoming a bit more interesting. The<br />
recursion is started when we get to row 12 and hit the blocking cells.<br />
<br />
<pre><br />
................. 16 # = blocking cell<br />
......###....... 15 . = non-blocking cell<br />
.....###....... 14 <br />
....###..#..## 13 <br />
...x#........ 12 x = first blocking cell<br />
<br />
Fig.4c The first blocking cell<br />
</pre><br />
<br />
When the first blocking cell is hit (x) a new scan is started on row 13. The<br />
start slope is ofcourse the same as for all of the previous rows (ie. 1), but<br />
the end slope is different. The end slope is calculated using a line from the<br />
starting point to a point that 'brushes' by to the left of the blocking cell. If<br />
we zoom in it looks something like this:<br />
<br />
<pre><br />
+---+xxxxx##### x = first blocking cell<br />
| |xxxxx##### a = point that 'brushes' by to<br />
| |xxxxx##### the left of the blocking cell<br />
| |xxxxx#####<br />
+---axxxxx#####<br />
+---++---++---+<br />
| || || |<br />
| || || |<br />
| || || |<br />
+---++---++---+<br />
<br />
Fig.4d Zoom in on the first blocking cell<br />
</pre><br />
<br />
Thus, the end slope is obtained using a line from the center starting cell to<br />
the point marked 'a' in the figure. This gives an end slope of about 0.82.<br />
<br />
Ok, so now we have two scans; the original that continues to scan row 12 until<br />
the rightmost cell is reached and a new scan that scans row 13 from the leftmost<br />
cell (start slope 1) to the cell at row 13 that intersects the line with a slope<br />
of 0.82 (end slope):<br />
<br />
<pre><br />
2222............. 16 # = blocking cell<br />
2222..###....... 15 . = non-blocking cell<br />
222..###....... 14 <br />
222.###..#..## 13 1 = original scan <br />
111##11111111 12 2 = new scan<br />
<br />
Fig.4e Current scans<br />
</pre><br />
<br />
Ok, lets return to the original scan on row 12. The scan had just come across<br />
the first blocking cell and recursivly started a new scan one row further away<br />
with a new end slope. The original scan now checks the next cell and finds that<br />
this one is also a blocking cell. Since the previous cell was a blocking cell<br />
too, we have come across a section of blocker and just continue scanning until<br />
we reach a non blocking cell:<br />
<br />
<pre><br />
................. 16 # = blocking cell<br />
......###....... 15 . = non-blocking cell<br />
.....###....... 14 <br />
....###..#..## 13 <br />
...##o....... 12 o = first non-blocking cell after a section of blockers<br />
<br />
Fig.4f First non-blocking cell after a blocker<br />
</pre><br />
<br />
When the first non-blocking cell is found after a section of blockers we need to<br />
calculate a new start slope for the scan. This is done using a line from the<br />
center of the starting cell to a point that 'brushes' by to the right of the<br />
blocking cell. If we zoom in it looks something like this:<br />
<br />
<pre><br />
##########aoooo o = first non-blocking cell<br />
##########o o a = point that 'brushes' by to the<br />
##########o o right of the blocking cell<br />
##########o o<br />
##########ooooo<br />
+---++---++---+<br />
| || || |<br />
| || || |<br />
| || || |<br />
+---++---++---+<br />
<br />
Fig.4g Zoom in on the first non-blocking cell<br />
</pre><br />
<br />
Thus, the new start slope of the original scan is obtained using a line from the<br />
center of the starting cell to the point marked 'a' in the figure. This gives a<br />
start slope of 0.6.<br />
<br />
Ok, once a scan has reached it's last cell the scan is finished and a new scan<br />
is started one row further away if, and only if, the last cell was a<br />
non-blocking cell. In the case of our original scan the last cell was a<br />
non-blocking cell so a new scan is started one row further away with the new<br />
start slope of 0.6 (instead of the old 1).<br />
<br />
<br />
When the original scan starts on row 13 a blocking cell is immediately found:<br />
<br />
<pre><br />
................. 16 # = blocking cell<br />
......###....... 15 . = non-blocking cell<br />
.....###....... 14 <br />
....##x..#..## 13 x = blocking cell in original scan<br />
<br />
Fig.4h Starting with a blocking cell<br />
</pre><br />
<br />
When this happens we continue scanning until a non-blocking cell is found. In<br />
this case the next cell is a non-blocking cell and we calculate a new start<br />
slope in the same manner as on row 12 when we passed the section of blockers.<br />
After this is done we continue to scan from left to right until we reach the<br />
last cell or until we hit a blocking cell. In our example a blocking cell is<br />
found before we reach the last cell:<br />
<br />
<pre><br />
................. 16 # = blocking cell<br />
......###....... 15 . = non-blocking cell<br />
.....###....... 14 <br />
....##...x..## 13 x = blocking cell in original scan<br />
<br />
Fig.4i Another blocking cell<br />
</pre><br />
<br />
A new scan is now recursively started in the same way as on row 12. The scan has<br />
the same start slope as the original scan (0.6) and an end slope of a line that<br />
'brushes' by to the left of the blocking cell (marked x in fig.4i). Now we have<br />
three active scans:<br />
<br />
<pre><br />
2222......33..... 16<br />
2222..##333..... 15<br />
222..##333..... 14 <br />
222.###11#11## 13 <br />
<br />
Fig.4j Active scans<br />
</pre><br />
<br />
The same procedure is repeated once more when we move out of the blocking cell,<br />
find two new non-blocking cells and the run into yet another blocking cell:<br />
<br />
<pre><br />
2222......33444.. 16<br />
2222..##333.44.. 15<br />
222..##333.44.. 14 <br />
222.##111#11## 13 <br />
<br />
Fig.4k Active scans<br />
</pre><br />
<br />
When the original scan ends at the rightmost cell in row 13 we end with a<br />
blocking instead of a non-blocking, as we did in row 12. Since the original scan<br />
ended with a blocking cell a new scan is NOT started one row further away. We<br />
now have scan 2, 3 and 4 to do the job of scanning the rest of the field of<br />
view. These scans follow the same procedures and rules as the original scan.<br />
<br />
When the scans are done we get this field of view:<br />
<br />
<pre><br />
....ssssss.....ss 16 @ = starting cell<br />
....ssss#..s..ss 15 # = blocking cell<br />
...ssss#..s..ss 14 . = non-blocking cell<br />
...ss##..#..## 13 s = shadowed cells<br />
...##........ 12<br />
............ 11<br />
........... 10<br />
.......... 9<br />
......... 8<br />
........ 7<br />
....... 6<br />
...... 5<br />
..... 4<br />
.... 3<br />
... 2<br />
.. 1<br />
@<br />
</pre><br />
<br />
This procedure is repeated on the other octants, thus producing a complete<br />
field of view. An implementation along with source and DOS executable can<br />
be found here.<br />
<br />
Copyright 2001 Bj&ouml;rn Bergstr&ouml;m<br />
bjorn.bergstrom@roguelikedevelopment.org<br />
<br />
An [[PythonShadowcastingImplementation|implementation]] of this algorithm in Python.<br />
<br />
Another [[Ruby shadowcasting implementation|implementation]] in Ruby.<br />
<br />
[[Category:Articles]][[Category:LOS]]</div>Rico