Tile rendering alternatives

[zhulien]

I am wondering what would be the best method for tendering tiles in a scrollable area. I amnthinking a game area like in Feud.

Imagine 126x126 tile map for a location, each tile can be an index into a 512 byte 16bit tile number so the full tilemap with this Indirection can be 16kb held in main memory. Then actual tiles in extra memory. Allows up to 65536 tile types or tile frames if they are animated. 

Let's say we have a tile as 16x16 pixels (mode 1)... we might display 20x12 tiles as a window to the 126x126 scrollable area.  Whst is the fastest way to render them?

[andycadley]

What practical use is there for 65536 tile types? Especially on a 126*126 map that will only have ~15000 map locations?

[lmimmfn]

The fastest way to render them is(and always is) via the stack but that means disabling interrupts or rendering between interrupts but considering the vsync also, I.e. don't render to screen at the point of vsync(worse if rendering multiple lines with each one impacted by vsync)
You could use dual buffering, using the stack on the back buffer thus eliminating the interrupt issues.

[lightforce6128]

That is an interesting question. I never implemented a tile based display. But I got some ideas.

If nested tiles are used - bigger tiles or blocks made of several smaller tiles - then the tile map can span much more pixels with less memory consumption. I did some calculation for tiles of 16x16 pixels, blocks of 4x4 tiles, and a map of 135x30 blocks. This map would show 16 megapixels and 270 screens.

- The pixel data of 256 tiles can be stored in one 16K page. More tiles will need more pages. The maximum in this data structure is reached by unique blocks with a total of 4096 tiles in 16 pages or 4 banks.
- The tile indices currently visible on screen can be organized in a 2D ring buffer of 512 bytes (with some additional off-screen).
- The tile data of 256 blocks can be stored in 4096 bytes.
- The block data of the map can be stored in 4050 bytes.

The process is the following: If the screen scrolls, it is checked if new blocks get visible. In this case the blocks are unpacked to the 2D ring buffer of tile indices. With this, the newly visible screen part can be updated by drawing the tiles. If animation should be applied, the 2D ring buffer should not store tile indices directly, but indices for an indirection table as suggested.

There are two drawbacks: With this organization of data, if more than one page is used for tiles, for drawing any tile an OUT command is necessary to select the right page. This will slow down drawing. Also, unpacking the blocks does not happen fluently step by step, but for 3 scrolls nothing happens, and then e.g. 5 blocks with 80 tile indices are unpacked at once. This could lead to rugged scrolling if timing is tight.

[lightforce6128]

The fastest way to render them is(and always is) via the stack but that means disabling interrupts or rendering between interrupts but considering the vsync also, I.e. don't render to screen at the point of vsync(worse if rendering multiple lines with each one impacted by vsync)
You could use dual buffering, using the stack on the back buffer thus eliminating the interrupt issues.

The problem here is that the tiles are quite small. After only 2 PUSH commands the stack pointer needs somehow to be moved to the next line. This can be done with this sequence:

Code Select Expand

PUSH BC      ;; 4
PUSH DE      ;; 4
LD HL,offset ;; 3
ADD HL,SP    ;; 3
LD SP,HL     ;; 2

These are 16 NOPs per tile line. Using HL to store the data only needs 14 NOPs in this case:

Code Select Expand

LD (HL),B : INC L ;; 2+1
LD (HL),C : INC L ;; 2+1
LD (HL),D : INC L ;; 2+1
LD (HL),E : INC L ;; 2+1
SET 3,H           ;; 2

For writing 6 bytes instead of 4 bytes per line both methods need 20 NOPs. For writing 8 bytes or more PUSH will be faster. But as long as the tiles are organized in small 16x16 pixels, the second method is a bit faster.

Both methods have the problem that somehow the registers have to be set to the right values to draw nice, non-repetitive tiles. A method that reads the pixel data from somewhere else will be much slower than both.

[zhulien]

What practical use is there for 65536 tile types? Especially on a 126*126 map that will only have ~15000 map locations?

I am coding CPCs first ever MMORPG, its not that I want thst many tilr types. But there could well be more than 255, and the types could include the frames for each depending on whether I store the frames in the tile data itself or each frame is a separate tile. 126x126 is a reasonable location size to wander around between downloads. 

