# OrangyTang

Member

6170

1298 Excellent

• Rank
Legend
1. ## Solved

Um, did you check out the code I posted? It should be much, much faster than the brute force stepping approach.
2. ## Curves 2

Almost forgot, you'll need this semi-voodoo code as well: /** Length of a subsection of the curve, from the start (t=0) to the tMax specified. */ private float lengthTo(float tMax) { assert (tMax >= 0f && tMax <= 1f); return gaussianQuadrature(0f, tMax); } /** Get the speed at any given point on the curve. * Caution: Requires a square root operation. */ public float speed(float t) { // Speed is the magnitude of the velocity vector at point t Vector2f vel = velocity(t); return (float)Math.sqrt(vel.x*vel.x + vel.y*vel.y); } /** Find the velocity at a given point on the curve */ public Vector2f velocity(float t) { return velocity(t, new Vector2f()); } public Vector2f velocity(float t, Vector2f dest) { assert (t >= 0f && t <= 1f); assert (dest != null); // Calculate the first derivative of the curve, which is the velocity at that point // Cubic equation is: // (1-t)^3*p + 3t(1-t)^2*q + 3t^2(1-t)*r + t^3*s // Expanded is: // (-t^3 + 3t^2 - 3t + 1)p + (3t^3 - 6t^2 + 3t)q + (3t^2 - 3t^3)r + (t^3)s // So First Derivative is: // (-3t^2 + 6t - 3)p + (9t^2 - 12t + 3)q + (6t - 9t^2)r + (3t^2)s float t2 = t*t; // Find weights float w0 = -3*t2 + 6*t - 3; float w1 = 9*t2 - 12*t + 3; float w2 = 6*t - 9*t2; float w3 = 3*t2; float vx = startPoint.x*w0 + controlPoint1.x*w1 + controlPoint2.x*w2 + endPoint.x*w3; float vy = startPoint.y*w0 + controlPoint1.y*w1 + controlPoint2.y*w2 + endPoint.y*w3; dest.set(vx, vy); return dest; } // Holy crap! Magical voodoo code! // Performs some kind of numerical intergration, which we use here on the speed, giving us the length // of the curve private float gaussianQuadrature(float fA, float fB) { // Legendre polynomials // P_0(x) = 1 // P_1(x) = x // P_2(x) = (3x^2-1)/2 // P_3(x) = x(5x^2-3)/2 // P_4(x) = (35x^4-30x^2+3)/8 // P_5(x) = x(63x^4-70x^2+15)/8 // Generation of polynomials // d/dx[ (1-x^2) dP_n(x)/dx ] + n(n+1) P_n(x) = 0 // P_n(x) = sum_{k=0}^{floor(n/2)} c_k x^{n-2k} // c_k = (-1)^k (2n-2k)! / [ 2^n k! (n-k)! (n-2k)! ] // P_n(x) = ((-1)^n/(2^n n!)) d^n/dx^n[ (1-x^2)^n ] // (n+1)P_{n+1}(x) = (2n+1) x P_n(x) - n P_{n-1}(x) // (1-x^2) dP_n(x)/dx = -n x P_n(x) + n P_{n-1}(x) // Roots of the Legendre polynomial of specified degree final int iDegree = 5; final float s_afRoot[] = { -0.9061798459f, -0.5384693101f, 0.0f, +0.5384693101f, +0.9061798459f }; final float s_afCoeff[] = { 0.2369268850f, 0.4786286705f, 0.5688888889f, 0.4786286705f, 0.2369268850f }; // Need to transform domain [a,b] to [-1,1]. // If a <= x <= b and -1 <= t <= 1, then x = ((b-a)*t+(b+a))/2. float fRadius = 0.5f * (fB - fA); float fCenter = 0.5f * (fB + fA); float fResult = 0.0f; for (int i=0; i<iDegree; i++) { fResult += s_afCoeff[i] * speed(fRadius * s_afRoot[i] + fCenter); } fResult *= fRadius; return fResult; } public float length() { return gaussianQuadrature(0f, 1f); }
3. ## Curves 2

