godot code review

[konsumer]

Hi again, sorry to bother you so much. I am working on implementing all the algorithms in luamaze in godot here. If you are familiar enough with godot, I'd love it if you could do a code-review. I had to translate a few things to a different style to work with godot, and I wanted to store the maze as a big array of numbers (using bitwise flags) to track open doors & visited, as it's more efficient and lighter to pass around. That said, although I think they still do the same thing, I'm not 100% sure.

You can test it by downloading the repo, and running it as a project in godot. Eventually, I will have other render-methods (like rectangle and tile-based) but for now, I've got braille & # text-based methods setup, and the demo-scene uses braille and has a nice UI.

These are the algorithms I have completed:

• [X] - recursive_backtracker
• [X] - prim
• [X] - aldous_broder
• [ ] - binary_tree
• [ ] - eller
• [ ] - growing_tree
• [ ] - hunt_and_kill
• [ ] - kruskal
• [ ] - recursive_division
• [ ] - sidewinder
• [ ] - wilson

If you are willing to do a code-review, I can keep this list updated, as I finish them.

[shironecko]

Hey! No worries, I'm not bothered in the slightest 😄

About Godot and GDScript, I have virtually 0 knowledge of those, but I can try to provide some general suggestions on the code structure. On bitwise stuff, I've looked around and it seems that GDScript has support of those: https://www.reddit.com/r/godot/comments/hb382k/bitwise_operations_bit_flags/ I feel that using | to set a flag would be generally more readable than doing mask + flag and also a bit more "correct", since addition is only accidentally equivalent to bitwise OR in some circumstances.

I also have an idea of sorts. LuaMaze can help in testing the algorithms that you're reimplementing. Well, perhaps it can. I'll need to research what algorithm Love and Godot are using for RNG and, if they match or if there's an alternative matching implementation, it would be possible to set up LuaMaze to output a text version of a maze with a fixed RNG seed. Then you could generate a maze with the same seed and compare it to the one that came from LuaMaze.

[konsumer]

No worries, I'm not bothered in the slightest ::smile::

Good! Just let me know if it's too much. When I get on a code-topic, I can often hammer it until it's "done", and then leave it alone forever after. hehe

I feel that using | to set a flag would be generally more readable than doing mask + flag and also a bit more "correct", since addition is only accidentally equivalent to bitwise OR in some circumstances.

