Grauw’s RPG in development

Página 25/25
18 | 19 | 20 | 21 | 22 | 23 | 24 |

Por santiontanon

Paragon (1806)

imagem de santiontanon

06-06-2020, 19:15

I like the 16x16 partition idea!

What I am doing in my current game (for the upcoming MSXDev) is like this (although I only have horizontal scroll, maps can be arbitrarily large):
- I have a circular buffer of width 128 (although I could make it smaller if needed)
- My map is divided in chunks of 16 tiles wide
- Every time the scroll moves 16 tiles to the right, I add another chunk to the circular buffer to the right (and when I'm on the right-most position, it circles around, and adds it to the beginning)
- When I check for collisions or anything in the map I always AND #7f the x coordinate, to make sure it's circular

In this way, maps are arbitrarily long, but I only need a smallish buffer in memory. This might be a bit more complex for a multi-direction scrolling game, but I wonder if a similar idea could be used.

About the indirection for collision data, not sure how complex is your collision data. But what I did to avoid the indirection is to sort the tile types by collision type. So, I know that tiles with indexes in [0, N1] are non collidable, those in [N1+1, N2] are "collidable only by the player", those in [N2+2, N3] are something else. etc. I mark the collision types in some data file, and then I have a Java script that reorders the tiles for me and puts them in these buckets.

Por Grauw

Ascended (10768)

imagem de Grauw

06-06-2020, 20:42

Ah good! That gives me some confidence this is a good approach worth implementing Smile. And thanks for elaborating about your set-up, it’s interesting to read!

I’ve a similar idea for a 32x32 circular buffer in RAM which represents the “local” area. Kind of like a simulated name table in RAM. Then code would only have to deal with one buffer in a fixed memory location. Tile animations could modify and flag tiles for repaint, and entities could activate as they enter it. However it’s not implemented yet and maybe it’s not needed, it would require copying a bunch of data within a strict frame budget, so I would have to stagger the copying to limit the overhead.

About the collision indirection, tiles aren’t referenced by index but by a memory address so I can’t take the approach you mentioned. However I do have some unused bits in the memory address that I could encode a few collision bits in, or I can add more bytes per tile.

But another thing I’m more convinced about after watching Reidrac’s video is that, originally I thought it would be efficient to encode certain things like animations and collision in the tile data, since you only need to consider the tiles the player is standing on. That’s why I set up the tiles as objects which are referenced indirectly, so I could extend the type of the tiles with additional functionality. However in practice it isn’t really working out, so along with this partitioning I’ll remove that indirection on the tiles, keep ’em dumb. And specify those other things as separate entities, the partitioning will improve the efficiency of looping over them.

Por pgimeno

Champion (328)

imagem de pgimeno

10-06-2020, 23:33

Regarding compression, this may be one compressor/decompressor that isn't too hard to implement:

Comes with C and 68000 assembly versions. I don't know any 68000 though.

It's a somewhat similar idea to the LZEXE one (Lempel-Ziv 77, that is, distance-length pairs) but IIRC with a fully byte-oriented encoding (it's been long since I looked into it).

An alternative could be to look into LZW, the one used for GIF, which is described in several sites; but that one is bit-oriented, which makes it slowish in comparison.

Por DarkSchneider

Paladin (1020)

imagem de DarkSchneider

11-06-2020, 12:26

If the game is for MSX2+, you have at least 64KB of RAM. So even if it is a ROM, you can copy the map data into RAM at load time (when moving to another area) and exchange the page slots to RAM-ROM when required.
This allows to have a more alive environment, as you can modify/update data in RAM like animated ones even if they are out of screen area.

About special tiles, I use standard data (common) for tiles, reducing its data a lot, and for special cases simply GameObjects placed in the map. Can be an invisible GameObject (no gfx attached), with a collision coinciding with the tile area size to cover, so you see the tile but the collision is handled by the involved GameObjects scripts. This is for some specials like items and interactive ones.

