Exposing and implementing more core data structures and classes

[Xrayez]

Related proposal: godotengine/godot-proposals#279.

Problem

GDScript can be quite inefficient when dealing with non-trivial datatypes and structures. It takes at least an object to define some which could take a lot of memory consumption/leak problems etc. Using an ordinary array or a dictionary is simply not enough!

Suggestion

There are a number of core data structures and classes which I'd like to see in Godot being built-in, and some which find some existing/future use cases.

Structures

List

Update: This is implemented in Goost, see LinkedList documentation.

The advantage of this is having ability to pass around elements and see previous/next elements easily, which is somewhat difficult to do with an ordinary array. An Element would have to be exposed for this to work.

var list = List()
var element = list.push_back(value)
# ...
element = element.next
element = element.prev

See also godotengine/godot#7194.

Set

When you need to ensure you only insert unique elements. It can be simulated with an array but you have to repeat code a lot, which basically boils down to this:

# Using array
var array = []
if not array.has(element):
    array.append(element)
var set = array # native

# Using dictionary
var dict = {}
dict[value] = null # or `true`
var set = dict.keys() # allocating array

Classes

Graph

Currently present as a GraphEdit + GraphNode UI classes. It would be nice to have this class decoupled. See related proposal at godotengine/godot#15647. In fact, a doubly linked list could be represented as a PathGraph (as I think about it, it's a simple tree, which can be constructed with nodes, but still the scene tree is too general purpose for that).

StringBuiler

