Bad Mood : Falcon030 'Doom'

[dml]

How about a conservative method where only a percentage of the objects are updated each tick? In particular, if there is visibility between A and B, there's probably no need to check if it disappeared for 5 ticks or so, and it's not unrealistic.

That's actually part of the plan

The way recorded demos work is to pump player control info into the server, and the game runs 'normally' so if the game tick doesnt behave as it did when the demo is recorded, the demo gets out of sync and things aren't where they should be at the right times.

However it should be possible to tell how a demo was recorded (in BM versus Doom) and control game tick behaviour to suit. So long as demo replay matches recording conditions, it should work.

By limiting the number of LOS tests per tick, levels with more enemies will also have 'dumber' enemies, until some are killed off. That should work ok.

I'm looking at a few other things related to the BSP walk involved, and DSP vector arithmetic for the partition planes. This should help get the LOS-tests-per-tick limit up a bit too.

[dml]

I think I have spotted a flaw in the original implementation of the BSP-based line-of-sight test in Doom. The same flaw is present in all the other versions I looked at, including some optimized rewrites.

The line-of-sight rays are not being split/cropped by partition planes as the BSP tree is walked, which leads to a significant increase in the number of incorrectly visited subsectors and therefore ray->wall intersection tests. The number of incorrect triggers increases exponentially with the length of the ray.


I implemented a quick test using what I think is the correct algorithm, and in the first test saw a 55% reduction in calls to the expensive part of the test. Because of the way i implemented it, the total cost is about the same as before, but a big reduction in subsector visits (by adding some vector arithmetic) means it's easier to claim back the time spent on extra arithmetic using the DSP - it's good at that stuff.

I need to do a bit more with this to make it 'fast' but I think it's good news generally for getting this to work on F030 with minimal compromise.

Note: it may be that Id were aware of this but the i386 was better at walking BSP nodes than it was at vector calcs, so they didn't complete the algorithm. However I think it's more likely to be an oversight because of the potential it has for runaway cost. In any case it's a useful one to fix for BM

[dml]

Another strange thing in the Doom code - there's a PVS lump (potentially visible set) stored in the WAD file indicating which subsectors can't be seen from others. This is used in the line-of-sight test, but not in the scene drawing itself.

There may be a good reason for this - maybe the PVS is imperfect and would cause glitches - but apart from that it looks like a good idea to use it even if Doom doesn't. I wasn't aware of this lump when I worked on BM the first time, but I'll try to use it now and see what happens.

[Eero Tamminen]

Another strange thing in the Doom code - there's a PVS lump (potentially visible set) stored in the WAD file indicating which subsectors can't be seen from others. This is used in the line-of-sight test, but not in the scene drawing itself.

There may be a good reason for this - maybe the PVS is imperfect and would cause glitches - but apart from that it looks like a good idea to use it even if Doom doesn't. I wasn't aware of this lump when I worked on BM the first time, but I'll try to use it now and see what happens.

You might first check whether all WADs seem have that lump. WAD editors might have omitted it, if the game didn't use it...

[dml]

Another strange thing in the Doom code - there's a PVS lump (potentially visible set) stored in the WAD file indicating which subsectors can't be seen from others. This is used in the line-of-sight test, but not in the scene drawing itself.

There may be a good reason for this - maybe the PVS is imperfect and would cause glitches - but apart from that it looks like a good idea to use it even if Doom doesn't. I wasn't aware of this lump when I worked on BM the first time, but I'll try to use it now and see what happens.

You might first check whether all WADs seem have that lump. WAD editors might have omitted it, if the game didn't use it...

That's possible, although it does seem to be used by LOS tests, so either it's always present or it's filled with all 1's when it's missing.

In any case, if it's present it can be used to filter the exisiting visibility checks (unless it's somehow flawed).

[dml]

I did a quick test with the PVS lump and now I see why they didn't use it - there are holes in it. At various places around the map some sectors don't get drawn when there is a clear line of sight to them.

Either the PVS is incomplete or it was re-dutied for AI and sound propagation, and can be blocked by special invisible wall attributes.

That explains why it's not used in the drawing code However that doesn't mean it's not a useful thing to have for drawing...

[EDIT]

Hmm... so 'special effect' sounds like 'special invisible wall attributes'. They knew it would be useful as a rendering PVS but specialized it for AI... perhaps the cost of storing it meant deciding which performance problem needed it more - and the LOS tests must have won?

Code: Select all

// REJECT
// For fast sight rejection.
// Speeds up enemy AI by skipping detailed
//  LineOf Sight calculation.
// Without special effect, this could be
//  used as a PVS lookup as well.
//
byte*		rejectmatrix;