The idea is, new location would download the 16k location tile map with a limit of 255 tile types per location. This can be cached locally on sdcard so future goings to the same location will fetch it from local.  Separately item and NPC data is fetched from a server, debating caching this too, depends if I want roaming NPCs or not. Players locations within the visible view port of the tilemap  are separately fetched multiple times per second so they can be rendered correctly on the players screen. 

I can make sprites/tiles 1 character sized as per my previous POC but id rather make it 2x2 per sprite/tiles and give a more Feud type of look. I am still debating moving half tiles as animation but really nobody can be located halfway between tiles.  It won't be as fluid as Feud but hopefully better than a turn based game, at least from a movement point of view. 

[zhulien]

The fastest way to render them is(and always is) via the stack but that means disabling interrupts or rendering between interrupts but considering the vsync also, I.e. don't render to screen at the point of vsync(worse if rendering multiple lines with each one impacted by vsync)
You could use dual buffering, using the stack on the back buffer thus eliminating the interrupt issues.

I am thinking of keeping the location tile map in main memory which includes 512 bytes of tile indirections.  Usually a location would have repeated tiles so I would quickly make a unique list of tyles (or maybe I can have thst prepare pared also, make it 125x125 but I'd likely need to make a list of unique tiles thst are visible, not within the entire map. I can then reduce the number of bank switches to render the visible tiles.  It could work on 64k machines but I'd have to test how fast tiles could be loaded from sdcard whether it can still be playable.

[zhulien]

What practical use is there for 65536 tile types? Especially on a 126*126 map that will only have ~15000 map locations?

Just to clarify the 126x126 is the size of a single location, not the total map size. Its the location tile map. It could be a massive dungeon section or part of a huge plains.

[zhulien]

The fastest way to render them is(and always is) via the stack but that means disabling interrupts or rendering between interrupts but considering the vsync also, I.e. don't render to screen at the point of vsync(worse if rendering multiple lines with each one impacted by vsync)
You could use dual buffering, using the stack on the back buffer thus eliminating the interrupt issues.

The problem here is that the tiles are quite small. After only 2 PUSH commands the stack pointer needs somehow to be moved to the next line. This can be done with this sequence:

Code Select Expand

PUSH BC      ;; 4
PUSH DE      ;; 4
LD HL,offset ;; 3
ADD HL,SP    ;; 3
LD SP,HL     ;; 2

These are 16 NOPs per tile line. Using HL to store the data only needs 14 NOPs in this case:

Code Select Expand

LD (HL),B : INC L ;; 2+1
LD (HL),C : INC L ;; 2+1
LD (HL),D : INC L ;; 2+1
LD (HL),E : INC L ;; 2+1
SET 3,H           ;; 2

For writing 6 bytes instead of 4 bytes per line both methods need 20 NOPs. For writing 8 bytes or more PUSH will be faster. But as long as the tiles are organized in small 16x16 pixels, the second method is a bit faster.

Both methods have the problem that somehow the registers have to be set to the right values to draw nice, non-repetitive tiles. A method that reads the pixel data from somewhere else will be much slower than both.

The tiles could be 4x4 characters, it means the game would be more zoomed in having about 10x5 viewport. 

[andycadley]

You'd be better off limiting each location to 256 tiles from the same bank and just have the page number part of the data. That way you'll cut out all the indirection which will definitely slow things down. Graphically it probably won't matter much as similar locations will tend to have similar graphics (outdoors, dungeon etc) and if you have that much RAM to play with you can afford to spare some if its necessary to repeat tiles in different tile sets.

[zhulien]

You'd be better off limiting each location to 256 tiles from the same bank and just have the page number part of the data. That way you'll cut out all the indirection which will definitely slow things down. Graphically it probably won't matter much as similar locations will tend to have similar graphics (outdoors, dungeon etc) and if you have that much RAM to play with you can afford to spare some if its necessary to repeat tiles in different tile sets.

I will consider that but I'm thinking that caching the tiles where different locations potentially added over time could have very different appearances.  256 tiles throughout the game doesn't give a lot of variety, does it?

[andycadley]

You'd be better off limiting each location to 256 tiles from the same bank and just have the page number part of the data. That way you'll cut out all the indirection which will definitely slow things down. Graphically it probably won't matter much as similar locations will tend to have similar graphics (outdoors, dungeon etc) and if you have that much RAM to play with you can afford to spare some if its necessary to repeat tiles in different tile sets.

I will consider that but I'm thinking that caching the tiles where different locations potentially added over time could have very different appearances.  256 tiles throughout the game doesn't give a lot of variety, does it?

It doesn't need to be 256 across the entire game. You just have different sets of 256 per type of area. So multiple locations can share one set, or have a unique set if they're a special location. The overall total number of sets of 256 is simply limited by overall RAM. But the savings from avoiding needing to go through an indirection later are massive (you can every easily do a data lookup based on the tile number and the current active bank and you only need to manage the paging once, since all tiles for a given location will be in the same bank).

[zhulien]

You'd be better off limiting each location to 256 tiles from the same bank and just have the page number part of the data. That way you'll cut out all the indirection which will definitely slow things down. Graphically it probably won't matter much as similar locations will tend to have similar graphics (outdoors, dungeon etc) and if you have that much RAM to play with you can afford to spare some if its necessary to repeat tiles in different tile sets.

I will consider that but I'm thinking that caching the tiles where different locations potentially added over time could have very different appearances.  256 tiles throughout the game doesn't give a lot of variety, does it?

It doesn't need to be 256 across the entire game. You just have different sets of 256 per type of area. So multiple locations can share one set, or have a unique set if they're a special location. The overall total number of sets of 256 is simply limited by overall RAM. But the savings from avoiding needing to go through an indirection later are massive (you can every easily do a data lookup based on the tile number and the current active bank and you only need to manage the paging once, since all tiles for a given location will be in the same bank).

Then how do I cache tiles globally through the game if a tile has different IDs per level? The goal is to keep internet payloads to a minimum.

[andycadley]

You'd be better off limiting each location to 256 tiles from the same bank and just have the page number part of the data. That way you'll cut out all the indirection which will definitely slow things down. Graphically it probably won't matter much as similar locations will tend to have similar graphics (outdoors, dungeon etc) and if you have that much RAM to play with you can afford to spare some if its necessary to repeat tiles in different tile sets.

I will consider that but I'm thinking that caching the tiles where different locations potentially added over time could have very different appearances.  256 tiles throughout the game doesn't give a lot of variety, does it?

It doesn't need to be 256 across the entire game. You just have different sets of 256 per type of area. So multiple locations can share one set, or have a unique set if they're a special location. The overall total number of sets of 256 is simply limited by overall RAM. But the savings from avoiding needing to go through an indirection later are massive (you can every easily do a data lookup based on the tile number and the current active bank and you only need to manage the paging once, since all tiles for a given location will be in the same bank).

Then how do I cache tiles globally through the game if a tile has different IDs per level? The goal is to keep internet payloads to a minimum.

Cache entire tile sets, not individual tiles. If you try caching on an individual tile basis the network overhead of fetching a tile at a time will add a massive overhead that negates almost any benefit anyway.

[zhulien]

You'd be better off limiting each location to 256 tiles from the same bank and just have the page number part of the data. That way you'll cut out all the indirection which will definitely slow things down. Graphically it probably won't matter much as similar locations will tend to have similar graphics (outdoors, dungeon etc) and if you have that much RAM to play with you can afford to spare some if its necessary to repeat tiles in different tile sets.

I will consider that but I'm thinking that caching the tiles where different locations potentially added over time could have very different appearances.  256 tiles throughout the game doesn't give a lot of variety, does it?

It doesn't need to be 256 across the entire game. You just have different sets of 256 per type of area. So multiple locations can share one set, or have a unique set if they're a special location. The overall total number of sets of 256 is simply limited by overall RAM. But the savings from avoiding needing to go through an indirection later are massive (you can every easily do a data lookup based on the tile number and the current active bank and you only need to manage the paging once, since all tiles for a given location will be in the same bank).

Then how do I cache tiles globally through the game if a tile has different IDs per level? The goal is to keep internet payloads to a minimum.

Cache entire tile sets, not individual tiles. If you try caching on an individual tile basis the network overhead of fetching a tile at a time will add a massive overhead that negates almost any benefit anyway.

I wouldn't fetch a tile at a time, I would fetch required tiles I don't have in as few requests as possible in 16kb max payload size. If I am to support 128kb machines which is a hope, I'd like tiles for a location to fit within 64kb, ideally 32kb to 48kb. I am still debating how much memory I need for 256 tiles (with multiple frames of animation if possible)

[zhulien]

You'd be better off limiting each location to 256 tiles from the same bank and just have the page number part of the data. That way you'll cut out all the indirection which will definitely slow things down. Graphically it probably won't matter much as similar locations will tend to have similar graphics (outdoors, dungeon etc) and if you have that much RAM to play with you can afford to spare some if its necessary to repeat tiles in different tile sets.

I guess if the tiles are smaller then the indirection becomes a larger percentage of the rendering which is very wasteful as it potentially could be up to 30-40% of the time doing this. If the tiles are larger, the over head decreases.  

Are there any games on cpc that have large animated tiles?  I remember savage having extremely fast zooming sprites in one stage which really looks like a lot of movement in a small timeframe, a hardware trick? 

Perhaps I can have a separate animated tile list so those can be updated more frequently than processing rhe entire lot.

[retro space]

Do you want to port Pico-8 to the CPC?

[zhulien]

Do you want to port Pico-8 to the CPC?

I did actually look at that last year but not sure if anyone would want to... it would be cool if there was a cpcrom that emulated pico-8.  There isn't any mmorpg for that though is there?

[GUNHED]

Well, I'm not sure if this fits here, but for work with tiles I did some software before. Maybe it can help to show how to do it or how to do it not. 

[zhulien]

You'd be better off limiting each location to 256 tiles from the same bank and just have the page number part of the data. That way you'll cut out all the indirection which will definitely slow things down. Graphically it probably won't matter much as similar locations will tend to have similar graphics (outdoors, dungeon etc) and if you have that much RAM to play with you can afford to spare some if its necessary to repeat tiles in different tile sets.

I'm thinking now you are right and not having the redirection  is a lot simpler. Even if the payload is slightly larger, it is so much simpler to manage the tiles already prepared and cached (still prepared) than to gather the separate tiles as required. Even if we have repeated tiled across many locations s, we have gb sdcards which is a non issue.

I'm thinking now of the load process when moving between locations so it is somewhat ok for the multiplayer environment.  I.e. if you went to a door or gateway to another location, check if new one is cached or not, if not cached request new from server (which immediately registers you are not in current location anymore) then tell the server you are at the new location, if cached then just tell the server you have now moved to the new location. This does mean worst case players can have a few seconds delay sometimes between locations but when they are within a location, they will essentially be live with each other as fast as the network card allows constant fetching of a few bytes of data. 

[zhulien]

With 20x12 tiles visible at one time on screen to draw, I take those 240 bytes out of my 16k banked tile map into main memory, then I page in the actual tiles so I can draw them as fast as possible to screen memory without additional banking. I am not double buffering so the drawing isn't that fast.  For animated tiles maybe I shouldn't assume a full screen of animation but there are some benefits like if I had water tiles and want to animate the water. I'm thinking of making a separate animated tile list so I only redraw what needs animating rather than all.  I am also playing with alternate render logic, rather than rendering tiles in sequence maybe I can speed it up by rending tiles of each type in sequence or perhaps try rendering from top scan line downwards (likely slower?).  

[Sykobee (Briggsy)]

One thing to consider is that you won't have 50fps animations.

And you can't really update the full screen even at 12.5fps.

So you might want to consider only updating the animated tiles, which you could store as an x (0..19),y (0..11),tile (0..255),frame (0..3) or similar structure in non-paged memory, filled when drawing the screen the first time. Obviously there would be a limit (by memory, and cpu time to draw).

So say your animations are at 10fps, and if you have 40 animated tiles on the screen out of the 240, you only need to redraw 8 each 50Hz frame. You don't want to do them in order down the screen or you'll get a 'wave' effect of tile updates, so some mixing up of the order is needed.

You also need some care designing each screen to keep under your total animated tile number under what you can handle per frame.

And if there's scrolling this may all get very difficult

And some tiles you might want to animate at 25fps (waterfall), some at 10, and others even at 5fps or 2fps, so things to consider in the screen update code.

[GUNHED]

Well, 50 fps animations with 32 KB screen RAM have been show in games before.

[zhulien]

I was only thinking 2 to 4 fps for animated tiles, to give some movement such as flames flickering or water...  at the moment trying to think of the best way to handle the animated tiles without starting the animation sequence every time the screen scrolls.  Yes I could make it flick screen, but my preference is to scroll. Roland on the ropes gives a rough idea. Hmmm