As my third Glop example program I wrote a visualization of a quantum particle propagating in a crystal lattice^{1}. I did it all in plain old Perl to start, and it was painfully slow: 1/2 a frame per second on a 32 x 24 lattice. Uh oh, this kind of speed simply won’t do for any serious game.

I rewrote my computation sub in C using the glory that is Inline::C, and it blazed along, even on a lattice four times the size (64 x 48). But then I noticed numerical stability problems. One particle sitting there without propagation would first be 100% likely to be there, then 150%, then 200%, then 300%… while I’d certainly like to measure it and find that it was three times more than always like to be there, I’m pretty sure the real world doesn’t do this (what happens when there is propagation and it’s 100% likely to be in two places at once).

I switched over to a Runge-Kutta integrator for the single particle case (which requires four computations of the derivative per frame), and that fixed the stability problems. But then propagation was still unstable, and in order to use RK on that you have to do it to the whole lattice four times—not just each position in the lattice four times.

So I scrapped all my C code; I wasn’t about to write that complex process in C, and it would have gotten unbearably slow yet again. I looked at PDL, since I had used it once for matrix computations during my Conjoint Analysis^{2} project. I studied up a bit, and implemented the RK method on the whole lattice: a computationally expensive process. PDL flew through it, giving me the same frame rates as the Euler integration gave for my C implementation. That’s amazing! I heard it was fast, but geez, that’s execellent.

I’m considering adding PDL to the Glop distribution, since numerical lattices are ubiquitous in games. I won’t if I don’t end up using it from the core, but I won’t hesitate to add it if I do want it in the core. Well, maybe I will. If it turns out that it’s easy to do something both in pure Perl and from PDL, I might provide a scan for PDL and use the pure Perl implementation if it’s not available.

^{1}For the interested, the equation for zero-energy propagation on a one dimensional lattice is:

iħ ∂<x|ψ>/∂t = A <x|ψ> – 1/2 A <x-1|ψ> – 1/2 A <x+1|ψ>

Where <x|ψ> is the amplitude that the particle is at position *x*, ħ can be treated as an arbitrary constant when you’re doing a computational simulation, A is an arbitrary constant, and i is, of course, the square-root of -1. If you’re doing a multidimensional lattice, just add more of the negative terms, and change the 1/2 to 1/(the number of connected crystals).This is just a special case of a Hamiltonian integration. If you want to learn Quantum Mechanics, you *must* read Volume 3 of Feynman’s Lectures on Physics. It’s the absolute best.

^{2}Adaptive Conjoint Analysis is a method that uses linear algebra to balance trade-offs between preferences. It’s a good way to figure out what consumers actually want, rather than what they think they want.

Nice! I’m trying to convince some guys in the maths department here not to re-implement RK in C Yet Again – maybe this will help…