 Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me. |
Forum Index : Microcontroller and PC projects : CMM2: MMBasic - back in the pit of despair
Page 1 of 2   |
|||||
| Author | Message | ||||
| abraxas Regular Member  Joined: 16/06/2020 Location: CanadaPosts: 99 |
OK, this is really where I'm starting to doubt the feasibility of the CMM2 Boulder Dash project. I've added a few new features to the engine (most notably explosions and fireflies) and the thing is sloooow. With about 19 fireflies in a cave the game tick processing time is often in the 90ms range. If rocks are falling it's even higher. And the worst news is that I've already optimized the hell out of the game logic. Currently the engine only computes tiles that move or are immediately affected by movement. This means it should be quite close to a minimum amount of computation. Granted, I can still manually inline a bunch of functions and get maybe another 30% speed improvement... The problem is, that's not enough. Even in Boulder Dash I there is a cave with 30+ butterflies and lava and there is no way that this engine will keep up a respectable tick rate with that many objects. Right now with 19 fireflies it's already stuttery if you let them all out and start dropping stones on them. With 30+ butterflies (which follow nearly identical logic as fireflies so computationally just as expensive) plus some spreading lava the game will become unplayable. Also at this point I've made the game tick equal to one animation tick as I no longer harbor any hope for the game to maintain anything like 60 or even 30 fps when it comes to smooth animations. Just isn't gonna happen. At best I'm hoping for what amounts to ZX Spectrum style port with slow animations and a laggy viewport. Frankly I'm on the verge of giving up. The cost of logic expressions and SUB invocations and FUNCTION invocations is so prohibitive that one has to either code complete spaghetti or put up with performance that falls far short of ASM on classic 8 bit machines. Yeah, I know I could take the two main SUBs - SCANTILE and PROCESSCOMMAND and turn them into CSUBs. The issue I have with that is that a) it's really hard to iteratively write CSUBs and 2) it's really no longer a good example of MMBasic code as the most relevant components will be buried in the hex of a CSUB. If anyone has any suggestions for making this go any faster I welcome your ideas. As is I think the project isn't worth continuing because I can tell that the outcome isn't going to be what I've been hoping for. BDASH.zip |
||||
| mkopack73 Senior Member  Joined: 03/07/2020 Location: United StatesPosts: 261 |
About the only suggestion I can make is completely rethink the design of the engine so it's not doing as much work... I didn't look through the code but did follow your previous posts somewhat. I think you need to figure out ways to keep the iterative logic only working on the things that can possibly change so you're not spending a ton of time checking/updating things that can't. But I've only every played BoulderDash like twice so I'm sure there's a lot more to the game than I remember. Are your datastructures inefficient? Are you doing a lot of looping inside of loops? A ton of if/then checks (maybe consider case statements where possible?) Run it through the cruncher or thwill's transpiler? Remember, don't use an 32 bit int if a single bit will do (or of you can encode 32 data elements in a single 32 bit int). |
||||
| mkopack73 Senior Member Joined: 03/07/2020 Location: United StatesPosts: 261 |
Another thing I'm thinking - Use a 3D (width/height/2) array to keep the playfield, with Z holding the objecttype in the 1st level and an index into an array for objects of those types in the 2nd level (which are effectively pointers into the sets of arrays below) Then have smaller individual arrays for things like the butterflies and the boulders and such, so you only process those smaller lists for the dynamic objects rather than looping through the whole 2D screen array on each update. And that would also keep your logic for each type of thing more compact since you're not doing a check to see what the type is first and then what to do with it, etc. Again, don't know if this helps at all... You might want to try it on a smaller field in a test program.. One way vs the other to see if it helps you. |
||||
| abraxas Regular Member Joined: 16/06/2020 Location: CanadaPosts: 99 |
Here's the thing. I'm already doing what amounts to processing just the moving tiles as opposed to the whole cave. In a couple of most recent iterations I realized that even with some of the skip list optimizations that I previously had the game wasn't going to perform well enough. This version works as follows: - there are two global arrays that are updated on each game tick: a scanList and a commandList - the game starts with the scan list containing every tile in the cave. each entry in the scanList is processed once and possibly generates an entry in a commandList. The commandList is an array of commands to apply to the board such as "move firefly" or "drop heavy object". Now, every command results in a change in its immediate area. This means that every command in turn creates one or more scan requests in the scanList. And so goes the game loop: we consume the entries in the scanList to see if any actions need to take place. This in turn creates new action commands which may then create additional scan requests. This layout accomplishes two things - it ensures that I only process the tiles that I really need to and also makes sure that I don't get into problems with double-scanning any tiles as the board is not immediately changed during a scan but rather commands are buffered, deduplicated and in a correct sequence. |
||||
| mkopack73 Senior Member Joined: 03/07/2020 Location: United StatesPosts: 261 |
Hmm... in that case I don't know... Not without digging through the code a bunch. I'm sure you'll figure something out. Keep at it! If nothing else, you're learning a lot about how to code for this machine in the mean time that you can apply to other projects in the future. (I'm dealing with my own hell over here...Wasted an entire day that I had planned to spend coding because I decided to get an old Windows laptop set back up dedicated to using for MMEdit, which turned into a run to microcenter on the other side of Philadelphia for a copy of Windows 10, and then sidetracked to buy a huge haul of Commodore 8 bit gear, which then turned into organizing such a haul so I could actually walk in my condo again...) And only NOW have I been able to get back to coding... just in time to go to bed! sigh |
||||
| capsikin Guru  Joined: 30/06/2020 Location: AustraliaPosts: 341 |
I've got a few ideas. Do you know how much of the time is sort, vs the scantile loop, vs the processcommand loop? Anyway, one idea is to have global arrays caching LEFTOF and RIGHTOF. e.g.: A_LEFTOF(LEFT%)=LEFTOF(LEFT%) A_LEFTOF(RIGHT%)=LEFTOF(RIGHT%) A_LEFTOF(UP%)=LEFTOF(UP%) A_LEFTOF(DOWN%)=LEFTOF(DOWN%) then using array lookups for these in the firefly scantile code. Second, it might be worth changing the ADDSCAN code for fireflies, to only add 3 or 4 locations, like you did with ADDSCANFORHEAVY. In fact you could probably modify ADDSCANFORHEAVY to include the UP% case (last, so it doesn't slow down the other directions) and use that. I also noticed a bug, if you press escape too many times it gets slower and eventually crashes, so make sure you're testing times before you've pressed escape. I have some others (optimisation ideas) that might be more important, still typing them up. Edited 2020-07-26 13:50 by capsikin |
||||
| capsikin Guru Joined: 30/06/2020 Location: AustraliaPosts: 341 |
I think it could be worth moving the scantile code into a loop, instead of a SUB called by a loop. Maybe a new SUB called LOOPSCANTILE Then make sure all the local variable creation happens outside the loop. Same for PROCESSCOMMAND, make a LOOPPROCESSCOMMAND sub that creates all its local variables before looping. I think I remember someone, maybe Peter, mentioned subroutine calls especially with local variables taking time. |
||||
| capsikin Guru Joined: 30/06/2020 Location: AustraliaPosts: 341 |
The bug is that if you press escape the program never returns from PROCESSKEY, or KEYSCAN which calls it, or CAVELOOP which calls that. After doing it many times it would have a big stack of sub calls and crash when it reaches a limit. I don't know why it would slow down before that though. Edited 2020-07-26 14:12 by capsikin |
||||
| abraxas Regular Member Joined: 16/06/2020 Location: CanadaPosts: 99 |
Thanks, capsikin. I'm keeping tabs on all your suggestions and will be trying them in turn. |
||||
| abraxas Regular Member Joined: 16/06/2020 Location: CanadaPosts: 99 |
capskin, thank you so much! Your ideas really helped. I implemented most and the difference is very palpable. Now it's playable with 30 fireflies in the cave. We're definitely getting there. The changes that I've implemented: - inlined SCANTILE and PROCESSCOMMAND so they are part of the same SUB - optimized the scan around fireflies to use SCANFORHEAVY - cleaned up a bit in the render code to do the bare minimum but without any fancy skiplists The couple of things I don't know how to do: Not sure how this would work since LEFT%,RIGHT% etc are large integers because the bits they control are high up (like 24 bits or so). So A_LEFTOF would have to be a massive array with a lot of wasted space, no? OK, I understand the problem but not sure how to fix... how do I unwind the stack? I was calling GOTO thinking that it would in essence result in exiting all subs all the way up to the main scope. Anyway, thanks again for great ideas. I attached the revised version of the code for you to check out and see if you have more ideas. BDASH.zip |
||||
| berighteous Senior Member Joined: 18/07/2020 Location: United StatesPosts: 110 |
don't draw every animated thing every frame. draw half of them every other frame. |
||||
thwill Guru Joined: 16/09/2019 Location: United KingdomPosts: 4311 |
Which cruncher? I think it may only crunch out whitespace which is unnecessary on the CMM2 because the firmware automatically tokenises when you RUN. I think I can update the transpiler to automatically generate and apply short unique name replacements for all Ids, that might get you a few extra % of performance ... of course the resulting code will be almost unreadable, but you only have to maintain the untranspiled form. Best wishes, Tom MMBasic for Linux, Game*Mite, CMM2 Welcome Tape, Creaky old text adventures |
||||
| capsikin Guru Joined: 30/06/2020 Location: AustraliaPosts: 341 |
I thought they were small numbers, no, it wouldn't work how I thought. I'll see if I think of a good work around, otherwise never mind. I don't know if there's a direct way. Anyone? You could remove the GOTO and just set a flag. Then in the main program sub CAVELOOP, exit the sub when the flag is set. And put the GOTO right after the call to CAVELOOP. But I'd wait and see if there's any other suggestions. Great, I'll do that. And first I'll have a play with the new version. |
||||
| matherp Guru Joined: 11/12/2012 Location: United KingdomPosts: 10315 |
abraxas Please could you try the RC12 version posted here . I think I've found up to 10% extra performance depending on application specifically in the MMbasic parsing area |
||||
| capsikin Guru Joined: 30/06/2020 Location: AustraliaPosts: 341 |
I wasn't satisfied with what I came up with. I don't think it would help as much as the other ideas anyway. CONST dirShift = 20 A_LEFTOF(LEFT% >> dirShift)=LEFTOF(LEFT%) A_LEFTOF(RIGHT% >> dirShift)=LEFTOF(RIGHT%) A_LEFTOF(UP% >> dirShift)=LEFTOF(UP%) A_LEFTOF(DOWN% >> dirShift)=LEFTOF(DOWN%) '(similar for rightof) A_RIGHTOF(LEFT% >> dirShift)=RIGHTOF(LEFT%) A_RIGHTOF(RIGHT% >> dirShift)=RIGHTOF(RIGHT%) A_RIGHTOF(UP% >> dirShift)=RIGHTOF(UP%) A_RIGHTOF(DOWN% >> dirShift)=RIGHTOF(DOWN%) ... prefDir = A_LEFTOF(dir >> dirShift) ... finalDir = A_RIGHTOF(dir >> dirShift) Second idea was to hide it inside another function, but at this point I don't know if it's improving the speed. FUNCTION GETLEFTOF dir GETLEFTOF=A_LEFTOF(dir >> dirShift) END FUNCTION FUNCTION GETRIGHTOF dir GETRIGHTOF=A_RIGHTOF(dir >> dirShift) END FUNCTION ... prefDir = GETLEFTOF(dir) ... finalDir = GETRIGHTOF(dir) |
||||
| capsikin Guru Joined: 30/06/2020 Location: AustraliaPosts: 341 |
The RUN command looks promising, but I don't know how it works. |
||||
| thwill Guru Joined: 16/09/2019 Location: United KingdomPosts: 4311 |
You can't use GOTO to do a "long jump" out of a subroutine or function you'll have to set/return a flag and unwind the stack the long way. To be honest just avoid GOTO and GOSUB like the plague in code of any significance. Not sure what you are planning for RUN. It throws away the existing program and its variable storage and starts a new one. Regards, Tom Edited 2020-07-26 22:57 by thwill MMBasic for Linux, Game*Mite, CMM2 Welcome Tape, Creaky old text adventures |
||||
| abraxas Regular Member Joined: 16/06/2020 Location: CanadaPosts: 99 |
Thanks, Peter. I'll try it later today when I get a chance to play with the CMM2. |
||||
| capsikin Guru Joined: 30/06/2020 Location: AustraliaPosts: 341 |
Okay. So you could use RUN to restart the game, if you don't need to keep high scores or anything. Otherwise need to set a flag. Can check the flag in CAVELOOP and do EXIT SUB. Put the initialisation code and the call to CAVELOOP into their own DO LOOP instead of having the GOTO to go back to the initialisation. Edited 2020-07-27 00:37 by capsikin |
||||
| capsikin Guru Joined: 30/06/2020 Location: AustraliaPosts: 341 |
Okay, I've had an idea, I hope the explanation makes sense. Every cell location has a flag "noTriggerScan". If that's set, an object moving off it (particularly a firefly, which moves a lot) doesn't have to add the surrounding locations to the scan list, because there's no rocks or diamonds waiting to fall into it. if (noTriggerScan(col,row)=0) then ADDSCANFORHEAVY ... Don't bother setting the flag for empty cells, but if an object moves into an empty cell, set the flag. So basically, set it for any cell an object moves into, except when there was already an item there, like rockford pushing a rock or collecting a diamond or earth. Maybe just don't set it when it's rockford moving into the cell, if that's easier. noTriggerScan(testCol,testRow)=1 The flag needs to be turned off when there's a rock waiting for the space. So when a rock is scanned, and finds no path to fall/roll, turn off the flag for the 5 locations it could roll towards (left/right/down/down left/down right). in the scanlist section: IF tile AND FALLING% THEN MAKECMD col,row,CT_CLEAR_BITS%,FALLING%,cmdList(),cmdIndex noTriggerScan(col-1,row) =0 noTriggerScan(col+1,row) =0 noTriggerScan(col-1,row+1)=0 noTriggerScan(col ,row+1)=0 noTriggerScan(col+1,row+1)=0 ENDIF (if it works, you may be able to adapt the idea to use a bit in the room array instead of a separate array) With this improvement, for most firefly moves, they wouldn't have to do ADDSCANFORHEAVY you'd need to add that they add a scan for just their new location, instead. (later ...) I tried this, it seems to be a major speed up. I've only added the check for fireflies so far, so it won't prevent falling diamonds and rocks from calling ADDSCANFORHEAVY unnecessarily. And I haven't coded setting the flag by falling rocks and diamonds either. So that's further room for improvement. I think I had to move clearing the "noTriggerScan" flag out of the "IF" part, to include the case where there was a pushed rock that should fall once the fireflies get out of the way. see (or run) gamecjm2.bas in the attachment zip file for the working code. Also a demo of replacing GOTO <something> with RUN gamecjm2buggy.bas is an attempt to recreate a bug when a pushed rock didn't roll even after the fireflies got out of the way, not sure if I did as it was always hard bug to trigger. gamecjm.bas I think was mainly timing measurement code I tried earlier. BDASH.zip |
||||
| Page 1 of 2 |
|||||
 Print this page |
 |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2025 |
