Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting > Code Gallery
FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 03-15-2008, 03:59 AM
DrakilorP2P DrakilorP2P is offline
Registered User
DrakilorP2P's Avatar
Join Date: Apr 2006
Posts: 755
DrakilorP2P is just really niceDrakilorP2P is just really nice
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.


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.

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=0x<64x++) {
    
bresenham(originxoriginyx0true5);
  }
  for (
x=0x<64x++) {
    
bresenham(originxoriginyx64true5);
  }
  for (
y=0y<64y++) {
    
bresenham(originxoriginy0ytrue5);
  }
  for (
y=0y<64y++) {
    
bresenham(originxoriginy64ytrue5);
  }

  
//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(x0y0x1y1stopAtWallpenetration)
{
  
x0 int(x0); y0 int(y0); x1 int(x1); y1 int(y1);
  
dx abs(x1 x0) << 1;
  
dy abs(y1 y0) << 1;
  
  if (
x1 x0ix 1;
  else 
ix = -1;
  if (
y1 y0iy 1;
  else 
iy = -1;
  
  if (
stopAtWall && onwall(x0y0)) penetration--;
  if (
stopAtWall && penetration 0) return;
  
plot(x0y0);
  
  if (
dx >= dy) {
    
error dy - (dx >> 1);
    
    while (
x0 != x1) {
      if (
error >= 0) {
        if (
error != || (ix 0)) {
          
y0 += iy;
          
error -= dx;
        }
      }
      
      
x0 += ix;
      
error += dy;
      
      if (
stopAtWall && onwall(x0y0)) penetration--;
      if (
stopAtWall && penetration 0) return;
      
plot(x0y0);
    }
  }
  else {
    
error dx - (dy >> 1);
    
    while (
y0 != y1) {
      if (
error >= 0) {
        if (
error != || iy 0) {
          
x0 += ix;
          
error -= dy;
        }
      }
        
      
y0 += iy;
      
error += dx;
      
      if (
stopAtWall && onwall(x0y0)) penetration--;
      if (
stopAtWall && penetration 0) return;     
      
plot(x0y0);
    }
  }
}

function 
plot(xy)
{
  
index 100 300;
  
showpoly(index, {xyx+1yx+1y+1xy+1});
  
changeimgcolors(index0.250.250.250.01);
  
changeimgmode(index3);
  
changeimgvis(index3);
}

// 300 + 64 + 64 * 100 = 6664
function clearPlots()
{
  
hideimgs(3006664);

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(x0y0x1y1)
{
  
// 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 x0ix 1;
  else 
ix = -1;
  if (
y1 y0iy 1;
  else 
iy = -1;
  
  
plot(x0y0);
  
  if (
dx >= dy) {
    
error dy - (dx >> 1);
    
    while (
x0 != x1) {
      if (
error >= 0) {
        if (
error != || (ix 0)) {
          
y0 += iy;
          
error -= dx;
        }
      }
      
      
x0 += ix;
      
error += dy;
      
      
plot(x0y0);
    }
  }
  else {
    
error dx - (dy >> 1);
    
    while (
y0 != y1) {
      if (
error >= 0) {
        if (
error != || iy 0) {
          
x0 += ix;
          
error -= dy;
        }
      }
        
      
y0 += iy;
      
error += dx;
          
      
plot(x0y0);
    }
  }


Last edited by DrakilorP2P; 03-15-2008 at 12:57 PM.. Reason: Improving language
Reply With Quote
  #2  
Old 03-19-2008, 12:52 PM
xXziroXx xXziroXx is offline
Master of Puppets
xXziroXx's Avatar
Join Date: May 2004
Location: Sweden
Posts: 5,288
xXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant futurexXziroXx has a brilliant future
Send a message via AIM to xXziroXx Send a message via MSN to xXziroXx
Very nicely done, rep++
__________________

"A delayed game is eventually good, but a rushed game is forever bad." - Shigeru Miyamoto
Reply With Quote
  #3  
Old 03-19-2008, 03:10 PM
coreys coreys is offline
N-Pulse Assistant Manager
coreys's Avatar
Join Date: Mar 2005
Posts: 2,180
coreys has a spectacular aura about
Send a message via AIM to coreys Send a message via MSN to coreys Send a message via Yahoo to coreys
That's very impressive.
Whenever I make baddies I just check if a target is in the direction the baddy is facing to do field of view. xP
Now I feel like a chump.
__________________

Quote:
*SlikRick: so should I even ask about your aim status?
*Xor: well if you want to
*Xor: but i am LARPING
*SlikRick: While on a computer?
*Xor: yes
*Xor: in my living room
*SlikRick: ahh
*Xor: i have a fort setup to hide from beasts
Reply With Quote
  #4  
Old 03-19-2008, 03:24 PM
Chompy Chompy is offline
¯\(º_o)/¯
Chompy's Avatar
Join Date: Sep 2006
Location: Norway
Posts: 2,815
Chompy is just really niceChompy is just really niceChompy is just really nice
Send a message via MSN to Chompy
Quote:
Originally Posted by coreys View Post
Whenever I make baddies I just check if a target is in the direction the baddy is facing to do field of view. xP
Now I feel like a chump.
They aren't for checking distances tho

it's to draw pretty lights

But, the only thing I mislike in those scripts is that you edit variables with the same name as the function params Only that, other then that they are very nice
__________________
Reply With Quote
  #5  
Old 03-19-2008, 06:29 PM
DrakilorP2P DrakilorP2P is offline
Registered User
DrakilorP2P's Avatar
Join Date: Apr 2006
Posts: 755
DrakilorP2P is just really niceDrakilorP2P is just really nice
Quote:
Originally Posted by Chompy View Post
They aren't for checking distances tho

it's to draw pretty lights

But, the only thing I mislike in those scripts is that you edit variables with the same name as the function params Only that, other then that they are very nice
Only small adjustments are required in order to check if a particular baddy have a clear line of sight to the intended target.
PHP Code:
function lineOfSight(x0y0x1y1)
{
  
// 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 x0ix 1;
  else 
ix = -1;
  if (
y1 y0iy 1;
  else 
iy = -1;
  
  if (
onwall(x0y0)) return false;
  
  if (
dx >= dy) {
    
error dy - (dx >> 1);
    
    while (
x0 != x1) {
      if (
error >= 0) {
        if (
error != || (ix 0)) {
          
y0 += iy;
          
error -= dx;
        }
      }
      
      
x0 += ix;
      
error += dy;
      
      if (
onwall(x0y0)) return false;
    }
  }
  else {
    
error dx - (dy >> 1);
    
    while (
y0 != y1) {
      if (
error >= 0) {
        if (
error != || iy 0) {
          
x0 += ix;
          
error -= dy;
        }
      }
      
      
y0 += iy;
      
error += dx;
      
      if (
onwall(x0y0)) return false;
    }
  }
  
  
// Success
  
return true;

If you want distance with that, add a counter or employ trigonometry in a separate function.
Reply With Quote
  #6  
Old 03-19-2008, 07:03 PM
Tigairius Tigairius is offline
The Cat
Tigairius's Avatar
Join Date: Jan 2007
Location: Missouri, USA
Posts: 4,240
Tigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant futureTigairius has a brilliant future
Wow, nice.
__________________


“Shoot for the moon. Even if you miss, you'll land among the stars.”
Reply With Quote
  #7  
Old 03-19-2008, 10:06 PM
cbk1994 cbk1994 is offline
the fake one
cbk1994's Avatar
Join Date: Mar 2003
Location: San Francisco
Posts: 10,718
cbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond reputecbk1994 has a reputation beyond repute
Send a message via AIM to cbk1994
Amazing.
__________________
Reply With Quote
  #8  
Old 03-19-2008, 10:33 PM
Inverness Inverness is offline
Incubator
Inverness's Avatar
Join Date: Aug 2004
Location: Houston, Texas
Posts: 3,613
Inverness is a jewel in the roughInverness is a jewel in the rough
Excellent.
__________________
Reply With Quote
  #9  
Old 03-20-2008, 12:59 AM
smirt362 smirt362 is offline
Tee Hee
smirt362's Avatar
Join Date: Feb 2005
Location: Texas
Posts: 2,101
smirt362 has a brilliant futuresmirt362 has a brilliant futuresmirt362 has a brilliant futuresmirt362 has a brilliant futuresmirt362 has a brilliant futuresmirt362 has a brilliant futuresmirt362 has a brilliant future
Send a message via AIM to smirt362 Send a message via MSN to smirt362
Well that is just plain nifty.
__________________

Don Hertzfeldt <3
Reply With Quote
  #10  
Old 03-20-2008, 01:07 AM
xAzerothx xAzerothx is offline
Banned
Join Date: Aug 2006
Location: Gurnee, Illinois
Posts: 2,615
xAzerothx has a little shameless behaviour in the past
Send a message via AIM to xAzerothx Send a message via MSN to xAzerothx Send a message via Yahoo to xAzerothx
Is it bad if I don't understand what its used for?
Reply With Quote
  #11  
Old 03-20-2008, 02:36 PM
Chompy Chompy is offline
¯\(º_o)/¯
Chompy's Avatar
Join Date: Sep 2006
Location: Norway
Posts: 2,815
Chompy is just really niceChompy is just really niceChompy is just really nice
Send a message via MSN to Chompy
Quote:
Originally Posted by xAzerothx View Post
Is it bad if I don't understand what its used for?
no, it's good, but maybe bad for you since you don't know how to use it?

Anyways, the fun thing with this is if you add some sleep()'s inside the loops you can see how they act/work (Ie, going one line at a time and which direction they go in etc.)
__________________
Reply With Quote
  #12  
Old 03-22-2008, 08:07 PM
Dan Dan is offline
Daniel
Join Date: Oct 2007
Posts: 383
Dan is an unknown quantity at this point
Send a message via MSN to Dan
Nice. I like your tip Chompy hehe.
__________________
Reply With Quote
  #13  
Old 03-22-2008, 08:56 PM
Galdor Galdor is offline
░▒▓██▓▒░
Galdor's Avatar
Join Date: Feb 2004
Posts: 2,434
Galdor has a reputation beyond reputeGaldor has a reputation beyond reputeGaldor has a reputation beyond reputeGaldor has a reputation beyond reputeGaldor has a reputation beyond reputeGaldor has a reputation beyond reputeGaldor has a reputation beyond reputeGaldor has a reputation beyond repute
wow thats kinda cool =)
__________________
Links
Draenin's Villains
Draenin's Quests

My Albums
Quote:
Originally Posted by Unixmad
This forums is going worst each day.
Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 11:37 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.