Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 14 Jun 2011
Offline Last Active Sep 09 2013 02:34 AM

Topics I've Started

Ray casting walls and floors - speed needed!

18 January 2012 - 03:17 AM


I recently wrote a simple ray casting engine, which casts textured walls, ceilings and floors. This is written in Python, with the help of Pygame, and is this first bit of real Python work I have ever done - so it's a bit of a learning exercise for me. I'm about to add a sprite system and following that, I want to turn it into some kind of silly little dungeon-explorer game.

Unfortunately, it's just too darn slow. I cannot bring myself to enhance the functionality any further until I can get a lot more speed out of what's already there. I have a bit of an OOP approach which might not be the fastest, but it's categorised neatly. I'm willing to do a lot to the code, but I don't want to attack it too much until I get my facts straight on how to choke the most speed out of this.

I won't post the code itself (unless needed), but the drawing works pretty much as described below:
  • For every vertical pixel column, a ray is cast for wall intersections...
  • ...this ray checks for horizontal and vertical intersections only at grid intersections (as described by Permadi)
  • Wall height is calculated for each ray, and the correct texture is scaled and drawn to screen.
  • Floor / ceiling distances are pre-computed by rays cast downwards, after which each floor pixel is found using linear interpolation and then is drawn vertically, going downwards for every pixel after a wall slice till the bottom of the screen. This coordinate is simply mirrored to the top half of the screen to draw the ceiling.
Now, I think that maybe some aspects of these algorithms could stand to be improved, but not as much as I think the Python implementation could improve. I think I'm doing some expensive things, but I'm not too sure of what would give me a REAL speed boost. I've run a profiler, and not surprisingly, the raycasting itself and the drawing of screen pixels cost the most. The following are of concern:
  • I wrote an angle class which clamps the rotation angle (and all angles) between 0 and 360. I've used __add__ and __sub__ to handle this - obviously there are a lot of calls to this - should I avoid them and do this differently?
  • I am using a *lot* of list accesses. For example, my "castRays" function goes through all vertical columns and then stores results in a list... such as:
    wallDistances[i] = distance
    . Are such operations slow? If so, they will kill me because I do a ton of them. Any alternatives?
  • Regarding the lists again - I've heard that numPy can improve the speed of such things. I do not really understand why or how, but is this true?
  • Calls to functions or objects are apparently quite slow in Python - but from a bit of tweaking I haven't really seen that much difference. Is calling a "castRay" function really so expensive in python? And, how much is this influenced by passing parameters and returning values?
  • Regarding pygame: I'm making use of surfaces to store all textures as well as what's displayed on screen. I got a significant performance boost by using pixelArray (and setting those values) in place of set_at(x,y). Is there an even faster way to do this? Surfarray maybe?
  • Regarding walls only: I make use of a surface, which I then crop using subsurface (to get only the vertical column), and THEN rescale using transform.scale. Then I convert to a pixelarray. Eep! Is there a better way? Scale seems a bit silly for my purposes since I need to scale in 2 dimensions when I only need to do it in 1(it will not allow me to scale to width "1" either).
  • Is there much value in writing C bindings for some of the most common tasks? What about Psycho?
Apologies for the long post, but thank you for reading - I'm currently averaging about 8fps, which is pretty much unplayable. The floor casting is especially pricey but walls could use some work too. I know I'm asking a lot here, but I feel a bit directionless and would love to get some good feedback before butchering my code - I've already tried to take small steps at optimization with little or minor success.

Any help would be greatly appreciated!!