Help me with C++ for my game

(goes by "spacebruce" elsewhere) #263

Fun story, some modern camo designs are actually called Digital Camouflage and are made up of pixellated blobby shapes.


This is my cave generation applied to trees. If I combine this with my value noise, my forests should have empty space we can walk through Ninja edit: or I could use the lower values for something else. There are 10 possible values when using the my cave function. I haven’t tried lerping anything yet

For comparison, this is how link’s awakening is laid out:

I changed my method of “autotiling” trees. I don’t exactly autotile them anymore, I just generate the whole tree, starting from the top of the screen, and only when x%2 == y%2. The rest is ignored.

I didn’t, I tried reading the article multiple times and I seem to get lost… I seem to learn more easily with videos, or very very tiny chunks of information. I don’t have problems listening, fortunately

Edit: doesn’t mean I won’t go back to it, just means I start with some reading, then videos, then trying, more videos, then trying again, more videos again then finally reading. I usually end up understanding what I need by the end but it is a rollercoaster

Edit2 what I might actually need for forests is a maze algoritm, but scaled very wide so that it’s similar to Zelda’s forest instead of just tight corridors. Although maybe what I have now is good enough

(Pharap) #265

I’m not in the least bit surprised that you know this, or that it works.
The image in that article reminds me of some of the Dragon Quest overworld maps.

Looks quite good.

Unfortunately I don’t watch that many videos because I’m impatient,
so I don’t know many good videos.

I often find myself mentally screaming “get on with it!” a lot when I watch videos because I could usually read a transcript faster than it takes the person to narrate the video.

If there’s a lot of good diagrams or it’s entertaining then I might watch it, but if it’s just an infodump I’d rather read an article.


I might have found my dungeon generator…

(Pharap) #267

I tried to read the docs about convolve2d but it’s a bit confusing.

Thankfully they specified the rulestring in the text: B3/S12345.


I might end up using something else.

Honestly I’m just using my game as an excuse to learn more about procedural generation :D
Well, almost. I do need dungeons and an overworld

Edit: Wang tiles seem like a better option for dungeon/maze generation.
There’s a simple way to make them deterministic and independent of previous areas; generate half randomly like in a Chess board pattern, then generate what’s in-between. Plus it’s basically the autotiling thing I keep talking about

(Pharap) #269

That’s numberwang!

Seriously though, very good article.
I was vaguely aware of this technique but I didn’t know it had a name.

My only complaint is that in the second PRNG arrow,
I would argue that the PRNG actually becomes a hash function because it’s no longer stateful.


My RPG/Hack N Slash game world is a solved problem!

Summary: have a ruleset for biomes, generate biomes as slices of a circle, each biome contains the item/key to the next area The “locked door” is any obstacle that can be overcome with the item gained from the previous biome. Biomes also control for difficulty. I did this TL:DR for you @Pharap, I know you like to skip to the meat of what’s important :D

I’ll make a summary of the whole thing as this could almost be an essay, and it might be useful for someone later. I might turn this into a blog post later because I think it can really be that useful.

I’ll give credit to this reddit comment, since it helped me zone-in on the problem and the solution because it really helped me zone-in on the problem.

Important bits of the Reddit comment:

Person who asked for help:

in general, since Zelda and SoM have a lot of travel-blocking features (e.g. not being able to traverse terrain vertically, or having big “blobs” of impassible forest, or long rivers),

Good parts of his answer:

This. This is why. If you ever intend to create obstacles that block the player early on, but permit travel later (e.g. after collecting an item), you’ll need to put that right at the center of your design.

At the very least, you’d need an abstract, graph representation of the map. For my game, everything except the terrain height is based on the output of a lock-and-key puzzle generator

Might as well link his game, Lenna’s Inception, a procedurally generated Zelda-like (I like helping people who’ve helped me out, I think it’s appropriate to link to his game as a thanks)

The Problem
I need an open/semi-open world that is beautiful, feels believable, is fun to play in and can be stored on a tiny Arduboy. Great, now we need to define those things

What makes a fun world/fun game?

  1. Sense of exploration
  2. Sense of progress

What makes an open world?

  1. You can go anywhere you’re ‘supposed’ to be able to go to. No invisible arbitrary walls.
  2. Point 1 doesn’t matter, it actually just has to feel open. Link’s Awakening is truly open only when you can jump, cut bushes and have all the other items required to go everywhere. But it Feels open from the beginning.

What makes a world take no space to store it?

  1. Procedural generation (less control for sense of progress)
  2. Compression (takes more space than procedural generation/world needs to be smaller)

With those criteria, the problem becomes…

How to proceduraly generate a world that feels open, is believable, beautiful and fun to explore and has a progression system.

Making it beautiful

  1. Using a nice tileset of different areas (beach, river, forests)
  2. Using some type of noise/value noise/Perlin noise

Making a progression system

  1. Some areas need can be locked away from he player until he has a certain power or item
    Here’s Link’s Awakening layout - the forest is locked by a bush that can be destroyed when Link gets his sword
  2. Level/Skills system, but this is not as effective. It is not as rewarding as gaining access to a new area

