hex-maps

By wolf_

Ambassador_ (9896)

wolf_'s picture

21-09-2021, 18:32

Say, let's assume a game like Daisenryaku. How would a coder go about implementing the build-up of maps, while not having a game that's slow as hell? As the tiles are interlocking I figure you can't just use a regular quick VDP copy. But alas, nice to know what others would say. I think we can bring back the options to three, unless I forgot something:

1) copy-timp for each complete hexagon, which naturally implicates some slowness and some unused waste around those tiles in vram.
2) copy timp the square/rect part of a hexagon, and do the top and bottom with copy-timp, while half your tile will be pasted faster, there are also more VDP instructions. I dunno whether this is faster than option 1.
3) Fast copy, square/rect tiles in vram, and have quite a bunch o' top/bottom tiles with bits o' neighbour in it. This would implicate that the number of tiles is limited, and/or that perhaps some neighbour constructions aren't possible. In case of a land map, you could assume that sea and high mountains won't be neighbours, but sea and beach are. So, sea and beach require some dedicated tiles.

Keep in mind that I'm talking MSX2 only, I know it'd be easy to use V9990/P1 for this.

I'm experimenting with tiles that are 16x8 in size, with one full hex being 32x32. In the central 32x16 section could be unique things, like buildings, as long as they won't be on those neighbour ramps. So, this would be the third option. I'm just curious what coders would do... Running Naked in a Field of Flowers

Login or register to post comments

By Sandy Brand

Master (245)

Sandy Brand's picture

22-09-2021, 16:51

Hmm, interesting question indeed. I think you are on the right track by trying to reduce the expensive TIMP copies as much as possible.

It looks to me that the amount of combinations of different neighboring tiles is not too large? (although I am not too familiar with the game).

You could try to precompute and store all the 'corner permutations' in VRAM? You would then need to copy the correct permutations for the 'corners' and then just a single copy for the 'middle'.

If you don't have the VRAM available to store all permutations, you could even opt to generate permutations on the fly and store them in some temporary 'work' area in VRAM. When looking at the game you linked I can see a lot of repeating patterns. So drawing the entire map would then consist of a 'pre-phase' whereby you repeatedly identify a permutation, copy that into your work area (this would be 1 HMMM copy, and then a TIMP-copy) and then just copy the result everywhere on the screen where that specific permutations occurs. That should greatly reduce the amount of TIMP-copies you need to do.

However, you might then end up with doing lots of little copy commands (for 8x8 pixels, for example), which is going to be slow again. The problem with lots of small copies is that it lowers the possible through-put on the VDP (it will spend more time idling waiting for the next command), and you will need a lot more Z80 CPU cycles to send data to VDP registers to issue the commands.

Do you really need to redraw the entire screen? If it is just scrolling you can probably copy a large part to the background page and only draw 'new' stuff at the borders right? (well okay, if you need to change the content of the tiles while scrolling this is a bit more problematic, but probably overall there will be less tiles that 'changed' while scrolling, and you can patch these up afterwards)?

By Metalion

Paragon (1445)

Metalion's picture

22-09-2021, 20:01

Why don't you use VDP blitter and 'outs' at the same time ?
You copy the basic square with a copy command, and you 'out' the rest while the command is working.

By bore

Master (133)

bore's picture

22-09-2021, 20:33

The VDP will leave most registers unmodified or in a suitable spot to continue the operation. (Page 85 in V9938 MSX-VIDEO Technical Data Book)
After doing a TIMP-copy for the top part the source and destination are already set up for the HMMM part.
I think you only need to write R42 and R46 between the commands.

By wolf_

Ambassador_ (9896)

wolf_'s picture

22-09-2021, 21:39

Note that I'm merely asking for how coders would handle this kind of map structure, I'm not coding a game or something like that. Wink But the thread about that level contest raised this question for me. Most map editors don't have overlapping bits o' gfx, like there are in a hexagon map. And then I also read that these JP games are slow as f*ck if you don't have a tR.

I did some calculations a few minutes ago. Assuming a hexagon in a 32x32 area, meaning a central 32x16 rectangular area and four 16x8 tiles with ramps between neighbours. With eight different hex-types (or colours if you wish), you need 256 tiles of 16x8 containing all these ramps, that's half a screen in sc5 + a 256x16 area for the eight central areas. In this case any hex tile can match any hex tile at any side. In this case you don't need any timp-copy.

By turbor

Champion (486)

turbor's picture

23-09-2021, 09:53

Of course, there is also the lazy NES Daisenryaku way of doing things, simply use staggered squares instead of hexagons. LOL!

https://youtu.be/S4C8EQ8Iffk?t=104

FYI, internally in most games a hex map is still a 2D square map combined with some special "move logic" . A pretty good overview of these techniques can be found on his interactive page : https://www.redblobgames.com/grids/hexagons/

By bore

Master (133)

bore's picture

23-09-2021, 16:44

wolf_ wrote:

With eight different hex-types (or colours if you wish), you need 256 tiles of 16x8 containing all these ramps

I think you are counting the ramps twice.
For top left edge you have 8*8 combinations, then another 8*8 for top right.
The bottom left is always the top right for someone else so you already have that one. The same goes for bottom right.
So I think it is sufficient with 128 tiles that fits in a 256x64 area.

By wolf_

Ambassador_ (9896)

wolf_'s picture

23-09-2021, 17:08

Yeah, I had some ramps generated here and in this nested loop, so a specific combi happens at two positions in this 2d table. Ahwell, didn't notice yesterday. Wink

Either way, all the better; more space for more hex-tiles that don't need timp-copy. I can even imagine putting all the ramps on their own page and copy all ramps in a second pass of map build-up, after the central tiles coming from another page.

Now, assuming that these central tiles can have several variations, there can be quite a few tiles in fact. Now, I still wonder whether this particular method would be the preferred method among coders.

By bore

Master (133)

bore's picture

23-09-2021, 18:45

The preferred method is the one that gets reasonable performance.

It looks like all slopes happens on the same horizontal rows and all the regular tiles too.
Given that each row of tiles consists of 8 32x16 tiles followed by 16 16x8 slope-tiles I'm thinking that it would be interesting to think of the slope tiles as 8 rows of 16 16-width tiles.
Then you can write one of those rows linearly with the CPU for each 32x16 tile you copy.
The 32x16 tiles will be stored in VRAM while the slopes will be in regular RAM.