[dml]

After reading up on the 'special effect' side of the PVS in Doom (which seems to be mainly about 'hand painting' rare PVS entries to make monsters blind to certain or all parts of the map by killing line-of-sight) I think I see a way to use the PVS to accelerate rendering on the Falcon version.

It's possible to tell which entries are hand-painted, and correct them for use during rendering (but not for use during LOS tests). First I need to check that it's worth using in the BadMood renderer but the rest looks ok.

[EDIT]

On a 14MB system, it might even be worth creating a subsector->subsector PVS (the existing one is just sector->sector) although I haven't calculated the cost of storing that - it could be prohibitive. If it's practical it could be much more effective for rendering than the current one since sectors are non-convex and can be separated into non-contiguous areas that just happen to share the same attributes (floor heights, textures etc).

[EDIT]

Have tested the pvs/reject lump in BM's renderer and it turned out to be pretty useless - too little too late. I found just one spot on one map where the pvs rejected a subsector which the bsp occlusion tests didn't get first, and it's not possible to speed those up by doing the pvs first. So I'll leave it for another time go back to merging the projects now.

[dml]

Apart from other boring stuff, I did manage to do another optimization which folds the cost of the BSPNode visibility tests over the BSP walk process itself, so one or other is now 'free' and it has moved the FPS figure up a little (although this was not a serious bottleneck even in complex scenes - still nice to get something for free).

Doom & 'BMEngine' are now quite properly joined up but the video/framebuffer stuff is still separate. When I get those consolidated it should be possible to see some game-driven output from BM I think.

[EvilFranky]

What sort of frame rates are you seeing with Doom bolted on then Doug?

Sent from my Nexus 4 using Tapatalk 2

[dml]

What sort of frame rates are you seeing with Doom bolted on then Doug?

I won't be able to tell until I finish joining the video/display bits, and disable all graphics output inside Doom. The 3D scene view is disabled but other stuff is not. I haven't been able to do that yet because of other problems which surfaced, but will finish it soon and report.

[Eero Tamminen]

What sort of frame rates are you seeing with Doom bolted on then Doug?

My totally ignorant guess is that at least initially it will be less than half of what one is seeing with BM. Doom AI is still taking a lot of CPU and initially things won't be as optimally split between CPU & DSP as they are by now in BM. When keyboard control, sprites & sounds are added [1], that will slow it down further. CPU & DSP can then be again balanced & further optimized.

[1] Douglas did I miss anything? MIDI music might also slow it down a bit, but I don't think that will be significant, and it can be even left completely out. Normal sounds are important for the gameplay though, as they tell whether there are monsters nearby.

[dml]

What sort of frame rates are you seeing with Doom bolted on then Doug?

My totally ignorant guess is that at least initially it will be less than half of what one is seeing with BM. Doom AI is still taking a lot of CPU and initially things won't be as optimally split between CPU & DSP as they are by now in BM. When keyboard control, sprites & sounds are added [1], that will slow it down further. CPU & DSP can then be again balanced & further optimized.

[1] Douglas did I miss anything? MIDI music might also slow it down a bit, but I don't think that will be significant, and it can be even left completely out. Normal sounds are important for the gameplay though, as they tell whether there are monsters nearby.

I think that's pretty accurate. I was optimistic about the cost of the game code. It's not nearly as clever as the rendering stuff. However I'm sure it will be solved with a bit of extra effort.

I don't think MIDI will take much time but a panning-capable sample mixer will take a bite. There's still a chance this can be done on the DSP in a lazy way, even across the host port but not sure about that yet. Whatever happens, audio will take a back seat to rendering and AI in terms of cost...


Last tests with BM show that its nearly fill-limited now (except for one thing, which I will rework later). So the game code is the main holdup now. Will be focusing on that soon after I'm done merging the display, scene draw and level loading stuff. It's quite close but I got distracted with some bugs and other problems.

[dml]

After unspeakable pain with Doom spraying garbage over BM's internal state with faulty alloca() calls*, I finally got the two talking to each other. BM now accepts IWAD, PWAD, map, framebuffer, window & camera state from Doom, and outputs to Doom's framebuffer.

I can now see BM 'tracking' Doom's camera during the demo loop. That bit worked first time

It's really really slow, mainly because both Doom and BM are trying to render the same scene on top of one another. BM is also doing some strange things and corrupting the display in places, and the window inset is wrongly sized & positioned.

I'll need to fix these graphics glitches and then start removing Doom's drawing stuff to see what the balance of work looks like.