I fought with this a while ago - and was surprised to find that a proper analytical solution is actually impossible. Here's the best solution I could find. Basically you'll animate over your curve's length, then use the below function to convert the length to a T value (0-1), and then use that to actually find the 2d point on the curve. /** Takes a position (length) along the curve and finds the corresponding time (t) value. * Position is always in the range of [0, curveLength] * Time is always in the range of [0, 1] */ public float getTimeFromPosition(float position) { assert (position >= 0-epsilon); assert (position <= length()+epsilon); if (position <= 0) return 0.0f; if (position >= length()) return 1.0f; // Newton's method makes an initial guess and progressivly refines it final int maxIterations = 128; final float tolerance = 0.5f; // Initial guess float l = length(); float time = position / l; float difference = 0f; for (int i=0; i<maxIterations; i++) { difference = lengthTo(time) - position; if (Math.abs(difference) < tolerance) return time; float s = speed(time); time -= (difference / s); // Clamp time to [0,1] range time = Math.max(time, 0f); time = Math.min(time, 1f); } // Newton's method failed to converge. // If this happens, increase iterations, tolerance or integration accuracy. // assert (false) : "Failed to converge, closest position is "+difference+" out."; // Return current best guess return time; } Hopefully the code makes sense. It basically takes a guess (on the assumption that T is linear across the length) and refines it in several increments.
4. ## Digital Test Cards For Games

Quote:Original post by PolyVox Hey, very cool! You seem to have most stuff covered, though it might be interesting to include some HDR tests. Is it under any particular license? Creative commons, etc? Although HDR test images would be cool, I don't do HDR myself so I'm not sure I know what would need to be included and what constitutes useful test data. I've updated the original post with license info (Creative Commons 2.0).

6. ## Revolution, Part 1: Audio

Ok, I am officially creeped out. o_O The ghost doesn't sound quite as creepily real, but I'm guessing that's due to it being only 8 seconds. I can imagine there being a whole host of unique iPhone games that could come out of this.

Yeah, that's an approach I've heard a few people try (or think about trying). It does seem like a good idea in that you don't have to write an entire gui library and you get to write the logic in javascript. I usually dislike writing html and javascript, but if you're only targeting your own embedded browser it would probably be a whole lot easier - javascript is IMHO quite a nice language, it's cross-browser issues that make most people hate it.

Sometimes you get an idea that's a little bit oddball but for some reason you can't get out of your head and just have to run with it. This has been bouncing around my head for the last couple of days and has just been translated into code: Yes, I embedded a web server inside of Rescue Squad and as well as static content (like the images) it can serve up live render stats direct from the game engine. I'm pleasantly surprised how easy it was, it only took about an hour to grab NanoHttpd, integrate it and slightly tweak it to also serve a (semi)hardcoded stats page. I plan to extend this somewhat to make it more useful, like having multiple (cross linked) pages of stats, a logging page containing trace messages, and possibly a resource/texture/rendertarget viewer as well. Any suggestions as to what else to (ab)use http for are welcome. :)
9. ## Renderer Optimisations Part 1

Thanks. [grin] It's written in Java with LWJGL for display and graphics and Jython for scripting.
10. ## Two months later...WTF?

LWJGL is a good choice and what I use, it's stable and stays out of your way letting you code how you want. You might also want to check out Slick, it's a rather neat 2d library built on top of LWJGL and lets you get right into the meat of the game rather than messing around with openGL directly.
11. ## Renderer Optimisations Part 1

After I upgraded to a 720p display format (rather than just 800x600) the framerate took a little bit of a dip on my slower machine. Understandable really as it's drawing quite a few more pixels - 921k rather than 480k in the worst case, ignoring overdraw. I've spent the last few days optimising the renderer to see how much of the performance I could get back. Firstly, you've got to have some numbers to see what's working and what isn't, so I added a debug overlay which displays all kind of renderer stats: The top four boxes show stats for the four separate sprite groups - main sprites are visible ones like the helicopters and landscape, lightmap sprites contains lights and shadows, sonar sprites are used for sonar drawing, and hud sprites are those that make up the gui and other hud elements like the health and fuel bars. The final box at the bottom shows per-frame stats such as the total number of sprites drawn and the framerate. Most suprising is the "average batch size" for the whole frame - at only 4.1 that means that I'm only drawing about four sprites per draw call, which is quite bad. (Although I call them sprites there's actually a whole range of "drawables" in the scene, water ripples for example are made of RingGeometry which is a ring made up of many individual triangles, but it's easier to call them all sprites). Individual sprite images (such as a building or a person) are packed into sprite sheets at compile time. In theory that means that you can draw lots of different sprites in the same batch because they're all from the same texture. If however you're drawing a building but then need to draw a person and the person is on a different sheet, then the batch is "broken" and it's got to start a new one. To test this out I increased the sprite sheet size from 512x512 to 1024x1024 and then 2048x2048. For the main sprites (which is the one I'm focusing on) this pushed the average batch count up from 5.3 to 5.6 and then 16.2. Obviously the texture switching was hurting my batch count - 16 would be a much more respectable figure. Unfortunately not everyone's graphics card can load textures that big, which is why I'd been sticking to a nice safe 512x512. However further investigation found that the sprite sheets weren't being packed terribly efficiently - in fact packing would give up when one sprite wouldn't fit and a new sheet would be started. This would mean that most sheets were only about half full - fixing the bug means that almost all of the sheet is now used. Below you can see one of the fixed sheets, with almost all the space used up. Along with this I split my sheets into three groups - one for the landscape sprites (the grass and coast line), one for world sprites (helicopters and people) and one for gui sprites. Since these are drawn in distinct layers it makes sense to keep them all together on the same sheets rather than randomly intermingling them. One last tweak was to shave off a few dead pixels on some of the larger sprites - since they were 260x260 it meant that only one could fit onto a sheet and would leave lots of wasted space. Trimming them down to 250x250 fits four in a single sheet and is much more efficient. Overall these upped the batch count for main sprites up to a much more healthy 9.2, reducing the number of batches from ~280 to ~130. Good, but there's still optimisations left to be done...
12. ## HD Rendering Is The New Black

