You wanna start somethin'?
Mike O'Brien
algorithms to determine what is in the line of sight, and it is
very difficult to get them to go fast enough to be practical.
I think the only foolproof line-of-sight games I have seen are
Ultima 4 and 5, and that's probably only because they have such
a small screen to work with! If you are writing a game such as
Hack, Rogue, Moria, etc., with an 80x25 screen, there's no way
you could do a complete check each move. So you look for shortcuts,
but every shortcut seems to have its bugs.....
Anyway, my big programming projects are usually either arcade-type
games or multi-player fantasy/adventure games. The latter is the
most fun to write, but I have only written them for BBS's before.
So while players could find and attack each other, only one of them
could be online at once. The other had to find the result of the
combat in mail. I just recently (6 months ago) got access to a
mainframe, and I'd really like to try programming a true multi-player
fantasy/adventure game on here, once I get a little more knowledgeable
about this environment.
By the way, my latest free-to-copy creation is Pyro ][, an arcade-type
game of arson. If anyone has seen a copy of this, do me a favor and
write me a letter! I'd like to know how far it's spread so far.
Well, I too would like to see some more posting around here. Come on
everyone, don't be shy!
Mike O'Brien
ac...@cornu.ucsb.edu
Neil Gilmore
Boy, you could hear a pin drop in this group! I guess all of you wait
for someone else to post. Okay, I'll bite.
I tend to program games of 2 types. The first is the war-boardgame
type and the second is 'intelligent arcade' (not an oxymoron, but
close).
For the first type, I use a movement algorithm like so: I either
create a second array with the dimensions of the map, or designate part
of the map for a number which represents the number of moves (or
movement points) it takes to get there. When a (computer-driven) piece
moves, I set all those elements to -1, then the one on which the piece
stands to 0. Then, until I can't anymore, I find elements with
non-negative numbers. If I find one, I scan each adjacent element. If it
contains -1, I put (value of found element)+(movement points to get to
scanned element) into it. If it does not, I compute the lesser of the
value of the scanned element or (value of found element)+(movement
points to get to scanned element) and put that value into it. If the map
is printed at the end of this, you will find values increasing as you
move farther away from the initial position. I suppose I could increase
the speed of this technique by pushing the initial element onto a stack
and recursively assigning values to adjacent elements. Any body done
this differently?
Another problem (especially in games in which the scale is small)
is visibility. I currently use a looong process of doing a line
algorithm from the pieces position to the edge of the map. The technique
looks at the next element along the line. If it is not visible
(previously marked), all the rest of the elements along the line are
marked not visible. This workes well for results, but takes too long.
Any visibility algoritms out there?
Thirdly, I get most headaches from the computer opponent. It's a
hassle trying to assign numbers (ala Crawford) to each possible
action/reaction pair. I find that most computer opponents in non-trivial
(not that chess as a game is trivial, but the rules are simple, and
there is no randomness) games are quite stupid. From personal
experience, the opponents in UMS and Empire can be beaten while asleep,
unless you give them overwhelming odds. I would like to see games where
the opponents are good, and can change their strategy *as necessary*.
I think this group could be fun and informative, if only someone
would post!
+-----------------------------------------------------------------------+
| ready>run game Neil Gilmore internet:gil...@macc.wisc.edu |
| You lose! MACC, UW-Madison bitnet: gilmore@wiscmac3 |
| Play again (y/n)? Madison, Wi |
+-----------------------------------------------------------------------+
Jim Meritt
Your LOS REALLY depends heavily upon your terrain model. In the STAR land
combat model the terrain is given by a clever application of combined
bivariate distributions, and a LOS is a simple solution requiring a
very small chunk of code, not a lot of number crunching, and minimal
storage.
"People think it must be fun to be a super genius, but they don't realize how
hard it is to put up with all the idiots in the world." - Calvin
............................................................................
j...@aplvax.jhuapl.edu - or - j...@aplvax.uucp - or - meritt%aplvm.BITNET
Paul Canniff 2/1011
How about a pre-calcuated LOS table? Use a heuristic
or some observation of the terrain/tactics/weapons and
see if there is some small range at which most of the
LOS calculations occur. If this number is reasonably
small you can calculate, at the time the map is generated,
all LOS at that range or less. Expensive? Depends on
your memory situation. For a 100x100 grid with a LOS
table up to 5 units each direction, the cost is
about 160K.
Figure you can store bits for an 11x11 grid, which is the
LOS to all squares from origin (x,y). This assumes that
we even have a bit for the origin and the adjacent areas,
although the LOS to these is *usually* automatic. That's
121 bits; round to 128 for nice even storage boundaries.
That is (128/8) = 16 bytes. 100x100x16 = 160K.
This can be prohibitvely expensive at the range you must
store goes up. And, it is useful only for LOS that do
not change too often. If units themselves form obstacles
to LOS, or there is a lot of smoke or other transient
LOS blocks, this method is less useful.
Also, where LOS uses partial screening and some sort of
"chance" spotting, you may need to store more than a
bit. For example suppose light brush reduces the
xhance of spotting into OR THROUGH it by 10%. Then you
might need to store a number (0..10) for 0-100% chance
of spotting.
The LOS table can also be used to extend LOS beyond the chosen
range, if elevation is not a factor. Where the terrain is
flat (obstalces are buildings, etc.), you can use the
coordinates of 0,0 -> 5,5 and 5,5 -> 8,8 to calculate the
LOS of 0,0 -> 8,8. If using a 3D map this doesn't work of course.
And some fractions don't break down well; for example 0,0 ->
1,13 has no "center point" -- no point in fact except the
end points. A decent algorithm could be used to pick one
point which it "approaches" as a mid-point. Using a chain
of "midpoints" you can build a very long LOS.
Ooops, forgot the other pitfall. Suppose you can see into
and out of a building but no throgh one. Then you must be
careful not to choose a midpoint that lets you see through
walls! Hey, I suppose you *could* put that 88mm shell righ
through the bathroom window and out the back porch, into the
Centurion ... but there should probably be a negative to-hit
modifier :)
As always if you go beyond the table range, or come up
with some fraction that does not allow extension of LOS
by "addition", you calc it at runtime. But if the size of
the table is chosen well, it will be used much more often
than the calcutation method.
For smaller memory overhead, you can also build this table
dynamically. For example on a sparse map, build the LOS table
for each unit as it moves, or for a whole section of the map
that is heavily populated, or only for map sections where units
of more than one player are active ... I mean why bother spotting
your own units, right?
Whoo. Sorry you asked yet?
Line-of-sight can be done very quickly, at the expense of
memory, bu pre-calculating LOS. This can be done once for
fixed maps, or at creation time for variable maps. To put
a lit on memory requirements, set some maximum range for
stored LOS. For example if you have a lot of clutter, you
could store all LOS of 5 or less hexes/grids/whatever. On
a 100x100 grid map, that is approximately (11 x 11 x 100 x 100)
or 1210000 ... a lotta memory! Stored as a bitmap that is still
151K, but that is not unreasonable in SOME systems.
Other ways to speed this include caching calculated LOS, dividing
the LOS table into sections that are swapped into memory, and
using the LOS entries chained together to get longer "effective"
calculations. For a (simple) example of the latter, consider
a LOS from 0,0 to 20,20. If we know the LOS from 0,0 to 10,10 and
the one from 10,10 .. AND THE LOS DOESN't WORRY ABOUT ELEVATION ...
we can calculate the LOS for our current situation.
Don Wennick
> You brought up some interesting points. I too have worked with
> algorithms to determine what is in the line of sight, and it is
> very difficult to get them to go fast enough to be practical.
> I think the only foolproof line-of-sight games I have seen are
> Ultima 4 and 5, and that's probably only because they have such
> a small screen to work with! If you are writing a game such as
> Hack, Rogue, Moria, etc., with an 80x25 screen, there's no way
> you could do a complete check each move. So you look for shortcuts,
> but every shortcut seems to have its bugs.....
I suppose this has been looked into, but I wonder if there might be
some adaptation of comp.graphics' ray tracers to this problem. I've
been thinking of a telecomm-based D&D game, where the DM uses a
local database to look up relevant data, decide combat rounds, etc.,
and remote connections to players, allowing private player-to-player
or player-to-DM communications, etc. One of the thorns is that I'd
like to have the computer tell me (the DM) what the players can see,
in such a way as to allow me to edit, then transmit, each player's
perpective on the situation. Are there any simple, fast, and
adjustably coarse ray tracers capable of this sort of thing?
--
do...@rwing.UUCP UUCP: ...!uunet!mltco!camco!happym!rwing!donw
Don Wennick ...!uw-beaver!tikal!camco!eskimo!rwing!donw
Emil Rainero
Most of the previous posting for line of sight seem to want to compute all visible cells.
The following demo program computes a point-to-point line of sight using the Bresenham's
line digitization algorithm. Currently a rectangular map is used, but it is a trivial
addition to change to hexagonal coordinate system. Performance measurements for
the los function are
Function Processor MIPS ops/secs
los Sun 3/110 2 4,300/sec
los Sun 4/110 ~8 11,100/sec
#include <stdio.h>
#define PRINTING 1
#define MAP_ROWS 18
#define MAP_COLUMNS 35
typedef struct {
char terrain_type;
} MapCell;
#define TERRAIN_CLEAR ' '
#define TERRAIN_OBSTACLE 'X'
#define TERRAIN_LOS '*'
#define TERRAIN_LOS2 '+'
#define TERRAIN_OBJECT 'O'
MapCell map[MAP_ROWS][MAP_COLUMNS];
int
rand_range(n1, n2)
int n1, n2;
{
int result;
int diff;
extern long random();
result = random();
if (result < 0)
result = (-result);
diff = n2 - n1 + 1;
result = (result % diff) + n1;
return (result);
}
make_house(origin_r, origin_c, width, height)
int origin_r, origin_c, width, height;
{
int r, c;
for (r = 0; r < height; r++)
for (c = 0; c < width; c++) {
map[origin_r + r][origin_c + c].terrain_type = TERRAIN_OBSTACLE;
}
}
init_map()
/* initialized map with a set of rectangular boxes */
{
int r, c;
int center_r, center_c;
int i, count;
for (r = 0; r < MAP_ROWS; r++) {
for (c = 0; c < MAP_COLUMNS; c++) {
map[r][c].terrain_type = TERRAIN_CLEAR;
}
}
center_r = MAP_ROWS / 2;
center_c = MAP_COLUMNS / 2;
make_house(center_r - 2, center_c - 2, 8, 3);
count = rand_range(2, 6);
for (i = 0; i < count; i++) {
make_house(rand_range(0, MAP_ROWS - 5), rand_range(0, MAP_COLUMNS - 8),
rand_range(1, 8), rand_range(1, 5));
}
}
print_map()
{
int r, c;
printf(" ");
for (c = 0; c < MAP_COLUMNS; c++)
printf("%2d", c);
printf("\n");
printf(" +");
for (c = 0; c < MAP_COLUMNS; c++)
printf("--");
printf("+\n");
for (r = 0; r < MAP_ROWS; r++) {
printf("%02d|", r);
for (c = 0; c < MAP_COLUMNS; c++) {
printf(" %c", map[r][c].terrain_type);
}
printf("|%02d", r);
printf("\n");
}
printf(" +");
for (c = 0; c < MAP_COLUMNS; c++)
printf("--");
printf("+\n");
printf(" ");
for (c = 0; c < MAP_COLUMNS; c++)
printf("%2d", c);
printf("\n");
}
/* use a macro for better performance */
#define MACRO_checkpixel(r,c) \
(oldterrain = map[r][c].terrain_type, \
map[r][c].terrain_type = (oldterrain == TERRAIN_OBSTACLE) ? TERRAIN_LOS2 : TERRAIN_LOS, \
(oldterrain != TERRAIN_OBSTACLE))
int
checkpixel(r, c)
int r, c;
{
char oldterrain;
oldterrain = map[r][c].terrain_type;
if (oldterrain == TERRAIN_OBSTACLE)
map[r][c].terrain_type = TERRAIN_LOS2;
else
map[r][c].terrain_type = TERRAIN_LOS;
return (oldterrain != TERRAIN_OBSTACLE);
}
/* Bresenham's algorithm for stepping line from xa,ya to xb, by */
/* returns 1 if visible */
int
los(xa, ya, xb, yb)
int xa, ya, xb, yb;
{
register int result;
register int dx, dy;
int pos_slope;
register int g, r, c;
int f, inc1, inc2;
char oldterrain;
result = 1;
/* determine the components of the vector */
dx = xb - xa;
dy = yb - ya;
/* determine the sign of the slope */
pos_slope = (dx > 0);
if (dy < 0)
pos_slope = !pos_slope;
/* decide on whether to step across columns or up rows */
if (abs(dx) > abs(dy)) {
/* this is the gentle slope case */
if (dx > 0) {
c = xa;
r = ya;
f = xb;
} else {
c = xb;
r = yb;
f = xa;
}
inc1 = 2 * abs(dy);
g = 2 * abs(dy) - abs(dx);
inc2 = 2 * (abs(dy) - abs(dx));
if (pos_slope) {
/* now step across line segment */
while (c <= f) {
/*
* set nearest pixel in the frame buffer
* pixel c,r
*/
result *= MACRO_checkpixel(r, c);
/* next column */
c++;
/* should row change */
if (g >= 0) {
r++;
g += inc2;
} else
g += inc1;
}
} else {
while (c <= f) {
/*
* set nearest pixel in the frame buffer
* pixel c,r
*/
result *= MACRO_checkpixel(r, c);
/* next column */
c++;
/* should row change */
if (g > 0) {
r--;
g += inc2;
} else
g += inc1;
}
}
} else {
/* this is the sharp slope case */
/* here the above steps are repeated */
/* with the roles of x and y interchanged */
if (dy > 0) {
c = ya;
r = xa;
f = yb;
} else {
c = yb;
r = xb;
f = ya;
}
inc1 = 2 * abs(dx);
g = 2 * abs(dx) - abs(dy);
inc2 = 2 * (abs(dx) - abs(dy));
if (pos_slope) {
/* now step across line segment */
while (c <= f) {
/*
* set nearest pixel in the frame buffer
* pixel c,r
*/
result *= MACRO_checkpixel(c, r);
/* next column */
c++;
/* should row change */
if (g >= 0) {
r++;
g += inc2;
} else
g += inc1;
}
} else {
while (c <= f) {
/*
* set nearest pixel in the frame buffer
* pixel c,r
*/
result *= MACRO_checkpixel(c, r);
/* next column */
c++;
/* should row change */
if (g > 0) {
r--;
g += inc2;
} else
g += inc1;
}
}
}
return (result);
}
test_los(testcount)
int testcount;
{
int r1, c1, r2, c2;
int i;
for (i = 0; i < testcount; i++) {
int result;
init_map();
do {
r1 = rand_range(0, MAP_ROWS - 1);
c1 = rand_range(0, MAP_COLUMNS - 1);
} while (map[r1][c1].terrain_type == TERRAIN_OBSTACLE);
do {
r2 = rand_range(0, MAP_ROWS - 1);
c2 = rand_range(0, MAP_COLUMNS - 1);
} while (map[r2][c2].terrain_type == TERRAIN_OBSTACLE);
result = los(c1, r1, c2, r2);
#ifdef PRINTING
printf("from %d,%d to %d,%d is %s\n",
c1, r1, c2, r2,
(result) ? "visible" : "not visible");
#endif
map[r1][c1].terrain_type = TERRAIN_OBJECT;
map[r2][c2].terrain_type = TERRAIN_OBJECT;
#ifdef PRINTING
print_map();
#endif
}
}
main(argc, argv)
int argc;
char **argv;
{
int testcount = 1;
if (argc > 1)
testcount = atoi(argv[1]);
srandom(getpid());
init_map();
test_los(testcount);
}
Patrick C Beard
throw in my $.02.
I have never written a game, other than the simplest of board games
like tic-tac-toe. What I would like to find are some clear examples
of what it takes to make a game interesting. Every time I think about
getting started writing a game, I take a look around and see that it's
already been written. I really don't want to write YARL (yet another
rogue-like game) but I am interested in spreading my wings in object
oriented programming.
So, has anybody had any experience in writing games in object-oriented
languages (C++, Object-???)? If so, could you point me to examples?
It seems to me that games could benefit immensely from object oriented
design: players, places, objects (!), modelled as more than just data
structures, but as Objects. With properties, methods, inheritance, etc.
What's been done so far? I know these concepts are still new, but I'm
eager to try them out.
Thanks for your time.
-------------------------------------------------------------------------------
- Patrick Beard Macintosh Programmer -
- Lawrence Berkeley Laboratory Berkeley Systems, Inc. -
-------------------------------------------------------------------------------
Bill Oliver
myself here, this was SPI's S&T) one of the many experiments they did
with line of sight rules was a table that they made of distance vs.
height. One would mark the height of the spotter and the target and
stretch a straight edge between the two. If any potential obstacle was
above the line between the objects then LOS was blocked. I will try to
draw this now but if it looks horrible , remember I hate vi and use it
only when posting.
height / distance 0 1 2 3 4 5
(meters) (hexes)
50 . . . . . t
40 . . . o2 . .
30 . . . . . .
20 . . . . o1 .
10 . . . . . .
0 s . . . . .
s = spotter t = target o = potential obstacles
A straight line drawn on the dots between s and t (conveniently on the diag-
onal ) will show that o1 will not block the path of the LOS but o2 will.
Now the question on everyone's mind is does this have any relevence
to deciding LOS on a computer? I don't know. I am just an old wargamer
who likes to pretend that he can program a little. I will leave it up
to the guys who dream in machine code to decide if this would be any
easier, faster, or more accurate than what they are using.
Rick Hunt
rh...@med.unc.edu
Ross Ridge
writes:
> Another problem (especially in games in which the scale is small)
>is visibility. I currently use a looong process of doing a line
>algorithm from the pieces position to the edge of the map. The technique
>looks at the next element along the line. If it is not visible
>(previously marked), all the rest of the elements along the line are
>marked not visible. This workes well for results, but takes too long.
>Any visibility algoritms out there?
I don't know if this aglorithim it fast enough for you, but the one I'm
currently working seems to work pretty well. I'm in the middle of
putting it in to code so you'll have to with my explaination of how
the algorithim works. I'll explain the algorithim as if I was trying to find
the sqaures illuminated by a light source rather the than the sqaures
in the LOS of an observer. Simply it works by calculating the the minimum
and maximum slopes of the rays of light that leave each sqaure from
its side farthest from the light source.
Assume a standard cartesean plane. S(x,y) is the sqaure with veritcies
(x, y), (x + 1, y), (x, y + 1) and (x + 1, y + 1)
Smax(x,y) is the maximum slope of S(x,y)
Smin(x,y) is the minimum slope of S(x,y)
An "edge" square is a sqaure that is illuminated but blocks all light.
A "hidden" square is a square this is not illuminated.
A "noslope" square is a square that isn't an edge, is illuminated, but light
doesn't leave it's farthest edge.
A sqaure "passes" light if it dosn't block light and isn't a noslope square.
Let Smax(0,0) = infinity; Smin(0,0) = 1
For all sqaures S(xx, yy) where xx = 0, yy > 0:
[prereq: calculate all S(X,Y), X = 0, Y < yy]
if S(xx, yy - 1) is not illuminated or is an edge
then S(xx, yy) is hidden
else if S(xx, yy) blocks light
then S(xx, yy) is an edge
else Let Smax(xx, yy) = infinity; Smin = (yy + 1)/xx.
For all squares S(xx, yy) where yy > 0, 0 < xx < yy:
[prereq: calculate all S(X,Y), (X < xx and Y = yy) or (X <= Y and X <= xx and Y < yy)]
if S(xx - 1, yy - 1) doesn't pass light
or Smin(xx - 1, yy - 1) > (yy + 1)/xx
or S(xx - 1, yy) blocks light
then
if S(xx, yy - 1) doesn't pass light
then S(xx, yy - 1) is hidden
else if S(xx, yy) blocks light
then S(xx, yy - 1) is an edge
else if Smax(xx, yy - 1) < (yy + 1)/(xx + 1)
then S(xx, yy) is a noslope
else
Smin(xx, yy) = MAX(Smin(xx, yy - 1), (yy + 1)/(xx + 1))
Smax(xx, yy) = Smax(xx, yy - 1);
else if S(xx, yy) blocks light
then S(xx, yy) is an edge
else if S(xx, yy - 1) doesn't pass light
then
Smin(xx, yy) = Smin(xx - 1, yy - 1)
Smax(xx, yy) = MIN(Smax(xx - 1, yy - 1), (yy + 1)/xx))
else
Smin(xx, yy) = MAX(Smin(xx, yy - 1), (yy + 1)/(xx + 1))
Smax(xx, yy) = MIN(Smax(xx - 1, yy - 1), (yy + 1)/xx))
For all sqaures S(xx, yy) where xx = yy, xx > 0:
[prereq: Calculate all S(X, Y); X = Y, 0 < X < xx]
if S(xx - 1, yy - 1) doesn't pass light
S(xx, yy) is hidden
else if S(xx - 1, yy) blocks light
Smax(xx, yy) = Smin(xx, yy) = 1
else
Smax(xx, yy) = (yy + 1)/xx
The rest of of the sqaures can be calculated as above with different
definitions of S (8 in all). (eg. S'(x', y') = S(-x', y')
S'(x', y') = S(y', x'))
Any square not marked hidden is in the LOS of an observer in S(0,0)
This is fairly fast, as each square is calculated only once, and using
fixed pointed numbers and some creative use of pointers I've written
a pretty fast routine for finding the LOS over a field of sqaures.
[ Don't try just directly translating the above routine. I did it from
from memory, and it's a bit shakie about the corners of squares ]
Ross Ridge
--
l/ attcan!tmsoft!ziebmef!ross //
[OO] [oo]
-()- -()-
db 6502 assembly forever! //