Optimizing a Raycasting Engine

OK so I've been working on a raycasting engine, and really the fundamentals of it have been quite easy to get down. I have the entire thing fully functional in MMF1.5 using overlays to copy/paste slices of bitmaps onto the screen. But the devil has been in trying to optimize the thing to run at a decent speed. I've fixed a lot of slowdown problems; I implemented a system to cache/buffer images loaded from outside files, and it only checks collisions on the rays along a predefined grid at the array. So I've gotten it to the point where it can reliably run a display like this:
http://img247.imageshack.us/img247/8687/pixelsmv2.png
Without much slowdown.

The problem instead comes now when the player runs into a wide-open area; where the raycasting engine has to cast all of its rays to their maximum distance. Simple checks, like disabling the draw wall/sprite groups, revealed that the game was running slow just from the ray casting alone, not what was being drawn on screen. And so thats the problem; raycasting itself is too slow in MMF. And I need to find out WHAT is the limiting factor in it, that is keeping it from running fast.

In a normal slowdown, I might be running 200 "rays" (3 pixels wide each), each of which is checking on average 5 collisions; 1000 loops total. It seems that when the game exceeds this 800-1100 threshold, there is significant slowdown. The game is equally slow for a high resolution running few repetitions, and a low resolution running many. The total number of loops runs seems to be the slowdown.

My loop for the raycast looks like this:
http://img111.imageshack.us/img111/38/46272376ib0.png
http://img111.imageshack.us/img111/2104/20038394ur4.png

Theres two separate objects recording horizontal and vertical collisions. Their distances, X & Y velocities, interval, X & Y positions are all passed in, as well as the angle of the ray. Passed out of the procedure is the offset, "color" (type of wall), and distance, as well as flag 5 of the green detector, which records whether the collision was vertical or horizontal. The code roughly follows this sort of raycasting:
http://www.permadi.com/tutorial/raycast/rayc1.html

Now, what inside of that loop is causing such slowdown by being run 1000 times, and what can I do to speed it up? I've tried the obvious loop unwinding and such, to no avail. What the heck is the slowboat

The slowdown is that you have the "On Loop" like a million times.

And probably the pasting a lot of data to an overlay every loop part. Wouldn't it be better to just wait for the raycasting extension instead?

Pasting data to the overlay is not causing any slowdown whatsoever. If I disable the "draw wall" group, it has the same FPS as if it were active. I narrowed down the problem to being this section of code.

And I'm not sure what you mean by having the "On Loop" events; are you saying that each event inside of a loop is eating up massive overhead in the MMF architecture, or what? Like reducing it to as few lines of events as possible would speed it up?

well it would be nice if anyone who had some inside knowledge on the MMF architecture could help out

i don't know if i can help you with the inner workings of mmf, but may i suggest a hack?

Try splitting your rays into even and odd rays (ie, every other ray goes into a separate group)

each time you run through your code, only loop through the even rays one time, then switch to the odd rays. Thus you will cut the number off loops per code pass in half, and the difference will probably not be noticeable.

If you are getting small visual glitches from this, you can "fudge" the change in the uncast rays by averageing the change in the ray on either side of it that WAS calculated (by definition of the alternating odd and even rays...)

Hope this sparks some ideas.

-andy

actually thats a pretty good idea, it should halve the work done. I'll try implementing it.

Quote:

---

Originally Posted by MechaBowser

The slowdown is that you have the "On Loop" like a million times.

---

10 times actually XD

When MMF2 makes a loop, it looks for all events containing the "on loop" condition, for every step. If you run 20 loop steps in a fastloop and have 10 "on loop" conditions, MMF2 would work this

loop steps x on loops

times which in this case is 20 x 10, alias 200 times. In one frame.
And that's pretty much.

yah, but when it compiles that into machine code, its going to be the same length as if I had compressed those same actions into a single event, only plus the overhead that MMF uses for loops. And running an empty loop with 100 "on loop" events for X times, will have the same game speed as running a single "on loop" event 100 * X times, so the issue has to be something else inside the loop.

I'd say its either an issue with running a loop from inside a loop, or from the way MMF computers large integers (I assumed it was 32 bit so that shouldn't be an issue, should it?)

Quote:

---

Originally Posted by Pixelthief

And running an empty loop with 100 "on loop" events for X times

---

Except if you run it X times then it's not empty.
But yeah, having a 100 "on loop"s will be slower than running a loop with 100 steps because each time it has to search for every of the "on loop"s, and that causes more slowdown than a single step.

http://claniraq.googlepages.com/Test.cca

Nope. Slowdown seems specific to # of loop index, 10000 loops with 1 event is worse than 100 loops with 100 events, by an order of magnitude. Seems the answer would be to unwind both the inner and outer loops of the raycasting system, which will be a hassle.

.cca isn't an MMF2 file, so your results might not apply to MMF2?

