[flash width=480 height=320]http://64digits.com/users/DesertFox/alpha_test_v2.swf[/flash]
Minor alpha test of my Flash-SAT port, math-optimized build. 72 raycasts per frame, drawing raycast results and level. The level is generated from a tileset.Runs decently fast, and in standalone tests, I can do 100000+ raycasts per second (360 rays per frame, 300+ fps), if I don't draw the raycast results, even with drawing the level. Not too shabby, all things considered.I really need to opti mize the line-drawing code, because if I do draw the line results, that 300 fps drops to 40. Thank god I'll never actually need to draw 360 raycasts per frame.*Note - all framerates are in the standalone player unless otherwise noted. In-browser performance is usually a bit slower.Obligatory spiel for CNAlso, some of you should join Cybernations - it doesn't take up too much time, and if you join, it will get Hero off my back about getting people to join :DSeriously, its an interesting game if a bit slow paced, and it doesn't take up too much time. Humorous things happen to stupid people, wars are fought and won (or lost), and political turmoil was had for all!
I created something like this in GM using objects as pixels. Needless to say, it was very slow.
Yay! Ray caster!!
Very fast O-oDF <3Now make a voxel raytracer and you'll be my BFF.
Actually making a per-voxel raytrace hit detection would not be that hard, because with voxels it is either filled or not - and you get massive speed increases if you have some sort of BSP tree. 2D to 3D would be easy too :3
*does a bit of CODES*I'll probably post some nice voxel-traversal pseudocode soon.Here's the basic algorithm for pixel traversal. I've edited it for per-pixel tests, with pixels being either FULL or NOT_FULL. I have also neglected bound-checking so if you try to test a pixel that isn't in the array, it *will* error (index out of range, anybody :D). I may have made a mistake somewhere (it is pseudocode) but I've commented with what I'm trying to do and where. Also, read the pdf I supplied in the comments.
This algorithm should be fairly efficient - even more efficient than my flash implementation, as it is doing a simple boolean filled-or-not check instead of doing a ray-polygon intersection test.A final note, when doing actual raycasts, you will probably want to cast from the center of the pixel (Pixel.X + 0.5, etc). If you have a specific pixel target position (and not just an angle) you should also cast towards the center of that pixel.Array voxels is a 3D array of voxels, with a method of determining whether they are filled or not.Point origin is the starting 3-dimensional point origin of the raycast.Point target is point in space that the origin will cast towards.int max_len is the maximum number of pixels to check. It is not the max distance, but is a rough approximation of. You could probably easily modify the for loop for actual distance.//This voxel raycast/pixel-traversal algorithm based on: // <a rel="nofollow" href="http://www.cse.yorku.ca/~amana/research/grid.pdf">http://www.cse.yorku.ca/~amana/research/grid.pdf</a> //returns either the collision point, or null if no collisions within max_len pixel checks function RaycastVoxel(Array voxels, Point origin, Point target,int max_len) returns Point { //XYZ Pixel start int X=floor(origin.X); int Y=floor(origin.Y); int Z=floor(origin.Z); //if you are casting from a filled pixel, STOP and return it if(voxels[X,Y,Z] is not empty) return new Point(X,Y,Z); //do we increase or decrease on step? float stepX = 1; if(origin.X > target.X) stepX = -1; float stepY = 1; if(origin.Y > target.Y) stepY = -1; float stepZ = 1; if(origin.Z > target.Z) stepZ = -1; //position along "ray" at each boundary float tMaxX = 0; float tMaxY = 0; float tMaxZ = 0; //set up initial position - basically "where is origin.X/Y/Z in the pixel?" if (stepX == 1) tMaxX = ceil(origin.X) - origin.X; else tMaxX = origin.X - floor(origin.X); if (stepY == 1) tMaxY = ceil(origin.Y) - origin.Y; else tMaxY = origin.Y - floor(origin.Y); if (stepZ == 1) tMaxZ = ceil(origin.Z) - origin.Z; else tMaxZ = origin.Z - floor(origin.Z); //origin-to-target length float tDelta=sqrt( (target.X-origin.X) * (target.X-origin.X) + (target.Y-origin.Y) * (target.Y-origin.Y) + (target.Z-origin.Z) * (target.Z-origin.Z) ); //if ray origin in right on boundary, assume its in the pixel //that is further/greater along that axis if(origin.X==X)//on X boundary between points { tMaxX = tDeltaX; if (stepX == -1) tMaxX = 0; } if(origin.Y==Y)//on Y boundary between points { tMaxY = tDeltaY; if (stepY == -1) tMaxY = 0; } if(origin.Z==Z)//on Z boundary between points { tMaxZ = tDeltaZ; if (stepZ == -1) tMaxZ = 0; } //tDeltaN = tDelta/(target.N - origin.N); //unless (target.N - origin.N) is zero (DIVIDE BY ZERO ANYONE?) //in which case, tDeltaN = 0 and tMaxN = infinity (or 9999999 for numeric sake) if(origin.X == target.X)//X/Y/Z delta is zero { tDeltaX=0; tMaxX=999999; } else { tDeltaX = tDelta/abs(target.X - origin.X); tMaxX = tDeltaX * tMaxX; } if(origin.Y == target.Y) { tDeltaX=0; tMaxX=999999; } else { tDeltaY = tDelta/abs(target.Y - origin.Y); tMaxY = tDeltaY * tMaxY; } if(origin.Z == target.Z) { tDeltaZ=0; tMaxZ=999999; } else { tDeltaZ = tDelta/abs(target.Z - origin.Z); tMaxZ = tDeltaZ * tMaxZ; } //traverse pixels, checking a maximum of max_len pixels for (int i = 0; i < max_len; i++) { if(tMaxX < tMaxY && tMaxX < tMaxZ) { tMaxX = tMaxX + tDeltaX; X = X + stepX; } else if (tMaxY < tMaxX && tMaxY < tMaxZ) { tMaxY = tMaxY + tDeltaY; Y = Y + stepY; } else { tMaxZ = tMaxZ + tDeltaZ; Z = Z + stepZ; } if (voxels[X,Y,Z] is not empty) return new Point(X,Y,Z); } return null;//no collision within max_len pixel checks }OMG *yoink* *run*
Then much editing as pasting it turns into more of a barf then a clean sheet of code….