I think this would be useful for plugins which need to write formatted output more easily, generate code etc (the way it's done in VisualShader for instance).

RingBuffer

Stumbled upon this on accident, and I think it would be useful for input stuff, see godotengine/godot-proposals#100.

---

There are other structure and classes present in core, but I haven't found those to be performance critical, like Pair.

If you find some more use cases for existing core types which are not currently exposed to scripting, please describe it and I'll add it to the list here.

[willnationsdev]

Just as an FYI...

you can use a Dictionary<Variant, null> as a Set. It uses more memory than sit needs, but it otherwise accomplishes the same usability/speed task that a Set does.

I have a WIP List implementation in my fork of godot-next's list branch.

Creating a generic implementation of a graph is actually quite hard since their internal design is tied so deeply to the use case they target. You would need to define and expose a large variety of graph classes for them to be truly useful. I've already been here/done that with a graph branch in my Godot fork.

[Xrayez]

Yeah forgot to mention the usage of dictionary indeed. The performance drop could stem from allocating an array by having to use dict.keys() method down the road though, not sure. But definitely not as intuitive as native Set class.

One could also define a custom comparator for Set to be more useful than a Dictionary, sort of like sort_custom in Array.

[WilliamTambellini]

The core ring buffer header:
https://github.com/godotengine/godot/blob/master/core/ring_buffer.h
Is that idea/proposal been formally accepted by the godot owners : if anyone prepare a PullRequest in the master branch exposing ringbuffer, will it be reviewed/accepted/merged or is there any reason not to expose ringbuffer (for instance) ?
kind

[Xrayez]

@WilliamTambellini I don't think Godot core devs are even aware of this. One has to create a proposal at GIP first, but I think that the feature is a bit specific to be exposed to scripting (the existence of this idea here is to bring up possible use cases to justify making a formal proposal).

Talking about use cases, what do you need a ring buffer for personally?

[Xrayez]

So that you know, I've been working on a project which aims to complement Godot on the core level (and more than that), the project is Goost which is implemented as a C++ module, exposing core functionality to scripting as listed here could be likely worth it as almost every part of the engine is accessible through modules.

There was some ideas/discussion that Graph and related classes could be implemented in a general-purpose way (more or less), but I guess needs some design work up-front.

Of course we're basically limited to what the public API provides... So all those classes would have to be implemented inheriting Object for them to be exposed to scripting, I don't see other way.

[ghost]

i wish we could just get rid of the gd script madness and turn c++ into a "just in time" compiled language instead so that we could move on with our lives and focus on making games instead of wasting our lives away with two terrible languages

at least if c++ was REALLY FAST when compiling, we would only have to deal with ONE terrible language xD

i really hate this mindset of, "it's too much hard work" or "we can't just throw it all away cuz X", but gd script is bad, c++ is bad, and i wish gd script was gone so that we could be focused on the c++ side of things, and then we could add support to just hot reload c++, and we would enjoy the benefits of a high performance language, with tons of hardware support, or we could just keep on torturing ourselves with... just another lame ass interpreted language system

idk i feel like putting more trust into actual computer scientists who put thousands of hours of effort into a language is more worthwhile than, dudes on the internet who made yet another pretend scripting language, i just want to cut the middle man and put some effort where it's worth and actually do something cool

i really want the engine to just get to a point where it's actually done, where things stop constantly breakng, but man i look at the billions of issues on the github tracker and there are like CONSTANTLY all kinds of random bugs involving gd script and it's so frustrating, it doesn't put me in the mood to learn how to use it at all, knowing how unstable it is, and i hate how the engine is more focused on adding flashy graphical features instead of focusing on the fact that the engine has a trillion bugs

i wish godot could focus on actually getting things to work, i think modern day software development is quite honestly retarded, everything is left broken and nothing is ever fixed, i wish they could just sit down and focus and actually finish one feature for once, but even vulkan is just sorta half assed, nothing is ever fully implemented, it's all just VERY half assed, it's all in the EVENTUALLY stage and IT'LL GET FIXED LATER (spoiler: it never gets fixed)

unity, unreal, godot, all these engines quite honestly frustrate me to no end, i just want to make a game without having to worry about the user, having to wrestle with engine problems, caused by my own incompetence, to me that's unnacceptable and i find the state of modern day engines to be disgraceful, and i'm likely younger than everybody else here, and i just sorta feel like i'm insane for being the only guy who points out, just how ridiculous the lack of focus is, and i feel like i'm going crazy, to me even one bug, is too many, but A THOUSAND BUGS? holy shit, i would be EMBARASSED to work on something this broken

i would understand if this was a videogame emulator
BUT NO, THIS IS A GAME ENGINE, THE FACT THAT ANY PROBLEMS EVEN EXIST, IS UNNACCEPTABLE TO ME

i mean go on the unity or unreal bug tracker, and look at some of the oldest bugs, the developers always say, OR THEY ARE EASY BUGS, WE'LL FIX THEM LATER

and yet 10 years later, they are still, just sitting there

boy don't you love modern day software development

i want this engine to be good, I WANT IT TO BE THE BEST OF THE BEST, but i don't feel like most people see that way, they just see a big meanie who uses BIG BAD WORDS, OH MY GOD HE SAID BAD THING, BAD PERSON, GO AWAY

it's depressing

my only real option is to MAKE MY OWN GAME ENGINE... and no way hose, i don't have that kinda time to waste, my only hope is to take Godot, take it apart, fix it and just pray that i can get something done with it, otherwise i don't have the patience to deal with unreal and unity, i have a very low bullshit threshold, and not being in control of the engine or of the game 100% just annoys me to no end, so i just want things to be done properly for once, i hate this half assed approach every community on github has

whatever man, i don't even know why i bother saying these things, i'm the big bad wolf to most people, even though i see a ton of potential in everything as a whole, but it all just goes to waste if you just focus on what's visible instead

to me "talent" is worthless when you can't be bothered to ever finish anything in the first place
i get that it's hard work but come on, the lead people are getting paid to do this, i have higher expectations from them...

this is not an engine that's worth 15.000$ per month, no way in hell

the fact that people act like this is fine is total insanity to me, it's not fine at all, but feel free to lump in the "ur wrong" camp like everyone else just because i dare to think differently, god i hate the internet

[Xrayez]

@RaTcHeT302 I totally understand your frustration and even agree with general points you've made, but I guess that's the reality of software development...

You can read an interesting article about this in Leptonica (image processing library) documentation from a seasoned author which is pretty much blunt regarding this:

What is “Well-Tested” C Code?:

I have seen estimates that commercial software has between 5 and 20 errors per 1000 lines of code. This may seem high, but many of these errors do not result in serious bugs. Taking the low end, one might guess that the code in the Leptonica library, which at present is about 100K lines, would have about 1000 errors. I hope it is much smaller, but obviously cannot prove it.

There are definitely areas which require well-tested code like medical software. Games are soft real-time systems, so the amount of work is not justified to make it work reliably in 100% cases.

I just want to tell you that you're not crazy, but trying to change the world is also futile, the best thing you can do is to change yourself your project rather than the tools you use. 😛

IT'LL GET FIXED LATER (spoiler: it never gets fixed)

Actually yes, but not by original authors, here's an example to keep this thread on topic: godotengine/godot#42013, I believe this was present way before Godot got open-sourced, even. 🙂

So, it's not a problem until it actually becomes a problem, and that's another issue with Godot development in my opinion (despite the regurgitated "Waiting for Godot" which could imply that the issues can be possibly foreseen before they appear). I'm not as experienced as other core developers in Godot, so perhaps I'm just venting in a similar way, but now I just tend to accept things as they are, else I'd just burn out.

But yeah in general we just tend to live in a world with the "quick fix" mentality, so it's not necessarily the problem of software development.

[Xrayez]

Linked list implemented in the Goost module: goostengine/goost#12. Implementing a similar data structure in GDScript is possible but according to issues listed in godotengine/godot-proposals#1522, it may be difficult to do via GDScript, while also ensuring that the implementation is efficient enough, because in some cases using an Array would be faster (with some resize capacity hacks and moving indices around). 😉