cool stuff, seems to be “in”.
I just played a game at kongregate,
remembered me of a Java4k game 
what a shame that kongregate is pure flash…
Thanks for the tips guys. I’m slowly figuring out openGL so hopefully I’ll soon have a demo with shadows and fast, smooth alpha-blended gradients.
That’s a cool game, hmm what a pity about kongregate. Thanks for the link. That game reminded me of that WWII game ‘Green Berets’ where you sneak around and avoid the enemies. We should make something like that
I have almost got one working thats practically 100% shaders. Set the light position. Paint geometry with shadow polys, the shader sets the shadow polys to the correct place and shades them. No textures required either, and you can have the geometry as a single display list etc. There is some slight artifacts that can be delt with more or less, but i have not bothered.
Ha, I love the variety of techniques that people are taking here.
I’ve discarded four different attempts now (three custom ones of my own, one JTS-based one and one based on CommanderKeith’s code) because they’ve all been too unstable or produced artefacts when in game-like environments.
My fifth attempt is based on j2d CSG methods and (fingers crossed) seems much more stable. It’s not soft but it should produce nice results when rendered via LWJGL I hope. I’m a bit worried about performance and how much garbage it’ll create but I should be able to make some higher level optimisations to reduce the actual CSG ops to a minimum.
So hard shadows works very nicely. The shader is less than 20 lines of code and we only need a pass per light. The restriction? The light should not be inside an lightblocker.
So i have worked out all the soft shadow stuff. It would work quite well with only very minor artifacts in very specific situations, and even then would not be that noticable. However i have run out of time… So i wont put them in till i need em. I can make the code avalible for the hard shadows if anyone wants it.
So at a guess you’re masking off shadow regions (like in ye olde article) rather than constructing a visibility poly like CommanderKeith’s method?
Would love to see screenshots/demo of the soft version.
Wow, that’s some cool stuff guys 8) That article’s awesome OrangyTang, I wish I had the link earlier.
I would love to see how your method works delt0r, so few lines of code is pretty amazing!
I also got this from my new gamedev.net account news email, it seems like a way of doing shadows using tiles (but I haven’t read it fully): http://www.gamedev.net/reference/programming/features/wallshadow2d/default.asp
What are the instabilities you’ve found? i can’t produce any artifacts in my demos, i’d be interested to know any edge cases.
There were some cases where I had a single segment shadow caster and moving the light to certain positions caused the cast shadow to be radically off (like 45 deg in the wrong direction). I’m not sure if this is due to it not expecting single-surface objects or numeric precision.
To be honest it could have been an issue with how I was using your code - the interface was somewhat more complicated than I was expecting, I was hoping for something simple like:
Poly calculateVisibility(Point lightPos, ArrayList occulders)
which is how I’ve had all my versions, but you’ve got some complicated multi-step thing going on.
It is quite simply project shadows in 2d --more or less.
Here is the vertex shader:
uniform vec4 lightPoint;
void main(){
vec4 light=vec4(lightPoint.x,lightPoint.y,gl_Vertex.z,1);
light=gl_ModelViewProjectionMatrix*light;
gl_FrontColor = gl_Color;
gl_BackColor = gl_Color;
if(gl_Normal.z==0.0){
gl_Position = gl_ModelViewProjectionMatrix*gl_Vertex;
return;
}
//so now we assume its shadow geometry...
vec4 v=gl_ModelViewProjectionMatrix*gl_Vertex;
//find our distance point and then move our point to the boundry. In this case 3 units
float factor=10/distance(light,v);
gl_Position=light*(1-factor)+v*factor;
}
The fragment shader is just gl_FragColor = gl_Color; . Its not used untill i get round to soft shadows.
The rest of the code is here:
package proto.test.shadows;
import java.io.*;
import java.net.URL;
import java.nio.ByteBuffer;
import java.nio.IntBuffer;
import java.util.Random;
import org.lwjgl.BufferUtils;
import org.lwjgl.LWJGLException;
import org.lwjgl.Sys;
import org.lwjgl.input.Mouse;
import org.lwjgl.opengl.*;
import static org.lwjgl.opengl.GL11.*;
import static org.lwjgl.opengl.GL20.*;
/**
* a simple 2d shadow example. Cus its easer to show as code.
*
* The idea is a simple 2 pass algo. Well for lots of lights its needs more. One pass per light.
*
* first we paint the whole scene with the poly obsructions in the z buffer only. Perhaps we can
* colour these now and avoid having to paint them again. That was pass one.
*
* now set the vertex and frag shaders, and off each line in the previos we paint 4 polys that deal
* with the soft shadows and hard shadow parts. aka we paint shadows. A uniform is the the light
* point and radius.
*
* the orginal shadow geometry is a single line. but by doing cool things with normals we can push
* the correct verts to outside screenspace easily and paint shadow. the only attributes we need are
* normals. No textures required. For this example we will just use a collection of random trangles.
*/
public class ShadowLWGLtest {
// kiss for an example... triangles are nothing more than 3 2d points in the interval -1,1
public static double[][][] generatorOfrandomTriangles(int number) {
Random rand =new Random();
double[][][] tris =new double[number][3][2];
double size =.3;
for (int i =0; i < number; i++) {
double cx =rand.nextDouble() * (2 - 2 * size) - 1 + size;
double cy =rand.nextDouble() * (2 - 2 * size) - 1 + size;
// now a nice tri... at a size of whatever i have in the code.
for (int p =0; p < 3; p++) {
tris[i][p][0] =rand.nextDouble() * size + cx;
tris[i][p][1] =rand.nextDouble() * size + cy;
}
}
return tris;
}
private static StringBuilder getResourceAsString(String s) {
StringBuilder stringBuilder =new StringBuilder();
URL url =ClassLoader.getSystemResource(s);
if (url == null)
throw new RuntimeException("Resource Not Found:" + s);
try {
InputStream is =url.openStream();
if (is == null)
return null;
BufferedReader reader =new BufferedReader(new InputStreamReader(is));
String line =reader.readLine();
while (line != null) {
stringBuilder.append(line);
stringBuilder.append('\n');
line =reader.readLine();
}
} catch (IOException e) {
e.printStackTrace();
return null;
}
return stringBuilder;
}
private static int loadAndDefineShaders() {
int vshader =glCreateShader(GL_VERTEX_SHADER);
int fshader =glCreateShader(GL_FRAGMENT_SHADER);
String vertexShad =getResourceAsString("proto/test/shadows/shadow2dVertex.glsl").toString();
String fragShad =getResourceAsString("proto/test/shadows/shadow2dFragment.glsl").toString();
ByteBuffer vertexPointerString =ByteBuffer.wrap(vertexShad.getBytes());// org.lwjgl.BufferUtils.createByteBuffer(vertexShad.length()+1);
ByteBuffer fragPointerString =ByteBuffer.wrap(fragShad.getBytes());// org.lwjgl.BufferUtils.createByteBuffer(vertexShad.length()+1);
glShaderSource(vshader, vertexPointerString);
glShaderSource(fshader, fragPointerString);
glCompileShader(vshader);
glCompileShader(fshader);
int program =glCreateProgram();
glAttachShader(program, vshader);
glAttachShader(program, fshader);
glLinkProgram(program);
glValidateProgram(program);
System.out.println("Log of vshader");
printLogInfo(vshader);
System.out.println("Log of fshader");
printLogInfo(fshader);
org.lwjgl.opengl.Util.checkGLError();
return program;
// glUseProgram(program);
}
private static void printLogInfo(int obj) {
IntBuffer iVal =BufferUtils.createIntBuffer(1);
ARBShaderObjects.glGetObjectParameterARB(obj, ARBShaderObjects.GL_OBJECT_INFO_LOG_LENGTH_ARB, iVal);
int length =iVal.get();
System.out.println("Info log length:" + length);
if (length > 0) {
// We have some info we need to output.
ByteBuffer infoLog =BufferUtils.createByteBuffer(length);
iVal.flip();
ARBShaderObjects.glGetInfoLogARB(obj, iVal, infoLog);
byte[] infoBytes =new byte[length];
infoLog.get(infoBytes);
String out =new String(infoBytes);
System.out.println("Info log:\n" + out);
}
Util.checkGLError();
}
private static ByteBuffer toByteString(String str, boolean isNullTerminated) {
int length =str.length();
if (isNullTerminated)
length++;
ByteBuffer buff =BufferUtils.createByteBuffer(length);
buff.put(str.getBytes());
if (isNullTerminated)
buff.put((byte) 0);
buff.flip();
return buff;
}
public static void main(String[] args) {
System.out.println(Sys.getTimerResolution());
int targetWidth =1280;
int targetHeight = 1024;
DisplayMode chosenMode =null;
DisplayMode[] modes =null;
try {
modes =Display.getAvailableDisplayModes();
for (int i =0; i < modes.length; i++) {
System.out.println(modes[i] + "\t" + modes[i].getFrequency());
if ((modes[i].getWidth() == targetWidth) && (modes[i].getHeight() == targetHeight)) {
chosenMode =modes[i];
break;
}
}
System.out.println(Display.getDesktopDisplayMode());
// chosenMode =Display.getDesktopDisplayMode();
} catch (LWJGLException e) {
Sys.alert("Error", "Unable to determine display modes.");
System.exit(0);
}
// at this point if we have no mode there was no appropriate, let the user know
// and give up
if (chosenMode == null) {
Sys.alert("Error", "Unable to find appropriate display mode.");
System.exit(0);
}
try {
Display.setDisplayMode(chosenMode);
// Display.setDisplayModeAndFullscreen(chosenMode);
// System.out.println("Mode:"+modes[11]);
// Display.setFullscreen(true);
Display.setTitle("An example title");
Display.create();
} catch (LWJGLException e) {
Sys.alert("Dude", "Unable to create display.");
System.exit(0);
}
//load the shaders
int program=loadAndDefineShaders();
int lightPoint=glGetUniformLocation(program,toByteString("lightPoint", true) );
// set up otho properly.
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(-1, 1, -1, 1, -1.0f, 1.0f);// the default... but lets be sure about that
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glClearColor(1, 1, 1, 0);
glEnable(GL_DEPTH_TEST);
// glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
glDisable(GL_BLEND);
glUseProgram(program);
// now generate some funky geometry.
double[][][] tris =generatorOfrandomTriangles(100);
boolean gameRunning =true;
float pos =0;
int c =0;
while (gameRunning) {
// perform game logic updates here
Mouse.poll();
double dx=(double)Mouse.getX()/targetWidth;
dx=dx*2-1;
double dy=(double)Mouse.getY()/targetHeight;
dy=dy*2-1;
pos +=0.00f;
c++;
// render using OpenGL
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
glBegin(GL_TRIANGLES);
{
for (int i =0; i < tris.length; i++) {
for (int p =0; p < 3; p++) {
glColor3d(1, 0, 0);
glNormal3d(0,0,0);//pined
glVertex3d(tris[i][p][0], tris[i][p][1], 0.1);
}
}
}
glEnd();
System.out.println("mouse "+dx+" "+dy);
//now load my shaders...
//glUseProgram(program);
glUniform4f(lightPoint, (float)dx, (float)dy, 0, 0);
//paint some shadows. first set the light postion with a uniform.
glBegin(GL_TRIANGLES);
{
glColor3d(0, 0, 0);
for (int i =0; i < tris.length; i++) {
for (int p =0; p < 3; p++) {
//For each edge draw 2 triangles
double[] p1=tris[i][p];
double[] p2=tris[i][(p+1)%3];
glNormal3d(0,0,0);//pined
glVertex3d(p1[0],p1[1],0);
glNormal3d(0,0,1);//moves
glVertex3d(p1[0],p1[1],0);
glNormal3d(0,0,1);//moves
glVertex3d(p2[0],p2[1],0);
//2nd triangle
glNormal3d(0,0,1);//moves
glVertex3d(p2[0],p2[1],0);
glNormal3d(0,0,0);//pined
glVertex3d(p2[0],p2[1],0);
glNormal3d(0,0,0);//pined
glVertex3d(p1[0],p1[1],0);
}
}
}
glEnd();
// now tell the screen to update
Display.sync(60);
Display.update();
// System.out.println(Sys.getTime()+"\t"+System.nanoTime());
// finally check if the user has requested that the display be
// shutdown
if (Display.isCloseRequested() ) {
gameRunning =false;
Display.destroy();
System.exit(0);
}
}
}
}
I pin vertexs by just setting the normal.z to zero. Its pretty hacky… 
Oh and is all under a BSD license or whatever. Nothing here to be proud of, but if the soft shadows work well…
Yeah, that’s the same general idea of masking/carving the shadows out of the light in the framebuffer, although putting it in a shader is a neat trick.
I’ve found it to be the most robust but it burns fill rate something awful in complex scenes due to needing a pass per light and lots of shadow overdraw. But on the plus side if you’re doing a pass per light you can do proper bumpmapped lighting too and it gives you more options for casting shadows off sprites too.
By single surface objects do you mean a line or a set of collinear points? I never did consider that, I always assumed the occluders were proper 3+ pointed non-overlapping polygons. Thanks for pointing that out.
Yeah sorry, I’ve optimised that code to hell so it got slightly more complicated than the simple form you’re looking for. Basically I assume that the original sight polygon doesn’t change shape so it’s efficient to pre-calculate and cache some things once instead of every frame. I’ll make a version like you suggest in the next update.
Wow that’s pretty full on, I’ll have to learn more about openGL before I understand what’s happening! Looks very clever, thanks for posting it up 8)
Just a single 2d segment with start and end points.
A simpler interface to your stuff would be cool, I was cheating and passing everything in as moving objects. Although I can see a need for that kind of static/moving split, it’d be good if there was a simple way of calculating the intersection points. IIRC most physics apis get around this by having you create the geometry and then returning it in ‘baked’ form - a single object with all the precalculation associated with it.
Ah ok, yeah my code won’t be able to cope with unclosed lines, everything has to be a polygon. But you could make a really skinny polygon that looks like a line
I’ve got to stop optimising and thinking of new features and just use this in a game somehow
I have my doubts that anything but a really old card will have problems with fill rate on these days. When you move down to something like the iPhone, they don’t have enough pixels to use fill rate anyhow. There are also tricks one can use to get the zbuffer to fail tests when the area is already shadow. If you want 30 lights sure thats going to hurt some, but you going to have the same problem with “painting” light just as much as “painting” with shadow.
Hi… This looks pretty cool. I am new here and new to Java UI stuff in general. I hope this threadomancy is not frowned upon.
I am one of the (small)contributers to an OSS project called Maptool(RPTools.net) which is used as a Virtual Table top for playing Roleplaying(and some board games) over a network connection allowing multiple connected clients. It currently has an implementation of line of sight, currently using the base java Geometry classes such as AffineTransform and Area to draw stuff to the screen. The current program supports several optional features: Fog of war, including “soft fog”, light, vision shapes(circle, square, and conic(including facing and optional offset degrees) and ranges, as well as creation of vision blocking materials(exactly as your walls block vision in the demo).
Currently, the existing code works, however, complex shapes(when combining the vision blocking, light/vision overlaps and cutting out the FOW overlay) make the rendering code most likely much slower than the presented implementation. While it is acceptable for a good majority of people unless they just go crazy with the stuff, there are a number of features desired which are being delayed to avoid taxing the speed even further. Anyway, our lead developer(trevorscroft on this forum) had found this last year and was very impressed and was hoping to implement this in the next version of the product. However, as can happen sometimes, real life has gotten in the way. This brings me here to perhaps see if I can get nudge in the right direction in perhaps using the JTS stuff into our project if possible…
Any comments would be helpful.
EDIT Oh… one other thing I forgot to mention. Currently, we don’t have a means to calculate if a point can intersect with another object(without going through another geometry!!!), and was wondering if the base JTS has something that would allow this.
http://dl.dropbox.com/u/77426/CantSee.jpg
http://dl.dropbox.com/u/77426/CanSee.jpg
For example In the first image, there is no line of sight to the box and I was hoping there would be a fairly easy(read fast processing wise and low memory wise) method of determining that the vision origination point does not in fact have line of sight to the drawn box. Likewise, as a second case it would be true that the vision can see the drawn box.
Hi jfrazierjr,
Your project looks cool, have you got any big screenshots on your site? 8)
From the image at the top of the site, it looks like you are using a tile-based setup, so I’m not sure if this shadow algorithm is necessary, it might be easier to just do a tile-based shadow algorithm.
The code I posted here is best used for games where the units are not constrained to tiles.
Sure, you can iterate through SightField.sightPoints to find the SightPoint which is either a SPShadowPointObst or a SPObstPoint, and both of these objects have a ‘polygon’ field which will be the drawn box polygon if it is visible.
I’ve been making edits to the code and was thinking about turning into a google code project, so I’ll keep you posted when that happens.
Thanks for the comments!
Keith
PS: it is not well advertised but the latest JTS download is here: http://sourceforge.net/projects/jts-topo-suite/
I was using an old out of date one on the vividsolutions website which was buggy. Just thought I’d mention it so you don’t have the same problems!
Not sure about big screenshots, but there are a number of kind of video demos/tutorials in video available via youtube and rptoolstutorials.net. There are some screenshots scattered around the forum and galleries, but I can’t really give you any more details.
Oh… and I don’t want to take credit for Maptool. Trevor is the one who has put in 99.9% of the code over the past 5is years… me and a few other guys have done a few small features and bug fixes.
Not quite sure what you mean by tile based setup… read below…
Thanks for the update on the new JTS version… Will have to grab it. Actually, if my thinking is clear, the easiest way to see if pointA has line of sight to shape B is by using an A*Pathfinder (I saw the updated you JUST did which is super fast!!) and see if the calculated path contains more than 2 nodes… Does that sound right?
As for the vision blocking stuff, which would perhaps at some point be some type of implementation PathBlockingObstacle in your sample code. Currently, the creator uses a drawing tool to build up the various LOS blocking objects which are implement currently via the java.awt.geom.area class and stored for later use during the rendering (from a cache). The current implementation can do filled rectangles, hollow rectanges, filled circles(Ellipse2D objects), hollow circles, closed polygon, and polyline(which I believe is a really thin polygon).
At this point, I would hope to not have to rewrite those tools(well… at least not right away) and be able to figure out a way to convert those areas into a JTS Polygon and them combine them as needed into a geometry and then use that as a base for the LOS calculations. But I am having a problem figuring out just how that might be done…
Oh… and if your looking for yet another another side project… we would be glad to have the expertise… :
Ok I checked out this video (http://www.rptoolstutorials.net/videos/What_is_MapTool1/What_is_MapTool1.html) and I must say that I’m quite impressed. You seem to already have a decent shadow algorithm and your tools to add graphics look very flash. I take back the tile-based comment - your graphics are completely free-form which is great, just what I’m trying to achieve. I like how the map editor has lots of different environments - forest, space, dark/night, etc.
Cool, glad to hear it’s working well. That’s one way to figure out LOS for sure but it’s a little indirect. I’ll put up an example of how to figure out if an obstacle is visible or not using the LOS code… it’s just that whenever I take another look at the code I think it’s a mess and can’t stop refactoring…
It’s not too hard to convert stuff into a JTSPolygon, but this is not what my code uses under the hood - I only use JTS to buffer polygons (shrink or grow them by a fixed increment, which is different to a scaling operation). The LOS code here uses a basic polygon class that’s pretty much just an ArrayList of points.
I wish I had time to get involved because what you’re doing looks really cool, but I can barely find time to make progress on my own projects. But I’d be very happy to help you with any advice or adding some feature to the API to make it easier for you to use/adapt