Archived from groups: rec.games.roguelike.development (More info?)
This is an extension to an algorithm I already proposed some time
ago. It's supposed to be extremely fast, because it heavily depends
on a non-standard way of stroing level maps or the information
gathered during the level generation.
The idea is to store a graph of the level, having the rooms as it's nodes,
with additional information on the room sizes and locations. The nodes
would also contain lists of all objects contained in the room, together
with the relative locations of those objects.
You don't really need any kind of grid of squares -- altrough you can
keep such a grid or generate it on the fly for the current room if your
other algorithms depend on it.
The vision algorithm I describe additionally assumes that the rooms are
connected with one-square-wide doors only, and that the rooms are convex,
not counting some additional objects like pillars. Both of these
assumptions can be relaxed if you complicate the algorithm a bit -- I'll
get to that too.
The data structure we'll be using look something like this:
list of levels
- level
list of rooms
- room
list of doors in room
- door
index of other room
index of door in the other room
open/closed state
relative position in the room
list of terrain features in room
- feature
kind of feature, including light-blocking properties
relative position in the room
list of monsters in room
list of items in room
The player (or any other object we want to count FOV for) knows what room
he is in and what is his relative position in this room.
As the rooms are convex, we can safely assume that the whole rooms is
visible and display it:
#################
#...............#
#...............#
#...............#
#.......@.......#
#...............#
#...............#
#################
Key:
.: floor
#: wall
@: player character
But there might be pillars and other objects blocking the light -- we
must iterate the list of terrain features and draw them. We also make
cones of shadow behind all the opaque objects (the algorithm drawing
those cones will be described later):
#############
.........:...
#.*.::........*.#
#....:..........#
#.......@...:...#
#.*...........* #
.............
###############
Key:
:: rubble
*: pillar
Now we iterate the door list and draw all the closed door, and what's
visible behind open door. Again, we use the cone-drawing routine.
####+####+###
.........:...
######.*.::........*.# #
..'....:..........# ....#
#.......@...:...'........#
#.*...........* # ....#
............. #
###############
Key:
+: closed door
': open door
Now we must repeat the feature and the door list iterations in the
adjacent rooms, recursively. The cone-drawing functions need two additional
parameters -- the minimum and maximum angles, so that you don't see things
blocked by the first door behind the second door.
####+####+###
.........:...
######.*.::........*.#
..'....:..........# .*
#.......@...:...'......:.#
#.*...........* # ....'......
............. # ...
###############
Note that there's one special case -- when the player character stands in
a doorway. Depending on what wall thickness you assume, you will then
either treat both rooms as if the player character was standing in them
(faster), or assume he's not standing in any of them and draw cones from
both sides of the doorway.
Note also how extremely simple this system becomes when you assume that
all the doors close automatically behind the player character (which might
be very likely in an sf-based game).
Now, let's discuss the heart of this algorithm, the most dreaded part of
it -- the cone-drawing function.
We will modify the Breshenham's line-drawing algorithm -- basically,
we want to draw two lines at the same time, and instead of drawing
the squares of those lines, we will draw all the squares in between
them.
You'll begin to draw the squares once you pass the doorway, of course --
or you can try and bend your mind around your particular implementation
of line-drawing algorithm and figurethe initial values for the helper
variables. I'm too lazy for an example
The technique I sketched here can be also used on an arbitrary dungeon
that's separated into areas with one-square wide doors. Then, instead
of assuming the whole room is visible or drawing the cones, you simply
use any of generic FOV algorithm -- but only for the squares of the
current room. Then you iterate trough all the visible open doors, and
do the FOV calculation for therooms behind them. Repeat recursively.
Works especially well for *casting algorithms, since you can do them
for limited angles.
This thing needs some testing and, most importantly, the exact formulas
for cone-drawing function -- will work on it in my spare time.
--
Radomir `The Sheep' Dopieralski @**@_
(><) 3 Ouch!
. . . ..v.vVvVVvVvv.v.. .
This is an extension to an algorithm I already proposed some time
ago. It's supposed to be extremely fast, because it heavily depends
on a non-standard way of stroing level maps or the information
gathered during the level generation.
The idea is to store a graph of the level, having the rooms as it's nodes,
with additional information on the room sizes and locations. The nodes
would also contain lists of all objects contained in the room, together
with the relative locations of those objects.
You don't really need any kind of grid of squares -- altrough you can
keep such a grid or generate it on the fly for the current room if your
other algorithms depend on it.
The vision algorithm I describe additionally assumes that the rooms are
connected with one-square-wide doors only, and that the rooms are convex,
not counting some additional objects like pillars. Both of these
assumptions can be relaxed if you complicate the algorithm a bit -- I'll
get to that too.
The data structure we'll be using look something like this:
list of levels
- level
list of rooms
- room
list of doors in room
- door
index of other room
index of door in the other room
open/closed state
relative position in the room
list of terrain features in room
- feature
kind of feature, including light-blocking properties
relative position in the room
list of monsters in room
list of items in room
The player (or any other object we want to count FOV for) knows what room
he is in and what is his relative position in this room.
As the rooms are convex, we can safely assume that the whole rooms is
visible and display it:
#################
#...............#
#...............#
#...............#
#.......@.......#
#...............#
#...............#
#################
Key:
.: floor
#: wall
@: player character
But there might be pillars and other objects blocking the light -- we
must iterate the list of terrain features and draw them. We also make
cones of shadow behind all the opaque objects (the algorithm drawing
those cones will be described later):
#############
.........:...
#.*.::........*.#
#....:..........#
#.......@...:...#
#.*...........* #
.............
###############
Key:
:: rubble
*: pillar
Now we iterate the door list and draw all the closed door, and what's
visible behind open door. Again, we use the cone-drawing routine.
####+####+###
.........:...
######.*.::........*.# #
..'....:..........# ....#
#.......@...:...'........#
#.*...........* # ....#
............. #
###############
Key:
+: closed door
': open door
Now we must repeat the feature and the door list iterations in the
adjacent rooms, recursively. The cone-drawing functions need two additional
parameters -- the minimum and maximum angles, so that you don't see things
blocked by the first door behind the second door.
####+####+###
.........:...
######.*.::........*.#
..'....:..........# .*
#.......@...:...'......:.#
#.*...........* # ....'......
............. # ...
###############
Note that there's one special case -- when the player character stands in
a doorway. Depending on what wall thickness you assume, you will then
either treat both rooms as if the player character was standing in them
(faster), or assume he's not standing in any of them and draw cones from
both sides of the doorway.
Note also how extremely simple this system becomes when you assume that
all the doors close automatically behind the player character (which might
be very likely in an sf-based game).
Now, let's discuss the heart of this algorithm, the most dreaded part of
it -- the cone-drawing function.
We will modify the Breshenham's line-drawing algorithm -- basically,
we want to draw two lines at the same time, and instead of drawing
the squares of those lines, we will draw all the squares in between
them.
You'll begin to draw the squares once you pass the doorway, of course --
or you can try and bend your mind around your particular implementation
of line-drawing algorithm and figurethe initial values for the helper
variables. I'm too lazy for an example
The technique I sketched here can be also used on an arbitrary dungeon
that's separated into areas with one-square wide doors. Then, instead
of assuming the whole room is visible or drawing the cones, you simply
use any of generic FOV algorithm -- but only for the squares of the
current room. Then you iterate trough all the visible open doors, and
do the FOV calculation for therooms behind them. Repeat recursively.
Works especially well for *casting algorithms, since you can do them
for limited angles.
This thing needs some testing and, most importantly, the exact formulas
for cone-drawing function -- will work on it in my spare time.
--
Radomir `The Sheep' Dopieralski @**@_
(><) 3 Ouch!
. . . ..v.vVvVVvVvv.v.. .
Facebook
Twitter
Instagram