ダニエルの冒険

The FYP is finally complete! Weighs in at 28,465 words.. 135 pages printed (106 pages excluding title/TOC/etc and appendices).

Report (PDF, 2.06MB)

I just went to Tilmitt’s house to check out how well YakumoDemo would work (or if it would work at all) on a non-development machine.

At first, it was just crazy slow. When adding an object to the sphere, it would lock up for about a second or two. The framerate was averaging about 1.3fps. I opened perfmon to see what was going on, and saw that CPU usage was about 24%, but that figure was for all the cores. When I opened taskmgr I saw that the first core was being totally choked. But what was even more interesting was that when it started to get choked, YakumoDemo’s screen went black, then grey, then totally locked up.

It turned out that when taskmgr was active, it would always freeze when adding a new object to the sphere! I tried changing the affinity of the process to use only two of the four cores on his system and it was performing fine, just like at home. It chugged a bit but no real problem. Then I changed it to use only one core, and it was perfectly fast!! Keep in mind that all the threading code was totally unchanged.. the thing is still using about a dozen threads, but by throwing out all the other cores, it was dramatically faster! The only explanation I can imagine is Tilmitt’s: Vista’s threading model ends up moving threads between cores a lot. If there’s a lot else going on, maybe it takes a thread off a core and lets some other process use it, then tries to find a new core for the thread, which takes time? I don’t know…

Anyway, here’s the last-minute hack I put in to fix it:

// Due to some problem with either the Vista threading model,
// Havok's multithreading, or both, everything currently runs
// faster if only one core is used.
{
	// Find the number of cores available on this system.
	SYSTEM_INFO sysinfo;
	GetSystemInfo( &sysinfo );
	int cores = sysinfo.dwNumberOfProcessors;
	// Set this process to use only the last core.
	SetThreadAffinityMask( GetCurrentThread(), cores-1 );
}

Yesterday was Demo Day and apart from a lot of setup problems it went really well. At first, the monitor kept displaying everything in yellow, and I couldn’t get the iPod on the same subnet as the PC until I got my own wireless router set up, but after that it went pretty smoothly. I’m still recovering though: my back is sore from dragging around the PC/laptop/monitor/wireless router/bag of cables and I still haven’t recovered from this week’s sit-a-thon. Also, last night when I was trying to go to sleep I kept getting images of that big green ball rolling around with various objects attached to it though, and this morning when I knocked over some bottles of shampoo in the shower, for an instant I thought that the movement was slightly unrealistic. I made a mental note to try changing the shape radius of the bottles… and then the instant was over and I reminded myself that I don’t need to evaluate how real every physical interaction I see is anymore.

The most enjoyable thing yesterday was seeing people get really involved with the game. Because the player’s objective is to grow the size of the ball, they seemed to get an emotional involvement in that ball. I always felt the same with Katamari Damacy and it was really rewarding to see other people reacting the same way. Two people played it through to the end, and many others went as far as they could. Unfortunately some of the early players couldn’t actually finish the game because I hadn’t fully finished tweaking it, but as players went as far as they could, I would make a note of what was stopping them and make the change for the next player. for example, for an object to attach to the sphere, it must be 0.006 times the sphere’s volume. I changed this to 0.0064 and then people were able to attach to the milk/juice cartons and clear up the whole room. I also saw cases where a player had picked up everything they could, but the volume ratio was about 0.0061 or even less, so I added a couple more gameboys to the room.

One thing that might invalidate some of the playtesting is that I was playing a pretty big part in the gameplay. It was more like Dungeons and Dragons than Katamari Damacy, in that sense. If I felt that a player was getting discouraged, I helped them by directing them to the next goal, or reminding them how close they are to being able to stick to all those bananas (“just get those two matchboxes and you should be able to roll up the bananas and apples and then you’ll be well on your way to finishing it!”).