Yes! I came to same conclusion, and looked back at the source ruby stuff yours was based on, and found plain bitwise was much easier to just port from the original code (it's mostly identical) and the "helpers" I made to more closely match the lua code a bit more are not actually that helpful. I started re-implementing them in the other style (and actually got more algos complete), but it still needs a little work.

I also have an idea of sorts. LuaMaze can help in testing the algorithms that you're reimplementing. Well, perhaps it can.

Damn! I love that. Maybe, if they don't seed the same way, we could abstract the random functions, and then check in them for an env-var or something to return from a known-list, in order.

Some possibly good abstractions we both use:

rnd_int (limit, start=0): int
rnd_aitem (array): any

where rnd_aitem is just array[rnd_int(#array)]

Godot does allow a known-seed, but I dunno if it's at all similar or reproducible across languages.

I'll get the new code I wrote for better bitwise mazes in there, and ask for another review. Thanks!

[konsumer]

It should be noted, even lua gives different numbers for same seed:

math.randomseed(100)
print(math.random())
print(math.random())

--[[
  Lua 5.3.3 (linux 64bit)
  0.28494340414181
  0.24060135660693

  LuaJIT 2.1.0-beta3 (linux 64bit)
  0.042055841965104
  0.51786830488191
]]

It's the same every time, but different between lua & luajit. Love2d gave same numbers as luajit, though.

[konsumer]

I think this is equiv in godot, without doing any research:

extends Node2D

func _ready():
    var rng = RandomNumberGenerator.new()
    rng.seed = 100
    print(rng.randf())
    print(rng.randf())

# 0.549445
# 0.950485

It also outputs the same every time.

[shironecko]

Yeah, I've spent some time researching this and Lua spec doesn't mandate an RNG algorithm, so every implementation is free to use whatever they like. I also had an idea of taking a known list of pseudo-random number for using across languages and implementations and I think that's our best option. And yeah, creating some abstraction over RNG generator that either uses Lua RNG/Godot RNG or takes values from a file or something should be pretty straightforward. I'll take a look at implementing this from LuaMaze side this weekend.

[konsumer]

might be a cool abstraction to just have a simple file-format (1 random number per line, maybe 1000 of them) that they can both share for unit-tests, and we can keep it separate so it doesn't bloat the imported code. Godot doesn't have 1st-class functions, so it's a bit harder to monkey-patch the "get a random number function" but I could probly just setup a test-project that checks a variable or something.

[konsumer]

I started on some ideas here. But it still doesn't create the same maze every time, even though the monkey-patched math.random seems to work, so I'm not sure how to do it. Basically, I patch math.random to use a list of 1000 numbers, then do all the requires, and verify that it is calling my function instead of the real one. I increment a line-pointer on every random number request, and can reset the pointer. I must be missing something, as aldous_broder runs forever, and eller is a little different every run. It definitely is calling my function.

Here is the code I used to verify the new random:

for i=1,2000 do
  print(math.random())
end

for i=1,2000 do
  print(math.random(500))
end

for i=1,2000 do
  print(math.random(500, 1000))
end

then

lua tester.lua > /tmp/a.txt
lua tester.lua > /tmp/b.txt

diff /tmp/a.txt /tmp/b.txt

and it prints the same numbers every time.

Even if I do math.randomseed(100) instead of monkey-patching, I get a different maze every time, even though it otherwise outputs all the same numbers every time. It's all a bit confusing.

[konsumer]

Oh, hmm, maze (but not numbers) seems to be different every time if I seed in lua vs same in luajit. Monkey-patching actually works fine in luajit weird. So I guess test is only for luajit.

[konsumer]

Ok, I have all but "aldous_broder" and "wilson" testing. For some reason those 2 run forever.

Bizarre cross-engine behavior, maybe due to how it allows me to patch random:

[shironecko]

I think here it might be better to use a custom RNG object, something "implementing a trait" (sorry, my Lua is really rusty, so code in Rust, should be easy to read):

trait Rng {
  fn new(seed: Option<u64>) -> impl Rng;

  // resets the RNG generator
  // in case of a real one, reseeds it with the seed used in construction
  // when taking values from a file just resets internal number index to 0
  fn reset(&mut self);

  fn next(&mut self) -> u64;
}

Then you would have two implementations of this trait: one that uses math.random and another that gets pre-set numbers form a file (don't forget to loop around to 0 when you run out of numbers). Then generator function would take an RNG generator as an additional parameter. This has the added advantage of the abstraction being super-obvious. Monkey patching is hidden so it can be pretty difficult for someone new to the codebase to figure out what's actually going on here.

Also in this way you untie yourself from the quirks of Lua implementation completely. Lua runtime probably wouldn't reset math.random at random intervals (pun not intended) but it absolutely can. Relying on hidden implementation details makes me wake up in sweat at night 😅

[konsumer]

I think I got a pretty decent test setup otherwise, and I'm not exactly sure what you mean, but if you think it's better I'm all for it! Do you want to do that part (on the luamaze side) and we can integrate it?

Relying on hidden implementation details makes me wake up in sweat at night :sweat_smile:

I hear that. I think a case could be made for that style, too. It's not really hidden, as it's at the top of the unit-test. It seems pretty common to patch/mock things that a programmer can't rely on being the same every time (like time/date functions, network functions, or in this case pseudo-random stuff) for any language, in unit-tests. As long as the patching only happens in the unit-test (not in the library) it's easy enough to track down any issues, and it keeps the code completely independent of the pseudo-random stuff, so you can separate "bad unit test" from "bad implementation" in a simpler way. I'm totally fine with more abstraction though, if it puts your mind at ease. The differences between lua and luajit already make me sort of unhappy about how I did it, anyway (it should be the same if it works how I think it does) but that may also just be my lack of familiarity with lua.

[konsumer]

More on godot: I pushed my current godot code to the repo. It uses a more bitwise-first approach, and I implemented more algorithms. I also added import/export (still needs a little work on some algos) to make it possible to just generate a maze elsewhere (like in luamaze, with a JSON lib) and import it, or just save it directly from the tool and come back to it.

After I get done with the rest of the algos, I'll move on to more features for it. I could see it being a general maze-algo generation/exploration tool that could be useful for verifying or just viewing mazes generated in any language.

Godot has a function for saving a node as a scene, too, which I will implement eventually for tile/rectangle mazes, so you can generate a maze, but save a nice hard-coded scene object that stays the same. My original need fits more with this, I think, as I wanted to generate mazes, but save them and add goals/traps, by hand, in an actual game. In godot, it's much nicer to work with pre-generated assets than generating on the fly or using a data-file to generate it as needed, as you can visually add stuff wherever you like by drag-and-dropping. Also, for things like a min-map, in godot, you need a separate copy under a viewport-node anyway, so it will allow me to generate a couple different styles from the same generated maze (like a rectangle version for map, and a more complex tile version for the gameplay.)

I'm teaching some classes on programming this weekend, and want to work on my actual game, so I may not have much time to actually work on it, but I'd like to get more maze-algos done in godot, as it's fun and helps me learn godot in a low-stakes way. I'll update here as I get more done.

[shironecko]

About RNG, yeah the difference in implementation is what makes me uncomfortable. Though, if the patching works at least in one implementation we shouldn't throw that work away :) So I'm all for adding this to the lib. Later down the line we can always change the RNG abstraction, but at this point something that works in one Lua implementation is a lot better that what we've got, which is nothing :)

No worries, I too have a project that I need to devote most of my time now (gotta create something impressive to land my next contract) and we're in no way in a rush :)

I'll try to provide some suggestion, though some could be based just on my preference:

1. I saw some code like maze[x][y] & E == E in maze.gd. Is absolutely correct from functional perspective, but repeating mask two times makes it a bit error prone and may be somewhat confusing for people not used to working with bit mask. I find that usually you only need one custom function to work with masks and it goes something like this:

   function hasbits(n, mask)
   return n & mask == mask;
   end

   Just makes testing for bits a bit more ergonomic :)

2. In get_braile function there's lots of magic numbers, like 0x40. Would it make sense to map them to some constants?

[konsumer]

I find that usually you only need one custom function to work with masks and it goes something like this

Totally agree. that seems like a fine trade. It's closer to the original godot code I wrote, but I found that porting the ruby to godot was easier if I used the same operators & similar constants. That said, the original code was much less readable than your lua code, at least for me, so finding a good middle-ground is probly a good idea.

In get_braile function there's lots of magic numbers, like 0x40. Would it make sense to map them to some constants?

Agreed. Honestly, it's mostly that I'm not sure what to call them. They represent bitflags for the dots, so I just tried to put that in comments:

https://github.com/shironecko/LuaMaze/blob/master/source/braille.lua#L29-L33

So 0x40 is "the dot on the bottom-most left of a single character". So for a south wall, since it's 2 characters wide, it's [0x40, 0x80], [0x40, 0x80] or a west wall would be [0x01, 0x02, 0x04, 0x40].

If you have an idea how to name them, that would be great. I found it hard to pre-combine them (like adding the 4 dots for W with the 2 dots for S) and also permute combinations (N+E for example) so it seemed easier to work with just the flags for the dots, and OR/AND them 1-by-1, so I found it hard to call them by any name (like "W, dot 2" seems kinda unclear.) I guess I just kinda treat the braille function as a sort of black-box, like "if you want to work on this part, go read about how the braille dot-addressing works", which I agree is not ergonomic, but I couldn't think of a great alternative.

I feel like the godot rect/tile implementations will be much simpler to read, just because it uses much more common stuff, I just hadn't gotten to actually porting it. Braille is probly not even going to be used in my game, I had just already written it for luamaze, so it was a faster way to get a nice-looking (well, nicer than #, but still kinda ugly) maze on the screen. In my actual game, I am using only recursive-backtracker with tiles (and use the same logical maze to generate 2 different maps with different tile sets for min-map vs game) which is part of why I started on this whole journey, because I want a nicer base/lib to work with, and I'd like to have several algos and output styles to work with, from the same maze description. I was thinking it might be a common godot thing to "just put a maze made with this algo right here, and use rectangles". In my game it's meant to just be a filler for the rest of the game, like "create a little challenging area, and use the other game mechanics to get through this part." It's much faster/nicer to generate the maze, then modify it by hand to add little passages and risk/rewards.

[konsumer]

If you are curious here is the actual game I am working on. This is my initial simpler setup, and here is a generated godot scene that uses a min-map made with the same logical maze. The web-demo is terribly broken right now, so I highly recommend running it in godot locally, if you want to check it out. Originally, I basically just extended TileMap to have maze-generation super-powers. I like the idea of keeping it all more separate from the output-layer, though, and later building a plugin around that.

The numbers are just tilemaps I pre-assembled, to look kind of "hackersih" hehe.

[konsumer]

About RNG, yeah the difference in implementation is what makes me uncomfortable. Though, if the patching works at least in one implementation we shouldn't throw that work away :) So I'm all for adding this to the lib.

I totally feel you on this point. As I said, I hate that patching math.random doesn't work on all the luas I tested, so I won't be sad if there is a better way to do it. Another problem with this kind of patching is how hard it is to figure out what part is breaking. Like "did I do the random function wrong, am I calling it weird, does require order matter more than it should here?" that kind of thing. If you can think of a better way, I'm all for it, that was just my first-stab, probly overly guided by js/python unit-testing where I do this sort of thing a lot.

I think either way, the test-runner (with red FAIL and green OK) is pretty nice & simple, so maybe we could just fix the other stuff. I also like that's it's test-mazes are human-readable #-based text files. I have a feeling the lua issues could be some subtle thing where if you require a built-in it doesn't allow patching in lua, but it's fine in luajit (js used to be like this with Date, for example, in many cases, in node.) We might be able to get around the whole thing by just patching the maze instance with it's own general get random number function, as we first talked about.