I'd be happy for you to expand on it
You doing SWiV on the BBC then? Or have I misread that?
| www.retrosoftware.co.uk http://www.retrosoftware.co.uk/forum/ |
|
| Co-operative multitasking http://www.retrosoftware.co.uk/forum/viewtopic.php?f=73&t=316 |
Page 1 of 1 |
| Author: | sirmorris [ Wed Jul 29, 2009 9:39 am ] |
| Post subject: | Co-operative multitasking |
Anyone here know how useful this is for game development? Have you implemented it in 6502 yet? This is a technique I picked up working on a megadrive title (SWiV) back in the day. I've used it ever since. The game I was hoping to show at CC (before being struck down by the Tesco fish counter) is perhaps the largest project to date that is driven in this way. I don't want to launch into a discussion if I'm preaching to the converted, but I'll be happy to expand if anyone's interested. C |
|
| Author: | DaveF [ Wed Jul 29, 2009 9:50 am ] |
| Post subject: | Re: Co-operative multitasking |
I'd be happy for you to expand on it You doing SWiV on the BBC then? Or have I misread that? |
|
| Author: | SteveO [ Wed Jul 29, 2009 10:56 am ] |
| Post subject: | Re: Co-operative multitasking |
No used this technique. So guess you have some sort of command loop that calls a list of tasks and you can add new tasks or remove them from the list as you wish ? And each task when running has 100% processor usage whilst running until it releases back to the main controller at intervals each task determines or when task complete. Sounds very RISC-OS ish. Is that on the right lines ? |
|
| Author: | MurrayCakaMuzer [ Wed Jul 29, 2009 11:51 am ] |
| Post subject: | Re: Co-operative multitasking |
I believe so, from my limited knowledge. It's only a problem when OSes start using it (like the old Windows), in which case if an app crashes, the whole system crashes (since it never gives back control). For a game it should be fine, as long as you make sure all the "processes" are crash/infinite loop-free |
|
| Author: | PaulDv [ Wed Jul 29, 2009 12:09 pm ] |
| Post subject: | Re: Co-operative multitasking |
In the Commodore world this technique is pretty much the standard way of doing game development. Not true multi-tasking as such, but different parts of the code (graphics, music, controls, game logic etc.) running separately under interrupt synced to the raster. |
|
| Author: | sirmorris [ Wed Jul 29, 2009 12:15 pm ] |
| Post subject: | Re: Co-operative multitasking |
Indeed it is, though rather than have an overlord function you effectively make a linked list of data structures which represent private storage for each entity/object/whatever and the code runs in a never ending loop, jumping from one entity's code to the next. I've attached the source to the last game I wrote, a couple of years ago on zx81. It's not the best example as the flow is necessarily polluted with rendering code due to the system's limitations, and there are only a couple of entity types - smarties is much better but the code isn't here with me right now. Attachment:
File comment: zx81 game source - runs great in 'eightyone' emulator. 
BallBlaster2.rar [63.64 KiB]
Downloaded 5 times This is essentially how it works: Create a free-list of entity data blocks Allocate a block and assign it to an entity (place the entity's execution address in the data block) Insert it into the execution train at the desired place Execution takes place in a round-robin fashion. When an entity has finished processing it yields the processor by placing its next execution address in its data block, and looks to the next entity, taking its execution address and jumping there. This is all handled by a macro. What you get in return for the slight overhead is the ability to write your (for want of a better example) enemy code like so: Code: enemy: initialise chaseplayer: get position deltas work out accelleration update position time to fire? y - create bullet entity YIELD offscreen? y - DIE collision with player bullet? y - create death entity DIE goto chaseplayer Each enemy's code looks like a linear function. When an object's state changes it's often convenient to create a new entity to handle the updated state rather than have lots of tests and calls to functions. All entities can work the same way - there's no need for separate lists of object types and their related update calls, every object keeps its own state. Ordering of objects is critical and the ability to place a new entity in the right place in the execution sequence is a core requirement. Collision detection/rendering should happen after all enemies/bullets have updated, for example. The DIE macro removes an object from the execution chain and places its data vlock back on the free list. This is just a taster of the big picture, and there are loads of benefits to using this technique. If you want proof go and disassemble defender I had the original source for defender/joust which was used for the gameboy conversions by Rage, but I can't find it on any old CDs  E.J. uses a very similar system. So does netware, and many embedded systems where performance is critical.I'll be happy to expand more. C |
|
| Author: | RichTW [ Wed Jul 29, 2009 6:30 pm ] |
| Post subject: | Re: Co-operative multitasking |
Yes, I've used this technique in C/C++ when developing Playstation / PS2 titles - it really speeds up development and aids readability immensely, as the code can be read linearly, rather than the spaghetti nightmare you end up with if you were to implement it as a state machine. But I'm not convinced this kind of technique would be particularly valuable in 6502 Beeb code - to me it just doesn't seem quite high-level enough to benefit from this kind of fibre system (with no stack frame or variable management as such). It'd be interesting to see real examples of how you've used it - I'll take a look at the ZX81 stuff later on. |
|
| Author: | sirmorris [ Wed Jul 29, 2009 9:01 pm ] |
| Post subject: | Re: Co-operative multitasking |
Defender and Joust ran on 6809s. Arguably less powerful than a PS1 The stack framing isn't really important, this is a loose methodology which adapts to processor abilities. What you aim for is control over the program structure, and like you say the structure of a program like this is easier on the programmer. The version of this which underlay many megadrive/amiga games at SCI manipulated the stack and was really efficient. The yield macro essentially set the stack pointer to some memory associated with next ntt in line and did a ret.. I've also seen evolutions of this used in the unreal engine {shudders} though that was thread/interrupt assisted. There are some good in-depth explanations in one of the 'game programming gems' books. In it's C form though and I think the term used is stack winding, though part of me thinks this might be a subtly different technique. This is from smarties: Code: (cometask.asm) DangerNTT: extrn TextNTT: near GenChld TextNTT mov [edi + UFO_Frame],offset dangerString lea ebp,dangerString GSL mov eax,(360 / 2) shl 16 sub eax,ecx mov [edi + UFO_X],eax mov [edi + UFO_Y],(270 / 2) shl 16 mov [esi + UFO_GfxPtr],edi WaitFor 20 mov eax,[esi + UFO_GfxPtr] add [eax + UFO_X],01080000h WaitFor 20 mov eax,[esi + UFO_GfxPtr] sub [eax + UFO_X],01080000h WaitFor 20 mov eax,[esi + UFO_GfxPtr] add [eax + UFO_X],01080000h WaitFor 20 mov eax,[esi + UFO_GfxPtr] sub [eax + UFO_X],01080000h WaitFor 20 mov eax,[esi + UFO_GfxPtr] add [eax + UFO_X],01080000h WaitFor 20 mov eax,[esi + UFO_GfxPtr] sub [eax + UFO_X],01080000h WaitFor 20 mov eax,[esi + UFO_GfxPtr] add [eax + UFO_X],01080000h WaitFor 20 mov eax,[esi + UFO_GfxPtr] dec [eax + NTT_FOVal] WaitWhileChildren DelChld ; fall though into enemy generation code Attachment: This code draws the string 'Danger!' on screen, scrolling right to left across the playfield. The 1st few lines create a child entity and initialise it. In this case it's the 'render text string' object. The 80x86 have the lovely index registers ESI and EDI which make this kind of thing really easy. ESI always points to the active NTT's data. EDI is a 16 bit indexable register which points to the child's data memory, as returned by the create child macro. This is stored and the function yields. The WaitFor.. macro simply yields N times, providing a delay of N vsyncs. The child object's x pos is updated, moving it across the screen a set amount every 20 vsyncs. Finally it decrements the child's NTT_FOVal, which instructs the childto clean up and signal when it's finished. WaitWhileChildren repeatedly yields while the child entity is still active, and then it's deleted. The execution falls though into the comet generator.. Part of me which isn't itching to get my Atom pl8 MMC interface working wants to have a go at coding this on a 6502 to see how it pans out. It might be a wait though 
|
|
| Author: | sirmorris [ Thu Jul 30, 2009 10:13 am ] |
| Post subject: | Re: Co-operative multitasking |
and yes, it could have been a loop
|
|
| Author: | Samwise [ Mon Aug 10, 2009 11:56 am ] |
| Post subject: | Re: Co-operative multitasking |
Ya know, there's a perfectly good Sample Code wiki page which might benefit from this sort of goodly stuff, and to save it from being lost in the depths of the forum. Just a thought ... Sam. |
|
| Author: | RichTW [ Mon Aug 10, 2009 1:46 pm ] |
| Post subject: | Re: Co-operative multitasking |
Just since this is bumped, I'll add my further two cents. In the past, I've only ever needed to use a kind of 'virtual update' technique on the Beeb, e.g. Code: .Update LDA NumMonsters BEQ NoMonsters LDX #0 .UpdateLoop LDY MonsterType,X LDA MonsterUpdateLo,Y STA UpdateCall + 1 LDA MonsterUpdateHi,Y STA UpdateCall + 2 .UpdateCall JSR &FFFF ; monster index in X, monster type in Y INX CPX NumMonsters BNE UpdateLoop .NoMonsters .... .... MaxMonsters = 16 ; maximum which can exist at once MaxMonsterTypes = 8 ; how many different types there are .MonsterType SKIP(MaxMonsters) ; reserve MaxMonsters bytes .MonsterX SKIP(MaxMonsters) .MonsterY SKIP(MaxMonsters) .MonsterState1 SKIP(MaxMonsters) .MonsterState2 SKIP(MaxMonsters) ... .MonsterState5 SKIP(MaxMonsters) .MonsterUpdateLo SKIP(MaxMonsterTypes) .MonsterUpdateHi SKIP(MaxMonsterTypes) .MonsterSpriteLo SKIP(MaxMonsterTypes) .MonsterSpriteHi SKIP(MaxMonsterTypes) .MonsterWidth SKIP(MaxMonsterTypes) .MonsterHeight SKIP(MaxMonsterTypes) Essentially, it's the old state machine type approach, where the update routine updates a single frame's worth of behaviour (with the index of the monster being processed in X, and the type in Y, in case you want two different monsters to share largely the same update, with some very subtle differences). For me, this is surprisingly clear for 6502 code, and has always served me sufficiently well. I never coded any kind of behaviour on the Beeb for which a fibre system would be advantageous, but I can see how more complex behaviour could benefit, even in 6502, for readability, and perhaps even speed. I suppose a very minimal implementation might move the UpdateLo/Hi address to be an attribute of the monster instance, rather than the monster type. The Yield subroutine would then store its return address there, instead of actually returning to it, and instead JMP to the update loop again. But then, you would also have to save and restore the A, X, Y and P registers (hence requiring some another 4 bytes for these per monster instance). And as I said earlier, you'd have to be really careful with the stack. Here's a possible implementation: Code: .Update LDA NumMonsters BEQ NoMonsters LDX #0 .UpdateLoop LDY MonsterSaveY,X LDA MonsterUpdateHi,X PHA LDA MonsterUpdateLo,X PHA LDA MonsterSaveP,X PHA LDA MonsterSaveA,X PLP RTS ; calls the pushed address .BackFromUpdate INX CPX NumMonsters BNE UpdateLoop .NoMonsters RTS .... .... .CreateMonster ; Y = type of monster LDX NumMonsters CPX #MaxMonsters BEQ NoMonstersLeft LDA MonsterInitUpdateLo,Y STA MonsterUpdateLo,X LDA MonsterInitUpdateHi,Y STA MonsterUpdateHi,X TYA STA MonsterType,X LDA initxpos STA MonsterX,X LDA initypos STA MonsterY,X INX STX NumMonsters .NoMonstersLeft RTS .... .... .Yield ; have to call with X = monster index (hence no need to save X) PHP ; remember the flags as they are RIGHT NOW! STA MonsterSaveA,X PLA ; only way we can access P directly STA MonsterSaveP,X TYA ; no STY abs,X STA MonsterSaveY,X PLA ; return address, i.e. next instruction of the update STA MonsterUpdateLo,X PLA STA MonsterUpdateHi,X JMP BackFromUpdate .... .... MaxMonsters = 16 ; maximum which can exist at once MaxMonsterTypes = 8 ; how many different types there are ; tables, one entry per monster instance .MonsterType SKIP(MaxMonsters) ; reserve MaxMonsters bytes .MonsterX SKIP(MaxMonsters) .MonsterY SKIP(MaxMonsters) .MonsterUpdateLo SKIP(MaxMonsters) .MonsterUpdateHi SKIP(MaxMonsters) .MonsterSaveA SKIP(MaxMonsters) .MonsterSaveY SKIP(MaxMonsters) .MonsterSaveP SKIP(MaxMonsters) .MonsterState1 SKIP(MaxMonsters) .MonsterState2 SKIP(MaxMonsters) ... .MonsterState5 SKIP(MaxMonsters) ; tables, one entry per monster type .MonsterInitUpdateLo SKIP(MaxMonsterTypes) .MonsterInitUpdateHi SKIP(MaxMonsterTypes) .MonsterSpriteLo SKIP(MaxMonsterTypes) .MonsterSpriteHi SKIP(MaxMonsterTypes) .MonsterWidth SKIP(MaxMonsterTypes) .MonsterHeight SKIP(MaxMonsterTypes) Example of use: Code: .UpdateRightThenLeft LDY #0 .MoveRightLoop INC MonsterX,X JSR Yield ; stop processing this monster, will continue where we left off next update INY CPY #30 BNE MoveRightLoop .MoveLeftLoop DEC MonsterX,X JSR Yield DEY BNE MoveLeftLoop BEQ MoveRightLoop It's admittedly quite neat to be able to focus on the isolated logic of one entity like this, but it doesn't come without its own gotchas: There is a small overhead in Yield-ing, from having to save and restore the registers, both a memory and a speed cost. Simple logic might not particularly benefit from this extra overhead, particularly if there are many cheap entities being processed. A big gotcha is to do with the stack: this routine will break if the Update routine leaves something on the stack before calling Yield - this also includes calling Yield inside a JSR called from the Update routine. That's because we're not creating separate stack frames for each fibre, and so one fibre's PHA could later be paired with another fibre's PLA, with disastrous results! To fix this, we would have to remember the stack pointer for each fibre too, and initially allocate each one 8 bytes or so of the stack. Now, the 6502 stack is tiny, so this is already sounding like a bad idea. An alternative is to copy the stack frame elsewhere upon Yielding, and to copy it back upon Restoring, but this too is starting to get a little involved and probably not really worthwhile. So, with these limitations in mind, the fibre system could work OK on the Beeb - but for me, I'm probably likely to stick with my simple implementation for the moment (Multiple edits: to correct bugs in my hastily-written code) |
|
| Page 1 of 1 | All times are UTC [ DST ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|