There's not much gameplay here at the moment - just wander around the maze. It's mostly an exploration of some procedural generation. I might yet try to build a proper game around it, but I thought it might be of some interest on its own.
Features:
- 16x16 room maze generated with Kruskal's algorithm plus some extra connections to make it more interesting.
- Basic random room generation so that each room has connections to adjacent rooms that match up.
- Automatic wall borders.
- Textures assigned by randomly combining a selection of 3-colour palettes with a number of different wall, floor and border textures.
- Basic texture transitions between rooms.
- Transition textures and borders are assembled into pre-combined and paletted tiles on entering a room, saving a lot of time in rendering each frame.
- Basic shadows under the player and walls to give a bit more depth, with some hacky code to render quickly.
Issues:
- Each room has a few extra walls scattered around to make it a bit more visually interesting, but there are no constraints and it occasionally clogs up an exit.
- Sometimes there's a flash of garbage textures on entering a room, because the texture assembly works by rendering every tile combination to the screen, then it's memcpy'd back into sprite memory. This could probably be avoided by drawing straight into sprite memory in the first place, but it needs more custom code.
- Some of the colour palettes clash pretty badly, and there's no constraints to try to prevent the walls and floors being the same or clashing colours. Some rooms are utterly garish, and the transitions don't look great.
- There's only about 20% CPU free even with the optimizations. Any further decoration probably can't cover much of the screen.
- The code is pretty incomprehensible right now. I've not yet made a major effort to clean it up and try to improve the identifiers and comments. If you're curious about any part let me know and I can try to explain it.
It currently uses 4020 tokens, but I think that could probably be reduced a fair bit by stripping out redundant code.
Very cool, I'm currently exploring different algorithms for generating mazes. I really like what you made here, a lot of cleverness too with the texturing and transitioning.
I think you could probably do away with basic shadows though, as the code used to make them might be not worth it(just a hunch though)
I also have a hunch that if you go about cleaning up code, you might find more optimizations and get the CPU usage down.
How many rooms does it make?
Really cool so far!
The shadows are tricky. I find they make a huge difference to the readability of the room (i.e. how distinguishable the walls and floor are), but they are verrrry slow. There are two methods for rendering them - the super-slow pixel-by-pixel version that works at any x/y coordinates, and the faster-but-not-quick version that only works grid-aligned and must not be used across the edges of the screen. The latter is absolutely necessary to keep the frame-rate okay.
I'm not sure the texture transitioning is really paying for itself right now. The borders look lovely, but the texture transitions only look so-so. That said, once they have been set up for a room they are basically free (so far as CPU goes), whereas the borders need an extra rendering pass.
It's currently generating a 16x16 room maze, where each room is one screenful, so 256 rooms total. As far as I can tell there's still plenty of Lua RAM, so that could easily be increased - the maze itself is stored in a Lua table, but the map data is all generated deterministically when you enter each room. I don't want to go so big that the player becomes hopelessly lost, so I'll probably not go much larger.
I think I'm going to leave the tech about there and focus on building a game on top of it for now. After that I'm interested in seeing how large and detailed a free-scrolling world I can make, but I don't want to get too ambitious for the time being.
Really cool stuff!
I wonder if you can cache the shadows at the beginning and then render them as sprites without having to calculate them in real time? I haven't looked at the code but that thought crossed my mind so thought I'd share.
I hear you on not getting too ambitious, so far you have something really good and I'm looking forward to seeing it develop further :)
V1.1
V1.2
V1.3
And in V1.3 I finished cleaning up the codebase, and added some menuitems to assist with debugging and examining the biomes generated. Also did away with the massive 16*256-byte 'shadow bitmap' lookup system, as benchmarking showed it didn't save any appreciable time with the new restructured shadow-rendering path. Simply skipping 'empty shadow' dual-pixels allowed the bit-math that takes up no additional memory to work more than fast enough.
The only remaining map-space use is a 17x17 and 16x16 tile block for the base-layer and border rendering, with the shadows stored in a table instead. The borders could theoretically be stored in a similar table, but there's no pressing need for that currently so they're left in the map data to be more easily rendered.
At this point the shadow code is actually fast enough I'm experimenting with adding very thin shadows along the vertical walls as well, though that's not in this example yet.
I've also purged the 'temporary' map tile use while the levels are built and for collission-detection, moving the collision-detection to properly use fget() calls based on the sprite numbers. Red flag is an obstacle, so it's possible to add additional objects to the playfield directly as well though those are offset-grid-aligned only.
Also I went through and pre-loaded graphics and map data in to document the overall memory layout, to make further updates easier to visualize inside the editor and to pseudo-document 'available' space on both the map and sprite graphics areas more fully.
Planned update to allow viewing two intermixed 'biomes' in the explorer, right now you can only view one at a time.
HOLY MOLY! I never expected anyone to decipher the code, never mind improve it! Nice work! I've not been finding as much time to work on this lately, so my own version isn't much improved. It adds some more variation on room shapes and now actually guarantees that it won't completely block off a narrow corridor, plus it has a few non-interactive items scattered around. I'm trying a more dithered transition mask too. I think I prefer it, though for some colours it's a bit noisy. I'll probably not merge in all the changes to my own version for now since I think both versions have diverged a bit, but I'll definitely look at the faster corner-code functions.
Here's my current version:
Interestingly enough I've been experimenting with implementing something akin to dithering, in my case trying to make it aware of the underlying textures to some extent even if it slows down tile-generation some.
Nothing to show yet, I'm still experimenting with math, but the idea is to, for example, have only one spiral of the greek-spiral groove tiles overlap during the transition, the other showing the other biome, etc. So instead of just using raw 15/0 masks starting at 8 or 9 and subtracting out the 0-2 value of each pixel on the ex1/ex2 tile, then spreading bit 3/7 down to the other bits.
So 8+ = ex tile. 7-0 = main tile. So the 'color 2' regions on the ex tiles would get overwritten by main the most, the 'color 1' regions half-way, and the 'color 0' regions the least.
As I said, it's all still experimental math, nothing to show YET, but you're not the only one wanting more dithering and less arbitrary borders. :)
I do LOVE the new room shapes though, I may see about re-integrating that code, some of those look particularly epic! :D
So I finished my idea for the 'context sensitive dithering' and... I think I like it a lot?
The 'invading' biome is treated a bit like creep in Starcraft, and combined with some lightly dithered border masks I think the overall effect looks pretty decent. Colors 8 and 9 are the 'transition tones' with anything >9 always being the "main" texture and anything less than 8 being the "encroaching" one, but avoid colors 0, 1, 2, and 15 to avoid SWAR-induced math errors when assembling the final mask.
I also integrated your new cavern types, very slick bit of code you did there, seriously. I added one more type that's able to make some VERY windy-passage style rooms, at this point I'm going to focus on properly 'backgrounding' the room-generation as much as possible to remove the hitches entirely.
Still a lot of optimizations left to do, I'm working on a caching mechanism for the most recent X rooms worth of wall data, to avoid the expensive cavern-generation cost on every scene transition since there's just not much to optimize there unfortunately.
I haven't tried it yet, but I think the cavern-forming code could be sped up at the cost of more code by tracking a list of cells that are eligible to toggle and picking from it at random instead of picking any cell at random. You would need many fewer iterations for the same effect.
Very true, Weeble, it would have to be based on the number of free cells as well though, so that math might be intractable to keep things looking the same.
I'm working on a slightly different approach using bitfields, calculating which cells are valid and still using the 'random anywhere' idea, so checks (most of which still fail) are a single band(1,shr(v,y)) construct instead. It'll use the full function to update the 3x3 grid around the change, but that should be lower CPU usage usually.
Also I just finished doing a token-optimization pass (in large part by propagating constants forward and leaving comments in place instead of using global variables as constants, and replacing functions called on constants with the results) so I'm down to 2721 tokens for the core engine, without doing anything awkward on the code; I'll update things again when I have something to show later this evening. :D
...so I managed to find ANOTHER speedup. It calculates the 'masked' combinations a full 32-bit 8-pixel stripe at a time now, so one fourth as many complex calculations in exchange for a small increase in code around the underlying peeks and pokes.
The code change should be pretty easy to integrate back into your codebase though I hope, Weeble!
I haven't touched this in a while, so just in case I don't get back round to it again, I've put all the source code and related bits and pieces in a couple of github repos. Source code is all licensed MIT, graphics remain CC-BY-SA-4.0. It remains an utterly shameful undocumented mess, but I figure better to put it out there.
The game, libraries and a rudimentary palette editor:
https://github.com/weeble/picomaze
A tool for reassembling pico8 files as well as exporting a cart's map data as a big 1024x512 PNG (that particular feature is not relevant for this project, but handy anyway):
[Please log in to post a comment]
