#2D Top-Down procedural level generation

1 messages · Page 1 of 1 (latest)

cobalt peak
#

I've seen multiple methods out there, some involve entire pre-made rooms being placed, some tiles that build rooms, etc

It's less about the how for me and more about what you think would be best in terms of versatility but also scope

I want to generate a level that is almost exclusively an indoors area, lots of rooms, halls, passages etc.

Some rooms may have certain special uses.

Some rooms can reachable from multiple others(for looping), some single entrance, potentially something yo even allow dead ends

I just wanna see and weigh my options before I put effort into a system I might rework

loud jackal
#

@cobalt peak hi

cobalt peak
#

wassup

loud jackal
#

I don't think you can ever make a system that is extremely general

#

we can certainly help you design a system but we need more constraints

#

@cobalt peak what language

#

and for what project

cobalt peak
#

Unity, C#, 2D Top-Down, Industrial style, Flooded abandoned facility, simple maze-like structure

#

some rooms are objective rooms, some are just fillers I suppose, some loop, some are dead ends etc

loud jackal
cobalt peak
loud jackal
#

i'd imagine you could have a maze generation algorithm but weight paths that connect rooms together more heavily

#

so generally the rooms connect but there is some variation

cobalt peak
#

I'm not 100% sure if I want rooms connected by halls or just rooms... by each other, which is tighter with more space usage

loud jackal
#

and when connecting two rooms, you have a heuristic to make the hallway generation go towards the room, maintain its previous direction (to have straighter hallways) and some random weighting to make it change directions occasionally

cobalt peak
#

So does that require some sort of pathfinding (I suppose A*)

#

?

loud jackal
#

yeah graph algorithms

#

i would look at prem's algorithm its a nice maze gen one. in this algorithm it chooses connections based on randomly assigned weights between two nodes

#

you can probably modify these weights to modify how the paths generate

cobalt peak
#

Problem is

#

I want a decent balance between finding the objective in a newly discovered map, but also not make it long, it's more about stealth than the actual finding

#

So I imagine while the map is full of rooms and halls, it's not a full on maze

loud jackal
#

You control the maze-like nature with those weights

cobalt peak
#

but instead of connections

#

they're in a big "area" rectangle

#

and you start drawing lines to form the maze

#

just did some randomly

image.png
#

but like this concept ig?

#

and eventually this path is made and the rooms are gonna have "doors" in at least 1 of the points intersecting the formed maze

#

I remember there is this maze making algorithm, tho it was for a non-looping maze

#

so idk if it works here

#

also it had no gaps(rooms) in the middle of the maze

cobalt peak
loud jackal
#

i think you should look at existing algorithms and then maybe adapt

cobalt peak
#

yeah I saw one that makes a maze without loops, I should see if one with loops exist

cobalt peak
#