* alloca() appears not to work in the MiNT GCC, or Doom's use of it is buggy. That stuff has been removed in any case.

[dml]

At the last measurement, the Doom game code is currently taking at least 65% of total time - and that's with a full size 320x168 render window. About 350ms to tick the monsters (or 17 vblanks)... That's quite bad!

Before trying to optimize anything, I'm going to assume something is badly wrong and go looking for clues in the game & network server manager. Probably start counting events for things and maybe rip some stuff out too. There are no hidden costs - I can see where the time is going and there are definite targets for optimization - but everything just seems to be happening too many times per refresh.

I'm quite pleased BM is now rendering Doom's internal world sensibly. A bit disappointing that it's nowhere close to being the bottleneck, and probably more effort needed.

With any luck it will turn out to be something silly.

[Eero Tamminen]

* alloca() appears not to work in the MiNT GCC, or Doom's use of it is buggy. That stuff has been removed in any case.

GCC built binaries default stack size is 64k. Programs ported from other platforms, especially Linux, can use a *lot* more stack. MiNTlib alloca() (which would seem to map to (libgcc?) __builtin_alloca()) probably doesn't check whether it runs out of stack...

[shoggoth]

I'm quite pleased BM is now rendering Doom's internal world sensibly. A bit disappointing that it's nowhere close to being the bottleneck, and probably more effort needed.

With any luck it will turn out to be something silly.

Have you looked at the DoomAttack (Amiga) or AmigaDoom sources? They're on Aminet I think. If you can't find them, I could send them to you. AFAIK DoomAttack has been optimized in tons of ways.

[dml]

Have you looked at the DoomAttack (Amiga) or AmigaDoom sources? They're on Aminet I think. If you can't find them, I could send them to you. AFAIK DoomAttack has been optimized in tons of ways.

I was mainly looking at Boom 2.02 and ADoom, but it turns out the 'min spec' for Boom is a 68060 and a diff against linuxdoom-1.10 shows only game related fixes and extensions, no real optimizations as such - except for the bits that always get replaced (fixed mul/div, c2p etc.)

I got hold of JagDoom more recently and found it to be a near-complete rewrite - and perhaps most interestingly, has the P_CheckSight subtree (and a couple of other game components) rewritten in DSP assembler.

...but I haven't looked at DoomAttack at all - sounds like it would be a good idea! I'll have a look for that (if I can't find them I'll PM you - thanks!).


I did a number of experiments with P_CheckSight disabled and hacks to the time reading which controls the number of ticks per draw and the results made sense. i.e. I can get it to run a lot faster in most maps by bringing ticks-per-redraw nearer to 1:1 or disabling LOS.

It's also clear now that GCC is doing bad stuff to the game code performance-wise. By disabling various bloat-related optimizations it is already running much faster. There are still problems though - short ints seem to be always passed as 32bit arguments, and -mshort isn't possible until/unless I go through all the source an assign strict type sizes to ints everywhere. A few other clues have surfaced but it will take time to go through it all.

So the Doom2 demo loop is now showing about 8fps using a 160x120 window, with the game code running normally but with the LOS tests disabled. A couple of D2 maps (one in particular) are showing worse performance but again due to game code. I'm using a tiny render window to make sure BM doesn't register too much in the profiling view and I get a feel for when game performance is dropping.

I have yet to try with the original 3 episodes of Doom 1, which were aimed at lower spec kit. I expect it will be a bit faster with those too.

[dml]

A look at DoomAttack shows that they have optimized the P_DivlineSide function as the main bottleneck in P_CheckSight (that is the first thing I did too) - but there are no other optimizations in that area. The BSP part of it is untouched.

The additional bounding box check added by Id in later revisions (which IMO is completely useless) and is present in the Boom source is not present in DoomAttack.

(The Jaguar version has the whole P_CheckSight subtree converted to DSP asm - it would have stopped the 68000 dead otherwise)

There are some other areas optimized - mainly drawing & c2p related. The most interesting one is an optimized 68k version of 'R_StoreWallRange' which is roughly equivalent to the upper/middle/lower wall logic I haven't DSP'd yet in BadMood (but is already 68k).

I'll see what else is hiding in there, but I think the P_CheckSight code will need DSP'd and 'managed down' at the game level.

It's also clear that the game code is choc full of calls to FixedMul and FixedDiv - which are already optimized and small - but they are being used with constants like 20.0*, 24.0* in places where shifts would do. And some uses are basically integer or point-shifting operations which would be better done with a different bit of code. and so on...

[Eero Tamminen]