My solution

A procedurally generated giant island based on biomes in a circle, and an extra biome in the center. The biome in the center is the starting area that connects to every other. Each biome contains a final dungeon which allows the player to gain a new item, that will let him access a new biome of the island.

Which biome contains which item, and which obstacle blocks which biome can be constrained by a simple ruleset. That ruleset affects the procedural generation. Biome1 which is the starting biome contain item 1, which allows access to biome 2. The border between biomes will have noise/randomly generated entrances that fit only said item.

A circle can have an infinite number of slices, so the number of items and dungeons isn’t constrained by anything. Each biome can have a difficulty parameter attached to it, which can affect enemies an dungeon generation.

This ruleset combined with value noise or Perlin noise, my cave/forest generation or any other procedural generation system, should my for a game that can be won, that has a sense of progression, feels open world and takes very little space on the Arduboy, being deterministic.

Well that took a more time to write than I expected

(Scott) #271

Too bad the Arduboy Magazine by @arduboymag has stopped publishing. It would probably make a good article.

(Pharap) #272

That name rings a bell, but I can’t think why.

The system requirements seem a bit excessive.
Given the simple graphics and relatively simple gameplay I would have thought it could run on a toaster (or at least a mid range ARM Cortex with a decent screen, and/or a Pi/Pi Zero).

Skyrim and Zelda Breath of the Wild do this especially well.

In Skyrim, the only thing that limits you is the power of your enemies.
In one playthough I managed to gather most of the dragon priest masks and daedric artefacts and buy my own house before I even defeated my first dragon because I could choose to put it off.
Although this has its downside because it becomes a lot easier to slay the dragons and the big bosses.

When I played BotW I activated all the map towers before I even touched any of the main dungeons.
Although in that case I think it ruined the fun a bit.
BotW was a bit of a mixed bag, I loved exploring, but it bothered me that there were only 4 proper dungeons.
I found most of the mini dungeons pretty easy.

Actually, now I think about it, I think Wind Waker did a good job.
It forces you to stay on course for the first two dungeons, but after that you’re free to go to any island.
Some islands you can’t do anything on until you have the right tool, but that’s part of the fun, because you’re left guessing what tool you need and then when you finally get that tool you start thinking of all the islands that you need to revisit.
(Wind Waker is probably my favourite Zelda game. I think it was the second Zelda game I ever played.)

One of my other favourite Zelda games (partly because it was my first) was actually the Minish Cap, and that limits progress through the “you need a tool” approach.

(In all honesty there aren’t many Zelda games I don’t like. Skyward Sword is the only one I genuinely dislike.)

I’m still not sure how the biomes on a circle idea works.
At the moment I’m basically imagining a dartboard or slice of a tree.


Think of a pizza, where each slice has a unique set of vegetables, cheese and pasta. But, to eat some pizza slices, you need to have eaten some other ones first. The analogy breaks down with the biome in the middle, this is basically the hub/town in between all the other areas, and will also be the spawn point.

Who knows… maybe in the game I’m making, you get access to a boat which will let you go to a different island (simply changing the seed)

I still have to make it work, but I’m fairly confident. Edit: I just realized it was a compliment, thank you

I’m now playing around with the wang tiles idea. I don’t think it’ll end up feasible with the highest level of complexity, but for zelda-like dungeons all I need is 13 layouts/13images. My prototype is almost ready

One interesting problem is making all layouts equally likely. I if generate each wall randomly, it won’t be the same. So I made 8x8 sprites of each possible layout, and each number from 0 to 13 represents one of them. (included rotated and mirrored layouts)

Edit: there’s 15 possible room types, I counted wrong. 16 if we include a “not a room”.

Other edit: I wouldn’t do this for the Arduboy (unless I’m even more insane than I thought), but if I were to make a PC/commercial version of this game, I’d use icons/emojis for NPC dialogue. I tried having a conversation using only emojis once and it’s pretty ridiculous how much you can say without using any words. It’d be a good way to generate questlines without messing around with the complexity of creating sentences. And because of the “uncanny valley” principle, it would probably be better to have less realistic communication from the characters than failing at trying to make it decent. You also avoid the need to translate quest lines.

(Pharap) #274

I’m going to need a few moments to recover from this suggestion.
I heard ‘pasta on pizza’ and suddenly my mind went walkabout.

Ok, that makes more sense. Then the dartboard idea wasn’t too far off.

The technical term for ‘pizza slices’ is ‘sector’ aparently.

I had an idea a bit like this once, but it was planets rather than islands.

Although now I think about it, that’s sort of what Lego Worlds did.
(I’m pretty sure I thought of it before playing Lego Worlds though.)

Be careful of modulo bias.

4 bits

I’m sure I’ve seen games do this before, but I can’t think which ones…

I think some of the Lego games have done this, but I can’t think which ones.

I knew the meaning of the phrase but had a look at the link anyway.
I recognise this guy’s voice. Didn’t he used to have a channel called ‘goomba’ something or other?


First step of the deterministic method for generating wang tiles. Red X means not generated. (I also have a green X if the generator returns a wrong value… easier to debug problems this way)