My second reader is just as much a fan of Lafcadio Hearn (Koizumi Yakumo) as I am, so he was pretty excited even just about the name “Yakumo”. Lots of other people seemed interested too, and even though I was in the very corner of the room I seemed to have a bit of a queue sometimes. One or two of my friends had to wait about 10 or 20 minutes in line to get to talk to me! The game itself seemed to take about 10~15 minutes to complete, and there were some interesting questions.

Actually, about questions: I didn’t feel like I had to do much presenting or that people had many questions. As I was hoping the game seems to stand pretty well by itself. I just explained the controls (move the iPod to control movement, move your finger on the screen to tweak the camera) and people were happy to play the game as it was. There weren’t many suggestions for what could be done to make it better (which is possibly a good thing!) and there weren’t many questions about how things worked. For example, I only got to explain my camera workings to one person, and it’s the same story with how objects stick to the ball.

When asked how much/what sort of work was involved it was difficult to decide where to start. The subsystems which tie together the various libraries? The YkRemote library (library for iPod interaction)? How the gameplay is defined in code? How I developed the thing (Subversion, blog, etc)? The development system (Xcode w/ gdb over the USB cable for the iPod, VC++ for the PC, Havok VisualDebugger for the physics.. all over two or three computers)? The content pipeline (creating assets in Paint.NET/3ds max and how they end up as interactive objects in the game)? There’s just so much to talk about. Not a bad thing considering I’ve so much report-writing ahead of me though!

So much report-writing…

Looks like my ridiculously poor hkpListShape structure has come back to haunt me. I forgot that the max number of shape keys you can have is 8, so after reconstructing the shape 8 times, everything fell apart as soon as I tried a shape cast.

Now instead of just replacing the old list shape with a new one containing it plus a hkpTransformShape, I’m properly rebuilding the whole thing and it seems to be working!

Very late to be worrying about this sort of stuff! I wonder how many bugs I’ll find tomorrow?

Turns out it takes ~85ms to convert the PixelFormat for a PixelBuffer. Using a RenderTarget’s suggested PixelFormat (RenderTarget::suggestPixelFormat) means you don’t have to do this. Doubled the speed of framebuffer->PNG code

I have open sourced all of Yakumo’s source code under the Apache License v2.0 (ALv2).

Yesterday I went through a list of OSI-approved open source licenses, and found some a little too open (MIT and BSD) and others a little too restrictive (GPL). I found ALv2 to be just the right scope for what I want. Have a read through the licenses if you want to see the difference. It should be pretty clear how different they are from each other. One thing I like about ALv2 is that it enforces the distribution of a “NOTICE” file with the licensed work. Seems to be a fair, reliable and flexible method of attribution.

Apache.org also has a nice guide on how to apply ALv2 to your own project.

A piece from today’s report writing.

You probably can’t see the full width of the images within the post, but if you click an image you should be able to see it fully.

To position the camera, a target and an origin are decided. The target is the position of centre of the player character. The origin is the camera’s current position. The origin is then scaled so that its distance from the target is 1.5m.

In order to prevent other objects from getting between the target and origin, obstructing the view, a linear cast (or “shape cast”) is performed. This is a feature of Havok Physics and to explain how it works, first I will explain how I attempted to solve this problem using a simple raycast.

Figure 2a shows an origin→target vector without any obstruction. By casting a ray from the target to the origin, obstructions can be found and the vector clipped to a point where the obstruction is no longer in the way. In figure 2b an obstruction has been found by a raycast, and the origin will be moved to the point marked with a red X.

Figure 2: Detecting collisions with camera vectors.

This works well, except in the case where there is a very small angle between a polygon close to the origin. This often happens if the player character moves along a wall, for example. In this case, it is possible for the wall’s presence to have been detected by the raycast, but some of the wall’s surface falls between the origin and the near clip plane. This is illustrated in figure 3. In this case, the origin has moved away from the wall (and the raycast therefore reports there is no obstruction). However, part of the polygon (i.e., the surface of the wall) is behind the near clip plane. More of the same polygon is beyond the near clip plane, inside the viewing frustrum’s volume. Therefore there will be a visual artefact in the form of being able to see through the part of the polygon behind the near clip plane. In figure 3, this area which will not be rendered is shaded in red. The origin is marked as an orange point, and the totally unobstructed raycast, coming from the target and ending at the origin is green.