It's also clear now that GCC is doing bad stuff to the game code performance-wise. By disabling various bloat-related optimizations it is already running much faster.

AFAIK -O3 has "always" been something which needs to be specifically compared against -O2 to see which one is faster. Whenever I've tested -O3, it has always produced larger (= potentially less cache friendly) code than -O2 for anything that is even slightly non-trivial as main thing it seems to be doing is code unrolling/inlining. Best would be to use it only for objects where it clearly helps with performance.

There are still problems though - short ints seem to be always passed as 32bit arguments, and -mshort isn't possible until/unless I go through all the source an assign strict type sizes to ints everywhere.

I'm not sure GCC necessarily produces faster code with -mshort. While GCC supports many platforms, most of new GCC work is done 32-bit and 64-bit platforms, so newer GCCs might not optimize code using shorts as well as it could?

I would also like to try building BM+Doom with GCC v2 first, to see what difference there is in performance...

So the Doom2 demo loop is now showing about 8fps using a 160x120 window, with the game code running normally but with the LOS tests disabled. A couple of D2 maps (one in particular) are showing worse performance but again due to game code. I'm using a tiny render window to make sure BM doesn't register too much in the profiling view and I get a feel for when game performance is dropping.

Any chance for a new version that people could try?

[dml]

AFAIK -O3 has "always" been something which needs to be specifically compared against -O2 to see which one is faster.

Yes -O3 was just a default I plonked in, expecting to have to change it. However both -O2 and -O3 seemed to be slower than -Os (optimize for small size) plus a string of other specific flags. TBH I've been here before and finding the right pattern of args for a given platform and a given problem takes forever :-z and easily upset if the code changes at all - so I've taken note of the impact for now but won't chase all the gritty details until later.

I would also like to try building BM+Doom with GCC v2 first, to see what difference there is in performance...

I am getting there, promise the two projects are quite messy and separated in different dirs, and there are upper/lowercase filename issues and makefile issues I wanted to fix. I'm nearly done with that so I can push you a version soon.

Any chance for a new version that people could try?

TBH while a lot has happened to it recently, there isn't much of interest to see. It's uglier and slower than 'raw' BadMood - there are no display optimizations and no double/triple buffering (it flickers) - the only new thing is the fact it loads demo loops from the WAD and plays them (without monsters, which is a bit boring). The intermissions screens and weapon graphics are disabled because they are 8-bit output and drawing is quite slow (more about that later).

I can make a version available but I don't think its all that interesting yet.

I should probably at least get BadMood to use Sector records from Doom's game state for rendering, instead of the static copy it loads separately - this would show doors & floors moving properly, and lighting fx to be closer to what's intended.


I do have some (positive) news from 2 short tests done at lunchtime on the game code. I'll post about that next.

[Eero Tamminen]

However both -O2 and -O3 seemed to be slower than -Os (optimize for small size) plus a string of other specific flags.

That's a bit surprising, in later GCC versions -Os was changed to be strictly size optimization. Mozilla complained about that because they had been compiling Firefox with it and with GCC update it got suddenly noticeably slower... I guess you selected good other flags or things are different on m68k due to radically smaller cache.

I can make a version available but I don't think its all that interesting yet.

In that case I guess it's better to wait that waste your time on that.

[dml]

Some good news this time.

First of all, LaurentS has agreed to provide his high performance sprite compiler system (Beats Of Rage) for rendering BadMood's HUD and weapon overlays. In fact he has built some of the sprites already for me to conduct tests with. I'm not quite in a position to use them just yet (the HUD stuff is disabled until I solve the game performance problems), but a plan for integrating his precompiled sprite code is well underway


The other good news relates to the game performance problems. I was able to confirm that the gametick is 'chasing its tail' trying to keep up with realtime, and not quite managing it. I wasn't able to confirm it before because the tick manager is quite complicated and my early attempts to foil it were ...foiled. I found the best solution was to do it properly (as ever) and specify a new TICRATE which is much closer to the expected framerate, and an honest timebase based on a 200Hz tick.

The TICRATE-chasing stuff is really there for synchronizing network games, so each tick has a known, identical state on each client and no framerate-scaling is involved in AI movements etc. The client does however need to make sure it can keep up - otherwise a client locks up, or everyone has to slow down.

Having changed the TICRATE, the framerate gets 'capped' at that number and can't rise above it, but the gametick doesn't try to play catchup with more than 1 or 2 ticks per display refresh (instead of a burst - or continuous stream - of them, which was happening previously).

