Glop and PDL

As my third Glop example program I wrote a visualization of a quantum particle propagating in a crystal lattice1. 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 Analysis2 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.

1For 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.

2Adaptive 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.

About these ads

One thought on “Glop and PDL

  1. 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…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s