Figure 3: A demonstration of how a simple raycast-based camera vector clipping can cause artefacts.

A raycast can be thought of as a shape cast where the shape is a single point. Linear casting allows you use any shape at all though, instead of just a point. For example, a cube can be “swept” through 3D space, and any collisions with objects will be reported. (Please note that though collisions are detected, they are not resolved and the simulation is not affected by the cast.)

If one makes a sphere, with a radius equal to the distance between the camera origin and the near clip plane, this proves to go a long way to resolving the artefact mentioned above. In figure 4, this sphere is linear casted in place of the raycast. The sphere will collide with the wall, and the new position of the origin can be calculated from the returned contact point like so:

contactPoint.position + ( contactPoint.normal * sphere.radius )

Figure 4: Using a shapecast to clip the camera’s vector.

Figure 4 shows the normal as a purple arrow. As a normal is a vector normalised to a length of 1, this means that the near clip distance must be about 3 or 4 metres. However, the normal’s length was shortened for simplicity of illustration: please note that the near clip distance is set to 0.01m in YakumoDemo, which means that the resulting sphere is 20cm in diameter.

Looks like someone else picked up on the idea I’ve been working on for my FYP and is making it into a commercial product.

Yesterday I talked about how I cut a lot of useless operations in my code. In fact, after all my work yesterday, the codebase is 160 lines shorter!

Last night I was thinking of a few places where things aren’t so snappy, and realised a point where I was overdoing multithreading. What I was doing is taking collision callbacks and putting them onto a job queue do be processed by my own worker threads. In fact, I’m also using Havok multithreading as it is and it’ll already queue up Havok-related operations to be processed by its own worker threads. Removing the useless “threaded” collision callback code meant I removed 4 files from the codebase and dropped another hundred lines or so. And it runs faster!

So in a few days of work, I’ve written -260 lines of code. And I just reminded myself of this old Apple story.

I feel pretty bad talking about “faster” and “snappier” without having my profiling set up yet. I’m on the Havok forums right now trying to get some help with getting timers set up. For some reason, my own Havok timers aren’t working, but Havok’s internal ones are. … But their code ought to be the same as mine so surely it’s an all or nothing thing.. hum.

Until now I had avoided globals in my code, which I think is a good idea in general, but when I realised how many times so many of my classes were being access through their singleton accessors, I decided enough is enough and a few regex find and replaces later my code is set up with globals instead.

I don’t know why I didn’t have the confidence to do it before, now that I look at it. I should be saving a hundred or two calls every frame, or maybe about 10,000 every second!

Goodbye, YkdGraphicsSubsystem::getSingletonPtr(), hello gGraphicsSubsystem!!

Yesterday I was having trouble with the iPod accelerometer’s response time on the PC. I found it laggy to the point that it wasn’t really usable, and then realised that since I got rid of any threading on the iPod side, the whole thing blocks while it receives the image to display on the screen (about 50kb per image).

I came up with a way of having one thread receive the image, then set a flag for the main thread to check periodically in its main loop (with an NSTimer), and then receive the next image once the flag was reset by the main thread (indicating it had been consumed and put on the screen).

Before I started hacking into that, it occurred to me that I was sending a UDP datagram to the iPod telling it that an image was on the way first, and then transmitting the image over a TCP stream. I realised how silly that was, swapped the ordering so the datagram came after the image data stream had been written to the TCP socket, and in its new role as indicating that an image had been sent (as opposed to indicating one was about to be sent), the lag disappeared! Turns out that once the data is ready to be retrieved right away, the blocking recv() call in the main thread isn’t anything to be worried about! Hurrah!