You're welcome! Dealing with different resolutions and aspect ratios is one of the few areas where 3d games have it much easier. I've yet to find a method for 2d that gives perfect results everywhere, but this approach seems to be the best solution so far.
13. ## HD Rendering Is The New Black

I decided that the searching aspects of the gameplay are largely ruined by showing a larger area of the map at larger resolutions, so I've ruled that out as a possible way of dealing with multiple resolutions. Instead I've decided to pinch a trick from console games - the game world will internally always be rendered to a "720p" texture, and then that'll be streched over the full screen to upscale or downscale to the native resolution as appropriate. I say "720p" because (similar to how tvs do things) there isn't a single fixed resolution, instead it'll always be 720 lines vertically, and the number of horizontal pixels will vary depending on the aspect ratio. So someone with a 16:9 screen will have a virtual resolution of 1280x720, whereas those on 4:3 displays will have 960x720. In windowed mode the virtual resolution always matches the physical window size, so you still get nice 1:1 graphics when viewed like this. For fullscreen the streching may mean you'll get some loss of sharpness but doing it manually in-game gives much better quality than letting the user's TFT do the scaling. The menus are also drawn over the top with a 720p virtual resolution, but without the render-to-texture step (they're just scaled using the projection matrices). The HUD is the exception to the rule in that it's always rendered over the top at the native resolution instead of the virtual resolution. This is possible since the components are all relatively positioned according to the screen edges. Different aspect ratios are also handled tv-style in that anything less that 16:9 has bits of the edges chopped off. That's not a problem as it'll just make those with 4:3 displays a little more blinkered. And to avoid having to have scalable menus or multiple menu layouts I just need to keep the important stuff inside the center 4:3 area, which is easy enough now I've got red guidelines to mark off the areas for different aspect ratios. I think it all works out quite nicely - the code stays (largely) simple because it's all dealing with a single virtual resolution, the whole game looks better because it's natively at somethingx720 instead of 800x600, windowed mode still looks nice and crisp with 1:1 sprites and everyone gets the game in the correct aspect ratio - even in fullscreen.
14. ## Ooo, pretty...

So I was screwing around with some random bits of polish in the game and realised that I havn't tried fullscreen since I got my shiny new widescreen monitor a few months back. Unfortunately since the game is always rendered at 800x600 (and therefore a 4:3 aspect ratio) it looks a bit rubish when streched over a 16:10 display. An hour of hacky tinering and it's running at the native res and aspect ratio, and the results are rather pretty I think: (click for full size version) I was surprised to find that only a few things were resolution-dependant. The HUD was the most obvious, since it used hard-coded positional values, so it now uses relative offsets from the screen edges. The menus are all borked too, since they're hardcoded to 800x600 so end up huddled in the bottom corner, I'll worry about them later. The problem is that I think it breaks the gameplay - searching and exploring the map is a large part of the fun and challenge, and you don't get that when you can see half or a third of it on screen at a time. In fact it makes some maps laughably easy. But visually it looks so good I'm not sure I want to let it go. Decisions decisions...
15. ## Java4k 2009 Results

The results are up for the 2009 4k competition, with my NiGHTS 4k entry coming a rather satisfying 11th! W00t! Unsurprisingly (and deservingly) Left 4k Dead takes the top spot, and the worryingly addictive Bridge4k second. In fact pretty much all of the top games are worth playing, there's a surprising amount of content shoe horned into some of the games.