I'm not programming it in MMF2? Theres no difference in the loop architecture.

A .cca file is MMF1.5. MMF2 works differently so I suggest you switch to MMF2 before requesting support for it.
MMF1.5 goes to the "Older Products" forum.

sounds like a good candidate for MMF 2 HWA .

Quote:

---

Originally Posted by jpcr

sounds like a good candidate for MMF 2 HWA .

---

Except he's not having graphical problems, which is the only thing HWA solves.

doesn't it speed things up? also would allow him soon to play full screen.

Quote:

---

Originally Posted by jpcr

doesn't it speed things up?

---

Only graphics.

Only MMF's graphics. Custom overlay stuff like this is actually slower in HWA.

I've been around since KNP days and theres no difference between the MMF2 loop architecture and MMF1.5, and HWA would only speed up built-in graphical systems, not overlays, and the overlays aren't the problem anyway. The problem is specifically something inside this loop, and it would run the exact same speed in either MMF1.5 or MMF2

anyways the main problem is that you have too many loops. Shorten them and it'll be done.

[/thread]

any programmers care to comment? -_-

Sorry about some comments above...

I know that some MMF actions do have a bit of overhead on them, but I don't see any in your events there that really stick out apart from the ones that look up the values in the array - however, I'm not really sure how you could avoid those. It may be worth testing with different array-style objects (depending on the content), though I can imagine that it's a bit of a job switching them over each time.

well yeah the array was the first thing that stuck out to me, too. But simply deleting it, and running he raycast as if there were no collisions at all, yields incredible slowdown. So its definitely not that. It seems to simply be the overhead associated with a loop, rather than the events/actions. That whole loop is called maybe 8 or so time per angle, and a loop runs through 200+ angles each frame. I guess my next course of testing would be to try running side by side loops & unwinding the outer loops, but so far it seems doubtful that would work.


as far as I can tell, the actual complexity of the actions is insignificant, the slowdown being rather entirely dependent on the # of total loops run per frame, wherever they are called. Like in that example I posted, running an empty loop 10000 times will kill your system with its lag, yet running a ridiculously complicated loop 100 times is just fine. its beyond me why fast loops, especially the built in ones, would have such high overhead compared to regular events.

its kind of interesting. I made a counter that kept track of the total number of times a loop ran per frame, combining ALL the loops in the entire game. It seems to be that the FPS is inversely proportional to the # of loops run per frame, regardless of how complex the loops are, what graphics are doing, etc. Its just FPS = k/#loops, pretty much. And right now, its appearing that even with a TON of loop unrolling, like 4x in every single loop, I'm pulling in around ~800-1000 loops per frame, when the FPS starts to suffer. Apparently, exceed this ~700 loops threshold just plain tanks the game.

As a further test, I created a BLANK MMF project, with simple commands: On an always event, it runs "Loop A" 1000 times. Loop A does nothing but set Global Value B to (random(10)). When this loop is not running, the game gets 50 FPS. When the loop is running, it gets ~44 FPS, with spikes down to 40.

Now my program runs ~700 loops, with a decrease down to maybe 38 FPS. The worse effect can be explained as the loss due to the graphical paste to overlay element, which is far from enough to lag the game on its own, but probably exacerbates the already bad lag.


So from what I can tell, MMF simply can't run a large amount of loops per frame. It slows down. Can someone PLEASE explain why it can parse through the ~3000 lines of code that my game gridquest had in TGF, each frame, yet cannot run a simple machine code "JMP" command 1000 times in MMF?

Simple answer its not the same as creating the same project in C or assembly. Its using interpreted commands that MMF understands this is slower because your computer doesn't readily understand these commands. If MMF could create a "pure" executable then things would be zipping around faster and the size of the exe would probably be smaller too.

At the moment there are some things MMF just isn't practical for your raycaster won't deliver the speed you want. You will have to wait for MMF3/3D or a faster processor

You may find another way to overcome this bottleneck by creating an object.

yeah thats just about it summed up. I guess I'll try experimenting with replacing some loops with extenions, like the fast loop object & fast function instead of using MMF built in loops. Perhaps having the work spread out across a variety will speed things up. Perhaps not. Worst case scenario, I just keep the resolution down. But you're right that it might be worth making a raycasting extension of my own just for use in this.

Quote:

---

Originally Posted by Pixelthief

it would run the exact same speed in either MMF1.5 or MMF2

---

Have you tried it in MMF2? It's worth checking, Clickteam have done a lot of work on it since MMF1.5, even if it doesn't seem like it to you.

i could try, but I'd need to KCAmath.mfx extension for MMF2, or a LOT of work rewriting code.

that was a lot of work. I rewrote it to work in MMF2, and sure enough, 38 FPS in the same places that were 38 FPS in MMF1.5, etc. Exact same slowdown. So nope