Macro said:
Is flaky lately
Spin Pac-Dizzy Isometric 3D on Pac-Man hardware
- Thread starter Hurray Banana
- Start date
Is flaky lately
Room renderer 1st draft written
[tube]P6pwGH3eIfc[/tube]
Welcome to the latest update to the Spin Pac-Dizzy development. In this video I show the first draft of the full room renderer. This takes unpacked room data consisting of 256 bytes which describes what objects occupy the room. each room is a 7x7x8 area of objects.
The room has to be drawn back to front in a diamond pattern which is quite a challenge as you need to traverse the 2d array data for a particular floor level (of which there are eight) diagonally.
Two floors are encoded together in the un-packed format consisting of 7 bytes for each row and 7 for each column (if looking at it in 2d). odd floors have object numbers in the upper nibble of each byte (there are a maximum of 15 objects) and the even floors occupy the lower nibble.
It works pretty well (as you can hopefully see)
I fixed a few unseen errors in the compound lookup code and now I'm pretty sure that is fully working.
Next on the list to do:
+Implement all four viewpoints
+Write room unpacking code
+Sort out basic movement for Gerald
+Interaction with room
+maybe look at some form of compression for packed room data
+create as any levels as I have memory left for, I'm using about 4KB at the moment (12 KB left)
[tube]P6pwGH3eIfc[/tube]
Welcome to the latest update to the Spin Pac-Dizzy development. In this video I show the first draft of the full room renderer. This takes unpacked room data consisting of 256 bytes which describes what objects occupy the room. each room is a 7x7x8 area of objects.
The room has to be drawn back to front in a diamond pattern which is quite a challenge as you need to traverse the 2d array data for a particular floor level (of which there are eight) diagonally.
Two floors are encoded together in the un-packed format consisting of 7 bytes for each row and 7 for each column (if looking at it in 2d). odd floors have object numbers in the upper nibble of each byte (there are a maximum of 15 objects) and the even floors occupy the lower nibble.
It works pretty well (as you can hopefully see)
I fixed a few unseen errors in the compound lookup code and now I'm pretty sure that is fully working.
Next on the list to do:
+Implement all four viewpoints
+Write room unpacking code
+Sort out basic movement for Gerald
+Interaction with room
+maybe look at some form of compression for packed room data
+create as any levels as I have memory left for, I'm using about 4KB at the moment (12 KB left)
cmonkey said:
Yeah will do mate, half term nearly over so quite scary couple of months coming up now as we prepare students for new a levels exams in June.
cparsonsuk
Active member
- Credits
- 205CR
Amazing stuff Eric, great vid!
cNp said:
Cheers mate
This shows what you can achieve in 2 days if you can focus and find the time. I had nothing except loads of data and a hocum single tile renderer on Tuesday morning. Quite chuffed with my own progress here.
Managed to spend a little more time today on the code this is the result, rotating view.
[tube]zWHsuDhmcio[/tube]
Managed to implement rendering from any of the four general directions now and hooked this up to the player 2 start button.
Implementing this involves changing just 7 bytes of data to enable the 3 other view orientations, thanks to the way I implemented the original render algorithm.
Need to move on to speeding up the search of the compound tiles. The home screen (the flat one) searches over 500 times during rendering, so this is obviously something I can spend some time on.
Last video for a while will be tomorrow and that will be running on hardware.
[tube]zWHsuDhmcio[/tube]
Managed to implement rendering from any of the four general directions now and hooked this up to the player 2 start button.
Implementing this involves changing just 7 bytes of data to enable the 3 other view orientations, thanks to the way I implemented the original render algorithm.
Need to move on to speeding up the search of the compound tiles. The home screen (the flat one) searches over 500 times during rendering, so this is obviously something I can spend some time on.
Last video for a while will be tomorrow and that will be running on hardware.
Nes4life said:
Thanks Phil, I hadn't properly touched this for over a year, but just made the time to sit down this week for a few hours and set myself the task of converting the algorithms in my head into viable assembler code.
Sadly time is up for the near future but I'll come back to this when I can. I'm gonna re-write the search code before attempting to implement any player environment interaction as that is gonna need a massive sit down coding session.
Mitchell Gant
Active member
Wow you have been busy!
That's a lot of effort to put all that in, well done.
Visually it looks really good now that there's some shapes being drawn.
That's a lot of effort to put all that in, well done.
Visually it looks really good now that there's some shapes being drawn.
Mitchell Gant said:
Thank neil, yeah I've been a bit single bloody minded over the last few days, can't do this sort of shiz in dribbs and drabbs
backflipper
Active member
Top work Eric. It looks amazing already.
backflipper said:
Thanks Steve
Final update for a whole folks, burn't 5 2532 roms and stuffed them in my midway pac-man board, here's the results
moto3g does not take a good video and the crt washes it out a lot, did my best
[tube]O1I0U0se0Ds[/tube]
moto3g does not take a good video and the crt washes it out a lot, did my best
[tube]O1I0U0se0Ds[/tube]
Been working on Spin Pac-Dizzy, trying to sort out the impulse and deceleration of the main character (which is tricky to balance).
Anyway got round to designing 3 data different structures to allow 3 different compound tile lookup methods. Remember there are no transparent tiles it's just a single layer of tiles, so I have to use compound tiles to give the illusion of drawing tiles on top of each other.
The original method just linear searched a linear array with 3 byte values at each location, this was never intended to be the final version, just wanted something simple to test the rest of the renderer (which was complicated enough).
The original method required 930 bytes of data and 58 bytes of code. There are 94 tiles that have compound tiles associated with them, the most and single tile has is 16 compound tiles (that is there are 16 different tiles that can be placed on top of it in a scene).
The compound routine lookup needs to find out if an existing tile on the screen has any corresponding compound tiles (tiles that give the illusion of two tiles sitting on top of each other). If there aren't then the new tile overlapping is just written to the screen. IF there are any we need to then find if our new tile has a compound relation, if it doesn't then the new tile is written, if it does then the compound tile is written.
compound tile data in linear form
This involves basically searching twice, once for the existing tile and again for the new tile. unfortunately this has to be done for every object in a scene here's some simple maths about how many objects and tiles.
maximum objects in a scene is 7x7x8 = 392 objects
the number of tiles used to represent a standard half height cube is 12
So a room full of half height cubes (392), would require 4704 tile writes and hence 4704 searches of the compound tile data. This means this routine is crucial to the whole rendering process and needs to be optimised without wasting too much memory.
I came up with 3 different fast compound tile search methods, that required data being written in a specific way for each.
Method 1) binary tree index: 69 bytes of code and 1186 bytes of data
pointing to a linear array of tile pairs (new tile, compound tile), searched with a linear search
Each node in the tree takes 5 bytes:
Key byte: existing tile in tilemap we want to overwrite
compound pair array addr: where compound tiles for this tile existing
left offset byte: to move to the node hanging on the left branch
right offset byte: to move to the node hanging on the right branch
This tree takes up 470 bytes. It wasn't trivial to produce this data, which was a great exercise in itself. I had to binary search my linear data to create a tree strucutre, unfortunately the branch distances were larger than 255 bytes so I then had to breadth first search the tree to generate a node order that meant the offsets never got over 255 bytes, it then had to link up the tree in this depth ordered format. Like I say this was a wicked little coding exercise and even though I won't use this method going forward, it was cool doing it.
this uses a tree containing 470 bytes for the index, plus the linear pairs (shared between all 3 algorithms) of 620 bytes
Method 2) linear index: 85 bytes of code and 998 bytes of data
searched using a binary search, pointing to the same linear tile pair array
Has the tree is basically a binary searchable data structure I decided to try and lay the data out in a linear array and use the binary search technique on this.
The index needed 3 bytes per node:
Key byte: existing tile in tilemap we want to overwrite
compound pair array addr: where compound tiles for this tile existing
as this takes up 282 bytes it's just over the 255 limit for organising the top and bottom pointers, so a little jiggery pokery had to be performed, which made the code longer than I liked.
Binary search is a fantastic technique that allows you to discard half your data set every time you examine a single node, this makes it an ultra fast search method.
Method 3) index lookup table: 47 bytes of code and 1154 bytes of data (cheaper than the tree method !)
This is a memory waster, but it was worth a try anyway as it's the quickest method possible. As there are 219 different tiles that can be placed into a scene but only 94 that actually have compound tiles associated, there is gonna be some wastage. This cannot be a spare lookup table, so using this method 250 bytes are unused. I should be able to slot other fixed game data (as its in ROM) into these spare locations as some of them are in continuous blocks, so all is not lost.
So this system just consists of the 16 bit addresses of the compound tile pairs, it's a simple case of doubling the value of the existing tile looking for and adding this to the base of the lookup table, all very quick and pretty straightforward.
I spent some time writing code so that I could dynamically switch between the different compound lookup methods, so that I could test their effect on rendering, the results are interesting.
The lookup index manages to shave about 85% of the time taken by the original routine and as actually twice as quick on interesting scenes compared to the quicker index search methods 1 and 2. It does use 7% of the available ROM I have, which coupled with the renderer takes it to around 12% of the total ROM.
I'm decided to go with that method, but if I have to I can see that the other search methods are pretty quick and could be used if I get desperate.
I'll record a video showing the rendering tomorrow and you'll be able to see the speed differences quite clearly as I unlocked the view rotation so it runs continuously.
Here's images of the two scenes rendered
HB scene
Walled floor (quite intensive to render as all objects in front of another object)
Here's a spreadsheet of the data to look at and the two scenes being rendered.
Anyway got round to designing 3 data different structures to allow 3 different compound tile lookup methods. Remember there are no transparent tiles it's just a single layer of tiles, so I have to use compound tiles to give the illusion of drawing tiles on top of each other.
The original method just linear searched a linear array with 3 byte values at each location, this was never intended to be the final version, just wanted something simple to test the rest of the renderer (which was complicated enough).
The original method required 930 bytes of data and 58 bytes of code. There are 94 tiles that have compound tiles associated with them, the most and single tile has is 16 compound tiles (that is there are 16 different tiles that can be placed on top of it in a scene).
The compound routine lookup needs to find out if an existing tile on the screen has any corresponding compound tiles (tiles that give the illusion of two tiles sitting on top of each other). If there aren't then the new tile overlapping is just written to the screen. IF there are any we need to then find if our new tile has a compound relation, if it doesn't then the new tile is written, if it does then the compound tile is written.
compound tile data in linear form
This involves basically searching twice, once for the existing tile and again for the new tile. unfortunately this has to be done for every object in a scene here's some simple maths about how many objects and tiles.
maximum objects in a scene is 7x7x8 = 392 objects
the number of tiles used to represent a standard half height cube is 12
So a room full of half height cubes (392), would require 4704 tile writes and hence 4704 searches of the compound tile data. This means this routine is crucial to the whole rendering process and needs to be optimised without wasting too much memory.
I came up with 3 different fast compound tile search methods, that required data being written in a specific way for each.
Method 1) binary tree index: 69 bytes of code and 1186 bytes of data
pointing to a linear array of tile pairs (new tile, compound tile), searched with a linear search
Each node in the tree takes 5 bytes:
Key byte: existing tile in tilemap we want to overwrite
compound pair array addr: where compound tiles for this tile existing
left offset byte: to move to the node hanging on the left branch
right offset byte: to move to the node hanging on the right branch
This tree takes up 470 bytes. It wasn't trivial to produce this data, which was a great exercise in itself. I had to binary search my linear data to create a tree strucutre, unfortunately the branch distances were larger than 255 bytes so I then had to breadth first search the tree to generate a node order that meant the offsets never got over 255 bytes, it then had to link up the tree in this depth ordered format. Like I say this was a wicked little coding exercise and even though I won't use this method going forward, it was cool doing it.
this uses a tree containing 470 bytes for the index, plus the linear pairs (shared between all 3 algorithms) of 620 bytes
Method 2) linear index: 85 bytes of code and 998 bytes of data
searched using a binary search, pointing to the same linear tile pair array
Has the tree is basically a binary searchable data structure I decided to try and lay the data out in a linear array and use the binary search technique on this.
The index needed 3 bytes per node:
Key byte: existing tile in tilemap we want to overwrite
compound pair array addr: where compound tiles for this tile existing
as this takes up 282 bytes it's just over the 255 limit for organising the top and bottom pointers, so a little jiggery pokery had to be performed, which made the code longer than I liked.
Binary search is a fantastic technique that allows you to discard half your data set every time you examine a single node, this makes it an ultra fast search method.
Method 3) index lookup table: 47 bytes of code and 1154 bytes of data (cheaper than the tree method !)
This is a memory waster, but it was worth a try anyway as it's the quickest method possible. As there are 219 different tiles that can be placed into a scene but only 94 that actually have compound tiles associated, there is gonna be some wastage. This cannot be a spare lookup table, so using this method 250 bytes are unused. I should be able to slot other fixed game data (as its in ROM) into these spare locations as some of them are in continuous blocks, so all is not lost.
So this system just consists of the 16 bit addresses of the compound tile pairs, it's a simple case of doubling the value of the existing tile looking for and adding this to the base of the lookup table, all very quick and pretty straightforward.
I spent some time writing code so that I could dynamically switch between the different compound lookup methods, so that I could test their effect on rendering, the results are interesting.
The lookup index manages to shave about 85% of the time taken by the original routine and as actually twice as quick on interesting scenes compared to the quicker index search methods 1 and 2. It does use 7% of the available ROM I have, which coupled with the renderer takes it to around 12% of the total ROM.
I'm decided to go with that method, but if I have to I can see that the other search methods are pretty quick and could be used if I get desperate.
I'll record a video showing the rendering tomorrow and you'll be able to see the speed differences quite clearly as I unlocked the view rotation so it runs continuously.
Here's images of the two scenes rendered
HB scene
Walled floor (quite intensive to render as all objects in front of another object)
Here's a spreadsheet of the data to look at and the two scenes being rendered.
cparsonsuk
Active member
- Credits
- 205CR
Bloody amazing stuff Eric... I've no idea what you're on about half the time but still love reading about your work!
cheers Chris, I'll post a video this morning after my run, just off
Video uploaded now
[tube]hZB_jfpkjQ8[/tube]
watch in hi-res (when it's finished processing fully)
[tube]hZB_jfpkjQ8[/tube]
watch in hi-res (when it's finished processing fully)