I made a basic maze generator rq(console cause lazy but I got this down at least(

#

It is seed based and can be any size and I also managed to put gaps(rooms) in it(no pics sad)

#

(It's my work PC no discord on it so it's not a screenshot lol)

loud jackal
#

cool

cobalt peak
#

I suppose adding a few gaps for rooms and stuff can be considered a level?

#

To make navigating harder I can give a flashlight kinda mechanic where the level not around you is hidden?

loud jackal
#

that's up to you

cobalt peak
#

I do have 1 generation problem tho

#

It's easy to make gaps, and easy to make no cells around them connect to the gaps

#

However it's hard to control the amount of entrances

#

And direction especially

#

To elaborate, I'm using Kruskal's algorithm for maze generation, and I just skip cutting edges between certain x and y ranges to make gaps

cobalt peak
#

Ever so slowly....

Obviously a level wouldn't be as... mazey...

image.png
#

you can give less of a feeling by adding more rooms, shrinking the maze but scaling it up

#

giving less maze like feeling, bigger halls, and more rooms to explore

#

but rn I am just messing around with generation

loud jackal
#

is the level like a building or a dungeon

#

because a building fills all available space whereas a dungeon can have empty space excluded from the play area

#

@cobalt peak

cobalt peak
loud jackal
#

not how it appears lol how do you want it to be

cobalt peak
#

I know of how you can divide a rectangle to get rooms, it just didn't feel flexiable or interesting enough

#

I wanted a sense of struggle in navigation

#

perhaps not exactly a maze, but it being a part of the challange nontheless

loud jackal
#

I might try pruning very short dead end paths

#

it will make it look a bit less crazy

cobalt peak
#

How would you approach doing that?

#

I can of course easily check if closing a connection makes the maze solvable

#

so I can just close them

#

but that's also not the definition of short dead ends

loud jackal
#

you can probably just iterate over every cell and check for neighbors

#

if the cell has three walls, make a fourth wall to close it up

#

this will just shrink everything by one

#

you can then add more logic to see if the path was shallow

cobalt peak
#

cause that'll prob close the entire thing lol

#

I suppose you didn't mean that

loud jackal
#

one pass

cobalt peak
#

Hmmm I'll try that and show you the result

#

btw the generation is super simple (and I am making sure it's seed based)

#

tho I did use a graph instead of a tree

#

because I added(not used in this pic) the ability to add loops

loud jackal
#

Are you embedding rooms into the maze?

cobalt peak
loud jackal
#

cool

#

How do you guarantee connectivity between rooms

cobalt peak
#

Well the entire maze is connected

loud jackal
#

Or is that a dumb question

cobalt peak
#

every cell is reached from another

#

By carving more cells.. you could never break that

#

only by closing

loud jackal
#

I would also assume you have some entrance closing pass?

cobalt peak
#

wdym?

loud jackal
#

Because digging out a room will create lots of exits

cobalt peak
#

Ohhhh

#

I just made the room digging like

#

10 mins ago

#

I was gonna work on that

#

sooo... not yet

#

lol

loud jackal
#

I would put it in the room as a rectangle and then from the edges select your exits to open

cobalt peak
#

You mean like shut the entire room and then open X entrances?

loud jackal
#

Your seed should be a master seed which is used to generate the next seeds used for individual passes

loud jackal
cobalt peak
loud jackal
#

lol

cobalt peak
#

I tested it, by inputting the same "Settings" (Seed, width, etc) you always get the same map

#

alternatively

#

you can just input a seed, and it generates the settings

#

hence just a seed will also always yield the same maze

cobalt peak
# loud jackal Yeah

well if you open the wrong entrances you MIGHT just make some parts unreachable

#

my plan was finding all open areas

#

deciding which ones I want and shutting the rest

loud jackal
cobalt peak
#

tho that can also do that...

#

hmmm

#

You can ignore the looping for now(it works but I'd change that)

image.png
#

for now that's the settings tho I'm constantly adding more and tweaking those

loud jackal
#

Looping is literally just taking down one wall

cobalt peak
#

Yeahhh but I do it like

#

making sure it forms big loops

#

and not tiny ones

#

that are obvious

#

so I check the loop distance with BFS

#

I only look at edges that I know would form a loop(ones that the algorithm skipped for that very reason)

#

if they form a big enough loop, I roll a random to see if I remove them

#

Ideally I'd later change it to just be more likely to break the wall the bigger the loop

#

to give chacne to smaller ones too, just less so

loud jackal
#

hmmmm

cobalt peak
#

cause if it's a small loop

#

the player is just gonna see it's a loop

loud jackal
#

What if instead of generating mazes you generated loops. Overlapping loops

cobalt peak
#

a bigger one you might just get lost in

#

and not realize you went in loops

cobalt peak
loud jackal
#

Not sure what there is to elaborate. Like you could use a turtle to generate the loops which would probably be less crazy than the maze because you could lower the turn probability

#

And then you could overlay the loops to make it more confusing

cobalt peak
#

It'd look like a bunch of rectangles overlapping each other?

#

wouldn't that make perfect straight hallways all across?

loud jackal
#

The loops wouldn't be rectangles you'd use a turtle

cobalt peak
#

ohhh

#

I'm kinda wondering how much variety it's gonna give

#

I do agree a maze is a little too crazy

#

that's why I thought the levels would actually be relatively small mazes

loud jackal
#

I mean just another idea

cobalt peak
cobalt peak
cobalt peak
# cobalt peak

I'd say here the rooms take a significant amount of space, and the maze is suddenly less overwhelming

#

imagine it's darkness and you only see around you (not through walls)

#

You'd explore a little in a need to find the rooms

#

but not for that long

loud jackal
#

Have you seen those lidar horror videos

#

horror game

cobalt peak
#

I've seen the lidar video thingy

#

but no a game made of it

#

Alright basic premise

loud jackal
cobalt peak
#

You are a (potentially) group of people exploring a submerged facility, you have an objective and potentially "enemies"

#

it's a stealth game

#

imagine like

#

"retreive this item" and it's in some room somewhere

#

the water is basically just a mean of time "oxygen level"

#

and enemies can either use sight or maybe vibration/sound from the water

#

to sense you

loud jackal
#

cool

cobalt peak
#

maybe each one can be a little different

#

so now I am trying to imagine how a map for that could be like

#

OHH wait

#

I did forget to mention 1 thing

#

0 verbal communication

#

(Ik poeple would ruin it with discord lmao)

#

you communicate via signs, like divers

#

I actually got the water idea because originally I just wanted a stealth non-verbal comm game, and then I thought of hand gestures, and then I thought how when I went diving we had those lol

loud jackal
#

make them use semaphore flags

cobalt peak
#

Lmaooo

#

real

#

You could argue it's somewhat verbal

#

because you spell letters

loud jackal
#

When does the game come out

cobalt peak
#

I mean more like Point in a direction, the Stop hand, the "Come here" kinda hand etc

cobalt peak
loud jackal
#

Okay I'll be waiting

cobalt peak
#

yeyeyeye

#

totally

#

I'm a talented indie dev in a rough world

#

I'm sooo special

#

but yeah I'm just chiling and having fun when I find ideas I like

#

we'll see how far thinking "hmm that's cool" will take me lmao

loud jackal
#

Well you got less than 24 hours

#

Back to maze gen

cobalt peak
#

fr

cobalt peak
#

the same seed but one with closing the ones with 3 edges

#

and it looks kinda odd ngl

#

but ig you won't see that if you imagine the player being IN the maze and not above it (it's topdown but since you can't see through walls you won't see those squares)

#

there are still some oddities because I didn't quite fix the generation, I just did it quickly to see what'd happen

#

oddities fixed but nonetheless

image.png
cobalt peak
#

I can now reliably eliminate the areas where rooms will be, and the maze will ALWAYS be a perfect maze

image.png
#

This way, I can make the entrances whereever I want, I just remove more edges so the maze will always stay "perfect"

loud jackal
#

the fact you're not using an ortho cam for this view is slightly unsatisfying

#

share your algos

cobalt peak
#

this is the "Scene" view

#

I don't even bother with a cam cause I wanna move around and why make a spectator cam when I can just...

#

use the scene cam

#

LOL

#

there won't be spectation in the game anyways

cobalt peak
#

It's actually significantly shorter than you'd imagine

#

lol

#

Especially the tree one (scrapped for graph)

loud jackal
cobalt peak
#

Rn I am suffering trying to place the rooms in the holes

#

because fucking Unity anchors at the middle of theobject

#

instead of the corner

#

and you'd imagine

#

well half the width and add it

#

NOPE

#

it's not quite like that

#

welp

#

it finally worked

#

just needed some tweaking because of how scale works

cobalt peak
#

Currently a room carves just a single random door (this seed had the rooms generate RIGHT next to each other without intersecting, forming a big room with 2 doors)

image.png
#

I can make it choose more doors

#

but then I can't let them be random

#

or it might just make like 2 doors on the same edge seperated by like 1 node

#

which would look cringe

cobalt peak
#

even set the projection size to be perfectly fitting

cobalt peak
cobalt peak
#

made a bigggie for funsies

image.png
loud jackal
#

too maze like

cobalt peak
#

What makes it less maze like is the amount of rooms you put in

cobalt peak
#

I used SciprtableObjects to make LevelPreset and PreciseLevelPreset

#

LevelPreset takes ranges and randomizes a seed and makes a LevelSettings object which decides how the generation will be like

#

PreciseLevelPreset is basically always replicating the exact same LevelSettings, and you can decide a seed there

#

so one can be use for like a Difficulty where it makes a random map with specifications
and one generates an exact, desirable map

#

I prob need better naming tho-

#

yeahh I changed the names but lol

cobalt peak
#

had some fun

image.png
#

(It took like 1.5 mins to generate, instantiating 80000 objects is quite much lol)

loud jackal
#

is it the instantiation...?

#

i suspect graph traversal is slow

#

what's your data structure

#

@cobalt peak

cobalt peak
cobalt peak
cobalt peak
#

Graphs + Disjoint Set unions

#

the disjointed sets let me have an (almost) O(1) performance regarding checking connectivity between 2 nodes in the graph

#

which makes it significantly faster than the graph traversal, which is completely avoided during generation

cobalt peak
#

it's no small deal

cobalt peak
#

Basically those two

#

LevelGraph is the datastructure

#

and Level is the way I used it

loud jackal
#

@cobalt peak bruh

#

profile that crap

cobalt peak
#

oh??

#

that bad?

loud jackal
#

it's probably almost all those fetch methods

cobalt peak
#

aren't Dicts hashed and O(1)?

loud jackal
#

it's so many pointers and stuff

#

yeah but maybe a large constant

cobalt peak
#

a constant?

loud jackal
#

a 5 second constant lookup is constant

cobalt peak
#

where would I use a constant tho?

loud jackal
#

sorry let me speak in complete sentences lol

#

a O(1) time complexity is constant, but there might be a large constant multiplier which would make it slower than a linear time complexity with a smaller constant multiplier

cobalt peak
#

ohh yeahh I see what you mean

#

yeahh there are prob a lot of lookups

#

who'd you upgrade it?

#

the reason I use graphs and not trees is I eventually looping maps

#

and trees don't work like that

loud jackal
#

well profile first

#

I'm interested in the slowdown

cobalt peak
#

alright

#

tho not 100% sure cause I did do the Deep Profile and I still didn't find my methods

#

@loud jackal
a 100x50 map
(the last pic was 400x200)

image.png
loud jackal
#

lol

cobalt peak
#

yeahh it's a whole second, quite horrid

#

and the Union took much more than I thought-

#

I guess a ton of calls

#

lol

#

none of the methods are slow

#

they're just called a disgusting amount of times

loud jackal
#

yeah it's all the fetches

cobalt peak
#

I'm trying to save fetches and replace the (int, int) with a struct

loud jackal
#

you allocate 4.5 mb of memory and use all these fancy abstractions

#

as a C dev this hurts

cobalt peak
#

lollll

#

I love OOP

loud jackal
#

high level languages let you commit cursed code execution in a single line

#

why the union btw

cobalt peak
#

which, however slow it is here, would've been significantly slower

loud jackal
cobalt peak
#

it's basically a tree, but it tries to make it as flat as possible by placing children on the root rather than nested

#

and then checks if the root is the parent

loud jackal
#

I still don't get it

cobalt peak
#

basically comparing tree roots is faster than graph traversal

#

when 2 cells (merge) one of their parent becomes the other's root

#

you know 2 cells are connected if they share a root

hollow nightBOT
cobalt peak
#

oh rip

loud jackal
#

damn the bot

#

so each node has a graph built from it?

cobalt peak
#

lemme

loud jackal
#

and if there exists a root-child relationship between two nodes, they are neighbors?

cobalt peak
cobalt peak
#

just connected

#

directly or indirectly

#

this algo goes until all cells are connected

#

insuring a perfect maze

loud jackal
#

so in this case you have a grid of nodes, and randomize the edge weighting?

cobalt peak
loud jackal
#

and you connect the smallest edge values?

cobalt peak
#

I just have a list I shuffle and iterate

loud jackal
#

this is very similar to Prim's algorithm which is what I'm familiar with

#

so I still don't understand the union bit

cobalt peak
#

yeah I saw it but I heard Kruksal's makes more "interesting" shapes

#

so idrk

cobalt peak
#

and when you merge an edge

#

you first check if they belong together(same root)

#

and if they don't

#

you make node B's root Node A

#

so A and B are connected

#

now if B and C were to connect

#

C's root is C(none)
B's root is A

#

so now

#

C's root becomes B'a root(A)

#

so now they're all connected

#

Became I make C's parent A directly, and not B

#

I avoid a lot of recursion going up the tree

#

keeping it as flat as possible

#

so it's almost always just 1 lookup to find each root, and so you do 2 lookups to find the root, compare them, and if they're equal you know the cells are connected

loud jackal
#

you do this to avoid making cycles?

cobalt peak
#

Yupp

#

if you always connect

#

it'll just be one huge hall

loud jackal
#

okay now i understand more

#

so you arbitrarily choose one node to be the root in a group of nodes

#

nodes which are connected have the same root due to your flattening

cobalt peak
#

it's always the first of the two comapred

#

it doesn't matter which really

#

because they'll all end up under a single node

#

whichever it might be

loud jackal
#

no I mean when initially making a graph you need to chose a random node to make the root

cobalt peak
#

Ohhh

#

I choose a random edge

loud jackal
#

the first pair you join, one becomes the root

cobalt peak
#

and each edge is between 2 nodes

#

so it just takes the first from there

#

yeahh

loud jackal
#

so... why union

cobalt peak
#

Otherwise I'd need to traverse the graph to find if the cells are connected

#

to know whether I wanna connect them or not

#

with union it's 2 lookups and an equals

loud jackal
#

why doesn't each node just store a ref to a root

#

and compare the roots of each node

cobalt peak
#

I just use a dict instead of that, but possible

#

I used a dict because graphs are easier with it

#

trees are easier as classes

#

but for graphs it gets super weird(at least for me)

loud jackal
#

dict?

#

what type?

#

Dict<Node, List<Node>>?

cobalt peak
#

private readonly Dictionary<(int x, int y), (int x, int y)> parents;

#

each node is just expressed as x and y

#

I should prob just use the Vector2Int

#

but ig I just discovered this tuple feature and got hyped lol

#

appearntly they're somewhat slower after I just searched it now

loud jackal
#

how does this show the relationship between a node and its root?

#

is it just node -> root?

cobalt peak
loud jackal
#

bruh

cobalt peak
#

lolll

#

you suggest I make a struct that contains it and make it a list instead?

loud jackal
#

that would be better

loud jackal
cobalt peak
#

tho if you wanna POINT

#

it's prob gonna need to be a class

#

I mean ref can be used

#

but not ideal I imagine

#

Huh-- I was led to believe they act like structs and are not on the heap

image.png
#

Struct timeeee

loud jackal
#

uh

#

as a C dev I would skip this entirely

cobalt peak
#

lolll

loud jackal
#

but you try struct first

cobalt peak
#

in favor of classes?

loud jackal
#

struct or class

cobalt peak
loud jackal
#

some object

cobalt peak
#

like what's the alternative

loud jackal
#

oh just a uint32

cobalt peak
#

for both x and y?

#

I mean ig they can become shorts

#

oh a uint

#

does C# has it?

#

wait

#

oh-

#

it doess

loud jackal
#

no the coordinates are implicit

cobalt peak
#

I'm too used to java

loud jackal
#

I create a 2d array of uint32s

#

the 2d index is the coordinates

cobalt peak
loud jackal
#

the uint32 stores connection and cycle info

cobalt peak
#

the thing is, I am not sure I know the width and height(therefore the dimensions) in advances

loud jackal
#

heap allocate it then

cobalt peak
#

tho I can kinda just

#

create a new array when generating a maze

#

at the start of generation I do know their sizes

#

and there's no array.Clear() anwayys so Ig it's bound to be a new array either way

loud jackal
cobalt peak
#

my nodes are basically just a

#

AtomicReference<Direction>

#

since Direction is a flags enum

#

and all I care about in a node

#

are which directions it has connections to

#

but I wonder if all those AtomicReferences are also a problem lol

loud jackal
#

what is that

cobalt peak
#

I mean idk what alternative I have

#

uhhh basically a class wrapping a value type (like an enum) to make it reference-able

#

as easy as it can get

loud jackal
#

bruh

cobalt peak
#

if I just put in Direction

#

because it's an enum

#

changing it would not affect the dict

#

well ig unless I directly set I suppose that exists--

cobalt peak
#

Java did

#

blame java fr

#

I just copied it

#

(well I used Properties but yes)

loud jackal
#

I guess it avoid overhead of classes... Maybe

cobalt peak
#

I suppose there are ways to avoid that?

#

like just use Direction

#

lemme try

loud jackal
#

see how much you can optimize the generation

#

I think under 1 ms could be possible

cobalt peak
#

oh damn

#

also I guess

#

yeah you're right the whole connection can turn from this Dict

#

to

#

int[]

#

where index is the node and the value is the index of the parent(same way we use width and height to get the index)

#

or as you suggested

#

uint

#

since indecies are always positive

#

is tehre a performance benefit to unit?

#

or do we just enjoy a max value 2 times as big?

loud jackal
#

there isn't really a diff

cobalt peak
#

not like I'd ever reach int.MAX_VALUE anyways lol

#

uyhhh for graph connections...

#

currently Dict<(int, int), HashSet<int, int>>

#

do I just make it

#

HashSet<int>[]?

loud jackal
#

you really like these data structures lol

cobalt peak
#

or like maybe even

#

int[,]

cobalt peak
cobalt peak
#

than int[,]

#

in fact int[,] is not a fit at all, it's horrid for this lol

#

there's gonna be 1 problem with int[][] that I dislike

#

and maybe HashSet<uint>[] is actually gonan be better

#

a cell can have up to 4 connections. so I guess I can make an int[widht * height][4] (ik that's not the syntax) in advance

#

but it might not be connected to all 4 of them at all

loud jackal
#

do you need a hint

cobalt peak
#

so either I make 4 in advacne and they're mostly gonna be empty, or I'll make new arrays... which sucks ass

cobalt peak
loud jackal
#

use 4 bits from the int

cobalt peak
#

but like idk

cobalt peak
#

even if you divide it to 4

#

8 bits each

#

that's 256, not nearly enough to express the index

loud jackal
#

Or connected to up down left right

cobalt peak
#

I can make it a long, and ig 65k is enough(?)

cobalt peak
#

but that'd mean if I wanna find the connections

#

I gotta fetch the bitmask, and then extract all the directions from it, and then realize their indecies, and then fetch them

#

that's a performance vs memory thing I guess

loud jackal
#

no like 1000 UDLR means connection up

#

then traverse one node up

cobalt peak
#

yeahh that's how I store directions already

loud jackal
#

no but you dont need anything else

cobalt peak
#

I get for example

#

1010

#

so UP and Left

#

I need to check each of them individually with ((value & direction) == direction)

#

4 times

#

for each direction

#

and if its true

#

get the proper index

#

(-width,+width,-1,+1)

#

and then fetch with that index

loud jackal
#

if it's 2,2 then up is 2,1

cobalt peak
#

wait that's not -width

#

well you get the point

cobalt peak
loud jackal
#

you can easily flatten and unflatten

cobalt peak
#

yeah I know

#

it's mostly the checking each direction individually that's prob gonna be clanky

#

I mean I know BITWISE AND is prob super fast

#

it's more aobut it LOOKING weird lol

#

Hmmmm

cobalt peak
loud jackal
#

yeah

cobalt peak
#

oh so I was right about the +width and -width

#

alright lemme see then

loud jackal
#

you can make it nice even in c# without bitwise

cobalt peak
#

I mean I got no problems with bitwise

#

it's moreso just the doing it 4 times

#

I mean I can write a method that does it

#

heck even a for loop

#

well for loop is bad here

#

but lol yeah

#

Gonna need like index validation in there but like-- I say that does it

image.png
hollow nightBOT
cobalt peak
#

oh fuck

#

it was short asf bruh

#

since I only make 1 "cardinal" connection at a time, I don't do the bitmask check here, just a switch

#

tho I could-

#

is it better than a switch?

loud jackal
#

probably the same

cobalt peak
#

fair

#

welp I give up on units cause of the converstion issues(some things have to be int and then it's annoying)

loud jackal
#

int is fine

cobalt peak
#

yeahhh

#

I just realized when I init the parents array

#

I gotta iterate over all of them to set them to like -1

#

cause 0 is totally a valid parent

#

so I wouldn't be able to tell apart whether they have no parent or their parent is 0

#

welp at least I only loop once

loud jackal
#

just make 0 a not valid parent

cobalt peak
#

but index 0 is (0, 0)

#

it's a node

loud jackal
#

oh

#

you do it like that...

cobalt peak
#

0 * width + 0

loud jackal
#

sure that's one way

cobalt peak
#

you wanna do a +1?

#

it'd be odd but like possible lol

#

It only happens once at the start before generating

#

not ideal but like

loud jackal
#

whatever

cobalt peak
cobalt peak
loud jackal
cobalt peak
#

after all I need to display it later so I need to know

loud jackal
#

oh

cobalt peak
#

it's either another array or smth dumb like +1 on the flattening thing lol

loud jackal
#

when forbidding cycles you only need to compare parents, not know where they are

cobalt peak
#

but when I do a union

#

wait no

#

when I get the "root"

#

I check first if it has no root

#

aka a sole node

#

and if it is, I let it return itself in the result

#

but if I check its current root and its 0, idk if it's a sole one or is connected to 0

cobalt peak
#

moment of truth

#

(I did not implement rooms in this version, just the maze, the example with the profiling had 0 rooms anyways)

#

now the profiler won't show it hmmm

#

Now that's amazing to see

#

@loud jackal

#

alas the maze is bugged tho

#

comes all fucked up

#

Idk if that's just assigning the wrong direction

#

or wrong indexing

#

idk

#

but I doubt it'd be a huge performance thing to fix it

#

(those were made against the exact same seed and setting so same size too)

#

fixed

#

0 effect on performance, I just missed a Union call lol

cobalt peak
#

also like a few times less memory I believe, tho I don't remember and sadly not in the screenshot

loud jackal
#

hmmmm

#

what's your approach now@cobalt peak

cobalt peak
#

it's smth called ranking

#

it saves on calls but costs more memory(another int[])

#

tho from my understanding

loud jackal
#

you need to sort all edges right

cobalt peak
#

it's more relvant the bigger the array

#

so for small mazes it's meh

cobalt peak
#

right now my shuffle isn't an ideal one

#

I am aware

#

I just used Linq

#

I can deffo do better tho

#

but now as you can see

loud jackal
#

idk what you mean by shuffle but i think we are talking about the same thing

cobalt peak
#

this example was 16 times smaller than the one that took around a min

#

before optimizing

#

it took 1 sec

#

and objects took 3 to instansiate

#

sooooo

#

I imagine it'd be somewhat linear

#

16 seconds and 48 secs for each on the bigger exmaple, yielding the min or so

#

so now, making it around 10 times faster

#

the maze generation is great

#

but now instansiating is slow asf lol

cobalt peak
#

random sort

#

(based off a seed of course)

loud jackal
#

what is still taking up time in your generation code

cobalt peak
#

I'm in bed so I can't tell exactly but I'll check tomorrow what exactly takes time and let you know

#

(It's almost 4am)

loud jackal
#

okay lol

cobalt peak
#

Have a good one

loud jackal
#

crap... when you merge two different graphs when generating the maze, you need to do a full graph traversal to update it. or use a data structure like you did to easily get the root

#

is linked list actually the answer LOL

cobalt peak
#

Changed it to list

#

I also saw that lol

cobalt peak
#

But yeah I changed it out linked lists are not ideal for shuffling

cobalt peak
# cobalt peak

I'm not sure how 1.6MB were allocated tho...

There's essentially a byte array and an int array each width*height in length, of course there's the class wrapping it and the class wrapping the level, but it's just one each and don't contain much really...

Now byte is 1 byte and int is 4, and the example here had 5000 length

Aka
25k bytes... that's not nearly 1.6mb, even with the 2 classes, and the settings which have at most like a 8 integers or smth, what else allocates so much? Idk anything about memory allocation but like yeah-

loud jackal
#

there is overhead with classes

#

also consider repeated allocations

cobalt peak
cobalt peak
loud jackal
#

like creating a class in a loop

cobalt peak
#

I've only ever instantiated the Level class(and therefore the LevelGraph) once

#

I instantiate it on Start and that's it

loud jackal
#

well I mean drill down on the profiler

#

you'll see where the allocations come from

cobalt peak
#

I will when I'm back from work

cobalt peak
#

How else would you improve on that?

#

I mean it's down to a byte and int array

#

I mean I got 0 problems with the current performance ngl

#

It's approx 10 times faster than earlier LMFAO

#

Generating a 5k node level in 0.1 seconds is alright I guess

#

Assuming the increase is linear, a 80k level(the one that took a minute, including instantiation of gameobjects, which took longer than the map gen) would take like 1.6 seconds

#

Not great but it's also an unrealistically large map soooo

#

Idk

cobalt peak
#

Hmmm I wrote the exact same algorithm in java outside Unity

#

Displayed it using ascii

#

It made the 100x50(what we profiled on) in 5ms

#

I did not count display in tho

#

Still odd how much faster it is(I did change a few things tho)

#

I turned the edges into an int array
And used a slightly better shuffle method for them

cobalt peak
loud jackal
#

i'm getting around 1.9 ms for 100 x 100 in C

#

and around 380 ms for 1000 x 1000

#

i did end up using a kind of linked list to determine parents

cobalt peak
#

Well C is... C

#

I bet its more performant than Java

loud jackal
#

the linked list takes up half the time i need to find a better data structure

#

maybe your union structure is onto something lol

cobalt peak
#

And with Unity there's prob a bunch of Unity fuckery brining it up

cobalt peak
loud jackal
#

i am still confident you can reach near 1 ms

cobalt peak
#

Both in terms of memory and datatypes

#

Tho my 5ms should be taken with a grain of salt ig

#

I used System.currentTimeMillis()

#

I just subtracted

loud jackal
#

you can run it multiple times to be sure

cobalt peak
#

No profiler on that PC I used

loud jackal
#

what data structures do you use

cobalt peak
#

Byte array for directions,
Int array for parents(union)
Int array for edges

#

Edges aren't saved on class obv they're in the generate method

#

Used an array since there's always the same amount of edges for a given grid

#

And its easy to calculate too

loud jackal
#

hmmm that's basically what i did

#

i have an edges array, a int array for parents (implicit linked list), and a node 2d array which stores parents and edges

cobalt peak
cobalt peak
#

Oh I got only 1d arrays

loud jackal
#

a bit

cobalt peak
#

The negative bit

#

For me at least

loud jackal
#

well all mine are 1d arrays but i mean 2d how i reinterpret it

cobalt peak
loud jackal
#

i just did the LSB

cobalt peak
#

Lsb?

loud jackal
#

so edge & 1 is the direction and edge >> 1 is the index

#

least significant bit

cobalt peak
#

Ohhhj

#

I just did edge and -edge

#

It changes the leftmost bit iirc

loud jackal
#

its more than that but it works

cobalt peak
#

Oh welp

#

I guess my slowness is the if statement of

#

If (edge > 0)

#

Idk if you needed that

loud jackal
#

i think the slowdown is elsewhere

#

like for my code, 40% is traversing the linked list because i'm not flattening the graph every time i merge

cobalt peak
#

Maybe my initial -1 for loop?

loud jackal
#

so you need multiple jumps to find the true root

cobalt peak
#

But it can have some nested ones

#

Ranking takes more memory but can ensure a perfectly flat union

#

(Another int[])

#

But my impression was its insignificant until you do the big numbers

#

Tho ig 1.9ms and 5ms is considered "insignificant"

#

For a 1 time operation

#

Now we kinda optimize for sports and to learn things I guess

loud jackal
#

okay now i made it so that the graph flattens every iteration and it runs in 0.6 ms for 100 x 100 kekw

cobalt peak
#

DAMN

#

Now I wonder why what I did in java was slow

#

It seemed totally fine

loud jackal
#

that union data structure how does it work

cobalt peak
#

An int array

#

Index -> value
Node index -> parent index

#

You recursively find the root in get root

#

However whenever you apply a parent

#

You apply the roots not the nodes

#

Flattening the graoh

#

So when you Union x and y

#

You actually do

#

arr[Root(y)] = root(x)

#

By comparing the roots you know if 2 nodes are connected

loud jackal
#

wait no the change broke it lol

cobalt peak
#

The What?

#

Ohhhh

#

The flattening

#

Rip

loud jackal
#

wait what you describe is exactly what i do

#

wth

cobalt peak
#

Do you have a way to check if the maze is properly?

#

Proper

#

I used ascii in java

cobalt peak
loud jackal
#

i look at it

cobalt peak
#

Congrats you do disjoint union sets

hollow nightBOT
loud jackal
#

like this is wrong

cobalt peak
loud jackal
#

NOOOO

#

this is not coDE

#####################
#       #       #   #
# # # # # # # # # # #
# #                 #
# # # # # # # # # # #
#                   #
# # # # # # # # # # #
# #       #         #
# # # # # # # # # # #
#                   #
### # # # # # # # # #
#                   #
# # # # # # # # # # #
# #             #   #
# # # # # # # # # # #
#                   #
# ### # # # # # # # #
#                   #
# ### # # # # # # # #
#                   #
#####################

not code!!!

hollow nightBOT
cobalt peak
loud jackal
#

above is bugged maze

cobalt peak
cobalt peak
loud jackal
#

a

#####################
#   #   # #   # # # #
# # ### # ### # # # #
# #               # #
############# ##### #
#         # # #     #
##### ### # # ##### #
# #   # # # #   # # #
# # # # # # ### # # #
#   #   #   # # #   #
### # ####### # # ###
#   # #   # #       #
##### # ### # # # # #
# # #   #   # # # # #
# # ### # # ##### ###
#         # #   #   #
# ### ####### ##### #
#   #   #           #
# ##### ### ##### ###
#   #           #   #
#####################
hollow nightBOT
loud jackal
#

correct maze

cobalt peak
#

I used the whole

Alt + 185, 187, 200-2006 etc

loud jackal
#

i couldn't figure out how to do that

#

too many cases to consider

cobalt peak
#

Ohh I seeee

cobalt peak
#

I used a byte char map

#

1100 is a vertical sign

#

0011 is a horizontal

#

1011 is a t junction facing up

#

And since I don't count printing in the counting, as its just a measure to see if it's correct, idm it

cobalt peak
loud jackal
#

each cell is 2x2, which means i need a 1x topmost and 1x leftmost wall to make it all nice

cobalt peak
loud jackal
# 
right
***
*  
*##

down
***
* #
* #

right + down
***
*  
* #

nothing
***
* #
*##

not code

hollow nightBOT
cobalt peak
loud jackal
#

yeahh see

#

was too lazy for that

cobalt peak
#

Well 16 if you count nothing, but I don't make nothing cells

cobalt peak
#

And placed them in a dict

#

So very little work in logic

#

"Alt symbols" on Google is good shit fr

#

Does make pretty mazes

#

Oh wait that's the old one

#

The deadend characters here suck

#

That's a new one

cobalt peak
#

LMAO I PROFILED

#

remember how I said I got lazy with my shuffling??

#

it's 60ms out of 100ms

#

40ms is still a ton

#

I'll find the rest

#

but goddamn

#

fuck Linq

#

dropped to 26ms

#

still a lot (Unity) but clearly I know what caused it lolll

#

yeah now I know what's casuing this

#

I have extra logic for the rooms

#

I have AABBs checking intersections and stuff

#

to make sure to place rooms properly in the maze(even tho no rooms are placed rn)

#

takes up 50% of the runtime

#

5000 AABB.Contains calls lol

#

alright I ignored the AABB for now, that makes it 14ms, 5.61ms taken by the IsUnioned method, 3.51ms taken by the AddConnection, and 3.13ms taken by my Shuffle

#

that's the bulk of it

cobalt peak
#

Also Shuffling takes 3ms and 2.5ms of them are System.Random.Next()

#

ffs that's out of my hands

#

how did you make random numbers?

loud jackal
#

AddConnection? @cobalt peak

#

for mine it's about half half shuffle and the union handling

cobalt peak
# loud jackal AddConnection? <@390561209889587201>

daksjdalks dnot code not code

public bool AddConnection(int index1, Direction direction)
        {
            // if (!direction.IsCardinal())
            //    return false;

            int index2 = index1 + GetIndexOffset(direction);

            if (!Union(index1, index2))
                return false;

            nodes[index1] |= direction;
            nodes[index2] |= direction.Opposite();

            return true;
        }
hollow nightBOT
cobalt peak
#

muhahaha

#

IsCardinal took 0.5ms--- over all calls
barely nothing but I figured I can make it a protected method and shut it

cobalt peak
#

well what takes time for me is less the shuffling and more the random lol

#

maybe C# is just a slow fuck

loud jackal
#

how do you shuffle

cobalt peak
#

Fisher Yates

#

not code not code

public static void Shuffle<T>(this T[] array, Random random)
        {
            for (int i = array.Length - 1; i > 0; i--)
            {
                int dest = random.Next(i + 1);

                T intermediate = array[i];
                array[i] = array[dest];
                array[dest] = intermediate;
            }
        }
hollow nightBOT
cobalt peak
#

also the overhead reducded from that 1.6mb to 83kb

#

it was 60ish kb

#

but I now added the rank array

#

ranks recuded it from 13 to 10

loud jackal
#

Maybe the genetics killed it

cobalt peak
#

generics?

#

You think they slow it down?

loud jackal
#

T

#

who knows

cobalt peak
#

tho looking at profiling

#

I think I've made every reasonable optimization, idrk what else it can be

#

I suppose it's just C# being much slower than C

#

bigger case (400x200 instead of 100x50)

image.png
#

the time is deffo not linear....

loud jackal
#

it's the same time

#

what i don't get is you seem to call the random method twice?

for 100 x 50 you need ~5,000 calls only right?

#

and 400 x 200 you'd need ~160,000 calls

#

oh nvm

#

each node has two edges

#

it is linear tho. each single call takes around 0.3 us

loud jackal
cobalt peak
#

idk what C# fumbled

#

but it's slow asf lol

#

ANywayss I'm not gonna be anywhere near those times

#

this is after I've stripped the room generation, room subtraction and placement, looping etc

#

which all took a good amount of time

#

I did reduce it by a LOT

#

but yeah

cobalt peak
#

On java I couldn't push 400x200 lower than 10ms(sometimes 9.5ms but yk)

#

Much better than C#s capabilities (10ms on 100x50) but nonetheless...

cobalt peak
#

I now added rooms...

#

No rooms: 10ms~
15 rooms: 13ms~
35 rooms: 18ms~

#

On a 400x200

#

(Java)

#

What makes room slower is the intersection check to see I don't make rooms that intersect with each other

#

I tried without it and got overlapping rooms but the performance actually dropped to 8ms

#

(Less edges to calculate since rooms block them ig)

#

The way I sped up room placement is by setting node[index] = 16 where a room is, and then discarding invalid values (>=16), saving the fuckton of contains(width * height *roomCount calls) that clogged the generation earlier

#

Alas I'm still running the same number of loops but instead of a AABB contains I do = 16, which is much faster

loud jackal
#

how could java and c# differ so much

cobalt peak
#

I did practically the same thing in both of them

loud jackal
#

Show code for both

cobalt peak
#

Random was a big contribution to speed

loud jackal
#

Java is like 16x faster

cobalt peak
#

I can't profile the java but still

loud jackal
#

how are you timing? you should generate the maze multiple times

cobalt peak
#

And I added more optimizations

cobalt peak
#

And took average

#

Sadly the java PC is offline

#

So only fucking pictures can share the code lol

#

That's not the whole thing but I put the relevant parts as close together as I could to fit in 1 pic

#

Ignore roomSizes, imagine it's 0(no rooms)

20250521_162403.jpg 20250521_162417.jpg
#

C# ill send later when I'm home but it's extremely similar

#

Util.shuffle is a Fisher Yates

#

Not even generic(cause java won't allow generics for value types lol)

loud jackal
#

damn your edge generation is better than mine

#

you're using i or j == 0 to exclude those edges during initial generation

#

i skip those edges during the connection phase

cobalt peak
#

Yeah I just realized I can offset them forward because I always look left and up

cobalt peak
#

Anything you can notice here that looks odd?

loud jackal
#

recursive get root

#

that's the only thing I can think of right now

#

although the depth should be shallow

cobalt peak
#

I can try to make it not recursive shouldn't be this hard

#

At home I checked how deep that goes

#

For 400x200 it goes 7 deep

#

Not too much but also not little of course the deeper it goes the less calls

#

Smth like

#

1 for 7
55 for 6
300ish for 5(?)

#

I'll profile again

#

But yeah

#

I mean look at this point I optimize for the sports lol

#

But it's a cool thing to do and just general skill to pick up on

loud jackal
#

at this rate the game will run at 300 fps in 300 years

cobalt peak
#

LMAO

#

Nah its good

#

I mean technically this all runs once at the start of the level

#

Even if I had an abysmal 5 seconds you'd shove a loading screen lol

#

But yeah now it's fun to do that just to see how far I can push jt

#

And I'd prob be more careful with abusing dicts lolll

#

Tho if we gonna be practical

#

What we gotta push is the instantiation

#

The easiest solution is making the camera see less

#

And then pool objects to only display parts of the maze

#

Mc chunks style

loud jackal
#

im surprised your frame rate is good

#

wait maybe your computer is just worse than mine?? and that's why my C solution is so fast?

cobalt peak
#

Ig cause its a static scene with a static camera

cobalt peak
loud jackal
#

i7-8550U

cobalt peak
#

So likely the frame rate was bad and the scene is just perfectly statuc

cobalt peak
#

Not a hardware guy

loud jackal
#

the first number means 8th gen otherwise idk either

cobalt peak
#

Ohhh

#

Yeah idk that stuff about my pc

#

Lolll

#

Ik it's at least 6 years old

loud jackal
#

just go on task manager

cobalt peak
#

Sooooo

loud jackal
#

hmmmm

cobalt peak
#

I'm not home yet, omw

#

Also

loud jackal
#

100 x 50 is how many game objects?

cobalt peak
cobalt peak
loud jackal
#

is it just

while (room not overlapping with other rooms)
place room

cobalt peak
# cobalt peak Got an idea for that?

I made a basic inclusive 2d aabb, I do a for loop roomCount times, roll random dimensions in a min max range and find a random suitable x and y pos for them to make the aabb, I then go over all existing rooms aabbs and if any of them intersects I try to regenerate that room(up to 10 times), the reason I check intersection is to prevent 2 rooms from overlapping

cobalt peak
loud jackal
#

and you check overlap via iteration over all cells the potential room contains?

cobalt peak
#

Aabbs have a simple intersect method

#

It's basically

loud jackal
#

i don't understand why its so slow then

cobalt peak
#

x1 >= other.x2 && x2 <= other.x1 &&... same for y

cobalt peak
#

RoomCount * 10(at most for 10 max attempts, can be anywhere between 10 and 1) * i(index in the array, which is the number of already existing aabbs to compare eith)

loud jackal
#

the number of retries might be high

cobalt peak
#

I is the index of roomcount btw

cobalt peak
#

Well I say "i" but it's the same up until roomCount

#

So if 35 rooms

#

1 + 2 + 3 + 4 etc

#

Cause every time you add a room

#

You have 1 more to loop at for intersection check

#

Does that make sense?

#

I'm not there but it went smth like

hollow nightBOT
cobalt peak
#

Just psudo--

#

Fuckkkk

#

Welp

loud jackal
#

yeah no i get it

cobalt peak
#

And of course a big bulk is

#

Oh wait

#

That's not the slowdown

#

I tried avoiding calling Contains widthXheightXroomCount times

#

But I ended up doing it anyways lollll

cobalt peak
#

If I remember series lol

#

Ah yes my algo runs (at worse)

5RoomCount(RoomCount + 1) times

#

Lovely.

#

Exponential growth is so dun

#

Fun

#

(Wait that's not exponential just squared shhh)

loud jackal
#

its slightly worse than O(n^2)

cobalt peak
#

But I mean it's in the squared category