The other approach, is more general and more focused on special collision tiles, like spikes, as if you have many of them (separated so each block requires its own GameObject), adding so many objects could be much for the CPU.
In this case I set a number from which lower/greater (the best for you) than N are considered special tiles, i.e. we will use the lower. Then the collision module, when checks for map collisions against the tiles the character is over, it checks if it is lower than N, and if the case adds it to a list of special tiles collided. Then the MapCollision script of the character reads that list and handles it.
Yet working on it as the ideal would be to have a list of (tile, count) pairs so you get the tile and how many of them are in collision with the character, but handling lists in this way is CPU consuming, so currently they are simply added, so repeated values, and then let the MapCollision character script handle it.
There is an approach at the cost of using (N*2)+1 bytes to store that list, and I think slower for the CPU to handle it on the script, as it would be an indirect indexed table instead a single direction incremental indexing one.
The value of N can vary on each area or even per character, setting its value before checking collisions.
Something that adds much versatility is to add other byte of flags, that can be read and used by the scripts, but only adding a single byte doubles the size, and most of the tiles in the map will not use it. Currently using a single byte per tile and adjust the scripts and N value for it.

Por Grauw

Ascended (10768)

imagem de Grauw

11-06-2020, 21:38

Hi pgimeno,

Thanks for the pointer, I wil check it out! The mix of bit+byte-oriented encoding of LZEXE was quite interesting. The gunzip decompressor I implemented before was bit-oriented and too slow and complex for my purposes here, so LZEXE gave me some new insights. Hopefully looking at that LZRW1-A compressor code will as well!

Por Grauw

Ascended (10768)

imagem de Grauw

11-06-2020, 21:59

DarkSchneider, good points!

As for the RAM, a practical complication is that if I swap RAM in page 2 that leaves me just with two 8K segments in page 1 which are both going to be code. And I really want to stream various things from ROM through page 2. Maybe I could use the DOS environment (via a disk ROM) in combination with ROM in page 1 or 2, could be nice. Or switch page 2 between ROM and RAM, but not too often. Either way it’s kind of awkward. For now I think I have enough memory in page 3.

Regarding special tiles, indeed using entities (game objects) for them is my current thought. Good to have another confirmation that this is a good set-up. Also nice example about the spikes, indeed there the above approach won’t work, just like solid tiles. So it seems tile collision is still definitely needed. Thanks for the explanation.

To optimise the collisions, I was thinking to generate a “CollisionPair” object for each two colliders that can collide with each other, store the sum of the collider sizes on it (as an optimisation), and then each tick loop over them to evaluate which ones collide. The list of collision pairs would be part of those 16x16 partitions, and I only evaluate colliders that are in the same partition.

Por Grauw

Ascended (10768)

imagem de Grauw

06-11-2020, 01:46

I’ve lifted the maximum music track size restriction of 8K, now it’s only limited by the size of the ROM.

It’s done by changing the jump command (used for looping the track) to have a bank number in addition to an address, so that it can change the playback address to anywhere in the ROM. Additionally the build script now adds a jump command when it gets close to the end of the current bank, which jumps to the start of the next bank. Doing it this way I can avoid checking the address counter for overflow every time I increment it, which would come at a high performance cost.

The build that’s currently online now plays a longer track (from Xak) that it previously wasn’t able to play. Performance is the same.

On the topic of music data size reduction, I was looking for a particular kind of compression:

Grauw wrote:

Since I want to play it straight from ROM I’m thinking about either some kind of hierarchical data structure, or a bytecode VM with a stack. If someone has some tips or knows some nice articles about optimisation structures for this kind of data and how to compress somewhat efficiently, suggestions are welcome :).

After reading a lot of papers I’ve found exactly what I was looking for, which is longest-first off-line grammar compression. Long story short, it iteratively finds the longest repeated series of commands and extracts a production rule for it. The player is then extended with stack-based call and return commands to execute these production rules like a subroutine. This has little overhead and does not need a decompression buffer in RAM.

I’m currently implementing this in my gngplay project which is a bit more contained, but eventually I plan to port it to this project as well. When it’s completed I will post more information about the implementation and compression details.

Por Bengalack

Paladin (747)

imagem de Bengalack

07-11-2020, 08:43

Página 25/25
18 | 19 | 20 | 21 | 22 | 23 | 24 |