The room in program memory/PROGMEM will not be tiled based, but the room when loaded in RAM will be.
The alternative tiles would just be a different id that represents a different image, and what happens (or if nothing happens at all) when colliding with them will be written in the code of monsters and the player.
These are restrictions I can live with
I won’t need all the blocks of a floor loaded at once, just the blocks from a specific room. So I think I won’t need more than 3, maybe I’ll even only need 1. Scratch that, I will only need one in RAM at a time.
normal keys, sword upgrades, boss keys, heart upgrades, a shield and a torch. Nothing else.
There’s an upgradeable health bar the sword slot and the shield
Uniform size
Some traps will be entities others will just be a tile that kills you. I Absolutely agree on the enum class.
Correct
Correct
One of 16 prefabs, 0 is a room too but it has no doors. At least, that’s how the code will behave if the player were to someone be in room layout 0. (there are no actual room prefabs, just door prefabs)
Yes, but the stats won’t be scaled on the players’ stats. They’ll be fixed.
No I think it’ll just be an id. I won’t have more than 16 items and they’ll just be ids. The behavior of these will be in the player code
They’re not just decorative?
What sort of things will they be doing?
If it weren’t for that you could have just had different tile sets and have each dungeon or room pick a tileset so you can reuse the same tile ids.
That means that when leaving a room the block will reset,
so you’ll have to be careful not to trap the player.
Ok. So you probably won’t need an inventory system, that’s good.
Those can just exist as stats, you won’t need an inventory for them.
Then the width and height won’t need to be stored.
That’s a bit vague.
What sort of traps?
Camoflaged entities? Spiked tiles? Arrow shooters? Spinning bars?
So you’re now not calculating doors at runtime?
Or are you calculating them when you load the map?
Ok, this is slowly sounding less like a roguelike and more like just a Zelda game.
In the code, but probably not part of the player class.
Revised…
Dungeon:
A dungeon has M monsters
A dungeon has O objects
A dungeon has N floors
Floor:
All floors have the same dimensions
A floor has W by H rooms
Room:
All rooms are the same dimensions
A room can have 1 of 16 door configurations
Door configurations are calculated on map load?
Monster:
Has a SpeciesType to identify its species, sprite, stats and behaviour
Object:
Has a ObjectType to identify its sprite and behaviour
ObjectTypes:
Unlocked door
Locked door
Opened chest
Locked chest (normal key)
Locked chest (boss key)
Locked chest (heart upgrade)
Locked chest (sword upgrade)
Locked chest (shield)
Locked chest (torch)
Will the dungeon reset if the player leaves?
(This isn’t actually to do with storing the map as such,
I’m just starting to think about player stats and saving.)
It will be possible to just switch tileset, traps that are static/don’t have a behavior (aren’t entities) will just be an id with a corresponding image, the code for how to react to it will be in the player/monsters code.
Yep. That’s how the old Zeldas did it
Exactly
The width and height isn’t in pixels, it’s in tiles. The width is how many copies in a straight line there is of that tile, this will allow me to have walls in a room that don’t cost much. (this is basically my earlier box idea)
I don’t know yet what my enemies and traps are gonna be (actually I have a pretty good idea about what my traps are gonna be, but not the enemies) but what I do know is that some are stateless, they’re just data - like a hole in the floor. It doesn’t move, it has no behavior, but if you walk on it you fall and die. A spiky block could work the same way, but instead of killing the player just hurting him and pushing him back
So if we ignore the English language, there’s tiles, and there’s entities. The nuance exists only because of how we humans interpret things. Arrow shooters would be an entity, a monster. Spiked tiles would just be a tile id.
Sorry, by doors I meant locked doors “something that requires a key”. Otherwise whether two rooms are connected is implicitly stored in the room layouts. I guess a better word for it would be doorwayLayouts, because I won’t be using actual room prefabs.
I was learning procedural generation from roguelikes, but I was planning on using this for a Zelda-like, as a way to save space.
By the way the traps with special behaviors is why I prefer to use the word entities, since monsters won’t be the only “living” thing stored in the dungeons.
…
There are no “unlocked doors”, just doorways with a locked door blocking the way or a locked boss door blocking the way. Otherwise it’s just a hallway and is stored in the room/doorway layouts. (I’ll use doorway layout" from now on)
I took a break from programming, this is why I’m replying so late
Sorry I haven’t got round to replying to this properly.
It was on my todo list and then suddenly my week got busier than expected so it’s fallen to the wayside.
I think you’re probably best off to just dive in and have a go since you’ve got most of it figured out.
If a particular solution isn’t suitable it can always be changed later.
I decided to continue working on my ARPG/Zelda-like project.
I got a weird bug which I thought I solved, but turns out the project won’t properly upload to the Arduboy, so I guess I didn’t actually solve the problem. When I click “Verify” however, everything is fine, which is why I initially thought I figured it out.
player was a reference to the first index of my Entities array, I checked by doing a player be it’s own entity rather than a reference and everything behaved the exact same way.
So, here’s what the bug was:
exit status 1
too many arguments to function 'void init()'
Which had to do with this line in the main project file:
player:init(EntityType::Player, 22*8, 5*8);
If I removed my arguments it compiled fine, however this function really does take 3 arguments, so that was weird. Then I saw I was using : instead of a single dot . so I replaced it with just a dot.
Now it verifies just fine, but it won’t fully upload to the Arduboy, even after 5 minutes.
Here are the whole code for the three relevant files:
Here's the main file, game_prototype
// Sam Sibbens
// 2018 NOVEMBER 01
// Arduboy RPG Hack and Slash
#include <Arduino.h>
#include <Arduboy2.h>
Arduboy2 arduboy;
#include "Entity.h"
#include "Images.h"
#include "World.h"
#include "View.h"
View view;
constexpr uint8_t MAX_ENTITY_COUNT = 10;
Entity entities[MAX_ENTITY_COUNT];
Entity& player = entities[0];
/* FUNCTIONS DECLARED AND DEFINED IN THIS FILE */
void draw_entities();
void setup() {
arduboy.begin();
arduboy.clear();
arduboy.setFrameRate(30);
arduboy.initRandomSeed();
player.init(EntityType::Player, 22*8, 5*8);
}
void loop() {
//Prevent the Arduboy from running too fast
if(!arduboy.nextFrame()) {return;}
arduboy.clear();
//draw_world();
update_entities();
view.setPosition(player.x+TILE_HALF_WIDTH, player.y+(TILE_HALF_WIDTH/2));
view.draw();
draw_entities();
arduboy.display();
}
void update_section() {
for(uint8_t i = 0; i < SECTION_WIDTH_IN_TILES; i++) {
for(uint8_t j = 0; j < SECTION_HEIGHT_IN_TILES; j++) {
uint8_t tile = get_tile_progmem(i+view.x, j+view.y);
set_tile(i, j, tile);
}
}
}
/**** FUNCTIONS ****/
void update_entities() {
for(uint8_t i = 0; i < MAX_ENTITY_COUNT; i++) {
entities[i].update();
}
}
void draw_entities() {
for(uint8_t i = 0; i < MAX_ENTITY_COUNT; i++) {
entities[i].draw();
}
}
I assume I had/am having a fundamental misunderstanding of the : for having put that in the first place probably 8 months ago, either that or it was a typo. But I’m not sure why using a . doesn’t seem to really work either.
I’m not sure whether you mean ‘making player a global variable’ or ‘using a copy instead of a reference’.
Try uploading something else, like a simple ‘hello world’ program.
Chances are the problem lies is with what’s already been uploaded not being overwritten due to communication issues.
A short ‘hello world’ should be quicker to upload,
and certainly easier to verify (if it says ‘hello world’ then the upload worked).
If ‘flashlight’ mode doesn’t help, try the reset button (it’s hard to get the timing right).
There is one place in C++ where a single colon (:) is used, which is in a ranged for loop,
(e.g. for (auto & value : array) { /*do something*/ },)
but otherwise you should only see double colons (::).
In your case that’s the wrong place for a :: anyway.
:: is the scope resolution operator.
The scope resolution operator (::) is used for accessing a name (a variable, function, type alias, static member variable, static member function or enumerator (enum value)) via a parent scope (a namespace, a class/struct name or a scoped enumeration) - i.e. ‘resolving the scope’.
. is the member access operator.
The member access operator (.) is used for accessing a member (a member variable or member function) of an object.
Perhaps you were getting mixed up with Lua?
(It’s been a while but I think I remember you saying you’ve used Lua before?)
Thanks for the clarification about :: and . and : , I thought perhaps I had forgotten something but turns out it really must have been a typo, or maybe I got mixed up with Lua as you said.
…
Thank you by the way, flashlight mode didn’t work but using the reset button did
…
I wasn’t coding anything for the Arduboy when I did it, but it’s what I was thinking about when doing it. I learned properly how “Linear-feedback shift registers” works a few months ago. I’ll just have to port my code to have it work, I’ll be able to use it for procedural generation if I still choose to go that way.
I don’t know if people are looking for alternatives to the default function for random numbers, but if it works well, turning it into a tiny library when I’m done could be fun.
That would be ‘making player a global object rather than a global reference’.
That seems the more likely to me.
I remember reading something once where a Lua programmer said something like:
“For C++ I think of :: as Lua’s . and . as Lua’s :.”
Which is actually quite a good analogy for the most part.
(For functions at least, less so for variables.)
No problem. I’ve had the exact same problem before.
I don’t know quite what causes it, but it tends to be more frequent with larger and/or more complex programs.
You’re probably doing better than I am then, I only partly understand them.
Might be worthwhile.
Personally if I want to use something other than the built-in random I tend to use xorshift with 13, 17 and 5 because it’s small, has a full 32-bit period and also works well as a hash function.
(It happens to be a type of LFSR.)
If you decide you want to do that and what some help designing and/or documenting the library I might be able to help with that.
You also might be interested in this old thread (if it doesn’t bore you to tears by the end :P).
Some of my statements are a bit off because I didn’t know as much about PRNGs as I do now, particularly the work of Margaslia, but there’s lots of useful stuff there too.
I didn’t get bored until comment number 47, which is alright since the thread only has 57 posts :D
It seems people would be interested in a different PRNG, some to save bytes for more game stuff and others for other reasons, but there is interest.
This is actually one reason why I was interested in LFSRs - since a good set of ‘taps’ will result in all the possible numbers except 0, in theory any number could be used as a seed to get unique value. A 16 bit value for x and 16 bits for y position to have a 32 bit seed.
I’m actually a bit rusty so I had to go on Discord and find the old conversation I had when I asked help about LFSRs, and re-read parts of it. I’m pretty grateful for the built-in Discord search function.
…
Learning how to plan out/design a library could be a very worthwhile thing.
I don’t know how/if it’s possible to only use parts of a library, but if so, having stuff for gradient noise (like Perlin noise) and other things as well in it could be great. A “pseudo random generation” kit. I’m gonna have to make a bunch of things for procedural generation and I’m sure many people would love to use some of it. For example, instead of using a huge array to store their world map, using one seed that they like and only storing changes they’d make to it.
Since you’ve mentioned that in your experience Xorshift worked alright as a hash, I’ll be trying it out for some sort of gradient noise for world generation
…
Unrelated, but time passes so incredibly fast when reading and writing.
I definitely mentioned this idea once to someone here,
but it’s been so long I can’t remember who.
That depends what you mean by ‘use’.
Usually in C++ only the functions you actually use are compiled into the binary executable.
(A.k.a. “You don’t pay for what you don’t use”)
So you can write a large library and only the functions people actually use* will be included in their Arduboy games.
(* I think technically it’s functions that are ‘ODR-used’,
but I’m not sure, the compiler might be able to remove virtual functions.)
It’s an interesting idea, but I think it would be hard to make something that suits everyone’s needs,
so you might have to compromise a bit or provide different alternatives.
That’s one potential use, but bear in mind that you won’t necessarily know what a person’s map system might be like.
Unless you’re planning to also offer specific mapping facilities that is,
in which case I think that would be better off as a separate library.
(‘separation of concerns’.)
The most important factors are (non-exhaustive, in no particular order):
Predicting what users will want
Predicting what could go wrong
Figuring out how to make something as reusable as possible
Usually this involves templates
Avoiding surprising behaviour
Choosing good names
Documenting things
Adhering to principles like ‘separation of concerns’ and ‘do one thing and do it well’
(Obviously there’s more to it to that,
and there’s certain techniques for achieving these things,
but those are the ‘golden rules’ if you like.)
I’ve actually forseen the eventuality that someone might want to use a custom PRNG,
and as a result of that forsight I made a PR to Arduboy2 that introduces a generateRandomSeed function, which was added in 5.2.0.
How it works (a good lesson in API design)
Basically initRandomSeed used to:
Enable analogue-digital-conversion (ADC)
Read an unconnected input pin and shift it left 16 bits
Read the time since boot in microseconds
Add the two values
Feed that into randomSeed (similar to srand, possibly equivalent)
Disable ADC
generateRandomSeed does almost exactly the same thing,
but rather than feeding the value into randomSeed it returns that value.
initRandomSeed was then changed to randomSeed(generateRandomSeed()),
thus producing more or less the same code as before.
So essentially the seed source is the same,
but now that seed can be used to seed a different PRNG.
That’s good to know, I thought I was imagining it. :P
Turns out I was/am very rusty about LFSRs, or I think I was.
I had to read a lot to get familiar again with the concepts, obviously it was much easier than the first time around, but still. However I think I got what I wanted working on my first try, it compiled just fine, and now I’m just in utter disbelief about it. Either I understood it more than I thought and I wasn’t rusty, or I did it all wrong but it compiled anyway. (I definitely did it without following proper programming practices, at least I think). Even if I did everything right, I’m surprised that my C++ was valid at all and compiled since again, I’m feeling extremely rusty.
So far I’ve got this:
uint32_t xorshift32::random() {
// XOR-ing and bitshifting
// setting the current seed to the new seed
this->seed ^= this->seed >> 12; // a
this->seed ^= this->seed << 25; // b
this->seed ^= this->seed >> 27; // c
return this->seed;
}
And, using a working project with SDL2 that I could modify super quick and dirty, I used this function:
If it did work and all I needed was those three lines of code, then I don’t understand why I was so confused about the whole thing. (I did spend a lot of time reading about using different taps and XORing vs XNORing and other useful stuff, but still a big part of the time I spent reading about it was just to get back the understanding of it that I had 8 months ago). Maybe I’m just extremely prone to brain farts.
In the .PDF there’s a list of 8 different lines of code to produce pseudo random numbers from the same three taps, and there’s also a list of about 80 choices of taps we can use.
If I understood correctly, we could use different sets of taps for different things. For example one set of taps for World 1 in a game, a second set of taps for World 2. Just by changing the taps or between the 8 lines of code we should get different outputs, we could make it very cheap to have big worlds.
As long as you know about things like the period of a PRNG sequence then you don’t really need to know all the polynomial and tap stuff.
That won’t actually tell you much of interest.
What that tells you is the first entry of each sequence.
The things you need to think about are:
Period - how many values can you cycle through before you get back to the start value
Uniqueness - how many generated values are unique
The former is easy to test. Using your set-up it should be:
std::uintmax_t testPeriod(std::uint32_t seed)
{
std::uintmax_t period = 1;
// I assume you have a constructor that sets the seed
xorshift32 lfsr { seed };
auto value = lfsr.random();
while(value != initial)
{
++period;
value = lfsr.random();
}
return period;
}
The latter is much more difficult.
You need a good deal of RAM and something along the lines of a std::bitset.
I know because I ran the test myself on the values in SkullHash.h,
and before I thought to use a bitset I ended up chewing up all the RAM my process was permitted.
(I have 16GB installed, so that’s quite an impressive feat.)
But if you use values from the paper you don’t have to worry about that because Marsaglia’s already tested the values he provides and the whole paper is actually about why those particular values hold those properties (something to do with matrices, I don’t actually understand that part).
Like I say, for xorshift you don’t need to know all that.
If you wanted to do other engines like a Mersenne twister then you might need to know,
but you’d still be better off pulling values from research papers where you can.
Hence the saying “use it or loose it”.
I have it downloaded already from last time I visited it.
I even link to it in SkullHash.h:
Did you pull your 12, 25 and 27 from that page?
If not then you might want to use one of the sets of values Marsaglia lists in his ‘paper’.
Note that his code is under the GPL, but the document itself is under CC BY 3.0,
so if write your own code from scratch and just use the values listed in the paper it’s only the CC BY 3.0 you have to abide by.
(I’ve just realised I should make that clearer in my code,
so I’ve made any issue to remind myself.)
You don’t want to use GPL code, because then you’d have to release your library as GPL,
and then anyone using it would have to release their game as GPL.
That’s what people mean when they call it a ‘viral’ licence.
Things like MIT, BSD-3 et cetera only require that you provide the licence and copyright notice,
they don’t even force you to make your own code open source (wheras the GPL does).
That is indeed more or less how it works.
Though again, that depends how the mapping system works.
You really ought to decide what your goal is.
Your goal will determine how you should approach things.
An RPG-ish mapping engine
If you only want the mapping engine then you don’t have to worry as much about making things modular and can focus more on the specifics of the engine.
A PRNG library
If you want to make a PRNG library, you’ll have to think about making it modular and what things other people might want.
Both
If you want to do both, you have to make the PRNG library modular and make sure you don’t start heavily coupling it to your mapping system or assuming other people will want to use the library in the same way.
You also have to consider how to keep memory usage down.
In the C++ standard library, in <random> all the PRNGs are template classes and the settings are non-type template parameters.
E.g. linear_congruential_engine is:
template<typename UIntType, UIntType a, UIntType c, UIntType m>
class linear_congruential_engine;
However, while using a template-based approachwould probably be cheaper for a single instance of xorshift32,
after 2 or 3 sets of parameters it might be cheaper to use one class that stores the shift values as actual member variables.
One design note: for a PRNG system like this where the transition between states is a single pure function,
I find it’s often more useful to do something like:
// In xorshift32
static uint32_t nextValue(uint32_t value)
{
value ^= (value << 13);
value ^= (value >> 17);
value ^= (value << 5);
return value;
}
uint32_t nextValue()
{
this->state = nextValue(this->state);
return this->state;
}
For now I’m not dead set on anything specific, except these few things:
Being able to get a (pseudo) random value based on an X and Y coordinate
Using that as a seed to generate something or using it directly. (The reason I’d be tempted to use it as a seed instead of directly, is that the quantity of random numbers generated from a LFSR is finite, even if it’s huge, and there is a slight chance that two “somethings” at different coordonates could end up being partly generated from a same sequence of numbers. This is especially true if I end up using an implementation with fewer bits.)
I don’t have the specifics down yet, but there’s a chance that I’ll only need to store the state of a PRNG only temporarely while generating a part of whateverItIsIDecideToGenerateLetsSayMazes. So for example generating the layout of a thing, stopping there, keeping it in RAM like a tilemap/2Darray of room layout IDs only. Basically if the seed is the X and Y of a world section, I can use that, generate that section, keep that section in RAM for the player to play in and forget about the seed/state of the PRNG. I have ideas to keep the amount of memory down when it comes to whatever it is I’ll end up doing
In theory I should be able to end up with something very very cool that takes very little space, without busting the RAM limit either. I’ve been thinking about all this a lot :D
For now I’m just focusing on getting some LFSRs right, and then I’ll see if I’m going the right way about all this.
This is very good to know thank you
I have no clue where I got it from, but I’m definitely planning on using values that he found and already confirmed are great to use. For now I just really needed to get something up and running to get out of that brain fog I was in. It’s like I knew about all the theory, but somehow I had to implement it for it to actually click? It was weird
The period is the length of (how many bits * 2) - 1 when using good taps. How good the output is depends, but that’s why I’ll be using the table from the .PDF. I won’t try using my own taps. As for how unique each output is, it’s technically too unique - each number only comes up once. This is why I’ll actually need some other functions to “treat” the output to have something that is usable. Honestly I think I’ll just mention it all as I go along, there is just too much to say. But I promise I am keeping potential weaknesses and problems in mind
OK I found how to write it: the sequence is great, but it’s the same one no matter the seed, the only thing that changes is where you start in the sequence (which is why I should have used the word ‘state’ rather than ‘seed’, as the word seed is very misleading here). However if the sequence is good when ran normally, it doesn’t mean it’s also good when using it like I did here; starting at 0 and incrementing by one to get the next value. Maybe this results in a terrible sequence so I’ll have to check
…
Honestly I’d say a ton more but I need to test out all that stuff, I’ll report back with any successes and failures I end up with. I’ll double check what you wrote in a bit to see if I forgot to reply to anything
inline uint32_t xorshift32(uint32_t value)
{
// Or whichever parameters work well
value ^= (value << 13);
value ^= (value >> 17);
value ^= (value << 5);
return value;
}
And:
// int16_t would also work
uint16_t x;
uint16_t y;
I’ve previously demonstrated this in one of the threads when discussing @CatDadJynx’s rocketship/space project:
Assume for a moment that you’re going to use a 32-bit xorshift with some of Marsaglia’s parameters and the function I provided above that converts two 16-bit x and y coordinates into a 32-bit value.
Given the properties of those xorshift parameters - generating a full period and providing unique outputs for any given input,
that means you could generate around 232 - 1 (-1 for (0, 0)) unique values,
so you really could have a 65536x65536 map effectively stored as a function.
Furthermore, each of those values is a 32-bit value,
so you can make lots of decisions based on those 32-bits.
Size isn’t really the issue here.
This is the real hard part.
Generating good looking ‘things’ from pseudorandom numbers can be difficult,
especially when you don’t have a lot of memory to run with,
and when you consider that using random values means your world won’t necessarily end up with any coherant patterns.
Personally I’d be tempted to split the world into chunks (maybe 8x8 or 16x16 chunks),
have a means of selecting or generating a chunk from a hash of coordinates and then having the world consist of chunks knitted together.
(If you can’t quite imagine that, I’ll draw a diagram.)
I doubt that will be necessary given how much space you’d save by not having to actually store the map.
It can work as long as you’re mindful of how you do it.
E.g. how much RAM you need and how long the terrain generation takes.
(I’m honestly surprised that ‘NoiseTerrain’ runs as fast as it does given how much maths is involved. The original version generated the whole screen every time, making it really slow,
but this version only generates the columns and rows as they’re needed, so it runs much quicker.)
To be honest I think you should just start with an xorshift algorithm or two and start working on things.
Understanding loads about LFSRs isn’t going to make generating terrain any easier.
The LFSR is just a source of good quality pseudo-randomness,
it’s what you do with that randomness that really counts.
I tend to find diagrams help.
You can always discard some bits, or use certain bits for different things.
A few things from some old discussions that might be of interest:
This is exactly what I have in mind :D Using a seed for a section, a section being say an 16x8 area of tiles, and then generating the inside of that section using either a different PRNG or the same one with different tap values.
For dungeons this could already be perfect, for an overworld that makes sense I’d need something different but I have solutions in mind for it. I could write 8 paragraphs about it, but basically using different simple procedural generation algorithms at different scales. Oh and let’s go for it, here’s the essay for anyone interested:
Essay
So, for dungeon generation. There are two main options, one that is already implemented and already works. Wang tiles. It’s already working, the hiccup last time was the built-in random function, it simply wouldn’t behave at all when using X and Y coordonates as seeds. However I tried it just now using the xorshift32 thing (the thing I have may not even be xorshift32, maybe it’s a LFSR, my memory is foggy I’m not sure what the nuance is. Xorshift32 is a specific implementation but that’s far as I know)
Anyway, using the xorshift32 thing with the same taps I was using earlier, getting a seed from that and then setting the built-in Arduboy random function to that seed and then generating a random number between 0 and 15 inclusive, and then using that with the Wang Tile style dungeone generation I already had, it works super well. I don’t get repeating patterns (yet - I haven’t tested what happens when using different values. I might still have to completely forego the built-in Arduboy2 random functions, I don’t know yet.) But point is, before using this to generate a seed, I immediately got a repeating pattern. A repeating pattern in a 18x8 grid of tiles. For whatever reason it wasn’t working at all.
Anyway, for dungeon generation, I could either use Wang Tiles which was my original plan, or I could generate it like people would normally do: start from a corner of the dungeon section and generate it. No wang tiles, nothing fancy, any maze generation algoritm that can fit on the Arduboy would do. The only thing staying in RAM would be an array of 16x8 of the resulting section.
Or we can combine that stuff. Do this one a higher scale, the “dungeon” which could be made of the Wang Tile thing generation algorithm that I have working already (it’s been a long time so here’s a reminder of how it works: in a checkerboard fashion, using the X and Y coordonates as a seed, you generate a random tile among 16 possible tiles. Let’s assume those generated tiles are the black tiles, the white tiles of the chess board are simply whatever fits between the four black tiles surrounding it.) TL:DR this allows potentially infinite number of tiles that will always fit together and will always be the same no matter how you reach a given tile. You can leave and come back and the same thing gets generated.
Anyway, back to the main essay. We can use one algoritm like “broad strokes” of a brush when painting, and a different one for the details. We can have a big world with interesting things at every corner, rather than having to pick between “big and boring” and “interesting but too small”.
On another note, and I’ll mention this quickly - celular automata for cave generation could be used too. If we generate a 10x10 maze which basically ends up being again an array of room layouts (room layout being “which walls of this room has doors?”. They are represented by numbers from 0 to 15 inclusive), we can then generate cave-like walls to it using cellular automata. A single step/update of cellular automata already gives a pretty good cave result, which means it wouldn’t take long at all to generate the cave/dungeon walls of a single section, and by combining it with the maze/dungeon of room layouts, we can make sure that the cave sections/dungeon sections will connect for sure, without needing to generate the whole dungeon/cavern.
Now the question again becomes, how can I use this for the overworld? I’m not sure yet, but I’m pretty confident that the dungeons themselves are pretty much solved, there are some rough corners left that I’ll have to think about but nothing that is worrying me.
Hm… I guess see essay above :D
My only two worries are “how will I do this in C++” and “How will I make this fit on the Arduboy”. These two worries aren’t negligible, but everything else is under controls. I need decent PRNGs however to use whatever algoritm(s) I decide on.
I’ll quote myself for a moment
So yeah, with the built-in Arduboy2 PRNG, for whatever reason I was immediately getting a repeating pattern. I haven’t done enough testing so I am not sure, but it seems that for whatever reason setting the seed to and X and Y value (same way that you suggested), for my Wang Tile dungeon generation, simply wasn’t working well at all. It could be a mathemathical coincidence but I was immediately getting a repeating pattern. Anyway, instead of feeding the position as a seed, if I pass it to the xorshift thing I got, and then use the output of that as a seed to the Arduboy2, then I get good results.
It sounds like you were transforming the X and Y as well to end up with a proper seed to avoid that same problem (using a hash function?)?
Technically I guess I’m using xorshift as a hash function in this case. I could stop there (although I need to do more tests to verify whether or not I get repeating patterns with the built-in random), but I’d like to go further with xorshift.
I’ll need to test if I can use it directly for some value noise/gradient noise for overworld generation without obvious problems. If I use value noise I don’t need to do anything fancy but it won’t be as good as some sort of gradient noise (like Perlin noise).
I remember a very very long time ago we talked about pretty much this, you’ve mentioned brads (byte radiants?) which if it didn’t already exists is what I would have done anyway; 0 to 255 is so similar to 0 to 360. I’ll probably try just value noise first, and only then gradient noise if needed. (from my limited understanding of gradient noise, instead of just using random values and interpolating between them directly, we use distance/direction vector and tweak the results based on those vectors to make everything look either more natural or more twisted, depending on the needs.)
I’ll probably do this with SDL2 since i’ll be able to see a much bigger part of the generated world and more easily notice any patterns or problems.
…
Well, hopefully someday someone finds all of this information useful. I wrote a ton once more.
That would probably be easier.
No need to go overboard with different PRNG engines unless there’s actually a tangible benefit.
Reusing the same algorithm with different values might even use less memory than having two algorithms.
(Assuming the speed would be sufficient.)
Not necessarily.
Remember that a PRNG is an abstract source of randomness,
and the engine is just an implementation of that abstract interface. What you do with that randomness is just as important,
if not more important than which engine you use.
Even the same thing at different scales can be useful:
Therein lies the problem.
Most maze and dungeon generation algorithms need more RAM than the Arduboy has to spare.
(Particularly because they often involve trees or graphs.)
A drunk walk could work, but that’s slow and doesn’t always look good.
Something like a Lindenmeyer system might be a better bet.
This sort of approach is often used in complex collision systems.
A ‘broad phase’ (e.g. binary space partitioning, quad trees),
and a ‘narrow phase’ (e.g. convex hulls, oriented bounding boxes).
Aye, that too.
Even poor PRNGs with repeating patterns can produce acceptable terrain if used in the right way.
The fibonacci sequence turns up in snail shells and plant heads,
flourites grow into cubes, raindrops form radial patterns,
snowflakes have geometric symmetry.
It’s not actually Arduboy2 that dictates the PRNG, it’s avr-libc,
the C standard library implementation for AVR.
To be honest I’d suggest that you don’t even bother with the built-in random.
It is possible to get access to the source code,
but it’s better to write your own implementation to be sure it’s portable (particularly if you’re going to try to make an SDL2 version),
and that it won’t one day change with an IDE update (e.g. if the authors found a better PRNG and changed the implementation).
If you were using the built-in rand or random then it’s probably a really poor implementation.
Most likely it’s an LCG implementation with crappy parameters.
If you mean in ‘noise terrain’…
I ended up using ((x << 16) | (y << 0)) * (x ^ y)* for some reason,
so it’s possible that just ((x << 16) | (y << 0)) isn’t interesting enough, I can’t really remember.
(* Note that (x ^ y) gives out 0 if x == y, and n * 0 is 0, so you’d end up with a diagonal of zeroes if no further steps were applied.)
I then fed that into the (13, 17, 5) xorshift32 state transition function (i.e. using it as a hash function) before doing various other things (smoothing, value noise/‘octaves’) to create a suitable terrain.
To be pedantic
A ‘seed’ is the initial value fed to a PRNG to start a sequence,
you don’t ‘seed’ a hash function because a hash function is stateless.
‘Binary radians’.
Though as you’ve noticed, they’ve got more in common with degrees than radians.
(Note that the parallel is actually between 0 to 256 and 0 to 360 because 360° == 0° and 256br == 0br. Similarly you could say 255br is like 359°.)
Yes, to begin with you’re probably best off doing the absolute minimum that you need to generate decent results.
Perlin/gradient noise is probably a bit over-complicated.
As I’ve said once before, when it comes to procedural generation, trial and error is usually the better tactic.
You actually have to try things out to decide whether they’re any good or not.
It makes sense to do so, but bear in mind the little nuances between desktop and Arduboy programming.
E.g. int is usually 32-bit on a desktop, but it’s 16-bit on Arduboy.
Try to stick to using the fixed-width types if you can.
(And if you care about portability, remember to qualify them with std:: and use <cstdint> instead of <stdint.h>.)
I’d strongly recommend starting by writing demo programs showing off each technique before trying to knit them together.
Try out some various things to see what kind of patterns you get.
If you see a pattern you like, try to figure out why that pattern is created,
and if you can’t, don’t worry too much, just use it anyway.
Then when you’ve found some things you like, combine them all.
(Sorry if I missed anything, I’ve suddenly had a lot of things to reply to.)
I’d love to make a thorough video tutorial series about programming on the Arduboy at some point, I’ve learned a ton thanks to you but it’s spread out among this whole thread, it’d be hard for others to use. I have a decent microphone to record with now, but I still need to improve my C++ before I can start teaching about it (although, teaching others is an excellent way to improve our skill and knowledge about something)
Thank you, I like knowing that kind of stuff. So if I wanted to explain what my thing does, would “It takes the X and Y position as an input and outputs a seemingly random number” ? How can I describe my thing without only calling it a hash? (Or should I just call it a hash function that outputs a unique pseudo random number?)
(Knowing this would make asking for help and googling things easier in the future)
Oh! That explains why I couldn’t find the code for it in the Arduboy2 library
This is very true but I think it is easier to add patterns to a thing than to remove it. I guess separation of concerns apply here somehow; I want a decent enough source of pseudo random numbers, and then I’ll make whatever functions I need to transform the output depending on the needs. Still you’re absolutely right that just because something has patterns, doesn’t mean it’s bad
Yes, kinda like this! Generating the general layout of the maze, maybe in an 8x8 grid fashion, and then generating each section only temporarily when the player enters it.
Problem already solved! :D There’s at minimum one maze algorithm that would work, I actually bought a book on maze algorithms recently. I’m not done reading it so I don’t know which other algorithms (if any) would work on the Arduboy, but at least one would and it is super simple:
For every cell on a grid, toss a coin. If you get tails, remove the wall above the cell, otherwise remove the wall to the right. This type of maze can only result in diagonal paths (or a path straight up or straight right), but with some smart thinking this could be used well. (I tried finding an article or an image of this type of maze but I wasn’t able to, I’ll have to take a screenshot of one myself and show you later). The book Is “Mazes for Programmers” by Jamis Buck
When you use <cstdint> you should use std::uint32_t instead of uint32_t. <cstdint> only guarantees that std::uint32_t will exist,
the existance of uint32_t is implementation defined.
Out of interest, does this implementation use % (modulo)?
(And if so, do you know about ‘modulo bias’?)
Unfortunately that’s kind of the nature of the beast.
Programming doesn’t really have a fixed linear progression,
it’s like a tech tree/skill tree, with many many branches.
One of the reasons I’ve never written a tutorial myself is because there’s so many interconnecting ideas that it’s hard to enforce a linear order.
If you have the time, have a read of these:
LearnCpp.com, a C++ tutorial covering a lot of the modern stuff and things other tutorials brush over or get wrong.
Explain to whom? The intended audience affects how you should explain it.
For a search engine, ‘hash function’ is more likely to net you relevant information.
(Particularly ‘procedural generation hash function’.)
However...
There are at least three different kinds of hash functions: cryptographic hash functions, hash table hash functions and the kind you’ve been using for procedural generation,
each of which has different desirable properties.
(Unfortunately the last case has substantially less coverage because it’s of less general interest. Procedural generation is something that doesn’t appear to have as many applications as hashtables and cryptography.)
The one thing that unites them all is that they take a sequence of bytes (of either fixed or variable size) and output a fixed-size sequence of bits.
In fact Wiktionary’s definition is:
an algorithm that generates a numeric, or fixed-size character output from a variable-sized piece of text or other data; used in database table queries, cryptography and in error-checking
They also all tend to be stateless and desire ‘uniformity’ (“A good hash function should map the expected inputs as evenly as possible over its output range.”),
but I’m reluctant to say that’s true of all hash functions.
Whether you’re explaining to a beginner or an expert,
you should use proper terminology where possible.
If your audience isn’t likely to understand the proper terminology then you should explain it.
For example, if you were explaining what a ‘hash function’ is then you should explain its etymology:
The term “hash” offers a natural analogy with its non-technical meaning (to “chop” or “make a mess” out of something), given how hash functions scramble their input data to derive their output.
If you’re explaining it at a more advanced level then you might want to discuss the expected properties of the function (e.g. being ‘bijective’ - generating unique outputs for each input),
and possibly explain what those properties mean or the implications of them.
That’s quite a loose handwavey explanation,
but it would suffice for a simple introduction to the idea.
A hash function is any function that can be used to map digital data of arbitrary size to digital data of fixed size, with slight differences in input data producing very big differences in output data. The output is called a hash value.
Hash functions are particularly interesting for procedural generation for their ability to produce pseudorandom numbers. Unlike Pseudo Random Number Generators, hash function create a random number solely based on an input, with no dependency on previous queries.
Not all hash functions are well suited for procedural generation, as they may either not have sufficiently random distribution, or be unnecessarily expensive, but there are some that are very well suited.
That’s mostly true, but it does depend on the pattern and the operations involved.
For example if you did grid[x][y] ^= (x ^ y)* on every integer value in a grid of values then you’d end up with a checkerboard pattern mixed into the grid,
but applying the same operation again would remove that pattern**.
** This is because x ^ x == 0. There’s a branch of mathematics that studies properties and relationships like this called ‘group theory’, but that’s a rabbit hole for another time.
It’s a question of resources more than anything else.
It would work, but the caves it generates are probably immensely boring.
As I keep saying, you won’t know whether what you have is good enough until you actually test it in the situation in which you want to use it.
Bottom line: stop reading and researching PRNGs,
start writing demos and testing stuff out.
I want to see some pictures by the end of the week. :P
Like these...
Generated using a C# adaptation of “ArduboyNoiseTerrain”,
with return (hash(value) * (hash(x2) ^ hash(y2))); using xorshift with (13, 17, 5) parameters and uint value = (uint)((x2 << 16) | (y2 << 0));:
It doesn’t use modulo, and I am aware of the modulo bias, but I’m not sure yet how to go about avoiding it. My current implementation works but if the range is too small it could take a very long time before it returns a valid answer.
(The statistically “best” solution is simply to discard any invalid results and re-run the function until we get a valid output. However since each value only happens once with an LFSR, if the range is too small the function might need to be called over and over again until it has fully lopped back on itself. Although, if I only use some of the bits depending on what the range is, it should make sure that most values will be within range. I could also “pretend” that 0 to the max value of an uint32 is a percentage between 0 and 100 and pass in a percentage value between 0 and 100. There are ways around the problem).
Anyway, until I refactor it, this is what the code is:
uint32_t xorshift32::randomInRange(uint32_t minValue, uint32_t maxValue) {
uint32_t result = 1;
if (minValue < maxValue)
{
do
{
// we substract 1 so that 0 becomes a possible result
// we use a while loop and throw away any result that is outside the range
// instead of using the modulo operator because we want to avoid the modulo bias,
// at least with this function
result = this->random() - 1;
} while (!((result >= minValue) && (result < maxValue)));
}
return result;
}
I definitely do care about the modulo bias, it becomes especially apparent on smaller ranges. If you know of other solutions I’m all ears, but I think this one is the best (once it is refactored; the actual current code I got has issues as I’ve mentioned)
I would! But I’m tired of doing all my tests in GameMaker, I want to use C++ from now on :D
But, this isn’t a picture but I did implement this maze generation algorithm… in Halo 5. The results are actually pretty decent, and because that type of maze generation is so incredibly fast, I could make a maze that changes its layout as you play in it, similar to the pyramid which changes its layout in Aliens vs. Predator (the movie in Antarctica under the ice). I kept on forgetting to upload this to Youtube, but now I’ve done it. Here it is - North-East Maze Algorithm in Halo 5
A big downside of it is how the very east and very north wall are always ‘open’, but my mirroring the algorithm either on the X or Y axes (and both) we could get an interesting layout. I have some other ideas on how to tweak it.
Combined with the fact that I could make the maze change its layout in real-time every X amount of time or so, this could make for a very interesting dungeon (this was originally my plan for a Predator gametype and map that my friend and I already made; we made the map in a way that would “force” the survivors to move around and get split up, allowing the predator to take them out one by one. A map like this with parts of it being a proceduraly generated maze like this could be very fun). I didn’t phrase myself properly: this time of maze with a self-changing layout was our plan for the next map. I didn’t know this maze algorithm before we made that map.
(Fun fact, the video is unscripted and I was the predator in that game)
Hm. That sounds very similar to what I had came up with for autotiling my tree tiles. I did something along the lined of (if x % 2 == y % 2) then use this tile, otherwise use of of those other tiles. (this all sounds very vague because I actually forgot how I did it)
Here's the value noise based procedural generation of an overworld, which I actually don't _yet_ like, and of which I forgot how I did the autotiling of the tree tiles
Wang Tile based dungeon generator (the plan was that it would correspond 1:1 with the overworld; if there was a cave entrence on the overworld at a given world section, then there would be an exit at that same section in the cave
Most of these images are from a while back, so you probably will remember some of them, I’ll redo all of this in C++, tweak whatever I need to make things fit on the Arduboy, discard what doesn’t work and keep what does, and make it fun.
As a side note, I might simply ping the author of Ardynia and ask him if he wants to make a new version of his game but fully procedurally generated using whatever I come up with. I’d love to make a game fully on my own but, I loved his game so why recreate something that already exists and is already good if he’d like to collaborate. It would also allow me to focus on all that fancy procedural generation stuff which I like :D
(I might also do both, I haven’t actually asked him yet if he’d be interested. It’s just an idea I’m throwing out there.)
Hum for good measure, here's a last procedural generation algorithm I recently "learned" (in quotes because I think I did it wrong)
This one is “simple” if whoever implements it is familiar with various data structures, it’s basically a binary tree. You divide each section in two, then do the same on the other axis for each of the new sections, until you reach a “room size” that is close to what you want. The advantage of this approach is that there is no need to do collision detection between the rooms, they cannot collide since you only place one room per section. That makes this algorithm very quick. I don’t know if I’ll ever use this, for the Arduboy or otherwise, but it was fun to learn. (the thicker the white lines the more sections are overlapping on that same line, and the green dots and red lines represent the center of each section and to which other section it’s connected to)
…
Well I’m done for the day, I’ll give an update on whatever I come up with pretty soon
(Note that usually PRNGs use unsigned numbers for simplicity,
so answers using int should probably be using an unsigned equivalent.)
It’s probably not a big issue in your case in your case though,
I just wanted to check that you’re aware of it.
This would certainly work, but I can think of at least one way to make it more efficient:
uint32_t xorshift32::randomInRange(uint32_t maxValue)
{
// Use a while loop and throw away any result that is outside the range
// instead of using the modulo operator to avoid the modulo bias.
while(true)
{
// Subtract 1 so that 0 becomes a possible result.
std::uint32_t result = (this->random() - 1);
if(result < maxValue)
return result;
}
}
uint32_t xorshift32::randomInRange(uint32_t minValue, uint32_t maxValue)
{
// Returns 0 if minValue is greater than maxValue
return (minValue < maxValue) ? (minValue + uniformRandom(random, (maxValue - minValue))) : 0;
}
There are a number of more efficient solutions,
but it’s hard to get right and most example code isn’t very well documented.
The best way I can think of without doing more research is something like:
By reducing the result with the mask, you drastically cut down the number of discarded results because you end up only looking at the relevant bits.
The problem, however, is how to make an efficient nextPowerOfTwo on AVR.
If min and max are constant then it becomes a lot easier because you can use template parameters and then compute the mask at compile-time instead.
If you’re planning to use more than just xorshift32 then you might be better off turning randomInRange into a templated free function that could be used with all engines.
A while back I wrote something similar for the ‘on randomness’ thread based on the source of arc4random_uniform, though I’m not quite sure how it’s supposed to work:
// Modified version of OpenBSD's arc4random_uniform
template< typename UInt, typename Random >
UInt uniformRandom(Random random, UInt max)
{
const UInt min = (-max % max);
UInt result = 0;
while(result < min)
result = random();
return (result % max);
}
template< typename UInt, typename Random >
UInt uniformRandom(Random random, UInt min, UInt max)
{
return (min + uniformRandom(random, (max - min)));
}
I’d like to point out that this demonstrates why the PRNGs in the C++ standard library overload operator () to provide their random numbers instead of having a random() function.
Given the expression random(), random could either be a function or an object with an overloaded operator (), which makes writing template functions easier.
Objects that overload operator() are often called ‘functors’.
Halo 5 has scripting?
Or is it just a deformable world and you removed blocks manually?
If the latter, this could be done in Minecraft, Garry’s Mod, Scrap Mechanic, Space Engineers…
Actually, Minecraft has function blocks and commands,
so theoretically if you could create/find a source of randomness in Minecraft you could build a maze generator with command blocks and functions.
*Pharap’s ‘to do’ list loudly multiplies*
Simple answer: discard them.
Make the initial grid larger than it needs to be,
run the algorithm, then discard the outer walls.
Or running the algorithm 4 times and then rotating 3 of the resulting mazes.
Stitching them together might be difficult though,
so it might be better to divide a single maze into quadrants and change the direction of travel for each quadrant (up & right for top-right, up & left for top-left et cetera).
That reminds me of the scifi film Cube (and its sequels).
It predates a lot of things with similar ideas.
I’ve never seen any of either franchise.
I can imagine what pattern this would generate.
This is indeed more of a precise checkerboard than the xor pattern.
Aside from the over-abundance of lakes it seems mostly alright.
The trees and grass patches are particularly good.
That seems like a lot of extra work.
It’s easier to just handwave it and say “the caves/dungeons exist in a different dimension”.
(Which reminds me of how Spyro games have portals to levels.)
Much messier than the other approaches.
Might be a good start for islands or something that’s supposed to be messy like grass and dirt, but otherwise not as useful as the other two.
Vaguely. Mostly the trees.
More specifically it’s (axis-aligned) ‘binary space partitioning’, possibly even a k-d tree.