So the Doom2 test (Map11) that was producing about 2.5fps before is now producing between 4.5 and 6fps with the LOS tests and monsters still enabled. It's still a lot faster with LOS completely disabled but this change has reduced the problem a lot. The framerate is a bit erratic in this range because it's alternating between 1 and 2 gameticks per render and one alone is enough to impact the framerate.


I studied the JagDoom source and determined that the biggest optimization made there was reducing TICRATE from 35Hz (aimed at i486 or better) to 15Hz, and making sure the rendering was able to keep up with approx 15FPS plus some margin (GPU spans/columns, reduced resolution). The 'problematic' bits of the game code were optimized into DSP/GPU assembler to make this achievable.

The problem with the current Falcon version is that the balance of costs is roughly inverse to what the game was designed for - to minimize drawing at the expense of some extra calculation. With the Falcon version, the drawing is relatively cheap compared with the cost of the AI, because the drawing is all DSP'd and hand-optimized, whereas the AI is just C code aimed at a 486 CPU...

So I have a strategy now for making this work:

- Specify a sensible TICRATE which is just below the Falcon's 'average framerate', whatever that ends up being. Temporarily it will be 6Hz = 6fps. This may be too low and cause game code bugs to emerge, but the aim is to raise it again later if possible.
- Give up the ability to play back demos recorded at 35Hz, except in slow-motion (i.e. framerate ok, but things move sloooowly in the world)
- Demos recorded by BM will be recorded at the new TICRATE, and so will play back sensibly.
- DSP-ize the most offensive bits of the C code - several varieties of 'which side of line' tests used in line-of-sight and AI sector searches.
- 68k optimize the algorithms using those (LOS test, sector search)
- If the optimizations are effective enough, raise the TICRATE a bit to close the gap.
- Consider removing the realtime-hunting behaviour of the gametick, by giving up network support (which doesn't exist at the moment anyway) and fixing the gametick:render ratio at 1:1. This eliminates the tail-chasing problem completely, but when the framerate drops the 'game time' will slow down proportionally, as you'd expect with simpler games. The benefit here is that the framerate doesn't need capped so low, and can rise a bit in less costly areas of map without the gametick .

I'm a bit concerned that the game code isn't very clean w.r.t TICRATE and some monsters will not be moving at the right speed etc. having modified it. The Jag source is probably a good reference for fixes here. The Boom source does have fixes related to this too, but the TICRATE hasn't been changed from 35Hz which makes me wonder if those fixes are tested/good.

That's all for now. Longwinded post this time but the chances of this happening on a 16MHz Falcon just improved slightly.

[dml]

I made a (very bad) recording of the startup sequence and first demo loop from 'registered' Doom 1, running inside Hatari *without* fast-forward mode enabled so it's a pretty honest test with all the game code running, albeit with a reduced ticrate. The demo runs in slow-motion and it de-syncs quite rapidly because the monsters aren't responding properly at the new ticrate, relative to player movement. So the player gets stuck against walls etc. and dies in the wrong place.

Note that BM runs about 10-30% faster on a real F030 for all but the most complex scenes (Hatari usually runs those a bit faster for some reason).

Sorry about the poor quality and the fact it's SWF format - didn't have time to record it using decent software (and the file is 18mb).

https://dl.dropboxusercontent.com/u/129 ... omtest.swf

[EvilFranky]

Excellent progress as we've come to expect Doug!

It's looking like one of the big 'what ifs' of the Falcon scene will come to a close in the coming months, great to see and never thought a proper attempt at a Falcon Doom would ever materialize.

This is obviously for much mater in the development...but will you enable JagPad support please!

[Eero Tamminen]

- Specify a sensible TICRATE which is just below the Falcon's 'average framerate', whatever that ends up being. Temporarily it will be 6Hz = 6fps. This may be too low and cause game code bugs to emerge, but the aim is to raise it again later if possible.
- Give up the ability to play back demos recorded at 35Hz, except in slow-motion (i.e. framerate ok, but things move sloooowly in the world)
- Demos recorded by BM will be recorded at the new TICRATE, and so will play back sensibly.

I imagine that people with different machines (accelerated Falcons) might want to use different TICKRATEs and that it will be changed as BM performance changes. Doom1 WADs might also work with higher TICKRATE than Doom2 ones.

What if TICKRATE would be configurable from command line or config file, instead of being build time option?

That way BM could also use TICKRATE from the demo, as long as its small enough, and one could use demos recorded with earlier BM versions having smaller TICKRATE values. When not playing demo, TICKRATE might also be calibrated in few first frames of a map, and if it seems later in the map that it was actually too high, lowered.

PS. Really good news, thanks!