Limited memory solution of complementarity problems arising in video games
Michael C. Ferris, Andy Wathen · Oxford University Research Archive (ORA) (University of Oxford) · 2002
This paper describes the solution of a problem arising in the application of complementarity for physical simulations that occur within video games. The size of the problems is typically not very large, ranging from around 20 variables to a current limit of around 400 variables. The computational time available to solve each instance of the problem is limited by the frame rate of the simulation, and the memory allowed to solve each problem is severely restricted by the hardware available on many of the existing game (console) platforms. The typical time frame is of the order of milliseconds, while the amount of fast RAM available is 4-16K. A further important feature of the solution technique is that worst case behaviour is very important - if large spikes in computation occur this can lead to loss of frames and jumpy screen animations