The second step:

I thought it was the same as the autotiling I talked about before, but it’s actually different. Same principle, but it’s different. The tile isn’t affected from whether or not there is a tile beside it, but rather which tile is beside it. (all the four neighbours)

On the first step, this picks any layout that doesn’t have 4 exits and isn’t a wall, each layout having the same probability. If I tweak what can get chosen initially, and the probability for each layout, I can probably make it very maze like, or make it any other way I want. I tried making it choose between only corridors, up and down exits or left and right exits. It makes it a bit like a maze

Here's a few results of that

Not entirely sure how to make it more likely for it to be “feasable” but at the same time, maybe I don’t need it at all. Make the player enter a house or some type of entrence, spawn him in one random room layout. If it happens to be a straight line… so be it. If it happens to be a big maze… so be it. He can always comes back and leave, and go for another dungeon. Maybe it is a non problem.

I’ll try making a an AI to explore these and generate them as it goes, to simulate a player.
Edit: nevermind making an AI, I’ll just move the player around myself.

As a quick recap, this is done in two steps so that you can generate the same dungeon everytime no matter where you go and where you come back to. Either you can load the tile directly, or you can load the 4 tiles around it directly, and then load the one you want. To find the layout where you are, it’s just a few if and switch statements, no complex algorithm. I can make alternative layouts that fit with the same scheme

(Simon) #276

I have been following this thread with interest. That last image looks perfect for a Dark and Under maze generator.

(Pharap) #277

Although it works slightly differently.
D&U has solid walls that take a whole block rather than each block having 4 walls.
So we’d have to translate the edges between the blocks into solid blocks.

As a side effect, we’d have no big open halls, it would be more of a tight maze.

@SamSibbens While I’m at it, I’d like to point out a downside to this approach:

What you end up with is not one coherant maze, it’s lots of separate mazes.

(Stephane C) #278

Some things might be of interest for that other rogue like game I wanted to make happen too I think…


Yep that’s what I meant by “Not entirely sure how to make it more likely for it to be “feasable”” (but, I’m not entirely sure how my phrase was supposed to make sense…)

Doesn’t matter too much since you never see the mazes you can’t access. For the player, it’s one dungeon with nothing outside of it (when it’s in fact an infinite set of rooms and dungeons hugging each other :D :D :D :D (the child in me got out again)

You could add tiles for open halls. It’d make the algoritm a bit more complex but it would work. Edit: not more complex, just a bigger switch statement. It isn’t an algoritm… just half random tiles, half “which tile fits here?” There isn’t any actual limit. You also could have a rooms with 4 exits, but with the middle blocked. I quickly replaced my current 4 exit layout with one with a diagonal wall in the middle, just to show you:

As long as the layouts matche, the content in the room can be anything. You could simply scale the layouts by 2 or 3 or 4, and generate the inside differently too

(all this by the way is just a proof of concept, I’d probably make them twice as wide as they are tall, and I’d probably do a lot of alternative layouts like the one I just made for the 4 exits one)

Unfortunately GameMaker doesn’t allow to read sprites as if they were an array, so it might actually be easier to export those sprites and test it on the Arduboy. Although, now that I can visualize them, it should be easy to turn the layouts into code.

(Simon) #280

Too true. Let’s see how this thread pans out and then steal what we can borrow this code.


I don’t need it for for my dungeons, but I kept thinking about what you said. Now I’m wondering if there is a mathemathical ruleset that would guarantee an infinite dungeon/maze.

By that I mean, if you’re in one of those mazes, and you keep going in one direction or the other, you’ll always be able to go further, there’s always gonna be more rooms that you can reach. Like an infinite line that’s just very twisted (again without needing to store anything)

I wonder if there’s a ruleset that would make this happen, without it being just a repeating pattern.

Edit: I think there is: just… bigger Wang tiles. Wang tiles of 4 Wang tiles. It’s just a hypothesis but I’m pretty sure if you use a smaller set for the outer layout, you could make it so that you can continue. That’d be a new twist on the infinite runner genre. Infinite dungeon escape, how far can you go? Edit: wouldn’t be new, but it being deterministic no matter where you start from might be

@Pharap a corner wang tile implementation would probably be an alternative solution to the big rooms/big areas problem.

Edit before I even posted my previous edit:

I might have overcomplicated things. You can have some big rooms if I just remove the “doorways”. It also looks more like a maze, but it’s exactly as it was before, I just modified the sprites

Edit again: If I want to have a maze layout using trees, Wang tiles might actually work. This might be more versatile than I anticipated. Maybe just my regular value noise, with Wang tiles of trees laid on top of my my forests areas. But I think my other thing would work better for trees


I’ve been looking for an excellent way to generate a pseudo random number based on a seed generated from two inputs (x and y), and xxHash seems like the most promising option, but it uses 32 bits and I don’t know if that’ll be a limitation on the Arduboy.

Different implementations, including C++:

If I can make this work I’m absolutely turning it into an Arduboy library, getting a random number from 2 inputs is very important for any kind of 2D procedural generation.

Edit: I’m struggling quite a bit to understand how to replicate xxHash