I've done about as much of Alien 8 as I need to atm. My objective was to determine whether or not the engine core was improved (it wasn't) and whether I should/could use those improvements in my Knight Lore port (N/A). How far I take it from here will depend on whether I end up porting it to other platforms.
I have released a preliminary disassembly and an alpha binary for the TRS-80.
I'm intrigued by the shooting mechanic added to Pentagram. I was originally not going to look at it, but given how similar Alien 8 was to Knight Lore, and how quickly I was able to reverse-engineer the core, I think I'll give it a look as well!
I have been doing something similar to your RetroPorts and ported Pentagram to Atari 8bit: see here: http://atariage.com/forums/topic/247323-new-game-port-wip-pentagram/. I developed simple recompiler which took disassembly listing and produced equivalent 6502 code. I also developed a tool for debugging 6502 version, which run Z80 and 6502 versions parallely and compared memory accesses.
I am looking now for information how to speed up my 6502 port. I found that two most demanding procedures in terms of CPU used are sprite render and sprite sorter (calc_display_order_and_render). I am going to improve sprite renderer by changing data formats (separating pixel and mask data which will allow faster access on 6502). I also found that background sprites have masks equal to pixel data, so rendering mask can be skipped and sprite rendering can be faster. I see you have found a way to optimize sprite sorting. Can you elaborate some more details about method you used?
I have been doing something similar to your RetroPorts and ported Pentagram to Atari 8bit: see here: http://atariage.com/forums/topic/247323-new-game-port-wip-pentagram/. I developed simple recompiler which took disassembly listing and produced equivalent 6502 code. I also developed a tool for debugging 6502 version, which run Z80 and 6502 versions parallely and compared memory accesses.
Wow, that's cool! Don't suppose you've developed one for Z80->6809 have you? ;) That's my next task, to port it to the TRS-80 Color Computer 3. I've done 6502->6809 by hand before (Lode Runner) but Z80 is going to be a challenge.
Did you study the (homebrew) Atari 800 port of Knight Lore? Or the official BBC Micro port? They might have some hints that could help you with optimisations for the Atari.
I am looking now for information how to speed up my 6502 port. I found that two most demanding procedures in terms of CPU used are sprite render and sprite sorter (calc_display_order_and_render). I am going to improve sprite renderer by changing data formats (separating pixel and mask data which will allow faster access on 6502). I also found that background sprites have masks equal to pixel data, so rendering mask can be skipped and sprite rendering can be faster. I see you have found a way to optimize sprite sorting. Can you elaborate some more details about method you used?
I was planning to do some profiling but had my suspicions that sprite sorting was a big bottleneck. I also suspect the routines that calculate overlap/intersection take some time as well, as there are a lot of objects to check against one-another. Interesting to read your findings, thanks!
In my Lode Runner port, I reorganised the Apple II graphics data completely for the Coco3. In fact, I even generated coloured sprites from the video artifact output of MESS for use on the Coco3! Certainly makes sense to tweak the graphics for the target machine.
Not sure why you're under the impression that I have optimised sprite sorting?!? In fact, that's the only routine that I don't really understand the maths for. The only code that will be modified in the short term is the rendering for TRS-80. Everything else runs as-is. In fact, that's the way I'd prefer - with the exception of hardware access routines of course - to have a 100% accurate game play experience. So unfortunately I can't really help with optimisations atm, especially considering I know next-to-nothing about the Atari hardware.
I'd (humbly) suggest you study my Knight Lore disassembly, which is 99.9% complete, then look at my Pentagram disassembly in light of that. I haven't commented anything that is the same as Knight Lore, but all the data is formatted and labelled and all the routines are named, so it should be easy to follow most of what is happening. My Pentagram listing is already much more advanced than the Retrospec version, and is relocatable.
Good luck with it! I'll be following your progress with interest!
Wow, that's cool! Don't suppose you've developed one for Z80->6809 have you? ;) That's my next task, to port it to the TRS-80 Color Computer 3. I've done 6502->6809 by hand before (Lode Runner) but Z80 is going to be a challenge.
Did you study the (homebrew) Atari 800 port of Knight Lore? Or the official BBC Micro port? They might have some hints that could help you with optimisations for the Atari.
I checked BBC Micro version (Atari 800 port is based on it). BBC Port is a little bit different, because they had only 32KB RAM available, but faster CPU 2MHz 6502, so BBC version focuses on memory usage.
Not sure why you're under the impression that I have optimised sprite sorting?!? In fact, that's the only routine that I don't really understand the maths for. The only code that will be modified in the short term is the rendering for TRS-80. Everything else runs as-is. In fact, that's the way I'd prefer - with the exception of hardware access routines of course - to have a 100% accurate game play experience. So unfortunately I can't really help with optimisations atm, especially considering I know next-to-nothing about the Atari hardware.
I got impression you optimized sprite sorting after reading about your C port of Knight Lore, but maybe I misread something :)
Anyway, I think sorting may work better, if didivided into parts, one part with drawing objects for one wipe/draw rectangle. Currently code sorts all objects at once which gives n*n computational complexity, so it grows very fast with increasing number of objects. So. if there are two wipe/draw rectangles, drawing routing could be called twice, but each time with n/2 objects, so total time spent in this procedure should be n*n/2 (two times faster). But, if two wipe/draw rectangles intersect, they would probably need to be merged for proper sorting.
Also, sprite drawing doesn't use any clipping, and if drawing with wipe/draw rectangles, sprites could be clipped to current wipe/draw rectangle.
I guess it could be easy to implement such improvements in your C version first, before attempting to implement them in ASM version.
I'd (humbly) suggest you study my Knight Lore disassembly, which is 99.9% complete, then look at my Pentagram disassembly in light of that.
Found that already, and I am really impressed about quality :)
You posted on the blog that Pentagram changed memory layout without a reason, but I think that reason was Spectrum contended memory - i.e. RAM at $4000 - $7fff which is shared between ULA (graphics generator) and Z80 CPU. Because ULA has priority, Z80 may be stalled while acessing RAM, which results in worse perfrmance if Z80 need to access RAM at $4000-$7fff. So they probably moved work RAM variables and object structures to higher RAM adresses to get better performance.
I checked BBC Micro version (Atari 800 port is based on it). BBC Port is a little bit different, because they had only 32KB RAM available, but faster CPU 2MHz 6502, so BBC version focuses on memory usage.
Anyway, I think sorting may work better, if didivided into parts, one part with drawing objects for one wipe/draw rectangle. Currently code sorts all objects at once which gives n*n computational complexity, so it grows very fast with increasing number of objects. So. if there are two wipe/draw rectangles, drawing routing could be called twice, but each time with n/2 objects, so total time spent in this procedure should be n*n/2 (two times faster). But, if two wipe/draw rectangles intersect, they would probably need to be merged for proper sorting.
Also, sprite drawing doesn't use any clipping, and if drawing with wipe/draw rectangles, sprites could be clipped to current wipe/draw rectangle.
I guess it could be easy to implement such improvements in your C version first, before attempting to implement them in ASM version.
I won't pretend to have digested all you've said right now. My old brain doesn't work like it used to. :( But you're right, it would be easier to implement (and debug) in C first.
In fact I have plans to develop my own game using the engine, and I will definitely be implementing it in C first, before porting it back to the 8-bit platform(s).
Found that already, and I am really impressed about quality :)
You posted on the blog that Pentagram changed memory layout without a reason, but I think that reason was Spectrum contended memory - i.e. RAM at $4000 - $7fff which is shared between ULA (graphics generator) and Z80 CPU. Because ULA has priority, Z80 may be stalled while acessing RAM, which results in worse perfrmance if Z80 need to access RAM at $4000-$7fff. So they probably moved work RAM variables and object structures to higher RAM adresses to get better performance.
Thanks! I updated it yesterday with the handle_pause() routine, which I only discovered by accident when playing my re-assembled Pentagram in MESS! ;)
Interesting note on the re-arrangement - thanks! Most of the data before $8000 is the location and block/background type information that is only accessed when entering (and building information for) a room. There's a handful of sprites there too... they perhaps should have put the main menu code in there...
I've just ran through your blog, it makes a most interesting read. Looks like your having fun. It is a nice feeling when you get some sprites from an 8 bit source displaying on another isn't it.
There are lots of optimizations which you may consider while porting Knight Lore/Alien 8/Pentagram to other 8 bit platforms:
- frame skipping (game renders every second frame if it notices rendering of previous frame took too much time)
- optimized sorting algorithm (ame makes lots of comparisons of objects and I found a way to make these comparison do less and perform better)
- cached array of sorted sprites (if game determines that list of objects didn't change between frames, it uses sorted list from previous frame - sorting algorithm in game is faster when list is sorted)
- sprite data splitted for pixel data and mask data (rendering is faster on 6502)
- some sprites have masks equal to their data (mostly background trees and walls) - mask is removed for these (saves space) and rendering is faster
- spider and dragon sprites have flipped version included in game (as these are two which are flipped most often by the game)
If you are interested in details, I may describe them for you.
I liked your analysis of CPC version of Kinght Lore. Sadly, my platform cannot do 4 colors graphics in 256*192, so no possibility to prepare version on Atari with CPC graphics.
What's your plan for converting Z80 assembly to 6809? (I understood you plan to prepare CoCo3 version of Knight Lore and I think you are not going to use C version for that port?).
It's great, very interesting thanks! Tcdev, will you be releasing the C source to your ports please?
Yes, I will, soon. The Amiga port is all-but-complete, and the Neo Geo port has but one technical challenge to overcome. There's a few game play bugs I have to sort out first, but when I get around to looking at them, I'm not expecting them to take too long to fix.
Right now I'm overseas for work without the resources to continue with the Amiga/Neo Geo, so whilst I'm away I'm concentrating on the 6809 (Coco3) port which is going far better than I'd dared imagine! I'll probably want to continue this when I get home though, while I'm on a roll. So that may delay the C port release a little longer.
But rest assured it will get released!
There are lots of optimizations which you may consider while porting Knight Lore/Alien 8/Pentagram to other 8 bit platforms:
- frame skipping (game renders every second frame if it notices rendering of previous frame took too much time)
- optimized sorting algorithm (ame makes lots of comparisons of objects and I found a way to make these comparison do less and perform better)
- cached array of sorted sprites (if game determines that list of objects didn't change between frames, it uses sorted list from previous frame - sorting algorithm in game is faster when list is sorted)
- sprite data splitted for pixel data and mask data (rendering is faster on 6502)
- some sprites have masks equal to their data (mostly background trees and walls) - mask is removed for these (saves space) and rendering is faster
- spider and dragon sprites have flipped version included in game (as these are two which are flipped most often by the game)
If you are interested in details, I may describe them for you.
I liked your analysis of CPC version of Kinght Lore. Sadly, my platform cannot do 4 colors graphics in 256*192, so no possibility to prepare version on Atari with CPC graphics.
What's your plan for converting Z80 assembly to 6809? (I understood you plan to prepare CoCo3 version of Knight Lore and I think you are not going to use C version for that port?).
Nice work on Pentagram!
All those optimisations you describe make sense! I'll keep them in mind if I need them - thanks!!!
Check the blog for progress on the Coco3! I'm amazed at the progress; I've got about 30 years experience in Z80 and very little in 6809, but I'm finding that the 6809 is a great CPU and thus far I've had very little trouble converting the code.
One of these days I'm going to have to port a game _to_ the Speccy! ;)
Comments
My games for the Spectrum: Dingo, The Speccies, The Speccies 2, Vallation, SQIJ.
Twitter: Sokurah
My games for the Spectrum: Dingo, The Speccies, The Speccies 2, Vallation, SQIJ.
Twitter: Sokurah
I have released a preliminary disassembly and an alpha binary for the TRS-80.
I'm intrigued by the shooting mechanic added to Pentagram. I was originally not going to look at it, but given how similar Alien 8 was to Knight Lore, and how quickly I was able to reverse-engineer the core, I think I'll give it a look as well!
TRS-80 version up and running too.
I have been doing something similar to your RetroPorts and ported Pentagram to Atari 8bit: see here: http://atariage.com/forums/topic/247323-new-game-port-wip-pentagram/. I developed simple recompiler which took disassembly listing and produced equivalent 6502 code. I also developed a tool for debugging 6502 version, which run Z80 and 6502 versions parallely and compared memory accesses.
I am looking now for information how to speed up my 6502 port. I found that two most demanding procedures in terms of CPU used are sprite render and sprite sorter (calc_display_order_and_render). I am going to improve sprite renderer by changing data formats (separating pixel and mask data which will allow faster access on 6502). I also found that background sprites have masks equal to pixel data, so rendering mask can be skipped and sprite rendering can be faster. I see you have found a way to optimize sprite sorting. Can you elaborate some more details about method you used?
Mariusz.
Wow, that's cool! Don't suppose you've developed one for Z80->6809 have you? ;) That's my next task, to port it to the TRS-80 Color Computer 3. I've done 6502->6809 by hand before (Lode Runner) but Z80 is going to be a challenge.
Did you study the (homebrew) Atari 800 port of Knight Lore? Or the official BBC Micro port? They might have some hints that could help you with optimisations for the Atari.
I was planning to do some profiling but had my suspicions that sprite sorting was a big bottleneck. I also suspect the routines that calculate overlap/intersection take some time as well, as there are a lot of objects to check against one-another. Interesting to read your findings, thanks!
In my Lode Runner port, I reorganised the Apple II graphics data completely for the Coco3. In fact, I even generated coloured sprites from the video artifact output of MESS for use on the Coco3! Certainly makes sense to tweak the graphics for the target machine.
Not sure why you're under the impression that I have optimised sprite sorting?!? In fact, that's the only routine that I don't really understand the maths for. The only code that will be modified in the short term is the rendering for TRS-80. Everything else runs as-is. In fact, that's the way I'd prefer - with the exception of hardware access routines of course - to have a 100% accurate game play experience. So unfortunately I can't really help with optimisations atm, especially considering I know next-to-nothing about the Atari hardware.
I'd (humbly) suggest you study my Knight Lore disassembly, which is 99.9% complete, then look at my Pentagram disassembly in light of that. I haven't commented anything that is the same as Knight Lore, but all the data is formatted and labelled and all the routines are named, so it should be easy to follow most of what is happening. My Pentagram listing is already much more advanced than the Retrospec version, and is relocatable.
Good luck with it! I'll be following your progress with interest!
No, I am not 6809 expert at all :)
I checked BBC Micro version (Atari 800 port is based on it). BBC Port is a little bit different, because they had only 32KB RAM available, but faster CPU 2MHz 6502, so BBC version focuses on memory usage.
I got impression you optimized sprite sorting after reading about your C port of Knight Lore, but maybe I misread something :)
Anyway, I think sorting may work better, if didivided into parts, one part with drawing objects for one wipe/draw rectangle. Currently code sorts all objects at once which gives n*n computational complexity, so it grows very fast with increasing number of objects. So. if there are two wipe/draw rectangles, drawing routing could be called twice, but each time with n/2 objects, so total time spent in this procedure should be n*n/2 (two times faster). But, if two wipe/draw rectangles intersect, they would probably need to be merged for proper sorting.
Also, sprite drawing doesn't use any clipping, and if drawing with wipe/draw rectangles, sprites could be clipped to current wipe/draw rectangle.
I guess it could be easy to implement such improvements in your C version first, before attempting to implement them in ASM version.
Found that already, and I am really impressed about quality :)
You posted on the blog that Pentagram changed memory layout without a reason, but I think that reason was Spectrum contended memory - i.e. RAM at $4000 - $7fff which is shared between ULA (graphics generator) and Z80 CPU. Because ULA has priority, Z80 may be stalled while acessing RAM, which results in worse perfrmance if Z80 need to access RAM at $4000-$7fff. So they probably moved work RAM variables and object structures to higher RAM adresses to get better performance.
I won't pretend to have digested all you've said right now. My old brain doesn't work like it used to. :( But you're right, it would be easier to implement (and debug) in C first.
In fact I have plans to develop my own game using the engine, and I will definitely be implementing it in C first, before porting it back to the 8-bit platform(s).
Thanks! I updated it yesterday with the handle_pause() routine, which I only discovered by accident when playing my re-assembled Pentagram in MESS! ;)
Interesting note on the re-arrangement - thanks! Most of the data before $8000 is the location and block/background type information that is only accessed when entering (and building information for) a room. There's a handful of sprites there too... they perhaps should have put the main menu code in there...
My games for the Spectrum: Dingo, The Speccies, The Speccies 2, Vallation, SQIJ.
Twitter: Sokurah
Pat
http://www.wintzx.fr/blog
http://retroports.blogspot.dk/
...last update less than an hour ago. ;) :)
My games for the Spectrum: Dingo, The Speccies, The Speccies 2, Vallation, SQIJ.
Twitter: Sokurah
@luny@mstdn.games
https://www.luny.co.uk
There are lots of optimizations which you may consider while porting Knight Lore/Alien 8/Pentagram to other 8 bit platforms:
- frame skipping (game renders every second frame if it notices rendering of previous frame took too much time)
- optimized sorting algorithm (ame makes lots of comparisons of objects and I found a way to make these comparison do less and perform better)
- cached array of sorted sprites (if game determines that list of objects didn't change between frames, it uses sorted list from previous frame - sorting algorithm in game is faster when list is sorted)
- sprite data splitted for pixel data and mask data (rendering is faster on 6502)
- some sprites have masks equal to their data (mostly background trees and walls) - mask is removed for these (saves space) and rendering is faster
- spider and dragon sprites have flipped version included in game (as these are two which are flipped most often by the game)
If you are interested in details, I may describe them for you.
I liked your analysis of CPC version of Kinght Lore. Sadly, my platform cannot do 4 colors graphics in 256*192, so no possibility to prepare version on Atari with CPC graphics.
What's your plan for converting Z80 assembly to 6809? (I understood you plan to prepare CoCo3 version of Knight Lore and I think you are not going to use C version for that port?).
Right now I'm overseas for work without the resources to continue with the Amiga/Neo Geo, so whilst I'm away I'm concentrating on the 6809 (Coco3) port which is going far better than I'd dared imagine! I'll probably want to continue this when I get home though, while I'm on a roll. So that may delay the C port release a little longer.
But rest assured it will get released!
Nice work on Pentagram!
All those optimisations you describe make sense! I'll keep them in mind if I need them - thanks!!!
Check the blog for progress on the Coco3! I'm amazed at the progress; I've got about 30 years experience in Z80 and very little in 6809, but I'm finding that the 6809 is a great CPU and thus far I've had very little trouble converting the code.
One of these days I'm going to have to port a game _to_ the Speccy! ;)