| DrakilorP2P |
03-15-2008 03:59 AM |
Field of view using Bresenham's line algorithm.
This script is really just a big hack-up to get a sample field of view drawing set up. If you intend to use it somewhere, you probably want to heavily tweak it in order to render the scene in a sane manner.
It uses Bresenham's line algorithm to draw lines from the point of origin to the edges of the level, stopping if any walls are encountered. While this is a pretty fast operation, it's usually not a good idea to do it every 0.1 seconds. I suggest only updating when the integer position changes.
Since 64x64 tiles is pretty large for this algorithm, there will be artifacts over long distances, but since this isn't NetHack, I consider it good enough.
In these screenshots, the purple tile is the point of origin.
http://image2life.net/users/public/g10532fov3q13.png
The following iteration uses some penetration in order to display a few non-walkable tiles, which makes more sense since normal people can see walls.
http://image2life.net/users/public/c29984fov44g13.png
PHP Code:
//#CLIENTSIDE
function onCreated()
{
clearPlots();
settimer(1);
}
function onTimeout()
{
clearPlots();
originx = int(mousex);
originy = int(mousey);
//Only draw lines towards the edges of the level. This saves computation but produces artifacts at long distances.
for (x=0; x<64; x++) {
bresenham(originx, originy, x, 0, true, 5);
}
for (x=0; x<64; x++) {
bresenham(originx, originy, x, 64, true, 5);
}
for (y=0; y<64; y++) {
bresenham(originx, originy, 0, y, true, 5);
}
for (y=0; y<64; y++) {
bresenham(originx, originy, 64, y, true, 5);
}
//Drawing lines towards all tiles is a slow process but produces a lot less artifacts.
/*for (x=0; x<64; x++) {
for (y=0; y<64; y++) {
bresenham(originx, originy, x, y, true);
}
}*/
settimer(1);
}
// A variant of Bresenham's line algorithm. It's pretty fast, especially if you only use integers which GScript doesn't seem to support.
// If stopAtWall is true, the line drawing will terminate when a wall tile is encountered.
// In this case, penetration specifies how many walls a line will be able to pass before terminating.
// bresenham(0, 0, 64, 64, true, 4) will draw a line between (0, 0) and (64, 64) but will stop after passing four blocking tiles.
function bresenham(x0, y0, x1, y1, stopAtWall, penetration)
{
x0 = int(x0); y0 = int(y0); x1 = int(x1); y1 = int(y1);
dx = abs(x1 - x0) << 1;
dy = abs(y1 - y0) << 1;
if (x1 > x0) ix = 1;
else ix = -1;
if (y1 > y0) iy = 1;
else iy = -1;
if (stopAtWall && onwall(x0, y0)) penetration--;
if (stopAtWall && penetration < 0) return;
plot(x0, y0);
if (dx >= dy) {
error = dy - (dx >> 1);
while (x0 != x1) {
if (error >= 0) {
if (error != 0 || (ix > 0)) {
y0 += iy;
error -= dx;
}
}
x0 += ix;
error += dy;
if (stopAtWall && onwall(x0, y0)) penetration--;
if (stopAtWall && penetration < 0) return;
plot(x0, y0);
}
}
else {
error = dx - (dy >> 1);
while (y0 != y1) {
if (error >= 0) {
if (error != 0 || iy > 0) {
x0 += ix;
error -= dy;
}
}
y0 += iy;
error += dx;
if (stopAtWall && onwall(x0, y0)) penetration--;
if (stopAtWall && penetration < 0) return;
plot(x0, y0);
}
}
}
function plot(x, y)
{
index = x * 100 + y + 300;
showpoly(index, {x, y, x+1, y, x+1, y+1, x, y+1});
changeimgcolors(index, 0.25, 0.25, 0.25, 0.01);
changeimgmode(index, 3);
changeimgvis(index, 3);
}
// 300 + 64 + 64 * 100 = 6664
function clearPlots()
{
hideimgs(300, 6664);
}
Note that there is faster ways to do this, especially for large areas such as a Graal level. If you're serious about field of view, do some research and find something that better suits your specific purposes.
If all you want is the implementation of Bresenham's line algorithm, here's a cleaned up version. Please define the plot(x, y) function so that it draws wherever you want it to.
PHP Code:
function cleanBresenham(x0, y0, x1, y1)
{
// Things can screw up if we don't use integers.
x0 = int(x0); y0 = int(y0); x1 = int(x1); y1 = int(y1);
dx = abs(x1 - x0) << 1;
dy = abs(y1 - y0) << 1;
if (x1 > x0) ix = 1;
else ix = -1;
if (y1 > y0) iy = 1;
else iy = -1;
plot(x0, y0);
if (dx >= dy) {
error = dy - (dx >> 1);
while (x0 != x1) {
if (error >= 0) {
if (error != 0 || (ix > 0)) {
y0 += iy;
error -= dx;
}
}
x0 += ix;
error += dy;
plot(x0, y0);
}
}
else {
error = dx - (dy >> 1);
while (y0 != y1) {
if (error >= 0) {
if (error != 0 || iy > 0) {
x0 += ix;
error -= dy;
}
}
y0 += iy;
error += dx;
plot(x0, y0);
}
}
}
|
